Tree Node Ordering

[skirtle]

Having problems with 4.1.0-beta-1 and tree node order in Chrome. Reproduced the problem on both Linux and Windows but only in Chrome.

Ext.create('Ext.tree.TreePanel', {
    height: 200,
    renderTo: Ext.getBody(),
    width: 200,
    root: {
        text: 'Tree 1',
        children: [
            {text: '01', leaf: true},
            {text: '02', leaf: true},
            {text: '03', leaf: true},
            {text: '04', leaf: true},
            {text: '05', leaf: true},
            {text: '06', leaf: true},
            {text: '07', leaf: true},
            {text: '08', leaf: true},
            {text: '09', leaf: true},
            {text: '10', leaf: true},
            {text: '11', leaf: true}
        ]
    }
});

I debugged as far as this line in Ext.data.TreeStore:

Ext.Array.sort(records, me.sortByIndex);

Seems to me that sortByIndex is returning 0 for all comparisons, so the order will depend on the sorting algorithm used by the browser. In the case of Chrome that means things get messed up.

[Animal]

Strange. Chrome has a stable sort which is determined at startup time by testing using a sort with a comparator function which returns 0. But it's scrambling the nodes when it sorts in TreeStore.fillNode

Digging in, there's quite a bit of unnecessary sorting happening now that we have implemented findInsertionIndex in MixedCollection which allows you to maintain a MixedCollection in sorted order.

[Animal]

I just fixed it and made it more efficient.

Sorting by index is only done if there are differing indices within the new nodes.

And if there is local sorting configured anyway, an indexSorter is prepended into the collection of sorters which gets applied upon node add.

So instead of two sorts, it's now either zero or one.

[stahlman]

The problem is that Ext's logic for detecting the presence of a stable sort won't work for Chrome. Chrome actually uses 2 different sort algorithms: a stable algorithm for small arrays, and a non-stable (quicksort) algorithm for large ones. According to my tests, a "small" array has <= 10 elements. Ext's test uses only 5 elements, and hence, detects Chrome's sort algorithm as stable; most grids, unfortunately, will have more than 5 nodes, resulting in a broken (unstable) sort...

Note that there was actually a bug opened against the V8 JS engine for this in 2008, but the bug status is "WorkingAsIntended". Here's the thread:
http://code.google.com/p/v8/issues/detail?id=90

I created the following workaround for my own usage, but I would suggest that the number of elements used in the Ext test needs to be increased...

// CAVEAT!!!: Unlike JS and Ext sorts, this version sorts a copy.
// It does NOT modify the original array.
Ext.Array.trulyStableSortCopy = function(a, fn) {
    var i = 0,
        fnw = function(a, b) {
            var res = fn(a.v, b.v);
            return res !== 0 ? res : a.i - b.i;
        };
    return Ext.Array.map(
        Ext.Array.sort(
            Ext.Array.map(a, function(v) {
                return { i: i++, v: v };
            }), fnw),
        function(v) { return v.v; });
};