The Logic of Position Reordering
Order of The Cards — Photo by Sergi Viladesau [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
Imagine you have an array of letters, and you want to reposition some element to another position.
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
Instead of cascading other elements into a new position, what if the relocated element ‘squeezed’ itself so it fits into the new position?
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
Say we have a list that looks like below, and we want to move C to be the first element. Wait, “move ‘C’ between ‘what’ and ‘A’?” —
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
Now let’s update our data to be:
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
Now, in a programming language that uses an index to maintain the order of an array; it is unlikely that the drag and drop operation used our phrasing for the command, it is more likely that it will say something like “Move ‘C’ from index 2 to index 0’ — it would make sense if we code it as below right?
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
In the case of Cascading Reordering, we detect the direction of the movement to find which elements are going to be affected. We can use this direction information to calculate the target index of a Squeezing Reordering.
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
Due to this “virus” called decimals (and how infectious it is once you keep dividing and dividing), and the complexities of floating-point arithmetic; we can modify the distance between each element by an order of magnitude.
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
Both cascading and squeezing method works, it is just a matter of which trade-offs we want to make. When the database system that manages the position data is blazingly fast, cascading the position is not a big deal; or when the floating-point arithmetic implementation is eerily accurate, we can keep dividing it till infinity.
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.