Php: Converting a flat array into a tree like structure

Question

I need help with an array conversion. I have a flat array that looks like this:

Array
(
[0] =>  av_one_third
[1] =>  av_icon_box
[2] =>  /av_icon_box
[3] =>  av_button
[4] =>  av_icon_box
[5] =>  /av_icon_box
[6] =>  /av_one_third

)

The values of this array are actually tags from a xml like structure. what I now need is to convert this array into a nested array that resembles the following structure:

[0] => Array
    (
        [tag] => av_one_third
        [content] => Array
            (
                [1] => Array
                    (
                        [tag] => av_icon_box
                        [content] => Array
                            (
                            )

                    )

                [2] => Array
                    (
                        [tag] => av_button
                        [content] => Array
                            (
                            )

                    )  

                [3] => Array
                    (
                        [tag] => av_icon_box
                        [content] => Array
                            (
                            )

                    )


            )

    )
etc

Is there an easy way to do this? My first Idea was to convert the array to an xml string and use one of phps native XML functions but the problem is that self closing tags are not labeled as such. In the case above the fact that the av_button tag has no closing tag throws of the xml parsing functions i tried.

Some additional requirements: - elements can hold any number of children - final array must maintain correct order

Are there any smart array sorting functions that could easily solve this? Would appreciate any hints on this!

Best regards :)

Answer 1

Your array has a typical flat structure encoding a hierarchy. But only if you fix the error in there.

It basically then works like in the following list with PHP codes, including exceptions telling where errors are in the data so that you can fix your data (you can find similar examples on this website e.g. see the linked questions in How can I convert a series of parent-child relationships into a hierarchical tree?):

1. Initialize a root entry inside a tree array. There you can add children to.

   $tree     = ['children' => []];
   

2. Create an array of pointers into the tree of which it's first element (level 0) points to the root element of the tree:

   $pointers = [&$tree];
   

3. Now go over each line inside the data:

   foreach ($data as $index => $line) {
   

4. Decide whether the line closes and store that decisions result:

   $close = '/' === $line[0];
   

5. Store the current count of pointers:

   $count = count($pointers);
   

6. In case the line does not close, open a new element and continue:

   $pointers[$count]                   = ['tag' => $line, 'children' => []];
   $pointers[$count - 1]['children'][] = & $pointers[$count];
   continue;
   

7. In case the line does close instead, validate if the tagname is matches and if so, remove the last created pointer:

   if ($count === 1) {
       throw new RuntimeException('Can not close on lowest level.');
   }
   
   $name = $pointers[$count - 1]['tag'];
   
   if ($name !== substr($line, 1)) {
       throw new RuntimeException(
           "Invalid closing element <$line> (line #$index) in <$name>"
       );
   }
   
   array_pop($pointers);
   

8. After all lines have been processed like outlined all pointers can be removed:

   unset($pointers);
   

9. The result is the array that can be found in the first children in the root node. It can be assigned to a variable and the not needed references can be deleted then:

   $result = &$tree['children'][0];
   unset($tree);
   print_r($result);
   

If the data is correct, it exemplary outputs:

Array
(
    [tag] => av_one_third
    [children] => Array
        (
            [0] => Array
                (
                    [tag] => av_icon_box
                    [children] => Array
                        (
                        )
                )
            [1] => Array
                (
                    [tag] => av_button
                    [children] => Array
                        (
                        )
                )
            [2] => Array
                (
                    [tag] => av_icon_box
                    [children] => Array
                        (
                        )
                )
        )
)