Ordering algorithm for datastructure with single update.

Question

So I have a datastructure - a sort of List type - that needs to be ordered. When the order is set the elements know what comes before and after them.

When objects are removed from the list, the list isn't updated, the object that is removed just gets new parent id value, so other elements don't know that the element got removed (like they know in typical JAVA LinkedList way, where pointers are updated)

Also when the object is set to another position in the list I'd like to make single updated to the database.

Current solution is using versioning system. So the values for the the ordering algorithm can be 1.1.1 and 1.1.1.1 now when I but and object inbetween them I give it a value of 1.1.1.0.1

Would there be any other (better) system for this problem?

Answer 1

This sounds like a good question for Stack Overflow.

My random attempt: why not imagine the whole list is encoded with a (binary) number between $0$ and $1$ (note: you will never use $0$ or $1$). The first element you add will be right in the middle ($0.1$), the next would be either $0.01$ or $0.11$ (depending on whether it is bigger or smaller than the previous one) etc. In other words:

• Whenever you insert an element between two elements, you tag it with arithmetic mean of its two nearest neighbours.
• If you add an element bigger than any previously added, then the arithmetic mean is of the biggest previously added and $1$.
• If you add an element smaller than any previously added, then the arithmetic mean is of the smallest previously added and $0$.

This is actually similar to your versioning approach, but uses only two possible digits/symbols ($0$ and $1$); however, it may end up with long sequences of symbols (again, similar to your approach).