Recently I needed to implement a drag-and-drop reordering, with persistence.
At least with SwiftUI, reordering is easy if it’s all in memory: you have an array of items, the UI tells you which ones were dragged and where, and you call a method on the array that takes those same parameters to reorder it.
It gets more complicated if you want this to be persistent, so you’ll get the same order next time you run the app. You need a persistent representation of the order.
We’ll look at four approaches and the tradeoffs among them:
- Position as an Integer
- Position as Number with Gaps
- Position as Linked List
- Position as Hierarchical Number
A. Position as an Integer
This is the simplest approach: give each object a position corresponding to its position in the array:
Slot Position Name
0 0 A
1 1 B
2 2 C
3 3 D
4 4 E
5 5 F
6 6 G
Let’s say we move item F to be between C and D (sliding the others down).
When we move, we’ll have to renumber. Slots 0-2 have nothing moved before them, so their position stays the same. Slot 6 (and after, if any) doesn’t move, so its position is unchanged. Slots 3-5 are affected and must renumber.
Slot Position Name PriorPosition
0 0 A 0
1 1 B 1
2 2 C 2
3 3 F 5
4 4 D 3
5 5 E 4
6 6 G 6
Note that we’d like the shuffling to be in a single transaction.
The number of items moved is proportional to the distance dragged.
B. Position as Numbers with Gaps
A second approach is to number the positions, but allow gaps. Sort the positions to arrange the list.
Slot Position Name
0 1000 A
1 1500 B
2 2000 C
3 12000 D
4 25000 E
5 40000 F
6 90000 G
To move an item, change its position to the average of the items it’s going between. Again, moving item F to be between C and D:
Slot Position Name
0 1000 A
1 1500 B
2 2000 C
3 7000 F
4 12000 D
5 25000 E
6 90000 G
Note that only one persistent item had to change its position (though the array moves a bit).
We could use integers or doubles for the position. Either way, since computer numbers are usually finite, we’ll run out of bits at some point. If we do nothing, we’ll end up with two values with the same index, and we won’t know which order is right.
Thus, you sometimes have to do a larger-scale renumbering. In its simple form, we could renumber everything. Or we could invent some clever scheme that only renumbers crowded areas. Worst case, renumbering is proportional to the number of items.
How likely is renumbering? It depends on the number of moves to a particular area, and the limit is some log2 value. Let’s assume a 64-bit position. If we started with 256 items distributed equally (8 bits), that would leave room for ~56 moves between any two items before renumbering.
C. Position as Linked List
A third approach is to store the data as a linked list, and move items within that. I’ll assume a doubly-linked list since it requires limited traversal and a fixed number of changes. I’ll use the name as the id of each cell (though you’d probably use generated ids in a real app).
Slot (Pred,Next) Name
0 (-, B) A
1 (A, C) B
2 (B, D) C
3 (C, E) D
4 (D, F) E
5 (E, G) F
6 (F, -) G
Again, to put F to between C and D:
Slot (Pred,Next) Name
0 (-, B) A
1 (A, C) B
2 (B, F) C
4 (F, E) D
5 (D, G) E
3 (C, D) F
6 (E, -) G
I’ve treated the slots as reordered too. We wouldn’t persist the slots, just the pointers.
Here’s another example, showing details of how to update links in a doubly-linked list:
The reorganization involves at most 5 nodes:
- The two nodes being moved to must change one predecessor and one successor to point to the newly moved cell.
- The two neighbors of the newly moved cell must be changed to point to each other.
- The newly moved cell must change both arrows to point to its new neighbors.
(You have to be extra careful for short-range moves – fewer nodes will be touched.)
D. Position as Hierarchical Number
Our last approach is to treat the position as a number in an outline. I learned to number outlines with II.C.3.b style numbering (mixing roman numbers, letters in upper/lower case, and numbers). But it’s more convenient here to think of them as just numbers: 2.3.3.1.
When confronted with new items to place, we can either increment an existing number or append another one.
Slot Position Name
0 [0] A
1 [1] B
2 [2] C
3 [3] D
4 [4] E
5 [5] F
6 [6] G
To put F between C and D, observe that there’s no room between their positions, so F’s position will add a new number to the position of C:
Slot Position Name
0 [0] A
1 [1] B
2 [2] C
3 [2,1] F
4 [3] D
5 [4] E
6 [6] G
So we have to look at the two slots the new item will be between, and devise a number that fits between them.
To extend the example:
- Move A to between E and G. We can find room between [4] and [6], using [5] for A.
- Move G between F and D. Incrementing the last digit of F fits before D, so we can label G as [2,2].
- Move B between F and G. (F is [2,1], G is [2,2].) If we increment the last digit of F, we get [2,2], which is already in use by G. So we’ll extend it so B gets [2,1,1].
Positives:
- An unmoving item doesn’t have its position changed.
- Renumbering is never required.
Negatives:
- Calculating the new number is non-trivial.
- The size of the positions is unbounded.
The cost of inserting a new element is proportional to the keys of the existing items it’s going between.
Tradeoffs
There’s no clear winner among these. Let’s look at some of the tradeoffs:
| A. Integer | B. Gaps | C. Linked List | D. Hierarchical | |
| Cost to move | O(distance) | O(1) usually | O(1) | O(depth) |
| Renumbering? | Always | Rarely (but costs O(n)) | Never | Never |
| Cost to load | Low (assume sorted) | Low (assume sorted) | O(length) | O(depth)+O(sort) |
| Ease of implementing | Easy | Easy-Medium | Easy-Medium | Medium-Hard |
What I Did
For the program I was working on, I started with the Gaps approach (with a binary split to insert between existing items). This looked more complex than I liked, and we still had to program renumbering.
Since I’d have to do renumbering anyway, I moved to the simple Integer position approach. The sets of items to manage wasn’t that big, and I made sure to implement renumbering in such a way that it could tolerate persistence failures.
If that became a performance problem, I’d move to the linked-list approach
Conclusion
We’ve looked at several ways to implement reordering, and compared their cost and benefits. If you have used a different approach – please let me know!