javascriptbackbone.jsunderscore.js

Sort Backbone Collection based on a file order list

I have a inherited a system that utilizes a Backbone collection of files that needs to be sorted based on a series of values. The order variable is saved when you slide different files into a position in the view. It mostly works but there are rare times when it is not sorted correctly based on values in the files_order list. I found that using the unsigned right shift came the closest to working but the code is returning odd results as a number of the files in the collection are not in the files_order.

For filecollectionid = 1, the system result is: 36528,36524,36529,35526,36523,36525,36530,36531

The correct order should be: 36528,36523,36524,36525,35526,36529,36530,36531

I am assuming the unsigned right shift of variables that do not exist in the list are causing the problem. Any help would be greatly appreciated.

collection = new Backbone.Collection([
  { id: 36523, name: "File 1", filecollectionid: 1 },
  { id: 36524, name: "File 2", filecollectionid: 1 },
  { id: 36525, name: "File 3", filecollectionid: 1 },
  { id: 36526, name: "File 4", filecollectionid: 1 },
  { id: 36528, name: "File 5", filecollectionid: 1 },
  { id: 36529, name: "File 6", filecollectionid: 1 },
  { id: 36530, name: "File 7", filecollectionid: 1 },
  { id: 36531, name: "File 8", filecollectionid: 1 },
  { id: 36476, name: "Video 1", filecollectionid: 6 },
  { id: 36520, name: "Video 2", filecollectionid: 6 },
  { id: 36527, name: "Video 3", filecollectionid: 6 }
]);

sections = {
 "id": 1,
"files_order" : [36503,36513,36505,36506,36507,36508,36509,36510,36511,36521,36528,36522,35523,36524]
}

