CODEWITHSUNDEEP
javascriptarrays
Dreamer XD
Dreamer XD

Reputation: 204

Dynamically convert array to tree-like structure

Can someone show me the most efficient way to convert an array to a tree-like structure?

var array= [
        {id: "1",     name: "header1"},
        {id: "2",     name: "header2"},
        {id: "1.1",   name: "subheader1.1"},
        {id: "1.2",   name: "subheader1.2"},
        {id: "2.1",   name: "subheader2.1"},
        {id: "2.2",   name: "subheader2.2"},
        {id: "1.1.1", name: "subheader1detail1"},
        {id: "2.1.1", name: "subheader2detail2"}
];

Result array must be like this:

var array = [{
    id: "1",
    name: "header1",
    items: [{
        id: "1.1",
        name: "subheader1.1",
        items: [{
            id: "1.1.1",
            name: "subheader1detail1",
        }]
    }, {
        id: "1.2",
        name: "subheader1.2"
    }]
}, {
    id: "2",
    name: "header2",
    items: [{
        id: "2.1",
        name: "subheader2.1",
        items: [{
            id: "2.1.1",
            name: "subheader2detail2",
        }]
    }, {
        id: "2.2",
        name: "subheader2.2"
    }]
}]

Thanks in advance

Upvotes: 5

Views: 1170

Answers (3)

kukkuz
kukkuz

Reputation: 42360

Was fiddling with the problem here - sharing across a solution using Array.prototype.reduce and a local hash table - also sorting the result. Cheers!

var array=[{id:"2",name:"header2"},{id:"1",name:"header1"},{id:"1.1",name:"subheader1.1"},{id:"1.2",name:"subheader1.2"},{id:"2.2",name:"subheader2.2"},{id:"2.1",name:"subheader2.1"},{id:"1.1.1",name:"subheader1detail1"},{id:"2.1.1",name:"subheader2detail2"}];

var result = array.sort(function(a,b) {
  return a.id - b.id;
}).reduce(function(hash) {
  return function(prev, curr) {
    var keys = curr.id.split('.');
    hash[curr.id] = hash[curr.id] || {};
    hash[curr.id] = {id: curr.id,name: curr.name};
    if (keys && keys.length > 1) {
      keys.pop();
      var key = keys.join('.');
      hash[key].items = hash[key].items || [];
      hash[key].items.push(hash[curr.id]);
    } else {
      prev.push(hash[curr.id]);
    }
    return prev;
  };
}(Object.create(null)), []);

console.log(result);
.as-console-wrapper {top: 0;max-height: 100%!important;}

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386786

You could use a tree and build the nested array upon. This proposal needs a sorted list.

Basically it looks for the parent of a node and if a node has no parent, then a root node is found and inserted into the result array. If a parent is found, then the actual node is inserted into the items property of the parent.

var array = [{ id: "1", name: "header1" }, { id: "2", name: "header2" }, { id: "1.1", name: "subheader1.1" }, { id: "1.2", name: "subheader1.2" }, { id: "2.1", name: "subheader2.1" }, { id: "2.2", name: "subheader2.2" }, { id: "1.1.1", name: "subheader1detail1" }, { id: "2.1.1", name: "subheader2detail2" }],
    result = [];

array.forEach(function (a) {
    var parent = a.id.split('.').slice(0, -1).join('.');

    this[a.id] = { id: a.id, name: a.name };
    if (parent) {
        this[parent] = this[parent] || {};
        this[parent].items = this[parent].items || [];
        this[parent].items.push(this[a.id]);
    } else {
        result.push(this[a.id]);
    }
}, {});

console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Upvotes: 5

Rajesh
Rajesh

Reputation: 24955

You can try something like this:

I have added comments to explain the logic

var array= [
  {id: "1",     name: "header1"},
  {id: "2",     name: "header2"},
  {id: "1.1",   name: "subheader1.1"},
  {id: "1.2",   name: "subheader1.2"},
  {id: "2.1",   name: "subheader2.1"},
  {id: "2.2",   name: "subheader2.2"},
  {id: "1.1.1", name: "subheader1detail1"},
  {id: "2.1.1", name: "subheader2detail2"},
];

var result = {};

// Sort in case values are not in order. 
// This is to ensure parent is rendered before child
array.sort(function(a, b) {
  return a.id > b.id ? 1 : a.id - b.id ? -1 : 0
})
// Loop over sorted array to parse
.forEach(function(el) {
  // Check if element does not exists to prevent duplicate
  if (!result[el.id]) {
    // if parent, push it
    if (el.id.indexOf('.') === -1)
      result[el.id] = el;
    // If child, compute depth and search object to push to
    else {
      var ids = el.id.split('.');
      var _id = '';
      // temp variable to hold position to push
      var r = result[ids[0]];
      for (var i = 1; i < ids.length; i++) {
        // Compute the object id
        _id = (_id ? _id + '.' : _id) + ids[i - 1];
        // initialize items
        r.items = r.items || [];
        // search in items to get object if exist
        var o = r.items.find(x => x.id === _id);
        // if object exists, assign it to temp variable
        // If not, push to parent
        if (o) r = o;
      }
      if (r) {
        r.items = r.items || [];
        r.items.push(el);
      }
    }
  }
})

console.log(result)

Note: I have changed structure to hold an object instead of an array

Upvotes: 0

Related Questions