Generating nested list from flat list with parent/child lists in JavaScript

I'm building a web-app that needs to process nested geographical data to both display in a treeview, but also be searchable. The raw data looks something like this:

id:1, name:UK
id:2: name: South-East, parentId: 1
id:3: name: South-West, parentId:1
id:4: name: Berkshire, parentId: 2
id:5: name: Reading, parentId: 4

and I want it to look somethi开发者_JAVA百科ng like this:

id:1: name UK, children[ 
 {id: 2, name: South-East, children:[
    {id:4: name: Berkshire, children: [
       {id:5: name: Reading}
     ]
  }, 
   {id:3: name: South-West}
]

so that each geographical location has a "children" array property, which contains all the sub-areas, each of which has another "children" array property, and so on. It would probably make sense to have a "parent" property as well, so I could navigate from any child item up to its parent.

I also need to be able to search the list - searching each branch of the tree may take some time, so perhaps I need to also keep the list in flat format.

I know how I could do this in JavaScript (possibly using jLinq for filtering, grouping and sorting), but I don't know how fast it would be. Has anyone already had a go at this in JavaScript or know of any general algorithms/patterns that solve this?

It's actually not that difficult to make the flat array into a tree and do it pretty quickly, I think the slowest bit will be getting the definition of the data structure onto the page (hence why you're lazy loading was successful!). This can be helped though by making the data structure definition smaller.

In Javascript I did it like this:

    //Make the data definition as small as possible..
    //each entry is [ name, parent_pos_in_array]..
    //note: requires that a parent node appears before a child node..
    var data = [
        ["UK", -1], //root..
        ["South-East", 0],
        ["South-West", 0],
        ["Berkshire", 1],
        ["Reading", 3]
        //...etc...
    ];

    //Turns given flat arr into a tree and returns root..
    //(Assumes that no child is declared before parent)
    function makeTree(arr){
        //Array with all the children elements set correctly..
        var treeArr = new Array(arr.length);

        for(var i = 0, len = arr.length; i < len; i++){
            var arrI = arr[i];
            var newNode = treeArr[i] = {
                name: arrI[0],
                children: []
            };
            var parentI = arrI[1];
            if(parentI > -1){ //i.e. not the root..
                treeArr[parentI].children.push(newNode);
            }
        }
        return treeArr[0]; //return the root..
    }

    var root = makeTree(data);

To test the speed on a larger list you can run:

    var data = [['root', -1]];
    for(var i = 1; i < 100000; i++){
        var parentI = Math.floor(Math.random()*(i-1));
        data.push(['a_name', parentI]);   
    }
    var start = new Date().getTime();
    var tree = makeTree(data);
    var end = new Date().getTime();

    console.log('Took: ' + (end-start) + 'ms.');

With 100000 elements in the array it takes < 200ms on my old desktop. Not sure what kind of performance is acceptable though!

If you have a simple id & parent-id objects array with no other clue on the level, it's a tough task to generate the nested form. I would assume recursive approaches won't be practical in long lists. The best method that i could come up with so far is sorting that array in such a way that all children come after their parents. Parents and children and even the root objects can be mixed but a child must come after it's parent. Assuming that the object structure is like var data = [{id: KL442, pid: HN296}, {id: ST113, pid: HN296}, {id: HN296, pid: "root"},...] Yet sorting is the first phase of the job. While sorting we can generate a LUT (look up table) to access the parents almost at no cost. At the exit of the outer loop just one single instruction lut[a[i].id]=i; is sufficient for this. This makes the job enormously fast at the nesting stage. This is the sorting and LUT preparation phase.

function sort(a){
  var len = a.length,
      fix = -1;
  for (var i = 0; i < len; i++ ){
      while(!!~(fix = a.findIndex(e => a[i].pid == e.id)) && fix > i) [a[i],a[fix]] = [a[fix],a[i]];
      lut[a[i].id]=i;
  }
  return a;
}

Once you have it sorted than a reverse iteration is the only thing you have to do to get your nested structure. So that you now have your data array sorted and LUT prepared, then this is the code for nesting.

for (var i = sorted.length-1; i>=0; i--)
    sorted[i].pid != "root" && (!! sorted[lut[sorted[i].pid]].children
                                && sorted[lut[sorted[i].pid]].children.push(sorted.splice(i,1)[0])
                                || (sorted[lut[sorted[i].pid]].children = [sorted.splice(i,1)[0]]));

For a working sample you can check a previous answer of mine.

With Lodash:

var index = _.mapKeys(data,'id');
var obj = {};
_.each(index,function(v){
  if(!v.parentId){
    obj[v.id]=v;
  }else{
    if(!index[v.parentId].children){
      index[v.parentId].children=[];
    }
    index[v.parentId].children.push(v);
  }
});

Demo is here