How to reorder instances in Rails

Question

This is less of a how to in a technical sense, but a more of what approach to use in an algorithmic way, I guess..

I have a Photo model, which has an id, created_at and the image itself.

I want to allow the user to order their photos in whatever order they feel like. So I guess I can add an attribute which will note the order somehow, and then reorder it by that column. But how would I build that column in a way that is efficient?

My options as I see it are:

1. a simple integer to denote the order. so 1,2,3,4,5. If the user chooses to put photo#5 before photo#2, I need to reassign all photos with a new sequential numbering to match the new order. With many photos, and drag and drop, this could have a lot of writes to the DB, and could be slow and inefficient

2. Make it so that any photo that is first, will get a higher number, so when the user puts photo#5 before photo#2, #5 will get a higher number than #2 but smaller than #1, but this can also get messy pretty quick..

3. Allow only "bump to first place or bump to last place" and in the last place make it a larger number than the previous last, and in the first place make it a smaller number than the previous first place. seeing that users won't have millions of photos, using an integer could work.

4. linked-list - this could technically work, but only in very limited situation where I have/ want to use all the photos. If I need a subset of the photos and want it custom ordered this won't work. I prefer a way that I can use <=> in o(1) and know immediately how to sort and not to go through all of it (which would be o(n^2))

Is there a better way to do this?

Answer 1

There are two ways that I can think to do this. Two basic data structures are Arrays and LinkedLists. The main difference between the two is that an item in an Array is referenced by it's index location, where as an item in a LinkedList is referenced by what's in front of it and what's behind it.

Therefor you could have a location (or number as you mentioned) that is correlated to is position on the page or screen, and you can store this number in the model and change it whenever the user moves the image. To do this effectively you would not want to push every image back one or forward one, but instead only allow swapping. So two photos could swap places easily.

Another way to do this would be to have each photo have a pointer that points to the next photo, in essence creating a linked list. Then you would print out all the photos until you reach a null pointer. This would be very easy to move one photo around. To insert a new photo, you set the pointer index of the photo being inserted to the next photo in the list, and then you change the photo that was pointing to the next photo, to the photo being inserted.

1 -> 2 -> 3  #insert 4 after 1, before 2
1 -> 2 -> 3   4 -> 2  # point 4's pointer to 2
1 -> 4 -> 2 -> 3  # change 1's pointer to 4

Answer 2

I have done the exactly same stuff in RoR. I think the approach you choose depends on what kind of operation you will do on the model most frequently.

I tried to use database to implement a double linked list. Which means, your Photo model have two more attributes, prev and next. prev is the id of the previous Photo item, and next is the id of the next Photo item. If you are still not clear, check out any data structure book about double linked list.

For this data structure, complexity for inserting is O(1), and querying is O(n).

Another approach is the one you mentioned in item 1: a simple integer to denote the order. so 1,2,3,4,5. .... Complexity inserting is O(n), and querying is O(1).

Thus, if you do inserting more than querying, choose my approach. Otherwise choose your first approach.