Hierarchical <ul><li> from MySql

[eluser]JimmyJ[/eluser]
Ok, here we go. Thought this mind be a good problem solver for all you mysql coding junkies out there. I'm trying to create a simple menu for a simple cms system. All the pages are stored in a database like so:

Code:

CREATE TABLE `pages` (
  `pageID` int(3) NOT NULL auto_increment,
  `pageParent` int(3) NOT NULL default '0',
  `metaTitle` varchar(200) NOT NULL,
  `metaDesc` varchar(255) NOT NULL,
  `metaKeywords` varchar(100) NOT NULL,
  `pageTitle` varchar(150) NOT NULL,
  `pageDesc` text NOT NULL,
   `altUrl` varchar(100) NOT NULL,
  `linkName` varchar(25) NOT NULL,
  `pageOrder` int(3) NOT NULL,
  `templateID` int(3) NOT NULL,
  `dateCreated` datetime NOT NULL,
  `dateModified` datetime NOT NULL,
  PRIMARY KEY  (`pageID`)
) ENGINE=InnoDB  DEFAULT CHARSET=latin1 AUTO_INCREMENT=5 ;

--
-- Dumping data for table `pages`
--

INSERT INTO `pages` (`pageID`, `pageParent`, `metaTitle`, `metaDesc`, `metaKeywords`, `pageTitle`, `pageDesc`, `altUrl`, `linkName`, `pageOrder`, `templateID`, `dateCreated`, `dateModified`) VALUES
(1, 0, 'Website Home', 'This is the desc for page 1', 'keywords here...', 'Home', 'this is the text...', '', 'Home', 1, 1, '2007-12-13 19:05:13', '2007-12-13 19:05:16'),
(2, 0, 'Page 2', 'This is the desc for page 2', 'page 2 keywords...', 'Demo page 2', 'This is the desc', '', 'Information', 2, 2, '2007-12-13 19:06:14', '2007-12-13 19:06:17'),
(3, 1, 'Sub page 1', 'desc of subpage 1', 'keywords for sub1', 'Subpage 1', 'blah blah', '', 'Company', 3, 1, '2007-12-13 19:07:05', '2007-12-13 19:07:08'),
(4, 2, 'Sub page 2', 'desc for page 2', 'keywords for page 2', 'Subpage 2', 'blahdblah...', '', 'What we do', 4, 2, '2007-12-13 19:07:42', '2007-12-13 19:07:45');

What i'm looking to do is spit them out in an hierarchical order using the pageParent into an ul li list - for example:

Code:

<ul>
<li>toplink
   <ul>
   <li>sublink
      <ul>
       <li>subsublink</li>
       <li>subsublink</li>
       <li>subsublink</li>
      </ul>
   </li>
   <li>sublink</li>
   <li>sublink</li>
   </ul>
</li>
<li>toplink</li>
<li>toplink</li>
</ul>

I've got my code for spitting them out in a straight ul li like so:

Code:

<ul>
<li><a href="/">Home</a></li>
&lt;?php

$sql = "SELECT pageID, pageParent, metaTitle, linkName, pageOrder FROM pages ORDER BY pageOrder ASC LIMIT 1,999";
$query = $this->db->query($sql);
foreach($query->result() as $row){
?&gt;
<li>&lt;?php echo anchor(base_url() . '/keyword/' . $row->pageID . '/' . url_title($row->metaTitle, 'dash'), $row->linkName); ?&gt;</li>
&lt;?php
}
?&gt;
</ul>

So the big question is how the hell do i do this? I've spoken to a friend of mine and he's passed me some of his code for a project we worked on a while ago, but it looses me too. I've pasted it below:

Code:

<ul id="nav">
        &lt;?php
function recurse_over_categories($children, $firstLevel = true)
{
        global $page_vars;

        $count = 0;

        foreach($children as $child) {
                if(($firstLevel == true) && (Site::GetConfig("brandDisplayLimit") <= $count)) {
                        break;
                }

                echo("<li><a href=\"$child[url]\" title=\"$child[name]\">$child[name]</a>");

                if(sizeof($child["children"]) > 0) {
                        echo("<ul>");
                                recurse_over_categories($child["children"], false);
                        echo("</ul>");
                }

                $count++;

                echo("</li>");
        }
}

