Reordering objects with order property

Question

Consider objects with an order property. Objects will be sorted based on this property.

How would you assign the order property given the following restrictions and operations?

Operations (in order of importance)

push(object): Insert object at index 0.

swap(indexN, indexM): Swap object at index N with object at index M.

remove(object): Remove object. Remaining elements must retain the same order.

insert(object): Insert object with given order.

Restrictions

Changing the order property of an object is expensive. Changes should be minimised.

order can be integral or floating point, as required by the implementation.

If order is kept unique, then operation insert must include a way to fix the order if it already exists, making as few changes as possible. It can be assumed that if an inserted object has the same order than an existing object, there is another criteria to determine which one goes first.

If order allows duplicates, then operation swap must include a way to fix the order of the swapped elements if they have the same value, again making as few changes as possible. Penalising operation insert is preferred.

Most likely this problem has a name and a known solution already but I couldn't find it at first glance.

Answer 1

Use floating point for order

For push, assign the object an order equal to the order of the object that's now at index 1, minus 1 (list[0].order = list[1].order - 1)

For swap, swap the two objects' orders (temp = list[i]; list[i] = list[j]; list[j] = list[i]; temp = list[i].order; list[i].order = list[j].order; list[j].order = temp); if this might introduce consistency problems then ideally you could put a transit flag on the elements to indicate that their order is in the process of being modified, or worst case lock the objects until they're consistent

For remove, do nothing - the objects in the list are still ordered, you've just introduced a gap in the sequence which shouldn't be a problem

insert is the only problematic one. If you're inserting an element at index i, then its order is equal to the average of the orders of the elements at indices i-1 and i+1 (list[i].order = (list[i-1].order + list[i+1].order)/2). Verify that this new order doesn't equal the order at index i-1 or i+1 (list[i].order != list[i-1].order && list[i].order != list[i+1].order) - this would indicate that you've hit machine epsilon. When this occurs (and this should rarely if ever occur) you've got two options:

1. Bite the bullet and reorder your entire list, i.e. assign an order of 0 at index 0, an order 1 at index 1, ... an order n at index n.
2. Do a local reorder to try to minimize the cost. Reorder the adjacent elements to list[i-1].order = (list[i-2].order + list[i-1].order)/2 and list[i+1].order = (list[i+2].order + list[i+1].order)/2 before reordering list[i] = (list[i-1] + list[i+1])/2, again verifying that you haven't reached machine episilon at your [i-1] and [i+1] reordering - if you have reached machine epsilon at e.g. [i-1], then first reorder [i-2] to list[i-2].order = (list[i-3].order + list[i-2].order)/2, and then reorder [i-1]. If the [i-2] reorder hits machine epsilon then first reorder [i-3], and so on. (If you reach the end of the list then simply decrement the order of element [0] or increment the order of element [n].) As you can see, in the worst case you've got a cascade reordering that is more expensive than had you simply bit the bullet and reordered the entire list; however, in all likelihood the reordering will remain local. A good compromise is that if you've cascaded too many times (for a reasonable value of "too many") then do a complete reordering.

Answer 2

Just to throw it out there, a doubly linked list gives you:

• push(object): O(1), give it order 1 less than the current head.
• swap(indexN, indexM): O(n), swap the orders
• remove(object): O(1), don't touch any orders
• insert(object): O(n), insert the order so the list is sorted in terms of order

Might not be good since the 2nd most important one has an expensive (change order) operation.