Converting an array from one to multi-dimensional based on parent ID values

I've got a one-dimensional array of objects that represent multi-dimensional data:

array(
    array(
        "id" => 45,
        "parent_id" => null
    ),
    array(
        "id" => 200,
        "parent_id" => 45
    ),
    array(
        "id" => 345,
        "parent_id" => 45
    ),
    array(
        "id" => "355",
        "parent_id" => 200
    )
);

How should I convert it into a multi-dimension开发者_JAVA百科al array:

array(
    array(
        "id" => 45,
        "parent_id" => null,
        "children" => array(
            array(
                "id" => 200,
                "parent_id" => 45,
                "children" => array(
                    "id" => "355",
                    "parent_id" => 200
                )

            ),
            array(
                "id" => 345,
                "parent_id" => 45
            ),
        )
    ),
);

---

The following code-example converts the array $array into the tree-structure you're looking for:

// key the array by id
$keyed = array();
foreach($array as &$value)
{
    $keyed[$value['id']] = &$value;
}
unset($value);
$array = $keyed;
unset($keyed);

// tree it
$tree = array();
foreach($array as &$value)
{
    if ($parent = $value['parent_id'])
        $array[$parent]['children'][] = &$value;
    else
        $tree[] = &$value;
}
unset($value);
$array = $tree;
unset($tree);

var_dump($array); # your result

This does not work, if there is an existing parent id that is 0. But could be easily changed to reflect that.

This is a related question, that has the original array already keyed, so the first half of the solution could be spared: Nested array. Third level is disappearing.

Edit:

So how does this work? This is making use of PHP variable aliasing (also known as references) and (temporary) arrays that are used to store a) aliases to the nodes ($keyed) and b) to build the new tree order ($tree).

Could you [...] explain the purpose of $array = $keyed, $array = $tree and the unsets?

As both, $keyed and $tree contain references to values in $array, I first copy over that information into $array, e.g.:

$array = $keyed;

As now $keyed is still set (and contains references to the same values as in $array), $keyed is unset:

unset($keyed);

This un-sets all references in $keyed and ensures, that all values in $array aren't referenced any longer (the value's refcount is reduced by one).

If the temporary arrays are not unset after the iteration, their references would still exist. If you use var_dump on $array, you would see that all values would have a & in front, because they are still referenced. unset($keyed) removes these references, var_dump($array) again, and you will see the &s are gone.

I hope this was understandable, references can be hard to follow sometimes if you're not fluent with them. It often helps me to think about them as variable aliases.

If you want some exercise, consider the following:

How to convert your $array from flat to tree with one foreach iteration?

Decide on your own when you would like to click the link which contains a Solution.

---

function convertArray ($array) {
  // First, convert the array so that the keys match the ids
  $reKeyed = array();
  foreach ($array as $item) {
    $reKeyed[(int) $item['id']] = $item;
  }
  // Next, use references to associate children with parents
  foreach ($reKeyed as $id => $item) {
    if (isset($item['parent_id'], $reKeyed[(int) $item['parent_id']])) {
      $reKeyed[(int) $item['parent_id']]['children'][] =& $reKeyed[$id];
    }
  }
  // Finally, go through and remove children from the outer level
  foreach ($reKeyed as $id => $item) {
    if (isset($item['parent_id'])) {
      unset($reKeyed[$id]);
    }
  }
  return $reKeyed;
}

I feel sure this can be reduced to only two loops (combining the second and third) but right now I can't for the life of me figure out how...

NOTE This function relies on parent_id for items with no parent being either NULL or not set at all, so that isset() returns FALSE in the last loop.