4

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?

  • The Order field has been implemented for more than 50 years as an integer in most cases I have seen. Typically, you don't need to store order until leaving the UI as there are plenty of techniques for determining the correct order in the UI. Just before sending the data to its storage mechanism, set a counter to the Order value of your data. – Adam Zuckerman Dec 15 '14 at 2:28
  • How about as linked list? Each item will contain a "previous" field which contains a unique identifier referring to the previous item. Each "move" will be represented as a deletion from its original place and an insertion at its new place. A deletion takes one update; an insertion takes two updates. Moving a consecutive range of items takes the same number of updates as moving a single item. – rwong Mar 15 '15 at 6:07
  • 2
    @rwong: A Linked list would be a good conceptual solution; the problem is it's difficult to sort the list. Don't think there's an efficient way to do that with MongoDB, for example? – Dan Dascalescu Mar 16 '15 at 6:54
3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.