Convert an array of objects into a nested array of objects based on string property?

Question

I am stuck on a problem trying to convert a flat array of objects into a nested array of objects based the name property.

What is the best way to convert the input array to resemble the structure of the desiredOutput array?

var input = [
    { 
        name: 'foo', 
        url: '/somewhere1',
        templateUrl: 'foo.tpl.html',
        title: 'title A', 
        subtitle: 'description A' 
    },
    { 
        name: 'foo.bar', 
        url: '/somewhere2', 
        templateUrl: 'anotherpage.tpl.html', 
        title: 'title B', 
        subtitle: 'description B' 
    },
    { 
        name: 'buzz.fizz',
        url: '/another/place',
        templateUrl: 'hello.tpl.html',  
        title: 'title C',  
        subtitle: 'description C' 
    },
    { 
        name: 'foo.hello.world', 
        url: '/',
        templateUrl: 'world.tpl.html',
        title: 'title D',   
        subtitle: 'description D' 
    }
]

var desiredOutput = [
    {
        name: 'foo',
        url: '/somewhere1',
        templateUrl: 'foo.tpl.html',
        data: {
            title: 'title A',
            subtitle: 'description A'
        },
        children: [
            {
                name: 'bar',
                url: '/somewhere2', 
                templateUrl: 'anotherpage.tpl.html',
                data: {
                    title: 'title B', 
                    subtitle: 'description B'
                }
            },
            {
                name: 'hello',
                data: {},
                children: [
                    {
                        name: 'world',
                        url: '/',
                        templateUrl: 'world.tpl.html',
                        data: {
                            title: 'title D',   
                            subtitle: 'description D'
                        }
                    }
                ]
            }
        ]
    },
    {
        name: 'buzz',
        data: {},
        children: [
            {
                name: 'fizz',
                url: '/',
                templateUrl: 'world.tpl.html',
                data: {
                    title: 'title C',   
                    subtitle: 'description C'
                }
            }
        ]
    }
]

Note the order of the objects in the input array is not guaranteed. This code will be running in a Node.js environment and I am open to using libraries such as lodash to achieve the desired output.

Any help is greatly appreciated.

Answer 1

Using Lodash (because why on earth would you want to manipulate complex data without a utility library). Here's the fiddle.

function formatRoute(route) {
    return _.merge(_.pick(route, ['url', 'templateUrl']), {
        name: route.name.split('.'),
        data: _.pick(route, ['title', 'subtitle']),
        children: []
    });
}

function getNameLength(route) {
    return route.name.length;
}

function buildTree(tree, route) {
    var path = _.slice(route.name, 0, -1);

    insertAtPath(tree, path, _.merge({}, route, {
        name: _.last(route.name)
    }));

    return tree;
}

function insertAtPath(children, path, route) {
    var head = _.first(path);

    var match = _.find(children, function (child) {
        return child.name === head;
    });

    if (path.length === 0) {
        children.push(route);
    }
    else {
        if (!match) {
            match = {
                name: head,
                data: {},
                children: []
            };
            children.push(match);
        }

        insertAtPath(match.children, _.rest(path), route);
    }
}


// Map the routes into their correct formats.
var routes = _.sortBy(_.map(input, formatRoute), getNameLength);

// Now we can reduce this well formatted array into the desired format.
var out = _.reduce(routes, buildTree, []);

