MPTtree, Hieararchical trees in a database table

[eluser]renownedmedia[/eluser]
I will def be considering this class for a pyramid type affiliate based eCommerce application.

[eluser]crises[/eluser]
I finally found a way of doing a collapsible tree menu from data stored in this way (in my case categories of products for an online catalog). But now i would like to know if this solution is efficient.

In my app i have categories stored as:

Code:

+Root
|--Main Category 1
| |--Subcat 1
| |--Subcat 2
| | |--Sub-subcat 1
| | |--Sub-subcat 2
| |--Subcat 3
|--Main Category 2
| |--Subcat 4
| |--Subcat 5
|   |--Sub-subcat 3
|--Main Category 3
|--Main Category 4
| |--Subcat 6
| |--Subcat 7

I think you got the idea, nothing strange Then i want a menu that firstly shows only the Main Categories, and then if i click in Main Category 1 for example it shows ONLY the first two childs of Main Category (Subcat 1 and Subcat 2). Then if i click in Subcat 2 the menu should show me the childs of Main Category 1 plus childs of Subcat 2. And so on, usual menu as shown in many websites.

To the point. In my catalog controller:

Code:

function category($current_category_url = null, $page=null)
{
    /*Rest of stuf*/

    $current_category = $this->Catalog_model->get_current_category($current_category_url);//Array with all data of the current category
    $root = $this->MPTtree->get_root();
    $main_categories = $this->MPTtree->get_children($root['lft'], $root['rgt']);//only Main Categories, without their childrens
    $data['menu'] = $this->Catalog_model->do_menu($main_categories, $current_category);

    /*Rest of stuf*/
}

And the functions in the model (Catalog_model):

Code:

function get_current_category($category_url)
{
    $this->db->select('*');
    $this->db->from('prod_category');
    $this->db->where('category_url =', $category_url);
    $this->db->limit(1);
    $query = $this->db->get();
    
    if ($query->num_rows() > 0)
    {
        $result = $query->row_array();
        return $result;
    }
}

function do_menu($tree, $current_category)
{
    $category_childrens = $this->MPTtree->get_children($current_category['lft'], $current_category['rgt']);
    $parents_current_category = $this->MPTtree->get_parents($current_category['lft'], $current_category['rgt']);
    $str = '<ul class="category-list>"';
    foreach($tree as $category)
    {
        $str .= '<li>';
        if ($category['name'] == $current_category['name'])
        {
            $str .= '<strong><a href="'.base_url().'catalog/category/'.$category['category_url'].'">'.$category['name'].'</a></strong>';
            $str .= $this->do_submenu($category_childrens, $current_category);
        }
        else
        {
            $str .= '<a href="'.base_url().'catalog/category/'.$category['category_url'].'">'.$category['name'].'</a>';
        }
        if ($current_parent = $this->check_parents($category, array_reverse($parents_current_category)))
        {
            $childrens_of_current_parent = $this->MPTtree->get_children($current_parent['lft'], $current_parent['rgt']);
            $str .= $this->do_submenu($childrens_of_current_parent, $current_category);
        }
        $str .= '</li>';
    }
    $str .= '</ul>';
    return $str;
}

function do_submenu($tree, $current_category)
{
    $category_childrens = $this->MPTtree->get_children($current_category['lft'], $current_category['rgt']);
    $parents_current_category = $this->MPTtree->get_parents($current_category['lft'], $current_category['rgt']);
    $str = '<ul class="subcategory-list">';
    foreach($tree as $category)
    {
        $str .= '<li>';
        if ($category['name'] == $current_category['category'])
        {
            $str .= '<strong><a href="'.base_url().'catalog/category/'.$category['category_url'].'">'.$category['name'].'</a></strong>';
            $str .= $this->do_submenu($category_childrens, $category);
        }
        else
        {
            $str .= '<a href="'.base_url().'catalog/category/'.$category['category_url'].'">'.$category['name'].'</a>';
        }
        if ($current_parent = $this->check_parents($category, array_reverse($parents_current_category)))
        {
            $childrens_of_current_parent = $this->MPTtree->get_children($current_parent['lft'], $current_parent['rgt']);
            $str .= $this->do_submenu($childrens_of_current_parent, $current_category);
        }
        $str .= '</li>';
    }
    $str .= '</ul>';
    return $str;
}
    
function check_parents($category, $parents_current_category)
{
    foreach($parents_current_category as $parent)
    {
        if ($category['name'] == $parent['name'] && $parent['name'] != 'Root') //Name of root node in tree
        {
            $current_parent = $parent;
            return $current_parent;
            exit;
        }
    }
}

Functions do_menu() and do_submenu() are esentially the same, but as i want different <ul> class i had to make two functions. If you dont need it you can only use one function. Well the code is not as simple as i would like, but at least is working. Now the question again: it is efficient enought? ty

[eluser]iDenta[/eluser]
How do i get has_children() to work? The documentation doesn't cover has_children() much, but i've tried $this->MPTtree->has_children($root['lft'],$root['rgt']) and so on but it just returns "Call to undefined method MPTtree::has_children()"

[eluser]Mahmoud M. Abdel-Fattah[/eluser]
does anyone has an answer to this topic :
http://ellislab.com/forums/viewthread/128614/

[eluser]TheFuzzy0ne[/eluser]
has_children doesn't seem to exist at the moment, even though it's documented. You need to be using hasChildren() for the interim.

[eluser]ntheorist[/eluser]
I found an interesting article regarding nested sets:
http://explainextended.com/2009/09/29/ad...ets-mysql/

apparently you can speed up access of nested set queries by defining the left & right columns as spatial indexes. Any thoughts on how difficult it would be to implement this? Also the idea of also recording a level column for cases when adjacency-type queries would be faster is interesting.

_n

[eluser]m4rw3r[/eluser]
Looks really interesting, bookmarking that article for later use when I create a plugin for RapidDataMapper (will be a switch or something, because not all uses MySQL).

It does not seem to be too hard to implement, but I haven't tried it and it was a long time since I worked with the details of MPTT.

[eluser]nardanadam[/eluser]
Thank you for the mptt class firstly.
As the documentation of MPTtree says:
* When someone deletes a node which has subnodes, those connections must be re-established to another node.
* It takes many querys to get all descendants or parents for a given node, in Nested Sets it takes only one.
* You have two columns with the same data (id and parent_id).

According to this disadvantages of mptt, I wonder how can I write the implementation of hierarchical(threaded or nested) comment system. As comments may have children comments and children have the parent comment.

Because adding, deleting and editing the comment are available for user, I think mptt would be not a right choice. So any ideas for a situation like mine?

My regards

[eluser]m4rw3r[/eluser]
If you need a tree something like this:

Code:

comment 1
comment 2
  comment 3
    comment 6
  comment 7
comment 4
  comment 5

Then maybe consider storing an order and a depth value, that will make it easy to do inserts (but it still needs locking as you have to make place for the new node).

Code:

order depth id  other data...
1     0     1
2     0     2
3     1     3
4     2     6
5     1     7
6     0     4
7     2     5

There are many ways to store a tree in a database, the hard thing is to find the most effective solution to the situation.
MPTT is great if you're going to traverse the tree, but it isn't great if you just move one level at a time or move things in the tree very frequently.

[eluser]nardanadam[/eluser]
m4rw3r, your solution requires update of 'order' columns of data, when an insert operation is processed.
Do you think it really fits for this situation?