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

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);
		store.add(item);
	},
	
	/**
	 * 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.