collection.sort(function(a,b) {
    // Lets group files by the file collection id first
    if(a.filecollectionid != b.filecollectionid){
        return a.filecollectionid - b.filecollectionid;
    }

    // Lets try to use the files_order variable
    try {
        // Get the files_order field
        var files_order = _.find(sections, function(section) {
            // They should both have the same filecollectionid
            return a.filecollectionid == section.id;
        }).files_order;

        files_order = _.map(JSON.parse(files_order.toString()), function(item) {
            return parseInt(item);
        });

        // use unsigned right shift to keep the original and add the unadded to the end
        return (files_order.indexOf(a.id) >>> 0) - (files_order.indexOf(b.id) >>> 0);
    } catch(e) {
        // If no sorting order this really should be oldest first and newest last.
        a = a.id;
        b = b.id;
        return ((a < b) ? -1 : ((a > b) ? 1 : 0));
    }
});
Solution

  • I will start by pointing out the mistakes in your code. Then, I will explain the unexpected results. Finally, I will show an approach that works.

    The mistakes

    Here:

    sections = {
 "id": 1,
"files_order" : [36503,36513,36505,36506,36507,36508,36509,36510,36511,36521,36528,36522,35523,36524]
}

    you probably meant an array of objects:

    sections = [{
    "id": 1,
    "files_order" : [36503,36513,36505,36506,36507,36508,36509,36510,36511,36521,36528,36522,35523,36524]
}]

    but I guess this mistake was only in your question and not in your actual code, because you would be getting worse results otherwise.

    Here:

    collection.sort(function(a,b) {

    You pass a comparator function directly to Collection#sort. However, Collection#sort is different from Array#sort; it does not expect you to pass a comparator function. You can only pass an optional object with options. The comparator is supposed to be a permanent property of the collection.

    Here (and elsewhere in the function body):

        if(a.filecollectionid != b.filecollectionid){
        return a.filecollectionid - b.filecollectionid;
    }

    you are trying to extract .filecollectionid directly from a and b. However, those are instances of Backbone.Model, not plain objects. The properties you are looking for are embedded in a.attributes and b.attributes. You are supposed to access them using the .get and .set methods.

    Here:

            files_order = _.map(JSON.parse(files_order.toString()), function(item) {
            return parseInt(item);
        });

    your code is doing something very different from what you seemed to expect. When you call .toString() on an array, it will stringify all values and concatenate them with commas, but it will not put square brackets around the entire list. For example, [123, 'abc', undefined].toString() evaluates to 123,abc,. Even if the string looks like 36529,36524, this is not valid JSON, so the JSON.parse call will throw an exception.

    There are also some parts of your code that are not technically wrong, but which are just not very efficient or more complicated than necessary. I will address those in the solution. But first: the reason for your unexpected results.

    Why you get the wrong order

    Your first problem is that your collection does not have a comparator property and you cannot pass it to Collection#sort, so the .sort method does not know how to compare the files. This results in it simply sticking to the input order.

    If this were not the case, the comparator function would still give you the wrong result. There are two reasons for this. Firstly, models do not have a .filecollectionid property, so this attribute is disregarded in the comparison.

    Secondly, the overal structure of your comparator function is like this:

    if(a.filecollectionid != b.filecollectionid){
    // Compare by filecollectionid
}

try {
    // Compare by files_order
} catch(e) {
    // Compare by id
}

    The try block never completes, because your call to JSON.parse always throws. Hence, files are never compared by their filecollectionid or by the files_order, but always by the id.

    Solution

    We can solve multiple problems at once by using _.invert. This function takes an object or array and returns a "flipped" version where the keys become values and vice versa. For your files_order, that means it turns [36503, 36513] into {'36503': 0, '36513': 1}. Conveniently, this means it no longer matters whther the ids in the array are encoded as numbers or as strings. You do not need any parsing and looking up the order of an id is fast, especially if you cache the inverted object.

    In the snippet below, I demonstrate how you can use _.invert to your advantage. I also demonstrate how you can stop relying on try/catch and show you a few nice Underscore tricks along the way. I encourage you to look up the documentation of each of these functions.

    var collection = new Backbone.Collection([
    { id: 36523, name: "File 1", filecollectionid: 1 },
    { id: 36524, name: "File 2", filecollectionid: 1 },
    { id: 36525, name: "File 3", filecollectionid: 1 },
    { id: 36526, name: "File 4", filecollectionid: 1 },
    { id: 36528, name: "File 5", filecollectionid: 1 },
    { id: 36529, name: "File 6", filecollectionid: 1 },
    { id: 36530, name: "File 7", filecollectionid: 1 },
    { id: 36531, name: "File 8", filecollectionid: 1 },
    { id: 36476, name: "Video 1", filecollectionid: 6 },
    { id: 36520, name: "Video 2", filecollectionid: 6 },
    { id: 36527, name: "Video 3", filecollectionid: 6 }
]);

var sections = [{
    "id": 1,
    "files_order" : [36503,36513,36505,36506,36507,36508,36509,36510,36511,36521,36528,36522,35523,36524]
}, {id:2}];

// Based on sections, we create two lookup structures. _.chain lets 
// us apply a series of functions to a value in order to massage
// it into a different shape step by step.
var baseLookup = _.chain(sections) // no semicolon, expression continues!
// Look up each sections object by its id.
.indexBy('id')
// Extract the files order.
.mapObject('files_order');

// That was the common part. The first lookup structure goes on:
var orderLookup = baseLookup
// Invert each one in order to find the index of each file id.
.mapObject(_.invert)
// Done, finish the chain.
.value();

// The second lookup has a different content per section:
var sizeLookup = baseLookup
// Get the size of the files_order array of each section.
.mapObject('length')
// Again, done with the chain.
.value();

// Collections have a comparator property that you can set.
// Let us use that to store the comparator function.
collection.comparator = function(a, b) {
    // Compare by collection id if different.
    var aCollection = a.get('filecollectionid');
    var bCollection = b.get('filecollectionid');
    if (aCollection != bCollection) {
        // + casts strings to number.
        return +aCollection - +bCollection;
    }
    
    // Same collection id, let us see whether we have a section
    // and a files order for it.
    var sectionLookup = orderLookup[aCollection];
    
    // If we do not, compare by id.
    if (!sectionLookup) {
        return +a.id - +b.id;
    }
    
    // We have a defined files order for the common section id.
    // In order to put files without a defined order at the end,
    // compute a maximum index value first.
    var beyondEnd = +sizeLookup[aCollection] + 1;
    
    // Try to look up the index of both ids. If the id is found,
    // add 1 to ensure we get a truthy value (greater than zero).
    // Otherwise, undefined+1 evaluates to NaN, which is falsy.
    // In the latter case, we use || to substitute the beyond the
    // end index, so these values are sorted last.
    var aIndex = +sectionLookup[a.id] + 1 || beyondEnd;
    var bIndex = +sectionLookup[b.id] + 1 || beyondEnd;
    
    // Finally, we have everything we need to compare by file order.
    return aIndex - bIndex;
};

// The collection knows its comparator, so we can call its sort
// method without arguments.
collection.sort();

// We log to console to inspect the final order.
console.log(collection.models);
    <script src="https://cdn.jsdelivr.net/npm/underscore@1.13.6/underscore-umd-min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/backbone@1.6.0/backbone-min.js"></script>