MPTtree, Hieararchical trees in a database table

[eluser]m4rw3r[/eluser]
Ok, seems like it's complaining on the debug_message() function.

Remove the ampersand in the definition of debug_message():
function debug_message(&$message){
to
function debug_message($message){

The default settings are covered in the manual.

[eluser]MaxPar[/eluser]
Wow, talk about a fast response! Now the error has changed to:

A PHP Error was encountered

Severity: Notice

Message: Only variable references should be returned by reference

Filename: MPTtree/MPTtree_ORM.php

Line Number: 199
A PHP Error was encountered

Severity: Notice

Message: Undefined variable: parent

Filename: controllers/wiki.php

Line Number: 48

Fatal error: Call to a member function get_all() on a non-object in /webserver/system/application/controllers/wiki.php on line 48

Do you think this could have anything to do with my version of MySQL? Also, I neglected to mention in my previous post that I'm running the latest version of CodeIgniter.

[eluser]MaxPar[/eluser]
I deleted and re-entered the database in MySQL, and now it seems to be working fine. I guess I must have typod something as I was entering it :\ :\

Anyway, thanks so much for your (extremely fast!) help and work on this code. This is a really great plugin!

[eluser]TheLoops[/eluser]
After installing MPTree in an application that uses Matchbox I get this conflict with Matchbox:

A PHP Error was encountered
Severity: Notice
Message: Undefined property: Tree_admin::$matchbox
Filename: libraries/MY_Config.php
Line Number: 81

Fatal error: Call to a member function argument() on a non-object in …/application/libraries/MY_Config.php on line 81

It would be great if this could be fixed.

Matchbox uses a library called "Loader.php" that replaces CI's native CI_Loader with an enhanced one.
It looks like there is a loading conflict with the loading order between MPTree and Matchbox.

I tried the following fix (rather a dirty hack):
I cut the class from MY_Loader.php and pasted it into Matchbox's Loader.php right after the CI_Loader class declaration.
Then I deleted MY_Loader.php. Works like a charme. But way too dirty to keep it that way, imho.

[eluser]TheLoops[/eluser]
I myself have have written (or rather adapted) a nested tree model for CI.
I actually just turned this class to a CI model that uses CI's native Active Record.

But unfortunately it does not have any useful editing functionality implemented.
Hence I'll most likely have to drop it in favor of MPTree.

Nevertheless there are some features in my model wich I'd like to see in MPTree.

(bool) isDescendantOf(…)
Would check if a given node is found in MPTree's get_descendants()

(bool) isChildOf(…)
Would check if a given node is found in MPTree's get_parents()

(array) getFamilyBranch(…)
Would fetch the immediately family of a node. More specifically, fetch a node's siblings, parents, parents' siblings, and its own direct children.

(int) getDescendantsCounts(…)
Would return MPTree's get_descendants() with an additional field holding the node's descendants count. (This is handy if want to print the count of descendants next to each node of a tree)

(int) getChildrenCounts(…)
Would return MPTree's get_children() with an additional field holding the node's children count. (This is handy if want to print the count of children next to each node of a tree)

Furthermore I'm curious why you did not add a parent_id and a nlevel field to MPTree.
Using such fields would make many of MPTree's so more simple. Both: to understand for the user and also to maintenance.

Just take thes simple query as example:

MPTree's approach WITHOUT a parent_id field:

Code:

function count_children($lft,$rgt){
        $result = $this->db->query(
"SELECT COUNT(*) as num FROM
(SELECT node.*, (COUNT(parent.{$this->id_col}) - (sub_tree.depth + 1)) AS depth
FROM {$this->tree_table} AS node,
    {$this->tree_table} AS parent,
    {$this->tree_table} AS sub_parent,
    (
        SELECT node.{$this->id_col}, (COUNT(parent.{$this->id_col}) - 1) AS depth
        FROM {$this->tree_table} AS node,
        {$this->tree_table} AS parent
        WHERE node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{$this->left_col} = {$lft}
        GROUP BY node.{$this->id_col}
        ORDER BY node.{$this->left_col}
    )AS sub_tree
WHERE node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{$this->left_col} BETWEEN sub_parent.{$this->left_col} AND sub_parent.{$this->right_col}
    AND sub_parent.{$this->id_col} = sub_tree.{$this->id_col}
GROUP BY node.{$this->id_col}
HAVING depth = 1
ORDER BY node.{$this->left_col}) as a");
        $result = $result->row_array();
        return $result['num'];
    }

Versus an approach WITH a parent_id field:

Code:

function count_children($lft,$rgt,$id = NULL){
        if($rgt - $lft < 3) // leaf node, 3 here because of the possibility of a gap (4 = have children)
            return array();
        
        $parent_col = $this->parent_col;
        if($id == NULL) {
            $current_node = $this->get_node($lft);
            $id = $current_node->$parent_col;
        }
            
        $this->db->select("COUNT({$this->id_col}) AS num",FALSE);
        $this->db->where($this->parent_col, $id);
        $this->db->limit(1);

        $query = $this->db->get($this->table);
        $result = $query->result();
        
        $result = $result->row_array();
        return $result['num'];
    }

Or another MPTree's approach WITHOUT a parent_id field:

Code:

function AR_from_children_of($lft,$rgt){
        // Circumvent the db escaping to enable a subquery
        $this->db->ar_from[] = "(SELECT node.*, (COUNT(parent.{$this->id_col}) - (sub_tree.depth + 1)) AS depth
FROM {$this->tree_table} AS node,
    {$this->tree_table} AS parent,
    {$this->tree_table} AS sub_parent,
    (
        SELECT node.{$this->id_col}, (COUNT(parent.{$this->id_col}) - 1) AS depth
        FROM {$this->tree_table} AS node,
        {$this->tree_table} AS parent
        WHERE node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{$this->left_col} = {$lft}
        GROUP BY node.{$this->id_col}
        ORDER BY node.{$this->left_col}
    )AS sub_tree
WHERE node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{$this->left_col} BETWEEN sub_parent.{$this->left_col} AND sub_parent.{$this->right_col}
    AND sub_parent.{$this->id_col} = sub_tree.{$this->id_col}
GROUP BY node.{$this->id_col}
HAVING depth = 1
ORDER BY node.{$this->left_col}) as child";
    }

Versus an approach with parent_id field:

Code:

function AR_from_children_of($lft,$rgt,$id = NULL){
    
        $parent_col = $this->parent_col;
        if($id == NULL) {
            $current_node = $this->get_node($lft);
            $id = $current_node->$id_col;
        }
        // Circumvent the db escaping to enable a subquery
        $this->db->ar_from[] = "(SELECT * FROM {$this->tree_table}
WHERE {$this->parent_col} > $id AND {$this->left_col} > $lft AND {$this->right_col} < $rgt
ORDER BY {$this->left_col} ASC) as descendant";
    }

I highly recommend to use a parent_id field. It just makes things much easier.
And the MySQL queries should also get a significant performance boost in some cases.

[eluser]TheLoops[/eluser]
And now why to add an nlevel field:

Just compare these functions for getting "A node's descendants for up to 3 levels in depth":

A MPTree-like approach WITHOUT an nlevel field:

Code:

function get_descendants_within_depth($lft,$rgt,$dpth){
        if($rgt - $lft < 3) // leaf node, 3 here because of the possibility of a gap (4 = have children)
            return array();
            
        $result = $this->db->query(
"SELECT node.*
FROM {$this->tree_table} AS node,
    {$this->tree_table} AS parent,
    {$this->tree_table} AS sub_parent,
    (
    SELECT node.{$this->id_col}, (COUNT(parent.{$this->id_col}) - 1) AS depth
        FROM {$this->tree_table} AS node,
            {$this->tree_table} AS parent
        WHERE node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
            AND node.{$this->left_col} = {$lft}
        GROUP BY node.{$this->id_col}
        ORDER BY node.{$this->left_col}
    )AS sub_tree
WHERE (COUNT(parent.{$this->id_col}) - (sub_tree.depth + 1)) <= {$dpth} AND node.{$this->left_col} BETWEEN parent.{$this->left_col} AND parent.{$this->right_col}
    AND node.{$this->left_col} BETWEEN sub_parent.{$this->left_col} AND sub_parent.{$this->right_col}
    AND sub_parent.{$this->id_col} = sub_tree.{$this->id_col}
GROUP BY node.{$this->id_col}
HAVING depth > 0
ORDER BY node.{$this->left_col};");
        return $result->num_rows() ? $result->result_array() : array();
    }

Versus an approach WITH an nlevel field:

Code:

function get_descendants_within_depth($lft,$rgt,$dpth){
        if($rgt - $lft < 3) // leaf node, 3 here because of the possibility of a gap (4 = have children)
            return array();
        $level_col = $this->level_col;
        $current_node = $this->get_node($lft);
        $result = $this->MPTtree->get_descendants_where($lft,$rgt,array("{$this->level_col} <=" => $current_node->$level_col + $dpth));
        return $result;
    }

[eluser]m4rw3r[/eluser]
How about get_parents()?
And xpath()?
And descendants()?
move and delete?

There are a lot of recursive queries there. Everything involving more than two levels next to each other would be more complicated. Plus you loose the order of the nodes and you store the same data in two places.

Some queries would be faster, but others would be a lot slower (ex. traversing the tree).

I could make a convert2adjacency_list() method, and another which does the opposite. And I'll look at those you painted in red, but I can't promise all of them. (I'll also look at that with matchbox).

Thanks for the feedback!

[eluser]TheLoops[/eluser]
[quote author="m4rw3r" date="1211004097"]How about get_parents()?
And xpath()?
And descendants()?
move and delete?[/quote]
Well, you're right parent_id doesn't help everywhere. But I did not ask you to get rid of nleft and nright.
I just asked you to add an additional parent_id and nlevel field to optimize certain sql queries that would be way too complex without it, imho.
get_parents() cannot get improved from how it is right now. Same for descendants(). Just keep them the way they are.
And for move & delete:
Move -> parent_id would only need to be updated once a node leaves its current parent. (nlevel would even stay the same until the node changes its parent AND level)
Delete -> the node just vanishes, so no need to update its parent_id or nlevel at all.

[quote author="m4rw3r" date="1211004097"] There are a lot of recursive queries there. Everything involving more than two levels next to each other would be more complicated. Plus you loose the order of the nodes and you store the same data in two places.

Some queries would be faster, but others would be a lot slower (ex. traversing the tree).[/quote]Well, as I said, take parent_id and nlevel as additional fields. Wherever parent_id or nlevel is of no help, the functions just stay the way they are right now. ;-) And having duplicate ID data in an additional field might be a (pretty damn small) overhead in case of memory, but it's definitely worth it, I think.

[quote author="m4rw3r" date="1211004097"]I could make a convert2adjacency_list() method, and another which does the opposite.[/quote]Not sure what you mean.
[quote author="m4rw3r" date="1211004097"]And I'll look at those you painted in red, but I can't promise all of them. (I'll also look at that with matchbox).[/quote]Thanks.

[eluser]m4rw3r[/eluser]
I could try to implement a hybrid of Modified Preorder Tree Traversal (lft and rgt) and Adjacency List (parent_id and level) (I will probably add it as an option to MPTtree).

About the getDescendantsCounts() and getChildrenCount(), should they really return an int? I believe you can use count_descendants() / count_children() otherwise, if you only need an int in return.

And the is_descendant_of() and is_child_of() I'll probably implement in the ORM, it seems more fitting there.

Haven't checked this with matchbox, haven't really used matchbox before, but I'll look into it (got some work with school, so it may take some time before I have time to do anything of those above).

[eluser]TheLoops[/eluser]
[quote author="m4rw3r" date="1211041197"]I could try to implement a hybrid of Modified Preorder Tree Traversal (lft and rgt) and Adjacency List (parent_id and level) (I will probably add it as an option to MPTtree).[/quote]That would be great. (else I'd have to hack it in myelf ;-P )

[quote author="m4rw3r" date="1211041197"]About the getDescendantsCounts() and getChildrenCount(), should they really return an int? I believe you can use count_descendants() / count_children() otherwise, if you only need an int in return.[/quote]Well, the benefit of this method is that you do not need to run an sql query for each and every node. And having a descendants-count at hand is very handy in many situations.

[quote author="m4rw3r" date="1211041197"]And the is_descendant_of() and is_child_of() I'll probably implement in the ORM, it seems more fitting there.[/quote]Right.

[quote author="m4rw3r" date="1211041197"]Haven't checked this with matchbox, haven't really used matchbox before, but I'll look into it (got some work with school, so it may take some time before I have time to do anything of those above).[/quote]Matchbox replaces (replacing, no subclassing!) the CI_Loader with its own enhanced class. And this crashes MPTree. Dunno why, though.