recurse_over_categories($page_vars["categories"]);
?&gt;
        </ul>

Hopefulyl someone can help. I'll release my cms here once it's done and you can take a look or use it for your own purposes. It's very simple to style - which is my biggest concern

[eluser]Grahack[/eluser]
Hi! I love these problems, so I take some time to discuss a bit but not enough to give you much code.
First, there are different ways to store hierarchical info in a db. Look at this post pointing to interesting articles. You'll find other useful posts searching for "nested set" in this forum.

So you "choosed" to associate a parent to each item. This needs to be processed RECURSIVELY. That's why it's intensive for big sets of information, it can't be done with a single query. Each node searches for his children with one more query. If you don't have more than 10 levels and 50 items, I bet it will be ok. More precisely, here you even want to have the full tree, so what I would do is make one big query to retrieve every item, then process them to build the tree with php.

You'll have to create a query that will build the $children array, each $child will have an url key, a name key and a parent_id key. That's easy.

1st method (use your code and be able to reuse the tree):
1st step:
Now I don't know how (in your project you had with your friend) precisely you build the $child['children'] array, but it's not very tricky: for each item, loop through the items and stick each children to him (could be optimized).
2nd step:
Recurse with the code your friend gave you.

2nd method: do the two steps above in the same recursive process

[eluser]zerone[/eluser]
This can - and should - be acomplished with one query.
The trick is to organize your items on an array.

Iterate all your menu entries and each one will go to a bag:

Code:

$all_items[ $row['parent_id'] ][] = $row;

Then just implement with your's friend function or create your own.
The function is first called with with the bag with empty parent_id;

Code:

echo recursive_tree($all_items['']);

Then recursive_tree is only responsible for printing each item of $items childs:

Code:

function recursive_tree($items)
{
    global $all_item;

    echo '<ul>';
    foreach ($items as $item)
    {
        echo "<li>{$item['name']}</li>";
        recursive_tree($all_items[ $item['id'] ]);
    }
    echo '</ul>';
}

There are prettier ways to do this, even by OOP which would be a lot more customizable.

[eluser]Shadi[/eluser]
hello,

check my class which exactly does your job,
http://www.phpclasses.org/browse/package/3693.html

Regards,

[eluser]JimmyJ[/eluser]
Man, this is quite hard to understand. Some great advice though, reading up as we speak

[eluser]Grahack[/eluser]
This is all about recursion.
Here is an example to compute n!=nx(n-1)x(n-2)x...x4x3x2x1.

Code:

<?php
function facto($n)
{
   if ( $n == 1 ) return 1;
   else return $n * facto( $n - 1 );
}

[eluser]zerone[/eluser]
[quote author="Grahack" date="1198000802"]This is all about recursion.
Here is an example to compute n!=nx(n-1)x(n-2)x...x4x3x2x1.

Code:

<?php
function facto($n)
{
   if ( $n == 1 ) return 1;
   else return $n * facto( $n - 1 );
}

[/quote]

Indeed
It would be achieved by iteration, but this problem requires tree recursion.
But iteration is far more efficient.

[eluser]Grahack[/eluser]
@zerone
This was just a simple example for understanding recursion.
Note: your recursive_tree() is great but returns an empty <ul></ul> if one item has no children.

[eluser]coffey[/eluser]
This works for me and my set up. I have slightly adapted this now so I can quickly employ/trial different tree css/js.

I am a recent convert from asp/.net so I have yet to fathom the depths of php coding and its many built in methods so I am sure this could be a great deal slicker.

Hope this helps

Code:

