сортировка данных в дерево

Question

У меня есть следующие данные:

var data = [
    { index : 1, sort : 10, parent : 0 },
    { index : 2, sort : 7, parent : 0 },
    { index : 3, sort : 15, parent : 1 },
    { index : 4, sort : 4, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 6, sort : 20, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 8, sort : 6, parent : 5 },
];

Как эффективно отсортировать это как по родительскому идентификатору, так и по значению сортировки, чтобы я в итоге получил:

var data = [
    { index : 4, sort : 4, parent : 0 },    
    { index : 2, sort : 7, parent : 0 },
    { index : 1, sort : 10, parent : 0 },
    { index : 5, sort : 13, parent : 1 },
    { index : 8, sort : 6, parent : 5 },
    { index : 7, sort : 2, parent : 8 },
    { index : 6, sort : 20, parent : 5 },   
    { index : 3, sort : 15, parent : 1 },
];

Этодревовидная структура.За каждым элементом сразу следуют любые дочерние элементы, и все элементы в одной ветви сортируются по значению сортировки.

Лучшее, что я могу придумать, - это сначала отсортировать по родителю, а затем выполнить вторую сортировку в каждой ветви.,Это кажется неэффективным.

Редактировать: пример порядка сортировки был неправильным.Я исправил это.

Редактировать для пояснения: каждая вложенная ветвь должна появляться сразу под родительским значением, а не в конце ветки.

Редактировать: дальнейшие исправления к данным.

Answer 1

Это не ваш первоначальный подход, но вы можете построить фактическое дерево из ваших данных, например:

function TreeNode(data) {
  this.data     = data;
  this.parent   = null;
  this.children = [];
}
TreeNode.comparer = function (a, b) { 
  return a.data.sort < b.data.sort ? 0 : 1; 
};
TreeNode.prototype.sortRecursive = function () {
  this.children.sort(TreeNode.comparer);
  for (var i=0, l=this.children.length; i<l; i++) {
    this.children[i].sortRecursive();
  }
  return this;
};

function toTree(data) {
  var nodeById = {}, i = 0, l = data.length, node;

  nodeById[0] = new TreeNode(); // that's the root node

  for (i=0; i<l; i++) {  // make TreeNode objects for each item
    nodeById[ data[i].index ] = new TreeNode(data[i]);
  }
  for (i=0; i<l; i++) {  // link all TreeNode objects
    node = nodeById[ data[i].index ];
    node.parent = nodeById[node.data.parent];
    node.parent.children.push(node);
  }
  return nodeById[0].sortRecursive();
}

С помощью этой настройки вы получите аккуратно вложенные узлы с помощью простого вызова:

var tree = toTree(data);

TreeNode:0
  parent  -> null
  data    -> undefined
  childen -> Array[
    TreeNode:1
      parent  -> TreeNode:0
      data    -> { index : 4, sort :  4, parent : 0 }
      childen -> Array[]
    TreeNode:2
      parent  -> TreeNode:0
      data    -> { index : 2, sort :  7, parent : 0 }
      childen -> Array[]
    TreeNode:3
      parent  -> TreeNode:0
      data    -> { index : 1, sort : 10, parent : 0 }
      childen -> Array[
        TreeNode:4
          parent  -> TreeNode:3
          data    -> { index : 5, sort : 13, parent : 1 }
          childen -> Array[
          ]
        TreeNode:5
          parent  -> TreeNode:3
          data    -> { index : 3, sort : 15, parent : 1 }
          childen -> Array[
            ... and so on ...
          ]
      ]
  ]

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

Для этого вымог бы добавить вспомогательную функцию, которая выполняет обход в глубину и выполняет функцию полезной нагрузки f для каждого узла:

TreeNode.prototype.walk = function(f, recursive) {
  for (var i=0, l=this.children.length; i<l; i++) {
    var child = this.children[i];
    f.apply(child, Array.prototype.slice.call(arguments, 2));
    if (recursive) child.walk.apply(child, arguments);
  }
}

и вызывает ее так:

tree.walk(function () { console.log(this.data) }, true);

, что приведет к:

{ index: 4, sort:  4, parent: 0}
{ index: 2, sort:  7, parent: 0}
{ index: 1, sort: 10, parent: 0}
{ index: 5, sort: 13, parent: 1}
{ index: 8, sort:  6, parent: 5}
{ index: 7, sort:  2, parent: 8}
{ index: 6, sort: 20, parent: 5}
{ index: 3, sort: 15, parent: 1}

Использование более сложных функций полезной нагрузки для других эффектов, таких как добавление строк таблицы в таблицу с jQuery или элементов в поле <select>.

Answer 2

Запрос Tomalak выше, что я публикую свою синглтон-версию их ответа.Вот оно:

/**
 * Represents sorted results in a tree structure.
 */
