PHP Nested JSON from flat JSON

Question

I have a database query that provides me the output of some employee data. I want to use this data to pass to a plugin that generates an org chart. There are a few fields in the JSON object that I am pulling down which are:

FirstName
LastName
EmployeeID
ManagerEmployeeID
Manager Name

The data is returned as flat JSON object with no nesting or corellation between employees and their managers in the hierarchy.

Since I am unable to change the output of the source data (the database query), I am trying to figure out a way to nest the data so that the JSON output becomes a nested output.

My goal is to take this array and nest it based on the ManagerID and EmployeeID so I can make a tree hierarchy.

Example Data:

•   Tom Jones
   o    Alice Wong
   o    Tommy J.
•   Billy Bob
   o    Rik A.
     ♣  Bob Small
     ♣  Small Jones
   o    Eric C.

My flat data example:

    {
        "FirstName": "Tom"
        "LastName": "Jones"
        "EmployeeID": "123"
        "ManagerEmployeeID": ""
        "Manager Name": ""
    },
    {
        "FirstName": "Alice"
        "LastName": "Wong"
        "EmployeeID": "456"
        "ManagerEmployeeID": "123"
        "Manager Name": "Tom Jones"
    },
    {
        "FirstName": "Tommy"
        "LastName": "J."
        "EmployeeID": "654"
        "ManagerEmployeeID": "123"
        "Manager Name": "Tom Jones"
    },
    {
        "FirstName": "Billy"
        "LastName": "Bob"
        "EmployeeID": "777"
        "ManagerEmployeeID": ""
        "Manager Name": ""
    },
    {
        "FirstName": "Rik"
        "LastName": "A."
        "EmployeeID": "622"
        "ManagerEmployeeID": "777"
        "Manager Name": "Billy Bob"
    },
    {
        "FirstName": "Bob"
        "LastName": "Small"
        "EmployeeID": "111"
        "ManagerEmployeeID": "622"
        "Manager Name": "Rik A."
    },
    {
        "FirstName": "Small"
        "LastName": "Jones"
        "EmployeeID": "098"
        "ManagerEmployeeID": "622"
        "Manager Name": "Rik A"
    },
    {
        "FirstName": "Eric"
        "LastName": "C."
        "EmployeeID": "222"
        "ManagerEmployeeID": "777"
        "Manager Name": "Billy Bob"
    }

Example Desired Output:

[
  {
    "FirstName": "Tom",
    "LastName": "Jones",
    "EmployeeID": "123",
    "ManagerEmployeeID": "",
    "Manager Name": "",
    "employees": [
      {
        "FirstName": "Alice",
        "LastName": "Wong",
        "EmployeeID": "456",
        "ManagerEmployeeID": "123",
        "Manager Name": "Tom Jones"
      },
      {
        "FirstName": "Tommy",
        "LastName": "J.",
        "EmployeeID": "654",
        "ManagerEmployeeID": "123",
        "Manager Name": "Tom Jones"
      }
    ]
  },
  {
    "FirstName": "Billy",
    "LastName": "Bob",
    "EmployeeID": "777",
    "ManagerEmployeeID": "",
    "Manager Name": "",
    "employees": [
      {
        "FirstName": "Rik",
        "LastName": "A.",
        "EmployeeID": "622",
        "ManagerEmployeeID": "777",
        "Manager Name": "Billy Bob",
        "employees": [
          {
            "FirstName": "Bob",
            "LastName": "Small",
            "EmployeeID": "111",
            "ManagerEmployeeID": "622",
            "Manager Name": "Rik A."
          },
          {
            "FirstName": "Small",
            "LastName": "Jones",
            "EmployeeID": "098",
            "ManagerEmployeeID": "622",
            "Manager Name": "Rik A"
          }
        ]
      },
      {
        "FirstName": "Eric",
        "LastName": "C.",
        "EmployeeID": "222",
        "ManagerEmployeeID": "777",
        "Manager Name": "Billy Bob"
      }
    ]
  }
]

Esentially I am trying to create a nested JSON output from a flat object using the EmployeeID and ManagerEmployeeID as the links between the two.

What is the best way to solve something like this with PHP?

Bounty Update:

Here is a test case of the issue: https://eval.in/private/4b0635c6e7b059

You will see that the very last record with the name of Issue Here does not show up in the result set. This has a managerID that matches the root node and should be within "Tom Jones's" employees array.

Answer 1

I have the following utility class to do exactly what you need.

class NestingUtil
{
    /**
     * Nesting an array of records using a parent and id property to match and create a valid Tree
     *
     * Convert this:
     * [
     *   'id' => 1,
     *   'parent'=> null
     * ],
     * [
     *   'id' => 2,
     *   'parent'=> 1
     * ]
     *
     * Into this:
     * [
     *   'id' => 1,
     *   'parent'=> null
     *   'children' => [
     *     'id' => 2
     *     'parent' => 1,
     *     'children' => []
     *    ]
     * ]
     *
     * @param array  $records      array of records to apply the nesting
     * @param string $recordPropId property to read the current record_id, e.g. 'id'
     * @param string $parentPropId property to read the related parent_id, e.g. 'parent_id'
     * @param string $childWrapper name of the property to place children, e.g. 'children'
     * @param string $parentId     optional filter to filter by parent
     *
     * @return array
     */
    public static function nest(&$records, $recordPropId = 'id', $parentPropId = 'parent_id', $childWrapper = 'children', $parentId = null)
    {
        $nestedRecords = [];
        foreach ($records as $index => $children) {
            if (isset($children[$parentPropId]) && $children[$parentPropId] == $parentId) {
                unset($records[$index]);
                $children[$childWrapper] = self::nest($records, $recordPropId, $parentPropId, $childWrapper, $children[$recordPropId]);
                $nestedRecords[] = $children;
            }
        }

        return $nestedRecords;
    }
}

