Displaying Backbone Collection as Tree

Today we will discuss tree.

Let's assume we have a collection of models:

var Model = Backbone.Model.extend({
});

var Collection = Backbone.Collection.extend({
    model: Model,
    sortTimeAsc: function(model) {
        var val=model.get('timestamp');
        return +val;
    },
    sortTimeDesc: function(model) {
        var val=model.get('timestamp');
        return -val;
    }
});

// fill our collection with data
var col= new Collection();
col.add(new Model({id:1, name:"Item1", timestamp:10, parentId: null}));
col.add(new Model({id:2, name:"Item2", timestamp:20, parentId: null}));
col.add(new Model({id:3, name:"Item1.1", timestamp:30, parentId: 1}));
col.add(new Model({id:4, name:"Item3", timestamp:40, parentId: null}));
col.add(new Model({id:5, name:"Item4", timestamp:50, parentId: null}));
col.add(new Model({id:6, name:"Item3.1", timestamp:60, parentId: 4}));
col.add(new Model({id:7, name:"Item3.2", timestamp:70, parentId: 4}));

// sor our collection by Time
col.comparator = col.sortTimeAsc;
col.sort({silent:true});      // silent option won't trigger reset event

We can go through our sorted collection pretty simple:

col.each(function(model_from_collection) {
    console.log("Got model", model_from_collection);
});

But this approach won't allow us to sort Collection into hierarchy. In C++ there was a template class (a class which can be instantiated with any type, usually basic one) called Iterator.

Introducing Iterator

Iterator is a class which 1 main method called next(). This method usually returns next element or null. In our case, we can create a class Iterator, which can be instantiated with the collection in constructor. Then we can implement these methods:

• reset() - sets the Iterator on start of the Tree
• next() - returns next Element in Tree or null

But first we have to be noticed about a few facts:

• Collection stores models in an Array
• We will not create a copy of the collection for our Iterator, because it's memory expensive
• We can't use shift, pop functions to remove first/last element from array because we have 2 pointers to 1 collection - 1 memory block
• We actually don't won't to mess up with our collection anyhow :)
• Because models are in Array, they have integer index starting at 0, so we can store them
• Tree traversing is basic Depth First Search (DFS) algorithm so it can be implemented with recursive function or a buffer

So enough talking, let's start up our class Iterator:

function Iterator(argument) {
    this.initialize(argument);
}
Iterator.prototype = _.extend(Iterator, {
    _tree: null,      // store our collection passed in constructor
    _stack: [],       // our stack for DFS

    initialize: function(collection) {
        this._tree = collection;
        this.reset();
    },

    reset: function() {
        // reset the iterator position at start of the Tree here...
    },

    next: function() {
        // implement here
    }
});

Between each step of DFS we need to pass the ID of parent and current level of the leaf. For this reason we will use simple object (called i.e. Backpoint) to store this data. For this we can add a method to our Iterator class:

    getBackpoint: function(level, index) {
        return {
            level: level,
            index: index
        };
    },

So finally we can focus on the Depth First Search algorithm! I do really like to simplify things, so here we are:

1. Fill the stack with element on level 0
2. The first element in the stack will be the one to return later
3. Check if the picked element has any children
4. If it has, add them at the beginning of the stack

This is basically it. Here is the whole code:

var Model = Backbone.Model.extend({
});

var Collection = Backbone.Collection.extend({
    model: Model,
    sortTimeAsc: function(model) {
        var val=model.get('timestamp');
        return +val;
    },
    sortTimeDesc: function(model) {
        var val=model.get('timestamp');
        return -val;
    }
});

// fill our collection with data
var col= new Collection();
col.add(new Model({id:1, name:"Item1", timestamp:10, parentId: null}));
col.add(new Model({id:2, name:"Item2", timestamp:20, parentId: null}));
col.add(new Model({id:3, name:"Item1.1", timestamp:30, parentId: 1}));
col.add(new Model({id:4, name:"Item3", timestamp:40, parentId: null}));
col.add(new Model({id:5, name:"Item4", timestamp:50, parentId: null}));
col.add(new Model({id:6, name:"Item3.1", timestamp:60, parentId: 4}));
col.add(new Model({id:7, name:"Item3.2", timestamp:70, parentId: 4}));

// sor our collection by Time
col.comparator = col.sortTimeAsc;
col.sort({silent:true});      // silent option won't trigger reset event

function Iterator(argument) {
    this.initialize(argument);
}
Iterator.prototype = _.extend(Iterator, {
    _tree: null,      // store our collection passed in constructor
    _stack: [],       // our stack for DFS
    options: {
        // these are options you can pass if your
        // collection uses key than 'parentId'
        id_name: 'id',
        parent_name: 'parentId'
    },

    initialize: function(tree, options) {
        this._tree = tree;
        this.reset();
    },

    reset: function() {
        var root = this;
        root._stack = [];
        // store lvl 0 backpoints into stack
        _.each(this._tree.models, function(model, index) {
            // as no parent allow a non number or number 0 value
            if (! _.isNumber( model.get(root.options.parent_name) ) ||
                  model.get(root.options.parent_name) == 0) {
                root._stack.push( root.getBackpoint(0, index) );
            }
        });
    },

    getBackpoint: function(level, index) {
        return {
            level: level,
            index: index
        };
    },

    // returns an array of indexes of first descendants of element in tree
    getDescendants: function(model) {
        var root = this;
        var output = [];

        this._tree.each(function(emodel, key) {
            if (emodel.get(root.options.parent_name) ==
                  model.get(root.options.id_name))
                output.unshift(key);
        });

        return output;
    },

    next: function() {
        var root = this;

        // get the first element from stack
        var bpoint = this._stack.shift();
        if (_.isUndefined(bpoint)) return null;

        var model = this._tree.at(bpoint.index);
        var desc = this.getDescendants(model);
        // prepend descendants to array (if any)
        _.each(desc, function(item) {
            root._stack.unshift( root.getBackpoint(bpoint.level+1, item) );
        });

        return model;
    }
});


it = new Iterator(col);

// this is how we display a list
while ((item = it.next()) != null) {
    console.log("#" + item.get('id') + " " + item.get('name'));
}

Here is the code on jsfiddle.net: http://jsfiddle.net/pavel_krupala/84bf4/1/. Hope this will be helpfull for you. If you have any questions, please leave a comment below.

Happy scripting! :)