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

Question

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-dimensional 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
            ),
        )
    ),
);

is data ordered so child always come after parent? – Blem Oct 14 '11 at 13:04 — Blem, Oct 14 '11 at 13:04
@Blem, It is not. That's a great question, btw. – Emanuil Rusev Oct 14 '11 at 13:07 — Emanuil Rusev, Oct 14 '11 at 13:07

score 5 · Accepted Answer · edited May 23 '17 at 12:24

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.

That's amazing! Could you add comments to explain the purpose of `$array = $keyed`, `$array = $tree` and the unsets? — Emanuil Rusev, Oct 14 '11 at 13:47
@Emanuil Rusev: I added a part about what the assignments and the unsets are about. And a little exercise if you like. Let me know; The solution of the exercise is actually a valid answer to your question as well, so it could be added to the answer for future reference later on. — hakre, Oct 14 '11 at 14:30
@EmanuilRusev: In another question, [PHP variables: references or copies](http://stackoverflow.com/questions/7691510/php-variables-references-or-copies/7693307), I answered in more detail about arrays and references as well. Might be something interesting for you, so I leave it as a comment here. — hakre, Oct 14 '11 at 14:37

DaveRandom · Answer 2 · 2011-10-14T13:29:07.000

2

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.

edited Oct 14 '11 at 13:29

answered Oct 14 '11 at 13:18

DaveRandom

87,921
11
154
174

The third loop unsets all items :? – Emanuil Rusev Oct 14 '11 at 13:29
It only unsets items where `parent_id` is not set, or set to `NULL` (so `isset()` returns FALSE). If this is not the case for your actual data, you will need to modify the `if` in the last loop so it uses a condition unique to items with no parent. If I run it on the sample data provided, it produces the result you expect. – DaveRandom Oct 14 '11 at 13:32
Thanks Dave! That was exactly the issue. I took care of it and now it seems to be working fine. Thanks again! – Emanuil Rusev Oct 14 '11 at 13:39

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

2 Answers2

Linked

Related