Archive for January, 2013

Paginate a Backbone.js collection

January 28, 2013

When you have too many results, you have to paginate, we all know that. With backbone.js there are different approaches, depending on whether you have all your data in the collection, or do you paginate “server-side” – that is, via calling a .fetch() on the collection every time you move to a new page, so essentially only storing one page at the time.
You could hold multiple pages, for example store page 1, currentPage – 1, currentPage, currentPage + 1, and the last page, in order to optimize the most common operations: move first, move previous, move next, move last.

In this article, I’m going to tackle a simpler scenario, when all the data is in the collection (in memory). No server round trips will be needed. In a subsequent article, I will build on this, to implement something more advanced. So let’s get started.

My first step was to enhance the collection so it can iterate over the selected page. I’ve added a so called “partialEach”, like .each, but only iterating over the given page.

Backbone.Collection.prototype.partialEach = function(offset, maxItemsPerPage, iterator, context) {
	for (var l = this.length; maxItemsPerPage !== 0 && offset < l; offset++) {
		var model = this.at(offset);
		if( model ) {
			iterator.call(context, model, offset, this);
			maxItemsPerPage--;
		}
	}
};

where:
   offset          - the offset within the colection of the element to start from (index of the first element on the page)
   maxItemsPerPage - the number of items per page
   iterator        - the callback, the function to call for each item (this will be used to render the element, or build the DOM or the html string for rendering)
   context         - a context to be passed back to the callback

Now, why do this, instead of a simple for loop, from offset to offset + maxItemsPerPage?
Because a simple pagination is generally not good enough. What if the user wants to filter the results and you have to paginate the filtered results? In that case, the for loop (offset to offset + maxItemsPerPage) doesn’t work anymore, as not all the items within that range will be included in the filter.

To support filters, I have modified the function above like this:

Backbone.Collection.prototype.partialEach = function(offset, maxItemsPerPage, iterator, context) {
	for (var l = this.length; maxItemsPerPage !== 0 && offset < l; offset++) {
		var model = this.at(offset);
		if( model && this.filterFunc( model, offset, this ) ) {
			iterator.call(context, model, offset, this);
			maxItemsPerPage--;
		}
	}
};

A filterFunc is just a function that takes a model and returns true or false. It has to be set on the Backbone.Collection.prototype in the similar way and then it can use a filterObject you can set on each individual collection, with the details of the actual search.

Now, a view that wants the items for a particular page needs to calculate the offset.
So how can a view calculate it?

For the scenario where there are no filters, it’s quite easy:

    offset = pageNumber * itemsPerPage;

with pageNumber starting from 0 to totalPages – 1.

But when you have a filter, it is not that straightforward. For this scenario, I will introduce the concept of a pageCache.
A pageCache will store for each page, the first index of the items on that page. This is the index where the search (filtering) should start from, it doesn’t mean that the first item will be included in the filter.

So, for the first page, pageCache will have:

   pageCache = { 0 : 0 }

First page starts (page number 0), starts from index 0. This will be true for all filters.
Rather than calculate all the others, we will be lazy here, for performance reasons, and only populate the pageCache as the user is searching.
Once we have the pageCache, we can calculate the offset as follows:

	getPageOffset: function(){
		if(!this.collection.hasFilter()){
			return this.pageNumber * this.itemsPerPage;
		} else {
			if(!this.pageCache){
				this.pageCache = { 0 : 0 };
				return 0;
			} else {
				return this.pageCache[this.pageNumber];
			}
		}
	}

This function is optimized for the scenario where the view/collection has no filter.
Then it gets the offset from the pageCache, it also builds the pageCache if it doesn’t exist.
With this offset, the view can then call into the partialEach to get the items it wants.

As for the lazy update, once the view iterates over the items, it keeps track of the lastIndex for each page, and then updates the pageCache:

	updatePageCache: function(pageNo, lastIndex){
		if(this.collection.hasFilter()){
			this.pageCache[pageNo + 1] = lastIndex + 1;
		}
	}

where:
        lastIndex is the last index on the page that has just been displayed, therefore the iteration on next page (pageNo + 1) will start from lastIndex + 1

This is just a rough implementation for you to get an idea. There are more exercises left for the user:

  • pageCache needs to be reset when the filter changes
  • determining whether there are more items that match the filter is not implemented (this needs to be done to know whether to show the Next button or not)
  • how do you deal with new items being inserted in the collection? The pagination technique above recovers on the second pass only (this might be sufficient)
  • how do you optimize operations like Move Last, which would require to iterate the whole list if there is a filter on and the pageCache is not populated
Advertisements