The Logic of Position Reordering

Aditya Purwa
Jun 18, 2020 · 5 min read
Order of The Cards — Photo by Sergi Viladesau on Unsplash

Reordering things seems to be something trivial. We do it almost every day, we sort our tasks, we sort our priorities — we move around that card on our Kanban board.

I mean, what could go wrong right?

The Cascading Reordering

const list = ['A', 'B', 'C', 'D']

We want to move ‘C’ to be the first element.

['C', 'A', 'B', 'D']

Now, let’s say we need to keep track of each element position. So it would be like:

C: 0
A: 1
B: 2
D: 3

Compare the order above, with the original state of the data below:

A: 0
B: 1
C: 2
D: 3

Notice what just happened?

The position of all elements except ‘D’ changed, we just moved ‘C’ to the beginning of the array, a very simple operation; but affected the array greatly. We can model it as:

function affected(startPos, targetPos){
if(targetPos > startPos) { // Forward
return [startPos ... targetPos] // Anything in between needs to be shifted backward
}
if(targetPos < startPos) // Backward {
return [startPos ... targetPos] // Anything in between needs to be shifted forward
}
}

It means anything between the start position and target position or vice versa, need to be updated.

Now imagine we have 1M records, and we reposition the last item to be the first, it would cascade the updates resulting in 1M updates just for one reposition.

Now I don’t understand why on earth someone would want a drag and drop reordering feature on 1M records.

The Squeezing Reordering

Now we need to change the phrasing of the command. We no longer say, “move X into Y”. But we say, “move X between Y and Z”. So the final position of the element would be between Y and Z position.

X.pos = (Y.pos + Z.pos) / 2

Zero Zero

A: 0
B: 1
C: 2
D: 3

Let’s welcome our first edge cases (pun intended). In Squeezing Reordering, position zero is special and should not be assigned to any element. If we say “move ‘C’ between the ‘very beginning (zero)’ and ‘A’” and apply the formula above. It would result in:

X.pos = (0 + 0) / 2
-> 0

Now both ‘C’ and ‘A’ is on position 0, which means they occupy the same space. Congratulations, we just made our own particle collider!

Starts From One

A: 1
B: 2
C: 3
D: 4

Say the same command “move ‘C’ between the ‘very beginning (zero)’ and ‘A’” — then we would have:

C.pos = (0 + 1) / 2
-> 0.5

Then our data would look like:

C: 0.5
A: 1
B: 2
D: 4

Notice that ‘A’, ‘B’, and ‘D’ position didn’t change. But ‘C’ position is squeezed in between the beginning and ‘A’.

Not Indexed Here

Y = list[targetIndex - 1]
Z = list[targetIndex]
X.pos = (Y.pos + Z.pos) / 2

However, the element before index 0 is nothing.

?: ? [?]
A: 1 [0]
B: 2 [1]
C: 3 [2]
D: 4 [3]

So we need to check if our target points to non-existent element, we set it to 0. Also consider the other side of the edge, when the target points beyond the array bounds, we set it to the array length + 1.

Y = list[targetIndex - 1] // Points to nothing
Z = list[targetIndex] // Points to 'A'
yPos = Y ? Y.pos : 0 // Lower out of bounds
zPos = Z ? Z.pos : list.length + 1 // Upper out of bounds
X.pos = (yPos + zPos) / 2
-> yPos = 0, zPos = 1
-> X.pos = (0 + 1) / 2
-> 0.5

Now we get the same result as our paraphrased command:

C: 0.5
A: 1
B: 2
D: 3

Now let’s say we got another command ‘Move C from index 0 to index 1’, we should be able to reuse our algorithm above right?

Y = list[targetIndex - 1] // Points to 'C'
Z = list[targetIndex] // Points to 'A'
yPos = Y ? Y.pos : 0
zPos = Z ? Z.pos : list.length + 1
X.pos = (yPos + ZPos) / 2
-> yPos = 0.5, zPos = 1
-> X.pos = (0.5 + 1) / 2
-> 0.75

This is the result:

C: 0.75
A: 1
B: 2
D: 3

Wait, we were told to ‘Move ‘C’ from index 0 to index 1’ right? Why is it still at index 0?

Direction Matters

Say, we run the same command “Move ‘C’ from index 0 to index 1” using the previous data:

C: 0.5
A: 1
B: 2
D: 3

With a slightly modified algorithm that considers the direction of the reordering:

if (targetIndex < startIndex) { // 1 < 0 = false
Y = list[targetIndex - 1];
Z = list[targetIndex];
} else { // Because the direction is forward
Y = list[targetIndex]; // Points to 'A'
Z = list[targetIndex + 1]; // Points to 'B"
}
X.pos = (yPos + ZPos) / 2
-> yPos = 1, zPos = 2
-> X.pos = (1 + 2) / 2
-> 1.5

Now our data looks like:

A: 1
C: 1.5
B: 2
D: 3

Order Distancing

Instead of a small interval such as:

A: 1
B: 2
C: 3
D: 4

We can use:

A: 1000
B: 2000
C: 3000
D: 4000

Now when we run the command “Move ‘C’ from index 2 to 0” — we would get:

C: 500
A: 1000
B: 2000
D: 4000

Conclusion

Feel free to share if you have any feedback on this article, or maybe you have a different approach to position reordering?

Special thanks to Aid, Adi, and Ihti which helped me a lot with brainstorming position reordering.

clearview.team

We’re a remote-first, distributed software company with team members spread across the globe.

Aditya Purwa

Written by

Software Engineer at Clearview Studios (https://clearview.team) - Software engineer, writer, designer, and artist.

clearview.team

We help startups and scaling companies build products and grow their engineering teams.

Aditya Purwa

Written by

Software Engineer at Clearview Studios (https://clearview.team) - Software engineer, writer, designer, and artist.

clearview.team

We help startups and scaling companies build products and grow their engineering teams.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store