Usage with your code:

$employees = json_decode($flat_employees_json, true);
$managers = NestingUtil::nest($employees, 'EmployeeID', 'ManagerEmployeeID', 'employees');
print_r(json_encode($managers));

Output:

[
  {
    "FirstName": "Tom",
    "LastName": "Jones",
    "EmployeeID": "123",
    "ManagerEmployeeID": "",
    "Manager Name": "",
    "employees": [
      {
        "FirstName": "Alice",
        "LastName": "Wong",
        "EmployeeID": "456",
        "ManagerEmployeeID": "123",
        "Manager Name": "Tom Jones",
        "employees": []
      },
      {
        "FirstName": "Tommy",
        "LastName": "J.",
        "EmployeeID": "654",
        "ManagerEmployeeID": "123",
        "Manager Name": "Tom Jones",
        "employees": []
      }
    ]
  },
  {
    "FirstName": "Billy",
    "LastName": "Bob",
    "EmployeeID": "777",
    "ManagerEmployeeID": "",
    "Manager Name": "",
    "employees": [
      {
        "FirstName": "Rik",
        "LastName": "A.",
        "EmployeeID": "622",
        "ManagerEmployeeID": "777",
        "Manager Name": "Billy Bob",
        "employees": [
          {
            "FirstName": "Bob",
            "LastName": "Small",
            "EmployeeID": "111",
            "ManagerEmployeeID": "622",
            "Manager Name": "Rik A.",
            "employees": []
          },
          {
            "FirstName": "Small",
            "LastName": "Jones",
            "EmployeeID": "098",
            "ManagerEmployeeID": "622",
            "Manager Name": "Rik A",
            "employees": []
          }
        ]
      },
      {
        "FirstName": "Eric",
        "LastName": "C.",
        "EmployeeID": "222",
        "ManagerEmployeeID": "777",
        "Manager Name": "Billy Bob",
        "employees": []
      }
    ]
  }
]

Edit1 : Fix to avoid ignoring some employees

If the last item is a employee with valid manager but the manager is not in the list, then is ignored, because where should be located?, it's not a root but does not have a valid manager.

To avoid this add the following lines just before the return statement in the utility.

if (!$parentId) {
    //merge residual records with the nested array
    $nestedRecords = array_merge($nestedRecords, $records);
}

return $nestedRecords;

Edit2: Updating the utility to PHP5.6

After some tests in PHP7 the utility works fine in php7.0 but not in php5.6, I'm not sure why, but is something in the array reference and the unset. I update the utility code to work with php5.6 and your use case.

 public static function nest($records, $recordPropId = 'id', $parentPropId = 'parent_id', $childWrapper = 'children', $parentId = null)
    {
        $nestedRecords = [];
        foreach ($records as $index => $children) {
            if (isset($children[$parentPropId]) && $children[$parentPropId] == $parentId) {
                $children[$childWrapper] = self::nest($records, $recordPropId, $parentPropId, $childWrapper, $children[$recordPropId]);
                $nestedRecords[] = $children;
            }
        }

        if (!$parentId) {
            $employeesIds = array_column($records, $recordPropId);
            $managers = array_column($records, $parentPropId);
            $missingManagerIds = array_filter(array_diff($managers, $employeesIds));
            foreach ($records as $record) {
                if (in_array($record[$parentPropId], $missingManagerIds)) {
                    $nestedRecords[] = $record;
                }
            }
        }

        return $nestedRecords;
    }

Answer 2

Here is a direct translation to PHP from your fiddle:

function makeTree($data, $parentId){
    return array_reduce($data,function($r,$e)use($data,$parentId){
        if(((empty($e->ManagerEmployeeID)||($e->ManagerEmployeeID==(object)[])) && empty($parentId)) or ($e->ManagerEmployeeID == $parentId)){
            $employees = makeTree($data, $e->EmployeeID);
            if($employees) $e->employees = $employees;
            $r[] = $e;
        }
        return $r;
    },[]);
}

It works correctly with your test input. See https://eval.in/private/ee9390e5e8ca95.

Example usage:

$nested = makeTree(json_decode($json), '');
echo json_encode($nested, JSON_PRETTY_PRINT);

@rafrsr solution is nicely flexible, but the problem is the unset() inside the foreach. It modifies the array while it is being iterated, which is a bad idea. If you remove the unset(), it works correctly.

Answer 3

You can use the magic power of recursion here. Please refer below example. getTreeData is being called under itself as you can see here.

function getTreeData($data=[], $parent_key='', $self_key='', $key='')
{
    if(!empty($data))
    {

        $new_array = array_filter($data, function($item) use($parent_key, $key) {

            return $item[$parent_key] == $key;
        });

        foreach($new_array as &$array)
        {
            $array["employees"] = getTreeData($data, $parent_key, $self_key, $array[$self_key]);

            if(empty($array["employees"]))
            {
                unset($array["employees"]);
            }
        }

        return $new_array;
    }
    else
    {
        return $data;
    }
}

$employees = json_decode($employees_json_string, true);

$employees_tree = getTreeData($employees, "ManagerEmployeeID", "EmployeeID");