Collection Sort on Model Change

[snoe]

The documentation for Collection.sort says

a collection with a comparator function will maintain itself in proper sort order at all times.

Yet, if my comparator is

comparator: function(model) {
    return model.get("name");
}

Then if I change the name:

model.set({name: 'zzz'});

and in the change event I use indexOf, I get the wrong index:

model.bind('change', changed);
changed = function(model) {
    var index = model.collection.indexOf(model)
     // index is based off the old name
}

This is because the collection does not resort automatically on change. I think the documentation should change, or preferably, a this.sort({silent}) in Collection._onModelEvent should occur.

[wookiehangover]

Here's a test case of what you're describing: http://jsfiddle.net/wookiehangover/mQEAJ/

Unfortunately, the line from the documentation you quote is referring to Collection.sort's usage in conjunction with Collection.comparator.

From the comparator section:

This means that as models are added, they are inserted at the correct index in collection.models.

The comparator is only run when inserting a model into a collection or when sort is called, not when a model is updated. Since comparator functions are potentially expensive against large collections, it makes sense to not have this behavior as the default.

BUT, if you need to sort your collection on change all you need to do is call model.collection.sort() In your change event handler. See the example.

@jashkenas / @tbranyen probably cool to close this one.

[snoe]

I understand there could be performance implications (although it would be interesting to compare vs insertion) and it is certainly possible to manually sort.

However, since the collection is allowed to become unordered through updates, then how can a model get a correct insertion index? Underscore uses a binary search to determine sortedIndex, so from a user's perspective an insert could seem to be placed randomly. I'd suggest that this invalidates the documentation that you reference.

So maybe it's a fair trade to only use comparator on insert. But why shouldn't the documentation at least be more clear that if you change a comparator field then the ordering guarantee goes out the window? I had to look through the source to confirm that updates didn't sort automatically, I assumed I was doing something wrong when I added sort to my change handler.

If the line I quoted instead said something like:

You probably only need to call this from change events that would affect the ordering;
a collection with a comparator function will maintain itself in proper sort order while inserting new records. 

I believe it would have saved me time.

edit: I also believe that if you go out of your way to define a comparator, it would seem odd to me that you would only want inserts to maintain ordering.

[wookiehangover]

agreed, +1 for clearing this up in the documentation

[wookiehangover]

not sure if this is bug per se... seems like any patch for this would be an "enhancement."

@jashkenas care to chime in on the intended behavior here?

[jashkenas]

I think this is fixable ... because of how Backbone.js currently does it's sorting -- which is a plain transformation of each model to a sort key. We can have collections (only collections that have comparators) cache the sort keys of their models. And then, when a model changes, we can have the collection check if the sort key has changed. If it has ... trigger a re-sort.

[jashkenas]

Nevermind -- if you change the sort key of ten models in a row -- you certainly don't want to re-sort your collection ten times over. Better to have the current behavior and call sort() when necessary.

[dcuddeback]

I disagree that there is a performance problem with automatically keeping a collection sorted. Assume you have a sorted collection of N elements and one of those elements changes. You don't have to resort the entire collection (O(N*log N)). Since you know that the other N-1 elements are already sorted relative to each other, you only have to reposition the one element, which is O(log N)---the same cost as inserting a model into a sorted collection.

Even in the scenario that @jashkenas describes, where you rapidly change ten models in the collection, resorting the individual models when they change is O(10*log N) which is still cheaper than even a single re-sort (again, O(N*log N)).

Is there any possibility we could revisit this to keep collections sorted on model changes? Or are there other reasons that I'm missing for not keeping a collection sorted? I'd be willing to work on this when I have free time. Is there some philosophical conflict that would prevent this from being accepted?

[maletor]

Is there some philosophical conflict that would prevent this from being accepted?

lol.

But seriously, @dcuddeback raises many a valid point.