Maintain ordered collection by updating as few `order` fields as possible

Question

I'm working on integrating a reorderable lists UI widget with a Meteor.js (MongoDB, in effect) collection:

{
  order: ???,  // what type to use here?
  property1: ...,
  ...
  propertyN: ...
}

Each document in the collection has an order field. The UI gets the collection from the server, sorts it by the order field, and displays it in a list. When the user drags an element into a new position in the list, I get the oldIndex of the document and the newIndex relative to the beginning of the list (where it was dropped). Now, I need to update the order field and save the affected document(s) back into the collection.

What should be the nature of the order field to minimize the number of updates, yet not limit the number of times a document can be reordered?

A naive implementation uses integers and sets the order of the dropped item to the arithmetic mean of the documents before an after. Of course, this will run into floating point precision limits (50 reorders in JavaScript if you start with consecutive integers).

Another implementation (also suggested in this question would change the order of all the intervening documents between the oldIndex and the newIndex of the dropped document, or between the start/end of the list and the dropped item (whichever involves fewer elements). Of course, this is less efficient, particularly for larger lists.

Anything smarter? Using a string or object of some sort for the order field?

Answer 1

One obvious solution is to use arbitrary precision arithmetic.

As an implementation with big.js:

var Big = require('./big.js');

function average(x, y) {
  // exact result; .div(2) requires specifying .DP
  return Big(x).plus(y).times(0.5);
}

var x = new Big(1);
var y = new Big(2);

for (i = 0; i <= 10; i++) {
  x = average(x, y);
  console.log(x.toString());
}

The disadvantage, of course, is that each reordering will add one byte to the order field. A normalize method could parse the orders and convert them to 0..N.