Wednesday, July 28, 2010

HowTo navigate through a tree without recursive methods (while loop instead)

today I was simply writing a local template in order to render a menu following the MVC pattern.
Now my local template system does not use a meta-language, but loops, if statements and so on are written directly in php, because I don't have enough time to write an interpreter.
So really I can use all php functionalities in my templates including recursive functions. But it's not the way I want to follow, moreover maybe some day I'll find the time to write my interpreter and then will be very easy to "convert" if statements and cycles, not so easy if not impossible to convert recursive functions.
Well, so the problem was the following:
I have a n-dimensional menu tree, and have to generate the classical html code for such a menu, that is something like:
<ul id="nav">
So let's see HOW TO get this without recursion. The code is well commented, here it goes:

 * Menu tree is represented by an n-dimensional array.
 * Array keys are the labels and array values are either a link
 * or a submenu (another array)
$voices["Home"] = array("Home1" => array("Home11"=>"#"), "Home2"=>array("Home21"=>"#"));
$voices["News"] = array("News1" => "#", "News2"=>array("News21"=>"#"));
$voices[_("About")] = array("About1"=>array("About11"=>array("About111"=>"#", "About112"=>"#")), "About2"=>"#");
$voices[_("Services")] = '#';
$voices[_("Faq")] = '#';

// control the exit from the loop
$continue = true;
// this variables stores the branch currently analized
$parsed = $voices;         
// stores all the branches parsered, because the tree is navigated following a branch
// until the foil. So when returning on top levels the navigation must continue on
// branches interrupted earlier.
$tree = array();
// stores the last key of the current branch array
$last = null;

echo "<ul id=\"nav\">\n";

while($continue === true) {
    // if the value of the current element parsered is an array than has a submenu
    if(is_array(current($parsed))) {
        // echo the current voice and open a new submenu (ul)
        echo "<li><a href=\"#\">".key($parsed)."</a>\n<ul>\n";
        // we're going to begin navigate the branch ->
        // we store the branch we're leaving in the tree array
        $tree[] = $parsed;
        // the branch to analyze is now the submenu
        $parsed = current($parsed);
        // get the last key of the new branch
        $last = key($parsed);
        // reset the array pointer
    // else if the value of the current element is not an array (but a link)
    // and not false (i.e. after calling next on the last element of an array)
    elseif(current($parsed)!==false) {
        // echo the current voice
        echo "<li><a href=\"".current($parsed)."\">".key($parsed)."</a></li>\n";

        // if the voice printed is the last of its branch
        // than close the submenu and get the last branch stored in the
        // varable tree (the parent branch) as the one to follow parsering
        if(key($parsed)==$last) {
            echo "</ul></li>\n";
            $parsed = array_pop($tree);
        // move the pointer to the next element
    // else the value of the current element is false -> we have already passed the last element
    // then we close the submenu and get the parent branch as the current one, passing to the next element
    else {
        echo "</ul></li>";
        $parsed = array_pop($tree);

    // if we are navigating the first tree level and have passed through all them -> exit
    if(count($tree)==0 && current($parsed)==false) $continue = false;

echo "</ul>\n";
Hasta la proxima!

No comments: