MPTtree, Hieararchical trees in a database table

[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.