Sort data into a tree

Question

I have the following data:

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 }, ]; 

How to efficiently sort this using the parent id and sort value so that I end up with:

 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 }, ]; 

This is a tree structure. Each element is immediately followed by any children, and all elements in the same branch are sorted by sort value.

The best I can think of is to sort by parents first and then do a second sort on each branch. This seems ineffective.

Edit: The sort order of the examples was incorrect. I fixed it.

Edit for clarification: each nested branch should appear immediately below the parent value, and not at the end of the branch.

Edit: Additional data fixes.

Answer 1

This is not your original approach, but you can create an actual tree from your data, for example:

 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 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(); } 

With this setting, you get neatly nested nodes with a simple call:

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

Once you have this tree object, you can do several things with it, including moving it recursively in the expected order.

To do this, you can add a helper function that performs a depth traverse and performs the payload function f for each node:

 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); } } 

and name it as follows:

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

which will produce:

  {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}

Use more complex payload functions for other effects, for example, add table rows to a table with jQuery or elements in a <select> field.

Answer 2

Tomalak's claim is higher that I am posting my version of the singleton answer. There he is:

 /** * 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); } } }; })(); 

Fill the tree with

 Tree.create(unsorted_data, parent_id); 

Get a sorted array using:

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

Answer 3

Edit: trick it, it doesn't work.

This is the best that I have succeeded. Which should bubble sort it. I have not tested it yet. I will leave the best answer open to find out if anyone can improve it.

 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; } } } 

Answer 4

After many attempts, I came up with this. It works, but not very elegant. You can also abstract in your class.

 // 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;