Javascript - сортировать массив по ссылке

Question

Я пытаюсь сортировать массив JavaScript по ссылке на другой объект.

У меня есть массив сетки. Каждая сетка содержит атрибут с именем «texture», который содержит ссылку на объект WebGLTexture. Объекты WebGLTexture не содержат никаких читаемых атрибутов, я могу сравнить их только по ссылке (==). Метод toString не определен.

Вот пример исходной ситуации:

var texture1 = gl.createTexture(/* blah */); // Returns a WebGLTexture object 
var texture2 = gl.createTexture(/* blah */); // Returns a WebGLTexture object 
var texture3 = gl.createTexture(/* blah */); // Returns a WebGLTexture object 
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 meshes = [ 
    {name: "Mesh 0", texture: texture1}, 
    {name: "Mesh 5", texture: texture1}, 
    {name: "Mesh 6", texture: texture1}, 
    {name: "Mesh 9", texture: texture1}, 
    {name: "Mesh 1", texture: texture2}, 
    {name: "Mesh 4", texture: texture2}, 
    {name: "Mesh 7", texture: texture2}, 
    {name: "Mesh 2", texture: texture3}, 
    {name: "Mesh 3", texture: texture3}, 
    {name: "Mesh 8", texture: texture3} 
]; 

Я знаю, что это может быть возможным, чтобы достичь ее с петель, но это потребует, чтобы создавать объекты и массивы, и делать много вложенных циклов. Производительность здесь действительно важна.

Лучшее решение, которое я могу найти, - это вручную добавить к каждой текстуре уникальный атрибут «id» и использовать на нем Array.sort. Но я не очень доволен этим решением, это подразумевает изменение собственных объектов.

Знаете ли вы какой-нибудь родной и быстрый метод?

EDIT: На основании ответа воевали, вот решение:

var tempSortTextures = []; 
meshes.sort(function(a, b) { 
    var iA = null; 
    var iB = null; 
    for(var i = 0 ; i <= tempSortTextures.length ; i++) { 
     if(i == tempSortTextures.length) { 
      if(iA == null) { 
       tempSortTextures.push(a.texture); 
      } else /*if(iB == null)*/ { 
       tempSortTextures.push(b.texture); 
      } 
     } 
     var currentTexture = tempSortTextures[i]; 
     if(iA == null && a.texture == currentTexture) iA = i; 
     if(iB == null && b.texture == currentTexture) iB = i; 
     if(iA != null && iB != null) return iA - iB; 
    } 
}); 

Answer 1

Вероятно, не самое лучшее решение, но это работает (с чистым JavaScript) :)

var map = [texture1, texture2, texture3]; 

meshes.sort(function (a, b) { 
    var i = 0, item; 
    while (item = map[i]) { 
     if (a.texture && item === a.texture) { a = i; } 
     if (b.texture && item === b.texture) { b = i; } 
     if (!a.texture && !b.texture) { return a - b; } 
     i++; 
    } 
}); 

Answer 2

Вы можете использовать подчеркивание для этого. Что в любом случае я предлагаю вам включить, если вам нужно манипулировать объектами, сделать вашу жизнь проще:

здесь есть скрипка: http://jsfiddle.net/pmcalabrese/2KSSn/

и вот код.

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

Предлагаю вам ознакомиться с документацией sortBy.

Answer 3

Сомневаюсь, что для этого есть встроенное решение.

Вы не можете использовать Array.sort(), если вы не можете определить отношение упорядочения на ваших объектах, например. выполнить операцию <=. JavaScript не предоставляет метаинформацию, такую ​​как адреса памяти, поэтому нет никакого навязчивого решения.

Как всегда, термин «быстрый» является относительным термином. Нет абсолютной скорости, только «достаточно быстро», поэтому для вас может быть реализована наивная реализация O(n^2).

Answer 4

Вот один из способов сделать сортировку с использованием новой экспериментальной WeakMap (поддерживается только в Firefox момент написания этой статьи).Сопоставляя каждую текстуру с индексом с помощью WeakMap мы можем использовать индекс в функции сортировки:

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/

Я понятия не имею, как быстро это, и как я сказал, только Firefox поддерживает WeakMap. Но, возможно, стоит протестировать его и использовать его для браузеров, которые поддерживают его, если он окажется быстрым.

Answer 5

Возможно, что-то вроде этого? Я не тестировал производительность.

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