PHP - Making a nested tree menu structure from a flat array

Question

I am making a nested menu array from the response that I get from WP database. I am getting the data from WP in the controller in Laravel with the help of corcel package, and then making an array with menu data, which is now one level deep. So, when a menu link has a submenu links, the array looks like this:

{
    "Hjem": {
        "ID": 112,
        "title": "Hjem",
        "slug": "hjem",
        "url": "http://hivnorge.app/?p=112",
        "status": "publish",
        "main_category": "Hovedmeny",
        "submenus": [
            {
                "ID": 129,
                "title": "Lorem ipsum",
                "slug": "lorem-ipsum",
                "url": "http://hivnorge.app/?p=129",
                "status": "publish",
                "main_category": "Nyheter"
            }
        ]
    },
    "Nytt test innlegg": {
        "ID": 127,
        "title": "Nytt test innlegg",
        "slug": "nytt-test-innlegg",
        "url": "http://hivnorge.app/?p=127",
        "status": "private",
        "main_category": "Nyheter",
        "submenus": [
            {
                "ID": 125,
                "title": "Test innlegg",
                "slug": "test-innlegg",
                "url": "http://hivnorge.app/?p=125",
                "status": "publish",
                "main_category": "Nyheter"
            },
            {
                "ID": 129,
                "title": "Lorem ipsum",
                "slug": "lorem-ipsum",
                "url": "http://hivnorge.app/?p=129",
                "status": "publish",
                "main_category": "Nyheter"
            }
        ]
    },
    "Prosjektsamarbeidets verdi": {
        "ID": 106,
        "title": "Prosjektsamarbeidets verdi",
        "slug": "prosjektsamarbeidets-verdi",
        "url": "http://hivnorge.no.wordpress.seven.fredrikst/?p=106",
        "status": "publish",
        "main_category": "Prevensjon"
    }
}

This is how I am creating this response:

        $menu = Menu::slug('hovedmeny')->first();
        $res = [];

        foreach ($menu->nav_items as $item) {
            $item->makeHidden($hiddenAttributes)->toArray();
            $parent_id = $item->meta->_menu_item_menu_item_parent;

            if ($parent_id == '0') {
              if ($item->title == '') {
                  $item = $this->findPost($item);
              }
              $parentItem = $item;
              $res[$parentItem->title] = $parentItem->makeHidden($hiddenAttributes)->toArray();
            }
            else {
              $childItem = $this->findPost($item);
              $res[$parentItem->title]['submenus'][] = $childItem->makeHidden($hiddenAttributes)->toArray();
            }
        }

        return $res;

The problem I have is that the response from WP only returns parent_id for each $item and no data about if an item has some children, so this is the meta data of the parent item for example:

         #attributes: array:4 [
            "meta_id" => 209
            "post_id" => 112
            "meta_key" => "_menu_item_menu_item_parent"
            "meta_value" => "0"
          ]

And this is the meta data of the child item:

          #attributes: array:4 [
            "meta_id" => 326
            "post_id" => 135
            "meta_key" => "_menu_item_menu_item_parent"
            "meta_value" => "112"
          ]

How can I make this flexible and enable deeper nesting, so that I can have submenus inside submenus?

I have tried to look for the solution here, because that is pretty much the same problem as mine, but wasn't able to implement it. In my array menu items also have only parent_id, and the parent_id that is 0 is considered as a root element. Also the parent_id if the menu item is a post, points to the meta id, and not the id of the post that I need, so I need to get that additionaly from meta->_menu_item_object_id.

UPDATE

I have managed to make a tree like structure, but the problem I have now is that I don't know how to get the title for the menu elements that are posts. I did that in the previous example by checking if the title is empty then I would search for that post by id:

          if ($item->title == '') {
              $item = $this->findPost($item);
          }

But, with the new code, where I am making a tree like structure I am not sure how to do that, since then I am not able to make the tree structure, since I am comparing everything with the id, and the ids of the menu element is different from the id of the post that is pointing to, so then I am not able to make the tree structure:

    private function menuBuilder($menuItems, $parentId = 0)
    {
        $hiddenAttributes = \Config::get('middleton.wp.menuHiddenAttributes');
        $res = [];

        foreach ($menuItems as $index => $item) {
            $itemParentId = $item->meta->_menu_item_menu_item_parent;

            if ($itemParentId == $parentId) {
                $children = self::menuBuilder($menuItems, $item->ID);

                if ($children) {
                    $item['submenu'] = $children;
                }

                $res[$item->ID] = $item->makeHidden($hiddenAttributes)->toArray();
                unset($menuItems[$index]);
            }
        }

        return $res;
    }

So, then the data I get is:

   {
    "112": {
        "ID": 112,
        "submenu": {
            "135": {
                "ID": 135,
                "title": "",
                "slug": "135",
                "url": "http://hivnorge.app/?p=135",
                "status": "publish",
                "main_category": "Hovedmeny"
            }
        },
        "title": "Hjem",
        "slug": "hjem",
        "url": "http://hivnorge.app/?p=112",
        "status": "publish",
        "main_category": "Hovedmeny"
    },
    "136": {
        "ID": 136,
        "submenu": {
            "137": {
                "ID": 137,
                "submenu": {
                    "138": {
                        "ID": 138,
                        "title": "",
                        "slug": "138",
                        "url": "http://hivnorge.app/?p=138",
                        "status": "publish",
                        "main_category": "Hovedmeny"
                    }
                },
                "title": "",
                "slug": "137",
                "url": "http://hivnorge.app/?p=137",
                "status": "publish",
                "main_category": "Hovedmeny"
            }
        },
        "title": "",
        "slug": "136",
        "url": "http://hivnorge.app/?p=136",
        "status": "publish",
        "main_category": "Hovedmeny"
    },
    "139": {
        "ID": 139,
        "title": "",
        "slug": "139",
        "url": "http://hivnorge.app/?p=139",
        "status": "publish",
        "main_category": "Hovedmeny"
    }
}