It works by reshaping the initial input so as to split the names into arrays and add the data / children properties. Then it reduces the data over buildTree which uses a mutating function ( :( ) to insert the current item in the reduce at the given path.

The strange if (!match) part makes sure that missing segments are added in if they're not explicitly specified in the initial data set with a URL etc.

The last two lines that actually do the work should probably be in a little function, and it could do with some JSDoc. It's just a shame I didn't get it completely recursive, I'm relying on array mutation to insert the route object deep within the tree.

Should be simple enough to follow though.

Answer 2

Here's my Lodash-based attempt.

First, I discovered that _.set can understand deeply-nested object notation, so I use it to build a tree encoding parent-child relationships:

var tree = {};
input.forEach(o => _.set(tree, o.name, o));

This produces:

{
    "foo": {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "title": "title A",
        "subtitle": "description A",
        "bar": {
            "name": "foo.bar",
            "url": "/somewhere2",
            "templateUrl": "anotherpage.tpl.html",
            "title": "title B",
            "subtitle": "description B"
        },
        "hello": {
            "world": {
                "name": "foo.hello.world",
                "url": "/",
                "templateUrl": "world.tpl.html",
                "title": "title D",
                "subtitle": "description D"
            }
        }
    },
    "buzz": {
        "fizz": {
            "name": "buzz.fizz",
            "url": "/another/place",
            "templateUrl": "hello.tpl.html",
            "title": "title C",
            "subtitle": "description C"
        }
    }
}

This is actually painfully so-close-yet-so-far from the desired output. But the children's names appear as properties, alongside other properties like title.

Then came a laborious process of writing a recursive function that took this intermediate tree and reformatted it in the manner you wished:

1. It first needs to find the children properties, and move them to a children property array.
2. Then it has to deal with the fact that for long chains, intermediate nodes like hello in foo.hello.world don't have any data, so it has to insert data: {} and name properties.
3. Finally, it mops up what's left: putting the title & subtitle in a data property and cleaning up any names that are still fully-qualified.

The code:

var buildChildrenRecursively = function(tree) {
  var children = _.keys(tree).filter(k => _.isObject(tree[k]));
  if (children.length > 0) {

    // Step 1 of reformatting: move children to children
    var newtree = _.omit(tree, children);
    newtree.children = children.map(k => buildChildrenRecursively(tree[k]));

    // Step 2 of reformatting: deal with long chains with missing intermediates
    children.forEach((k, i) => {
      if (_.keys(newtree.children[i]).length === 1) {
        newtree.children[i].data = {};
        newtree.children[i].name = k;
      }
    });

    // Step 3 of reformatting: move title/subtitle to data; keep last field in name
    newtree.children = newtree.children.map(function(obj) {
      if ('data' in obj) {
        return obj;
      }
      var newobj = _.omit(obj, 'title,subtitle'.split(','));
      newobj.data = _.pick(obj, 'title,subtitle'.split(','));
      newobj.name = _.last(obj.name.split('.'));
      return newobj;
    });

    return (newtree);
  }
  return tree;
};

var result = buildChildrenRecursively(tree).children;

The output:

[
    {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "children": [
            {
                "name": "bar",
                "url": "/somewhere2",
                "templateUrl": "anotherpage.tpl.html",
                "data": {
                    "title": "title B",
                    "subtitle": "description B"
                }
            },
            {
                "children": [
                    {
                        "name": "world",
                        "url": "/",
                        "templateUrl": "world.tpl.html",
                        "data": {
                            "title": "title D",
                            "subtitle": "description D"
                        }
                    }
                ],
                "data": {},
                "name": "hello"
            }
        ],
        "data": {
            "title": "title A",
            "subtitle": "description A"
        }
    },
    {
        "children": [
            {
                "name": "fizz",
                "url": "/another/place",
                "templateUrl": "hello.tpl.html",
                "data": {
                    "title": "title C",
                    "subtitle": "description C"
                }
            }
        ],
        "data": {},
        "name": "buzz"
    }
]

To the victor go the spoils.

Answer 3

This solution does not use recursion, it uses a reference pointer to the previous item in the object graph.

Note this solution does utilise lodash. JSFiddle example here http://jsfiddle.net/xpb75dsn/1/

var input = [
    {
        name: 'foo',
        url: '/somewhere1',
        templateUrl: 'foo.tpl.html',
        title: 'title A',
        subtitle: 'description A'
    },
    {
        name: 'foo.bar',
        url: '/somewhere2',
        templateUrl: 'anotherpage.tpl.html',
        title: 'title B',
        subtitle: 'description B'
    },
    {
        name: 'buzz.fizz',
        url: '/another/place',
        templateUrl: 'hello.tpl.html',
        title: 'title C',
        subtitle: 'description C'
    },
    {
        name: 'foo.hello.world',
        url: '/',
        templateUrl: 'world.tpl.html',
        title: 'title D',
        subtitle: 'description D'
    }
];

var nameList = _.sortBy(_.pluck(input, 'name'));
var structure = {};

var mapNav = function(name, navItem) {
    return {
        name : name,
        url : navItem.url,
        templateUrl : navItem.templateUrl,
        data : { title : navItem.title, subtitle : navItem.subtitle },
        children : []
    };
};

_.map(nameList, function(fullPath) {
    var path = fullPath.split('.');
    var parentItem = {};
    _.forEach(path, function(subName, index) {
        var navItem = _.find(input, { name : fullPath });
        var item = mapNav(subName, navItem);
        if (index == 0) {
            structure[subName] = item;
        } else {
            parentItem.children.push(item);
        }
        parentItem = item;
    });
});


var finalStructure = Object.keys(structure).map(function(key) {
    return structure[key];
});

console.log(finalStructure);  

Answer 4

Here's a totally recursion-free method using lodash. It occurred to me when I was thinking about how nice _.set and _.get were, and I realized I could replace object "paths" with sequences of children.

First, build an object/hash table with keys equal to the name properties of input array:

var names = _.object(_.pluck(input, 'name'));
// { foo: undefined, foo.bar: undefined, buzz.fizz: undefined, foo.hello.world: undefined }

(Don't try to JSON.stringify this object! Since its values are all undefined, it evaluates to {}…)

Next, apply two transforms on each of the elements: (1) cleanup title and subtitle into a sub-property data, and (2) and this is a bit tricky, find all intermediate paths like buzz and foo.hello that aren't represented in input but whose children are. Flatten this array-of-arrays and sort them by the number of . in the name field.

var partial = _.flatten(
    input.map(o =>
              {
                var newobj = _.omit(o, 'title,subtitle'.split(','));
                newobj.data = _.pick(o, 'title,subtitle'.split(','));
                return newobj;
              })
        .map(o => {
          var parents = o.name.split('.').slice(0, -1);
          var missing =
              parents.map((val, idx) => parents.slice(0, idx + 1).join('.'))
                  .filter(name => !(name in names))
                  .map(name => {
                    return {
                      name,
                      data : {},
                    }
                  });

          return missing.concat(o);
        }));
partial = _.sortBy(partial, o => o.name.split('.').length);

This code may seem intimidating but seeing what it outputs should convince you it's pretty straightforward: it's just a flat array containing the original input plus all intermediate paths that aren't in input, sorted by the number of dots in name, and a new data field for each.

[
    {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "data": {
            "title": "title A",
            "subtitle": "description A"
        }
    },
    {
        "name": "buzz",
        "data": {}
    },
    {
        "name": "foo.bar",
        "url": "/somewhere2",
        "templateUrl": "anotherpage.tpl.html",
        "data": {
            "title": "title B",
            "subtitle": "description B"
        }
    },
    {
        "name": "buzz.fizz",
        "url": "/another/place",
        "templateUrl": "hello.tpl.html",
        "data": {
            "title": "title C",
            "subtitle": "description C"
        }
    },
    {
        "name": "foo.hello",
        "data": {}
    },
    {
        "name": "foo.hello.world",
        "url": "/",
        "templateUrl": "world.tpl.html",
        "data": {
            "title": "title D",
            "subtitle": "description D"
        }
    }
]

We're almost home free. The last remaining bit of magic requires storing some global state. We're going to loop over this flat partial array, replacing the name field with a path that _.get and _.set can consume containing children and numerical indexes:

• foo gets mapped to children.0
• buzz to children.1,
• foo.bar to children.0.children.0, etc.

As we iteratively (not recursively!) build this sequence of paths, we use _.set to inject each element of partial above into its appropriate place.

Code:

var name2path = {'empty' : ''};
var out = {};
partial.forEach(obj => {
  var split = obj.name.split('.');
  var par = name2path[split.slice(0, -1).join('.') || "empty"];
  var path = par + 'children.' + (_.get(out, par + 'children') || []).length;
  name2path[obj.name] = path + '.';
  _.set(out, path, obj);
});
out = out.children;

This object/hash name2path converts names to _.settable paths: it's initialized with a single key, empty, and the iteration adds to it. It's helpful to see what this name2path is after this code is run:

{
    "empty": "",
    "foo": "children.0.",
    "buzz": "children.1.",
    "foo.bar": "children.0.children.0.",
    "buzz.fizz": "children.1.children.0.",
    "foo.hello": "children.0.children.1.",
    "foo.hello.world": "children.0.children.1.children.0."
}

Note how the iteration increments indexes to store more than one entry in a children property array.

The final resulting out:

[
    {
        "name": "foo",
        "url": "/somewhere1",
        "templateUrl": "foo.tpl.html",
        "data": {
            "title": "title A",
            "subtitle": "description A"
        },
        "children": [
            {
                "name": "foo.bar",
                "url": "/somewhere2",
                "templateUrl": "anotherpage.tpl.html",
                "data": {
                    "title": "title B",
                    "subtitle": "description B"
                }
            },
            {
                "name": "foo.hello",
                "data": {},
                "children": [
                    {
                        "name": "foo.hello.world",
                        "url": "/",
                        "templateUrl": "world.tpl.html",
                        "data": {
                            "title": "title D",
                            "subtitle": "description D"
                        }
                    }
                ]
            }
        ]
    },
    {
        "name": "buzz",
        "data": {},
        "children": [
            {
                "name": "buzz.fizz",
                "url": "/another/place",
                "templateUrl": "hello.tpl.html",
                "data": {
                    "title": "title C",
                    "subtitle": "description C"
                }
            }
        ]
    }
]

The embedded snippet contains just code without intermediate JSON to distract you.

Is this better than my previous submission? I think so: there's a lot less bookkeeping here, less opaque "busy code", more high-level constructs. The lack of recursion I think helps. I think the final forEach might be replaced with a reduce, but I didn't try that because the rest of the algorithm is so vector-based and iterative, I didn't want to diverge from that.

And sorry to have left everything in ES6, I love it so much :)

var input = [{
  name: 'foo',
  url: '/somewhere1',
  templateUrl: 'foo.tpl.html',
  title: 'title A',
  subtitle: 'description A'
}, {
  name: 'foo.bar',
  url: '/somewhere2',
  templateUrl: 'anotherpage.tpl.html',
  title: 'title B',
  subtitle: 'description B'
}, {
  name: 'buzz.fizz',
  url: '/another/place',
  templateUrl: 'hello.tpl.html',
  title: 'title C',
  subtitle: 'description C'
}, {
  name: 'foo.hello.world',
  url: '/',
  templateUrl: 'world.tpl.html',
  title: 'title D',
  subtitle: 'description D'
}];

var names = _.object(_.pluck(input, 'name'));

var partial = _.flatten(
  input.map(o => {
    var newobj = _.omit(o, 'title,subtitle'.split(','));
    newobj.data = _.pick(o, 'title,subtitle'.split(','));
    return newobj;
  })
  .map(o => {
    var parents = o.name.split('.').slice(0, -1);
    var missing =
      parents.map((val, idx) => parents.slice(0, idx + 1).join('.'))
      .filter(name => !(name in names))
      .map(name => {
        return {
          name,
          data: {},
        }
      });

    return missing.concat(o);
  }));
partial = _.sortBy(partial, o => o.name.split('.').length);

var name2path = {
  'empty': ''
};
var out = {};

partial.forEach(obj => {
  var split = obj.name.split('.');
  var par = name2path[split.slice(0, -1).join('.') || "empty"];
  var path = par + 'children.' + (_.get(out, par + 'children') || []).length;
  name2path[obj.name] = path + '.';
  _.set(out, path, obj);
});
out = out.children;

Answer 5

This solution uses only native JS methods. It can be optimized for sure, but I left it as is to make it easier to follow along (or so I hope it is). I also took care to not modify the original input as JS passes objects by reference.

var input = [{
  name: 'foo',
  url: '/somewhere1',
  templateUrl: 'foo.tpl.html',
  title: 'title A',
  subtitle: 'description A'
}, {
  name: 'foo.bar',
  url: '/somewhere2',
  templateUrl: 'anotherpage.tpl.html',
  title: 'title B',
  subtitle: 'description B'
}, {
  name: 'buzz.fizz',
  url: '/another/place',
  templateUrl: 'hello.tpl.html',
  title: 'title C',
  subtitle: 'description C'
}, {
  name: 'foo.hello.world',
  url: '/',
  templateUrl: 'world.tpl.html',
  title: 'title D',
  subtitle: 'description D'
}];

// Iterate over input array elements
var desiredOutput = input.reduce(function createOuput(arr, obj) {
  var names = obj.name.split('.');
  // Copy input element object as not to modify original input
  var newObj = Object.keys(obj).filter(function skipName(key) {
    return key !== 'name';
  }).reduce(function copyObject(tempObj, key) {
    if (key.match(/url$/i)) {
      tempObj[key] = obj[key];
    }
    else {
      tempObj.data[key] = obj[key];
    }

    return tempObj;
  }, {name: names[names.length - 1], data: {}});

  // Build new output array with possible recursion
  buildArray(arr, names, newObj);

  return arr;
}, []);

document.write('<pre>' + JSON.stringify(desiredOutput, null, 4) + '</pre>');

// Helper function to search array element objects by name property
function findIndexByName(arr, name) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (arr[i].name === name) {
      return i;
    }
  }

  return -1;
}

// Recursive function that builds output array
function buildArray(arr, paths, obj) {
  var path = paths.shift();
  var index = findIndexByName(arr, path);

  if (paths.length) {
    if (index === -1) {
      arr.push({
        name: path,
        children: []
      });

      index = arr.length - 1;
    }

    if (!Array.isArray(arr[index].children)) {
      arr[index].children = [];
    }

    buildArray(arr[index].children, paths, obj);
  } else {
    arr.push(obj);
  }

  return arr;
}