### A user maintained ordered list with minimal database writes

I need to provide a list of Things. The user can

• Prepend a new item
• Append a new item
• Insert a new item anywhere in the list
• Drag items around to change the order

Each item has a field called “seq” which contains a sequence number. The only constraint is that this is an integer and is ordered.

A simple solution would be to keep seq contiguous. The problem is that many of the above operations will require renumbering of the whole list of items, which in a system such as Ext-JS would require many PUT operations.

If the list is made non-contiguous the amount of PUTs can be kept to one in most cases, widening the range to effect more rows if needed. For example consider a sequencer that inserts items with a default step of 100, so we have a list

0 Item 1 Item 2 Item 3 Item 4 Item 5

Now to move “Item 1” between “Item 2” and “Item 3” I just set its sequence value to 150 and save it. If the Ext-JS Store is ordered then it will appear in the right place. I have reordered the list in one PUT operation.

If the space I want to move into is too small then I need to change more sequence values. A simple solution would be to give in here and renumber the whole list. This may be a good idea. Alternatively I consider the two items either side of the item I wish to insert. An intelligent algorithm may work out it only needs to look one side. This could be done later, but 3 PUTs are still better than modifying the whole list.

The core of the algorithm is the renumber method given below. Test code is attached to this post.

```	/**
* @private
* Renumber the list to maintain the sequence, trying to change as few records as possible.
* Items between but not including the pins are renumbered. If this fails then the pins are
* widened and the renumbering attempted again.
*
* @param {Ext.data.Model[]} items proposed new list of items
* @param {int} leftPin left most fixed item index
* @param {int} rightPin right most fixed item index
*/
renumber: function(items, leftPin, rightPin){
var me = this,
a,
b,
i,
seqField = me.seqField,
step = me.step * 2,
denominator,
arrayLength = items.length,
newSeq;

function isInArray(index){
return index>=0 && index<arrayLength;
}

// Ensure that the pins are within a sensible range, -1 to arrayLength.
if(leftPin < 0){
leftPin = -1;
}
if(rightPin > arrayLength){
rightPin = arrayLength;
}
denominator = rightPin - leftPin;

// Find the sequence value of the left pin, or create a false one if it's outside the array
if(isInArray(leftPin)){
a = items[leftPin].get(seqField);
} else {
a = 0;
for(i = 0; i < arrayLength; i++){
a = Math.min(a, items[i].get(seqField));
}
a-=step;
}

// Find the sequence value of the right pin, or create a false one if it's outside the array
if(isInArray(rightPin)){
b = items[rightPin].get(seqField);
} else {
b = 0;
for(i = 0; i < arrayLength; i++){
b = Math.max(b, items[i].get(seqField));
}
b+=step;
}

if(b-a >= denominator){
// There is space, so renumber
for(i = 1; i<denominator; i++){
newSeq = Math.round(a + (b-a)*i/denominator);
items[leftPin + i].set(seqField, newSeq);
}
} else {
// Move the pins outwards and try again.
// In the worse case we'll renumber the whole array adding 2*step to the range.
leftPin = leftPin-1;
rightPin = rightPin+1;
me.renumber(items, leftPin, rightPin);
}
}
```

The calling functions are:

```	/**
* Append an item to the end of the list.
* @param {Ext.data.Model} item the item to add.
*/
appendItem: function(item){
var me = this;
me.insertItem(me.store.getCount(), item);
},

/**
* Place an item at the given index in the list.
* @param {int} targetIndex index to place the new item at.
* @param {Ext.data.Model} item the item to add.
*/
insertItem: function(targetIndex, item){
var me = this,
store = me.store,
items = store.getRange();

items.splice(targetIndex, 0, item);
me.renumber(items, targetIndex-1, targetIndex+1);
},

/**
* Move an item from one place to another.
* @param {int} fromIndex index to move from.
* @param {int} toIndex index to move to **with respect to the now shorter array after it was first removed**
*/
moveItem: function(fromIndex, toIndex){
var me = this,
store = me.store,
items = store.getRange(),
item = items.splice(fromIndex, 1);

if(fromIndex !== toIndex){
items.splice(toIndex,0,item[0]);
me.renumber(items, toIndex-1, toIndex+1);
store.sort(me.seqField, 'ASC');
}
},
```

Full code is at DatabaseEfficientSequencer.zip. The test html outputs information to the console, so needs Chrome or Firefox or IE with the development tools. The code also needs Ext-JS which is not included.

This site uses Akismet to reduce spam. Learn how your comment data is processed.