1. #1
    Sencha Premium Member skirtle's Avatar
    Join Date
    Oct 2010
    Location
    UK
    Posts
    3,592
    Vote Rating
    323
    skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future skirtle has a brilliant future

      0  

    Default Tree Node Ordering

    Tree Node Ordering


    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.

    Code:
    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:

    Code:
    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.

  2. #2
    Sencha - Ext JS Dev Team Animal's Avatar
    Join Date
    Mar 2007
    Location
    Notts/Redwood City
    Posts
    30,502
    Vote Rating
    48
    Animal has a spectacular aura about Animal has a spectacular aura about

      0  

    Default


    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.

  3. #3
    Sencha - Ext JS Dev Team Animal's Avatar
    Join Date
    Mar 2007
    Location
    Notts/Redwood City
    Posts
    30,502
    Vote Rating
    48
    Animal has a spectacular aura about Animal has a spectacular aura about

      0  

    Default


    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.

  4. #4
    Sencha Premium Member
    Join Date
    Sep 2011
    Posts
    48
    Vote Rating
    1
    stahlman is on a distinguished road

      0  

    Default Root cause

    Root cause


    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...

    Code:
    // 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; });
    };
    Last edited by stahlman; 30 Mar 2012 at 6:48 AM. Reason: Wanted to clarify that the code workaround, unlike JS builtin and Ext sorts, does NOT modify the original array.

Thread Participants: 2