/*
* Unlimited level node array
* example of array garnered from eg table below
* Array (
    [0] => Array (
        [id] => 1 [name] => welcome [nodelevel] => 1
            [children] => Array (
                [0] => Array ( [id] => 4 [name] => more welcome [nodelevel] => 2 [children] => ) ) )
    [1] => Array (
        [id] => 2 [name] => about us [nodelevel] => 1 [children] => )
    [2] => Array (
        [id] => 3 [name] => contact [nodelevel] => 1 [children] => )

+------+------------------+---------+-------------+
|  id  |      name        |  p_id   | section_id  |
+------+------------------+---------+-------------+
|  1   |    welcome       |   0     |      1      |
+------+------------------+---------+-------------+
|  1   |    about us      |   0     |      1      |
+------+------------------+---------+-------------+
|  1   |    contact       |   0     |      1      |
+------+------------------+---------+-------------+
|  1   |  more welcome    |   1     |      1      |
+------+------------------+---------+-------------+

@param section_id - site has multiple sections each with its own menu list
@param p_id -  parent id, the first level of each section has a parent id of 0


Separated building the html from the node array collection itself
so I could employ other menu trees more easily if required and also check
in a straigntforward way if the array was gathering the information correctly
by testing via print_r()

The node collection is recursive but with a check (hasChildren)
to see if the recursion is necessary

$this->load->library('treeview');
//set section id
$this->treeview->section_id = $section_id;
//call the menu
$data = $this->treeview->buildmenu();
*/

class Treeview
{

    public $section_id = 1;
    private $nodesql = "SELECT id, node, nodelevel FROM nodes ";
    private $anchor = "/index.php/node/id/";
    private $orderby = " order by p_id, runorder, id, node ";  
    
    function __construct()
    {
        $this->obj =& get_instance();
    }
    
    // built specifically for silver stripe tree menu
    public function buildmenu()
    {
        // get the nodes array starting with the parent one
        $menu_array = $this->get_menu_nodes();
        
        $html='';
        foreach ($menu_array as $menu)
        {
            
            if ($this->hasChildren($menu['id']))
            {
                $html.="<li class=\"closed\"><a href=\"".$this->anchor."/". $this->section_id . "/\">
                      " . $menu['node'] . "</a>\n<ul>\n";
                $childarray = $menu['children'];
                foreach ( $childarray as $child)
                {
                    $html.="<li><a href=\"".$this->anchor . $child['id'] ."/" . $this->section_id . "/\">
                      " . $child['node'] . "</a></li>\n";
                }
                $html.= "</li>\n</ul>\n";
            
            } else {
                $html.="<li><a href=\"".$this->anchor .$menu['id']."/". $this->section_id . "/\">
                      " . $menu['node'] . "</a></li>\n";
            }
            
        }
        
        return $html;
    }
    
    //starts the gathering the section's parent nodes
    function get_menu_nodes()
    {
        $sql = "$this->nodesql ";
        
        // First get top level nodes i.e. parent id = 0
        $sql .= " WHERE section_id =  $this->section_id and p_id = 0 ";
                
        $sql .= $this->orderby;
        
        $result = $this->build_menu_array($sql);
        return $result;
    }
    
    //called if required by build_menu_array
    //@param pid = collects nodes with this parent id
    function get_child_nodes($pid)
    {
        // just get top level nodes initially
        $sql = "$this->nodesql
                WHERE p_id = $pid
                $this->orderby";
        $result = $this->build_menu_array($sql);
        return $result;
    }
        
    //the recursive menu 'engine'
    function build_menu_array($sql)
    {
        
    $query = $this->obj->db->query($sql);
    
    foreach ($query->result_array() as $row)
        {
            $node_items = array();
            $node_items['id'] = $row['id'];
            $node_items['node'] = $row['node'];    
            $node_items['nodelevel'] = $row['nodelevel'];    
            
            // if the node has children get them now - recursive
            // store in in children array
           if ($this->hasChildren($row['id']))
           {  
               $children = $this->get_child_nodes($row['id']);          
               $node_items['children'] = $children;          
           } else {
               $node_items['children'] = '';
           }
           $node_array[] = $node_items;
        }                  
        return $node_array;
    }


    function hasChildren($id)
    {
        $bool = FALSE;
        $sql = "Select id from nodes where p_id = $id";
        $query = $this->obj->db->query($sql);
        
        if ($query->num_rows() > 0) $bool = TRUE;
        
        return $bool;
    }


}

Cheers
Shane

[eluser]Niraj Dave[/eluser]
hi

thanks