Collection.indexOf() problems with isSorted == true

[alexandersoto]

Using indexOf() with isSorted set to true on a collection with a 2 argument comparator does not work as I would expect.

Ultimately, I think the issue lies with _.sortedIndex() not being designed for a 2 argument comparator. Related - I don't think Collection.sortedIndex() works if the collection has a 2 argument comparator. I think that's the root of the problem.

Other thought:
I think it would be great if isSorted defaulted to true if a collection defined a comparator.

[alexandersoto]

Here's a simple test case to illustrate the problem. Perhaps I've misinterpreted the docs and these functions aren't expected to work with a 2-arg comparator. If not, I hope this helps.

var Integer = Backbone.Model.extend({
    defaults: {
        value : 0
    }
});

var Integers = Backbone.Collection.extend({
    model : Integer,
    comparator: function(int1, int2) {
        return int1.get('value') - int2.get('value');
    }
});

var test = function() {
    var ints = new Integers();
    for (var i = 0; i < 10; i++) {
        ints.add(new Integer({value : i}));
    }

    var one = new Integer({value : 1});
    ints.add(one);
    ints.indexOf(one); // Works
    ints.indexOf(one, true); // Not found, -1

    // That's because underscore's sortedIndex won't work:
    ints.sortedIndex(one); // Crashes with "Cannot call method 'get' of undefined"     
    ints.sortedIndex(one, one.comparator); // Crashes     
};

[gmp]

According to the docs the collection comparator function is allowed 1 or 2 models as arguments and distinguishes between sortBy and sort respectively. So I don't believe you've misinterpreted there.

From what I can tell you appear to be spot on with your conclusion that _.sortedIndex is not designed for situations with two argument comparators. It also looks like this issue has briefly come up in the past #2102.

Additionally, since indexOf ends up referring to sortedIndex when passed true as an option, it breaks when you run:

ints.indexOf(one, true)

Lastly, the final line of your test case crashes because you have made a small mistake in passing the one model's (nonexistent) comparator method into sortedIndex. I think you meant:

ints.sortedIndex(one, ints.comparator)

However, this would give you the same "Cannot call method 'get' of undefined" error because the collection comparator is passed by default to sortedIndex anyways on the line before.

[gmp]

I've been looking into this a bit more, and it appears to be either a documentation issue or sortedIndex would need to be written in order to allow two argument comparators.

I think the docs for collection comparator could provide a caveat that better explains the two scenarios of 1 v 2 arguments.

A one argument comparator will delegate to sortBy and allows for the use of indexOf and sortedIndex. Whereas a two argument comparator will delegate to native sort which is optimal for larger collections as it removes the preprocessing step of sortBy, but it will not work by default with indexOf and sortedIndex.

I'd be happy to submit a pull request for the above or potentially even work on fix for the indexOf and sortedIndex methods to account for two argument comparators, but want to make sure everyone's on board.

[gmp]

@jashkenas see commit gmp@2327bad for a potential fix.

Or it could just be a small documentation fix, see gmp@0988372

Would be happy to submit a pull request if either of these make sense

[jashkenas]

Thanks for finding this. You're quite right. SortedIndex existed because we used to use it for previous implementations of collections with comparators. Now that we no longer use it internally, it shouldn't be exposed anymore. I'll remove it. (Of course, the Underscore function remains available, should you wish).

[jwheare]

The Underscore sortedIndex isn't actually available because it's not included in the mixins whitelist.