veni, vidi, fietsie

Building ordered multilevel menu's with PHP using the SpaceInvader Strategy Theorem

When developping web, sooner or later a need arises to create a menu for contentpages or ligning up a forum where bored people are reacting to other bored people's reactions. It has items, nodes, or whatevers, that may, or may not, have a parent and tend to go multilevel deep. The code I wrote years ago to tackle this problem had a recursive function that ran through the same data n*n times.

Usually you have some table in your database looking like this:

+----+-------------------------+-----------+--------------+
| id | title                   | parent_id | sortingorder |
+----+-------------------------+-----------+--------------+
|  1 | home                    |         0 |            1 |
|  2 | projectjes              |         0 |            2 |
|  3 | fiets reizen            |         0 |            3 |
|  6 | Naar Denemarken         |         3 |            4 |
|  5 | Naar België             |         3 |            5 |
|  8 | test child-child        |         6 |            6 |
|  9 | test child-child2       |         6 |            7 |
| 10 | test child-child2-child |         9 |            8 |
| 11 | klkjh                   |         6 |            9 |
|  4 | php                     |         0 |           10 |
|  7 | menubuilder             |         4 |           11 |
+----+-------------------------+-----------+--------------+

With a single query "SELECT * FROM contentitem ORDER BY sortingorder" you basically get all the information you need to build a multilevel menu. There are solutions out there that put queries in a loop to create the branches of a multilevel menu, but that - even 10 years ago - seemed not the most elegant solution. The code I came up may have taken even more resources, but at least I thought I jumped the scriptkiddy-level.
So I used some "new" PHP-functions that were not available in PHP3, to construct a method that handles multilevel menu structures from unordered data, doesnot run n*n times through the same data and needs to be no longer than just 5 rules of code. Well, that is when you put some {'s and }'s on one line, which we, for educational reasons, will not.

To accomplish all this, we will use the SpaceInvader Strategy Theorem. I can't imagine that what I made up here is original, but I did hack it up myself. It's a working beta class and will work if you put in some property declarations yourself.

After the getquery we want to create two arrays. Basically there's two types of entries in your content-table: those with a parent_id, and those without a parent_id. When building stuff you usually start with the foundations; i.e. the root menu-elements without a parent. These are the items that make up the mainmenu-items where the branches will be attached to. All other elements do have a parent, and they need to come on top of the correct elements.
So let's create these arrays by looping the queryresults:

        $arRow = $objQry->getQryData();

        foreach ($arRow as $arValue) {
            $arNwArRow[$arValue['id']] = $arValue;
            if (! $arValue['parent_id']) {
                $this->_arParentLess[] = $arValue['id'];
            }
            else {
                $this->_arParented[] = array( 'id' => $arValue['id'],
                                              'parent_id' => $arValue['parent_id']);
            }
        }

What we're doing here is just businesslogic; adding metadata about a hierarchy to our actual content. So we handle contentitem id's only. But by having the queryresults keyed with id's in the $arNwArRow, it's really easy to use our ordered data-array in any frontend- [or debugging-] context.

Now we need to populate the menutree: $arTree. We'll start our new method by building the foundations with the root, or parentless, menuitems:

    private function createArrayWithOrderedIds() {
        $arTree = array();
        $arTree = array_merge($arTree, $this->_arParentLess);

At this point you may get annoyed by the method- and propertynames. So do I, but if you code the first 4 pages with it, you really can't start doing it any other way on the 5th page. I'm probably stuck with it for the coming decade.

Next we need to add branches, preferably using native php methods instead of the usual self crafted loops. Yesterday I came across the very nifty method array_splice() which enables one to insert elements into any place into any array. If the place of the element in the array is known, it's really easy to insert a element before or after it. Now our $arTree starts at key [0], so that comes in handy when we combine this method with another one, that searches the values in an array and returns the key if the value was found. That PHP function is called array_search().

If we want to build a branch of the tree, starting from the rootelements, we need to get the elements where the parent_id equals the rootelement's id that's already present. If we find one, we need to insert that element after the rootelement. The solution is to run a loop with our $this->_arParented array, and look for the parent_id that matches a rootelement id. Once found, insert the element behind it, and we're off exercising in the wild outdoors.

No, we are not. If there's more elements with the same parent_id, they will also look for that same root element and get inserted behind it. That means that the former inserted element that had the same parent_id, gets moved a place down the $arTree array hierarchy. That results in a reversed order in the $arTree array compared to the order of things we got from the database.
At this point you probably want to reverse the order of the elements in the $this->_arParented array. Don't use arsort() here - it's a recipe for headaches -, but use array_reverse():

        $this->_arParented = array_reverse($this->_arParented);

So we loop our reversed $this->_arParented array, look for the parent_id that matches a rootelement id, and, once found, insert the element behind it, and then we're off cycling.

No, again we're not. The fact that the last element to come from the database, now shows up first, complicates things further. This element may (or may not) be an element that is on a tree level above the rootelements. Remember we're talking multi-level here.
If it happened to have a parent that matches the id of an element that was already added to $arTree, then this element 'finds a hook' and it's added behind it. But if this element has a parent_id that corresponds to an element that is down the loop and has not been added yet, than this element is skipped.
So what we need, is a loop in a loop. Damn. But there is an advantage to it. We get to that later. Here's the code:

        while( count($this->_arParented) ) {
            foreach ($this->_arParented as $intKey => $arValue) {

Because every while-loop fills exactly one level of your menu when you've set the sortingorder for all items, it enables you to count them and log the level at which an id is inserted. This makes your life a lot easier when presenting a menu using indents or other fancy markup at each branch-level.
NB: In an unordered dataset (for example after adding a child and before setting the sortingorder) a parent may preceed a child in the same loop, so both parent and child are added in the same level-run. You may need to check for that event while levellogging.
You'd have to insert the necessary arrays into the code yourself.

To prevent your browser sending error-reports to Mozilla, somewhere in the foreach loop $this->_arParented-elements have to be unset(). So it's search-and-destroy. Here's the search-part:

                $intCounter = array_search($arValue['parent_id'], $arTree, true);

What we get here is a really mixed result. If the parent_id was not found, array_search returns FALSE. In this case we continue the loop. Else { we use the found key-value to insert our element using array_splice(). We have to add 1 to $intCounter because the $arTree key-value starts at 0 and we need to find the actual 'place' in the array:

                if( is_int($intCounter) ) {
                    $intCounter ++;
                    array_splice($arTree, $intCounter, 0, $arValue['id']);

Than the destroy-parts follows:

                    unset($this->_arParented[$intKey]);

                }
            }
        }

That's all there is to it. Please note that this function runs for ever if there's a parent that has a no-showflag in the database while it's children don't have that flag - they keep searching for their parent and won't be destroyed. Otherwise, the while loop will only run as many times as your menu has levels, minus one, because the parentless items are in the array already. So if your max level-depth is 4, it will run just 3 times. Each run takes less effort, because the array gets shorter each run. This code has a strong SpaceInvader-feeling to it, because it "bombards" the foundations of the menu with elements; some miss, others hit, and these runs are repeated untill all elements are blasted.

The result is an array $arTree that holds the id's in the correct branch-order. If you're having menu's with lots of elements and levels, you may find it useful to run this code once and store the array in a static property  to make it sitewide accessible. The code even works on data where the sortorder-field is not set.

Here's the total snippet from my working beta pageorder class:

    /**
    *     Public method - gets ordered menuitems from Db
    *
    *    @uses        array $this->_arParentLess sets parentless elements
    *    @uses        array $this->_arParented sets parented elements
    *    @return      array contentitems ordered according to menustructure
    */
    public function getOrderedContentData() {

        $qry =    "SELECT * FROM contentitem ORDER BY sortingorder";

        //--> do your dbhandling here

        foreach ($arRow as $arValue) {
            $arNwArRow[$arValue['id']] = $arValue;
            if (! $arValue['parent_id']) {
                $this->_arParentLess[] = $arValue['id'];
            }
            else {
                $this->_arParented[] = array( 'id' => $arValue['id'],
                                              'parent_id' => $arValue['parent_id'] );
            }
        }

        $orderedArray = array();
        $niceArray    = array();
        $niceArray    = $this->createArrayWithOrderedIds();
        foreach($niceArray as $keyId) {
           $orderedArray[] = $arNwArRow[$keyId];
        }

       return $orderedArray;
    }

    /**
    *    Private method - loops through data-array and hierarchically adds elements
    *
    *    @uses      array $this->_arParentLess containing parentless elements to order
    *    @uses      array $this->_arParented containing parented elements to order
    *    @return    array $arTree with id's in menu branch ordered structure
    */
    private function createArrayWithOrderedIds() {
        $arTree = array();
        $arTree = array_merge($arTree, $this->_arParentLess);
        $this->_arParented = array_reverse($this->_arParented);
        while(count($this->_arParented)) {
            foreach ($this->_arParented as $intKey => $arValue) {
                $intCounter = array_search($arValue['parent_id'], $arTree, true);
                if( is_int($intCounter) ) {
                    $intCounter ++;
                    array_splice($arTree, $intCounter, 0, $arValue['id']);
                    unset($this->_arParented[$intKey]);
                }
            }
        }
        return $arTree;
    }