Answer 1

One way to solve this to make use of variable aliases. If you take care to manage a lookup-table (array) for the IDs you can make use of it to insert into the right place of the hierarchical menu array as different variables (here array entries in the lookup table) can reference the same value.

In the following example this is demonstrated. It also solves the second problem (implicit in your question) that the flat array is not sorted (the order is undefined in a database result table), therefore a submenu entry can be in the resultset before the menu entry the submenu entry belongs to.

For the example I created a simple flat array:

# some example rows as the flat array
$rows = [
    ['id' => 3, 'parent_id' => 2, 'name' => 'Subcategory A'],
    ['id' => 1, 'parent_id' => null, 'name' => 'Home'],
    ['id' => 2, 'parent_id' => null, 'name' => 'Categories'],
    ['id' => 4, 'parent_id' => 2, 'name' => 'Subcategory B'],
];

Then for the work to do there are tow main variables: First the $menu which is the hierarchical array to create and second $byId which is the lookup table:

# initialize the menu structure
$menu = []; # the menu structure
$byId = []; # menu ID-table (temporary) 

The lookup table is only necessary as long as the menu is built, it will be thrown away afterwards.

The next big step is to create the $menu by traversing over the flat array. This is a bigger foreach loop:

# build the menu (hierarchy) from flat $rows traversable
foreach ($rows as $row) {
    # map row to local ID variables
    $id = $row['id'];
    $parentId = $row['parent_id'];

    # build the entry
    $entry = $row;
    # init submenus for the entry
    $entry['submenus'] = &$byId[$id]['submenus']; # [1]

    # register the entry in the menu structure
    if (null === $parentId) {
        # special case that an entry has no parent
        $menu[] = &$entry;
    } else {
        # second special case that an entry has a parent
        $byId[$parentId]['submenus'][] = &$entry;
    }

    # register the entry as well in the menu ID-table
    $byId[$id] = &$entry;

    # unset foreach (loop) entry alias
    unset($entry);
}

This is where the entries are mapped from the flat array ($rows) into the hierarchical $menu array. No recursion is required thanks to the stack and lookup-table $byId.

The key point here is to use variable aliases (references) when adding new entries to the $menu structure as well as when adding them to $byId. This allows to access the same value in memory with two different variable names:

        # special case that an entry has no parent
        $menu[] = &$entry;
         ...

    # register the entry as well in the menu ID-table
    $byId[$id] = &$entry;

It is done with the = & assignment and it means that $byId[$id] gives access to $menu[<< new key >>].

The same is done in case it is added to a submenu:

    # second special case that an entry has a parent
    $byId[$parentId]['submenus'][] = &$entry;
...

# register the entry as well in the menu ID-table
$byId[$id] = &$entry;

Here $byId[$id] points to $menu...[ << parent id entry in the array >>]['submenus'][ << new key >> ].

This is solves the problem to always find the right place where to insert a new entry into the hierarchical structure.

To deal with the cases that a submenu comes in the flat array before the menu entry it belongs to, the submenu when initialized for new entries needs to be taken out of the lookup table (at [1]):

# init submenus for the entry
$entry['submenus'] = &$byId[$id]['submenus']; # [1]

This is a bit of a special case. In case that $byId[$id]['submenus'] is not yet set (e.g. in the first loop), it is implicitly set to null because of the reference (the & in front of &$byId[$id]['submenus']). In case it is set, the existing submenu from a not yet existing entry will be used to initialize the submenu of the entry.

Doing so is enough to not depend on any specific order in $rows.

This is what the loop does.

The rest is cleanup work:

# unset ID aliases
unset($byId); 

It unsets the look ID table as it is not needed any longer. That is, all aliases are unset.

To complete the example:

# visualize the menu structure
print_r($menu);

Which then gives the following output:

Array
(
    [0] => Array
        (
            [id] => 1
            [parent_id] => 
            [name] => Home
            [submenus] => 
        )

    [1] => Array
        (
            [id] => 2
            [parent_id] => 
            [name] => Categories
            [submenus] => Array
                (
                    [0] => Array
                        (
                            [id] => 3
                            [parent_id] => 2
                            [name] => Subcategory A
                            [submenus] => 
                        )

                    [1] => Array
                        (
                            [id] => 4
                            [parent_id] => 2
                            [name] => Subcategory B
                            [submenus] => 
                        )

                )

        )

)

I hope this is understandable and you're able to apply this on your concrete scenario. You can wrap this in a function of it's own (which I would suggest), I only kept it verbose for the example to better demonstrate the parts.

Related Q&A material:

• Php: Converting a flat array into a tree like structure
• Convert a series of parent-child relationships into a hierarchical tree?
• Build a tree from a flat array in PHP

Answer 2

So you would need to write a recursive function see What is a RECURSIVE Function in PHP?

So something like

function menuBuilder($menuItems){
    foreach($menuItems as $key => $item)
    {
        if(!empty($item->children)){
            $output[$key] = menuBuilder($item->children);
        }
    }
    return $output;
}