1

I've got a site (here) that lets users publish labs. I'm looking at adding a feature where users can customise the order that their labs appear in. To be clear, I mean that they can manually control the order, not that they pick sort by name/date/popularity/etc.

This feels like it shouldn't be too tricky but I'm finding it harder to implement that I expected. My initial attempt adds an order field to the Labs table. This is easy enough to sort on for display. But making changes to the order is a little tricky as a move needs to change order on at least two rows. Also, if a lab is deleted, that results in a gap, and the code needs to be more complicated to cope with this.

In a lot of ways it would be easer to just join the IDs together in the desired order, forming a string like "7,3,1,8,2" and save that in the database - but that feels like an anti-pattern.

1
  • 1
    Are the users only able to see their own labs, or can the labs be shared? If they are shared, then you cannot associate user-specific ordering with only the Labs table itself. BTW, if the lab list (or the part of it that is sorted) is not very large, you can just update all the order values at once - just throw away the the old values and replace them with the current index in the list. Commented Jun 24 at 22:52

2 Answers 2

3

Usually having an integer field and adding sort-by to your queries is sufficient. Gaps don't matter to sorting algorithms.

Start with the integer values spaced out by half the range, so your first item would have 0 for 32 bit integers, and the next items before or after would be +1073741824 and -1073741823. Any insertions between items also bisect the order.

If you bisect enough, eventually you end up trying to insert an item between two nodes with the same ordinal value, in which case you have to trigger a rebalancing (you can consider the values as indices into a binary tree).

Whether you use strings or numbers, and how many bits you use in the numbers, you will need to rebalance eventually; essentially you choose which to use whether to have the storage, transmission and comparison cost of a larger data type affecting every request (and a less trivial way of bisecting two values in the case of strings) against the more frequent rebalancing affecting insertions.

0
2

In one application we used a 20 character string which was alphabetically sorted. If a string was moved manually we took the strings for the two new neighbours and changed the order of the moved string so that it was between them. For example move an item between two items with order “P” and “Q” and it got order “PM”.

Since you add and remove gaps you can do that for a long time. You can create sequences of movements where you end up with two items with equal ordering strings, then you may have to change more strings.

Normally you change just the item you move, and deleting an item needs no action at all.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.