Reloading items without changing the ranks of all items
I have a list of items, each with a rank associated with it.
Item 1, Rank=1
Item 2, Rank=2
Item 3, Rank=3
Item 4, Rank=4
Item 5, Rank=5
I want to create a method that handles re-positioning with minimal or no changes in the rows of other elements.
One solution I was thinking about was using decimal places and using Java double variable type. For example, if I move item5 between item2 and item3, this is the output -
Item 1, Rank=1
Item 2, Rank=2
Item 5, Rank=2.5
Item 3, Rank=3
Item 4, Rank=4
Etc,
Item 1, Rank=1
Item 2, Rank=2
Item 4, Rank=2.25
Item 5, Rank=2.5
Item 3, Rank=3
This solution works, but after some point (~ 55 moves to the same position, I reach the double limit of the variable and I probably have to reset all the ranks at that point)
I'm just wondering if there is a better way to solve this problem?
A few things to keep in mind.
- I need to store this data structure in a database (Item, Rank) and I will be creating a web service that gets all items in sorted order based on ranking, so I would make a DB call to sort all items by rank.
- I will be using Java, so I can only deal with Java variables.
source to share
How do I write a small subroutine that evenly distributes the rank values of a range of elements in an array (or list or whatever)?
If you insert a new element at position x, you are passing the elements of the range x-1 .. x+1
to the routine. the values of the ranks in the start and end positions remain unchanged, the rest are calculated with an even distance. Return true if successful. Now if the distance gets too small, you return false, the caller expands the range to x-2 .. x+2
and goes back to the subroutine.
You will have to take care of hitting the bounds of the array or ending up with a value space altogether.
source to share
There may be several solutions, this is what I would prefer
I would divide this problem into several isolated ones:
- In your java server, you want to have a list of items sorted in some way, with a fast O (1) execution in order.
The best structure is a double list. You will need to use a hashmap to quickly find objects by the name / id of the item in that list.
You can easily store such a structure in the database, just add two foreign keys to the item table. During storage, you will only have to update the affected rows (bearing in mind that the previous / next elements are also affected when the element is moved). It will look like severalupdate table set prev=?, next=? where id=?
- In your java service, you want to display a sorted list of items as quickly as possible, possibly paginated.
The best structure is a pre-sorted array.
To store such a structure in the database, you need a column to store the position (rank). Of course, you need an index on that column.
To get such a structure, you will use a very simple, fast and efficient query, for example select item from table order by rank limit ?,?
.
Now you have a contradiction, your edit data structure does not match your fetch data structure, and any attempt to use the same data structure for both problems will result in performance degradation in one piece, lets you fix this problem yourself:
- You will create a separate asynchronous service (cron job) that will read data from one table, convert (recalculate the ranking for all items) and store it in another table.
Here you will have two options, either completely replace the data in the 2nd table after the calculation, or find the diff and update only the changed rows. I find that a full replacement is easier to implement, and in fact it can be much faster.
Thus, with this approach, the client sees visible parts of your system (the data management part and the data display part are working as fast as possible).
The only problem is propagation of changes, which is usually fine and most users will take it as a reasonable compromise.
source to share