Convert flat array of objects into nested array of objects

Question

Original JSON data (flat table):

[
    {"id":"1","first_name":"Jason","last_name":"Martin","start_date":"1996-07-25","end_date":"2006-07-25","salary":"1234.56","city":"Toronto","description":"Programmer","department":"Finance","active":"1"},
    {"id":"2","first_name":"Alison","last_name":"Mathews","start_date":"1976-03-21","end_date":"1986-02-21","salary":"6661.78","city":"Vancouver","description":"Tester","department":"Finance","active":"1"},
    {"id":"3","first_name":"James","last_name":"Smith","start_date":"1978-12-12","end_date":"1990-03-15","salary":"6544.78","city":"Vancouver","description":"Tester","department":"QA","active":"1"},
    {"id":"4","first_name":"Celia","last_name":"Rice","start_date":"1982-10-24","end_date":"1999-04-21","salary":"2344.78","city":"Vancouver","description":"Manager","department":"HR","active":"1"},
    {"id":"5","first_name":"Robert","last_name":"Black","start_date":"1984-01-15","end_date":"1998-08-08","salary":"2334.78","city":"Vancouver","description":"Tester","department":"IT","active":"1"},
    {"id":"6","first_name":"Linda","last_name":"Green","start_date":"1987-07-30","end_date":"1996-01-04","salary":"4322.78","city":"New York","description":"Tester","department":"QA","active":"1"},
    {"id":"7","first_name":"David","last_name":"Larry","start_date":"1990-12-31","end_date":"1998-02-12","salary":"7897.78","city":"New York","description":"Manager","department":"HR","active":"1"}
]

I need to call the function like this:

nest(data,["city","description","department"])

The first parameter is the entire dataset, the second is an array of columns which define the nesting level.

Expected JSON output:

[
{key: "city", value: "Toronto", count: 1, children:
    [
        {key: "description", value: "Programmer", count: 1, children:
            [
                {key: "department", value: "Finance", count: 1}
            ]
        }
    ]
},
{key: "city", value: "Vancouver", count: 2, children: 
    [
        {key: "description", value: "Tester", count: 3, children:
            [
                {key: "department", value: "Finance", count: 1},
                {key: "department", value: "QA", count: 1},
                {key: "department", value: "IT", count: 1}
            ]
        },
        {key: "description", value: "Manager", count: 1}
    ]
},

{key: "city", value: "New York", count: 2, children:
    [
        {key: "description", value: "Tester", count: 1, children:
            [
                {key: "department", value: "QA", count: 1}
            ]
        },
        {key: "description", value: "Manager", count: 1, children:
            [
                {key: "department", value: "HR", count: 1}
            ]
        }
    ]
}

]

I've tried writing a few recursive functions but keep getting stuck when I have to dynamically search the tree to avoid duplication.

Answer 1

Thought this was a fun little question, so I did it... but, I do agree with the people who asked "what have you tried so far". Typically, you should talk about a specific problem.

// Groups a flat array into a tree. 
// "data" is the flat array.
// "keys" is an array of properties to group on.
function groupBy(data, keys) { 

    if (keys.length == 0) return data;

    // The current key to perform the grouping on:
    var key = keys[0];

    // Loop through the data and construct buckets for
    // all of the unique keys:
    var groups = {};
    for (var i = 0; i < data.length; i++)
    {
        var row = data[i];
        var groupValue = row[key];

        if (groups[groupValue] == undefined)
        {
            groups[groupValue] = new Array();
        }

        groups[groupValue].push(row);
    }

    // Remove the first element from the groups array:
    keys.reverse();
    keys.pop()
    keys.reverse();

    // If there are no more keys left, we're done:
    if (keys.length == 0) return groups;

    // Otherwise, handle further groupings:
    for (var group in groups)
    {
        groups[group] = groupBy(groups[group], keys.slice());
    }

    return groups;
}

Call the method like this:

var groupedData = groupBy(data, ["city","description","department"]);

The output from this method for your data looks like this:

{
    "Toronto": {
        "Programmer": {
            "Finance": [
                {
                    "id": "1", "first_name": "Jason", "last_name": "Martin", "start_date": "1996-07-25", "end_date": "2006-07-25", "salary": "1234.56", "city": "Toronto", "description": "Programmer", "department": "Finance", "active": "1"
                }
            ]
        }
    },
    "Vancouver": {
        "Tester": {
            "Finance": [
                {
                    "id": "2", "first_name": "Alison", "last_name": "Mathews", "start_date": "1976-03-21", "end_date": "1986-02-21", "salary": "6661.78", "city": "Vancouver", "description": "Tester", "department": "Finance", "active": "1"
                }
            ],
            "QA": [
                {
                    "id": "3", "first_name": "James", "last_name": "Smith", "start_date": "1978-12-12", "end_date": "1990-03-15", "salary": "6544.78", "city": "Vancouver", "description": "Tester", "department": "QA", "active": "1"
                }
            ],
            "IT": [
                {
                    "id": "5", "first_name": "Robert",  "last_name": "Black", "start_date": "1984-01-15", "end_date": "1998-08-08", "salary": "2334.78", "city": "Vancouver", "description": "Tester", "department": "IT", "active": "1"
                }
            ]
        },
        "Manager": {
            "HR": [
                {
                    "id": "4", "first_name": "Celia", "last_name": "Rice", "start_date": "1982-10-24", "end_date": "1999-04-21", "salary": "2344.78", "city": "Vancouver", "description": "Manager", "department": "HR", "active": "1"
                }
            ]
        }
    },
    "New York": {
        "Tester": {
            "QA": [
                {
                    "id": "6", "first_name": "Linda", "last_name": "Green", "start_date": "1987-07-30", "end_date": "1996-01-04", "salary": "4322.78", "city": "New York", "description": "Tester", "department": "QA", "active": "1"
                }
            ]
        },
        "Manager": {
            "HR": [
                {
                    "id": "7", "first_name": "David", "last_name": "Larry", "start_date": "1990-12-31", "end_date": "1998-02-12", "salary": "7897.78", "city": "New York", "description": "Manager", "department": "HR", "active": "1"
                }
            ]
        }
    }
}

Because the groups are all javascript objects, you don't need that "count" member. You can simply use the .length property of the array(s).

Loop through the groups using javascript's for (var group in groups) syntax.

Answer 2

You might take a look at the nest() operator from D3.js: https://github.com/mbostock/d3/blob/48ad44fdeef32b518c6271bb99a9aed376c1a1d6/src/arrays/nest.js This is part of D3, a larger library, but looking quickly at the code I just linked to, I don't think this has any dependencies, so you should be able to lift the code here for use in your own project. Usage is described here in the docs - you chain .key() methods to define the keys for each layer of the nested structure. In your case, this might look like:

data = d3.nest()
    .key(function(d) { return d.city })
    .key(function(d) { return d.description })
    .entries(data);

The structure this spits out is a little different from what you have, but it's functionally quite similar:

[
  {
    "key": "Toronto", 
    "values": [
      {
        "key": "Programmer", 
        "values": [
          {
            "active": "1", 
            "city": "Toronto", 
            "department": "Finance", 
            "description": "Programmer", 
            "end_date": "2006-07-25", 
            "first_name": "Jason", 
            "id": "1", 
            "last_name": "Martin", 
            "salary": "1234.56", 
            "start_date": "1996-07-25"
          },
          // etc ...
        ]
      }
    ]
  },
  // etc ...
]