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:
- Bite the bullet and reorder your entire list, i.e. assign an order of
0
at index 0, an order1
at index 1, ... an ordern
at index n. - 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
andlist[i+1].order = (list[i+2].order + list[i+1].order)/2
before reorderinglist[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] tolist[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.