Tree = (function() {

    /**
     *
     * @type {Object} nodes Holds all the nodes in a flat format.
     * @type {Object} nodes.data The data that is held in this node.
     * @type {Object} nodes.parent Points to the parent object of this node.
     * @type {Array} nodes.children An array of the child nodes of this node.
     */
    var nodes = {};

    /**
     * @type {Object} root_node A Reference to the root node in nodes.
     */
    var root_node;

    /**
     * A sort function to sort the nodes by the data.sort value in each node.
     * @param {Number} a The first node to compare
     * @param {Number} b The second node to compare
     * @return {Boolean} Swap these nodes or not.
     */
    var comparer = function (a, b) {
        return a.data.sort < b.data.sort ? 0 : 1;
    };

    /**
     * Sorts all the nodes so that they are in the correct order according to each nodes data.sort value.
     * @param {Object} node A reference to the node in the nodes object.
     */
    var sortRecursive = function (node) {
        node.children.sort(comparer);
        var len = node.children.length;
        for (var i = 0 ; i < len ; i++) {
            sortRecursive(node.children[i]);
        }
    };

    /**
     * Create a new node with the passed in data.
     * @param {Object} data The data that is associated with this node.
     */
    var create_node = function(data){
        var node = {
            data : data,
            parent : null,
            children : []
        };
        return node;
    };

    return {

        /**
         * Create a new tree of data
         * @param {Array} data An array of data objects to transorm into a tree.
         * @param {Array} data[].index The id of this node
         * @param {Array} data[].parent The parent id of this node.
         * @param {Number} root_id Id of the root node.
         */
        create : function(data, root_id){

            // Clear any previous data
            nodes = {};

            var i;
            var len = data.length;

            // Create an empty root node
            nodes[root_id] = create_node({});
            root_node = nodes[root_id];

            // Make node objects for each data item
            for (i=0; i<len; i++) {
                if(typeof data[i].sort !== "undefined")
                    nodes[ data[i].index ] = create_node(data[i]);
            }

            // Link all TreeNode objects
            for (i=0; i<len; i++) {
                var node = nodes[data[i].index];
                node.parent = nodes[node.data.parent];
                node.parent.children.push(node);
            }
            sortRecursive(nodes[root_id]);
        },

        /**
         * Walk through the nodes in nested and then sorted order, calling the passed in callback for each node.
         * @param {Function} callback A callback function to call for each node.
         * @param {Boolean} recursive Should the walkback be recursive, or just fetch the top level results.
         * @param {Object|Undefined} node The node that is currently being walked.
         *                                Ommit this value and the root node will be used.
         */
        walk : function(callback, recursive, node) {
            if(typeof node == "undefined")
                node = root_node;

            for (var i = 0, len = node.children.length; i < len; i++) {
                var child = node.children[i];
                callback.apply(child, Array.prototype.slice.call(arguments, 2));
                if (recursive)
                    arguments.callee(callback, recursive, child);
            }
        }

    };
})();

Заполните дерево:

Tree.create(unsorted_data, parent_id);

Получить отсортированный массив с помощью:

var sorted = [];
Tree.walk(function(){
    sorted.push(this.data);
}, true);

Answer 3

После многих попыток я придумал это. Это работает, но не очень элегантно. Также можно сделать абстрагирование в свой собственный класс.

// Initial sort places items in the correct sort order.
data.sort(function(a, b) {
  return a.sort - b.sort;
});

vat top_parent_id = 1;          // The value of an items parent if it is a top level item.
var sorted = [];                // Empty array to copy sorted elements into.
var skipped = true;             // flag to indicate if any elements have been skipped.
var skip_count = 0;             // Counter to prevent infinite loops.
// Loop until no elements have been skipped. 
//This loops through each level of the tree until all nested branches have been added
while(skipped){
    skipped = false;
    skip_count++;
    if(skip_count === 50){      // Maximum tree depth.
        throw "Error in sorted data or tree depth too great.";
        break;
    }

    // Loop through the data in reverse order; this preserves the branch sort order.
    for (var i = data.length - 1; i >= 0; i--) {
        var item = data[i];

        // Skip if this element has already been processed.
        if(item.done)
            continue;

        // If this is this a top level item, then insert and continue.
        if(item.parent == top_parent_id){
            sorted.splice(0, 0, item);          // Insert at the start; last item is the top sort.
            item.done = true;
            continue;
        }

        // Loop the new array to try and find this items parent.
        var found = false;
        for (var j = 0; j < sorted.length; j++) {
            if(item.parent === sorted[j].index){
                sorted.splice(j + 1, 0, item);
                found = true;
                item.done = true;
                break;
            }
        }

        // If a place for an item has not been found then skip it for now so it can be tested again on the next iteration.
        if(!found){
            skipped = true;

        }
    }
}
data = sorted;

Answer 4

Редактировать: убери это, оно не работает.

Это лучшее, что мне удалось.Который должен разболтать это.Я еще не проверял это.Я оставлю лучший ответ открытым, чтобы посмотреть, сможет ли кто-нибудь улучшить его.

data.sort(function(a, b) {
  return a.parent - b.parent;
});

var changes = true;
while (changes){
    changes = false;
    for (var i = 1; i < data.length; i++) {
        if(data[i].parent === data[i-1].parent && data[i].sort < data[i-1].sort){
            var tmp = data[i-1];
            data[i-1] = data[i];
            data[i] = tmp;
            changes = true;   
        }
    }
}