Drag and Drop Ordering

Drag and drop ordering is a deceptively hard problem. The obvious solutions work well at first, but will start to fall apart over time. Thankfully there are some truly excellent options out there.

The Obvious Solution

One of the more common implementations for drag and drop is simply updating the order of every item every time the user adjusts the ordering. Take the following:

id	order
1	1
2	2
3	3

Say the user moves the item on the bottom to the top:

id	order
3	3
1	1
2	2

You could then update the order for every single item:

id	order
3	1
1	2
2	3

This works great for three items, but less great for 1,000,000 items.

The Slightly Less Obvious Solution

The next most common implementation for drag and drop is utilizing floating point numbers. We'll start with similar data:

id	order
1	1.0
2	2.0
3	3.0

The difference here is that the order is now a float. Say the user once again moves the item on the bottom to the top:

id	order
3	3.0
1	1.0
2	2.0

We can fix the ordering by choosing the number halfway between the start of the ordering (0) and the previous first item (1.0): 0.5. The data then becomes:

id	order
3	0.5
1	1.0
2	2.0

At first this seems great because you are making a single update for the reorder which will be fast even for large amounts of data. The issue is that as more reorders occur you will be digging deeper and deeper into the precision of floats, and eventually you will run out. I.e. your orders will eventually look something like .00000005 and you only get so many digits.

Even though the finite precision of floats catches us here the core of this solution is very good. We just need to add one more wrinkle.

The Less Obvious But More Correct Solution

Even if floats don't have enough precision there is something in our toolbox that has infinite precision: strings. We can store our numbers as strings and do the ordering math directly on them. But first we'll go down a rabbit hole around different bases.

Other Bases

The most widely used numeral system in the world is the Hindu-Arabic numeral system which is usually called decimal. This numeral system has ten symbols: 0,1,2,3,4,5,6,7,8,9. The number of symbols in a numeral system is called the base.

In spite of numeral systems having a finite number of symbols they can represent any number. To pull this off the symbols are repeated, and each place is assigned a place value. Take this grid of the first 99 numbers:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
...
90 91 92 93 94 95 96 97 98 99

Using two places we can represent 100 different numbers.

As an example let's look at the number 21. In that number 2 is in the tens place and 1 is in the ones place. Another way to understand place value is the so called expanded form of a number: $21 = 20*(10^1) + 1*(10^0)$ Or more simply put: $21 = 20 + 1$.

However you can define a numeral system out of any finite set of distinct symbols. For instance the Babylonians has a base60 numeral system called Sexagesimal. Whatever set of symbols you use the numeral system ends up working the same. Take the number grid for the base3 system:

00 01 02
10 11 12
20 21 22

And indeed that looks a lot like the decimal number grid. It isn't hard to craft an algorithm to convert a decimal number to one in an arbitrary base:

$$\begin{align} &123 = (2*7+3)*7+4 \\ &123 = 2 * (7^2) + 3 * (7^1) + 4 * (7^0) \\ &123 = (234)_7 \\ \end{align}$$

Here we repeatedly applied long division to the decimal number. This was called the representation theorem in the book I pulled it from: Understanding Numbers in Elementary School Mathematics.

This begs the question: why are we even going over this? Numeral systems with more symbols can express larger numbers with fewer numbers. For example 1,000,000 in base10 is 4C92 in base62. By using a numeral system like base62 that has a ton of symbols for our order column we can keep the order string shorter as more and more ordering operations occur.

Putting it Together

We have enough for a rough plan now:

Use a string for the order column
Use a numeral system with lot of symbols like base62 for it
Move items by calculating the midpoint between the two items it is being placed between

Take the following data:

id	order
1	00Npd
2	00lf7
3	019UR

If the user moves the third item between the first and second it will then look like:

id	order
1	00Npd
3	00ZkN
2	00lf7

Still nice and compact. And as more and more operations occur these values will stay pretty compact, and they can grow infinitely because we have infinite precision.

References

I did not invent this. I first came across this idea in a stackoverflow post. In that post someone expanded this idea into a real library called mudderjs. It's a shame that this approach isn't more widely used since it does the best job of solving the drag and drop problem of any approach I've seen.

Go Library

I ported the mudderjs approach over to Go for Armaria here. It is MIT licensed so it's free to use for your Go projects.

Conclusion

Understanding numeral systems is a powerful thing, and once you get them you will find uses for that knowledge outside of drag and drop.