Javascript - Sort Array By Reference

I'm trying to sort a JavaScript Array by the reference to another object. I have An array of Mesh. Each mesh contains an attribute named 'texture', which contains the reference to

Solution 1:

I doubt that there is a built-in solution for that.

You cannot use Array.sort() unless you can define an ordering relation on your objects, e.g. implement an operation <=. JavaScript does not expose meta information such as memory addresses, so there is no non-obtrusive solution.

As always, "fast" is a relative term. There is no "absolute fast", only "fast enough", so a naive O(n^2) implementation might work for you.

Solution 2:

Here's one way of doing the sorting using the new experimental WeakMap (only supported in Firefox as of this writing). By associating each texture with an index with the help of a WeakMap we can use the index in the sort function:

var texture1 = {name:"tex1"};
var texture2 = {name:"tex2"};
var texture3 = {name:"tex3"};

var meshes = [
    {name: "Mesh 0", texture: texture1},
    {name: "Mesh 1", texture: texture2},
    {name: "Mesh 2", texture: texture3},
    {name: "Mesh 3", texture: texture3},
    {name: "Mesh 4", texture: texture2},
    {name: "Mesh 5", texture: texture1},
    {name: "Mesh 6", texture: texture1},
    {name: "Mesh 7", texture: texture2},
    {name: "Mesh 8", texture: texture3},
    {name: "Mesh 9", texture: texture1}
];

var textureSortOrder = [texture1, texture2, texture3];
var sortMap = new WeakMap();

for (var i=0;i<textureSortOrder.length;i++) {
    sortMap.set(textureSortOrder[i], i);
}

meshes = meshes.sort(function(a, b){
   var indexA = sortMap.get(a.texture);
   var indexB = sortMap.get(b.texture);

    if (indexA < indexB) {
        return -1;
    } else if (indexA > indexB) {
        return 1;
    } else {
        return 0;
    }
});

console.log("sorted:");
for (var i=0;i<meshes.length;i++) {
    console.log(i, meshes[i].texture.name);
}

http://jsfiddle.net/ch5QJ/

I have no idea how fast this is, and as I said only Firefox supports WeakMap. But it might be worth testing it and use it for browsers which do support it if it does turn out to be fast.

Solution 3:

You can use underscore for this. Which anyway i suggest you to include if you need to manipulate objects, make your life easier:

here there is the fiddle: http://jsfiddle.net/pmcalabrese/2KSSn/

and here the code.

sorted = _(meshes).sortBy(function(meshes) {
    return meshes.texture;
});

I suggest you to give a look at the documentation of sortBy.

Solution 4:

Perhaps something like this? I haven't done any performance testing.

Javascript

function sortByTextureOrderOrGroupThem (theArray, theOrder) {
    var temp = [],
        thisOrder = theOrder || [],
        thisOrderLength = thisOrder.length,
        thisOrderIndex,
        order,
        theArrayLength,
        theArrayIndex,
        element;

    // if we were given an order then build the temp array from that and remove the element from theArray
    for (thisOrderIndex = 0; thisOrderIndex < thisOrderLength; thisOrderIndex += 1) {
        order = thisOrder[thisOrderIndex];
        for (theArrayIndex = theArray.length - 1; theArrayIndex >= 0; theArrayIndex -= 1) {
            element = theArray[theArrayIndex];
            if (element.texture === order) {
                temp.push(theArray.splice(theArrayIndex, 1)[0]);
            }
        }
    }

    // anything remaining in the array, group them together
    theArray.sort(function (a, b) {
        if (a.texture === b.texture) {
            return 0;
        }

        if (a.texture < b.texture) {
            return -1;
        }

        return 1;
    });

    // join any remaining grouped items to the temp
    temp = temp.concat(theArray);
    // empty theArray
    theArray.length = 0;
    // add the length and the starting index for use with apply
    temp.unshift(temp.length);
    temp.unshift(0);
    // splice temp back into theArray
    [].splice.apply(theArray, temp);

    // return theArray in case it is needed this way
    return theArray;
}

var texture1 = {"name": "texture1"},
    texture2 = {"name": "texture2"},
    texture3 = {"name": "texture3"},
    meshes = [
        {name: "Mesh 0", texture: texture1},
        {name: "Mesh 1", texture: texture2},
        {name: "Mesh 2", texture: texture3},
        {name: "Mesh 3", texture: texture3},
        {name: "Mesh 4", texture: texture2},
        {name: "Mesh 5", texture: texture1},
        {name: "Mesh 6", texture: texture1},
        {name: "Mesh 7", texture: texture2},
        {name: "Mesh 8", texture: texture3},
        {name: "Mesh 9", texture: texture1}
    ],
    order = [texture1, texture2, texture3];

sortByTextureOrderOrGroupThem(meshes, order);
console.log(JSON.stringify(meshes));

jsFiddle