PhpRiot
Become Zend Certified

Prepare for the ZCE exam using our quizzes (web or iPad/iPhone). More info...


When you're ready get 7.5% off your exam voucher using voucher CJQNOV23 at the Zend Store

Implementing An N-Level Nested Tree In PHP And PostgreSQL, Part 2

Some Utility Functions

Here are a few functions that are used to find out various metadata about the tree.

Check if a node descends from another node

This function checks if one node descends from another node.

Listing 8 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Check if one node descends from another node. If either node is not
         * found, then false is returned.
         *
         * @param   int     $descendant_id  The node that potentially descends
         * @param   int     $ancestor_id    The node that is potentially descended from
         * @return  bool                    True if $descendant_id descends from $ancestor_id, false otherwise
         */
        function isDescendantOf($descendant_id, $ancestor_id)
        {
            $node = $this->getNode($ancestor_id);
            if (is_null($node))
                return false;
 
            $query = sprintf('select count(*) as is_descendant
                                  from %s
                                  where %s = %d
                                  and nleft > %d
                                  and nright < %d',
                             $this->table,
                             $this->fields['id'],
                             $descendant_id,
                             $node->nleft,
                             $node->nright);
 
            $result = pg_query($query);
 
            if ($row = pg_fetch_object($result)) {
                return $row->is_descendant > 0;
            }
 
            return false;
        }
 
        // ... other code ...
    }
?>

Check if a node is a child of another another node

This function checks if one node is a child of another node.

Listing 9 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Check if one node is a child of another node. If either node is not
         * found, then false is returned.
         *
         * @param   int     $child_id       The node that is possibly a child
         * @param   int     $parent_id      The node that is possibly a parent
         * @return  bool                    True if $child_id is a child of $parent_id, false otherwise
         */
        function isChildOf($child_id, $parent_id)
        {
            $query = sprintf('select count(*) as is_child from %s where %s = %d and %s = %d',
                             $this->table,
                             $this->fields['id'],
                             $child_id,
                             $this->fields['parent'],
                             $parent_id);
 
            $result = pg_query($query);
 
            if ($row = pg_fetch_object($result)) {
                return $row->is_child > 0;
            }
 
            return false;
        }
 
        // ... other code ...
    }
?>

Find the number of descendants a node has

Using the nleft and nright values of a node, we can determine how many descendants it has. Remembering from the first article in this series, we can determine this using (nright – nleft – 1) / 2.

Listing 10 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Find the number of descendants a node has
         *
         * @param   int     $id     The ID of the node to search for. Pass 0 to count all nodes in the tree.
         * @return  int             The number of descendants the node has, or -1 if the node isn't found.
         */
        function numDescendants($id)
        {
            if ($id == 0) {
                $query = sprintf('select count(*) as num_descendants from %s', $this->table);
                $result = pg_query($query);
                if ($row = pg_fetch_object($result))
                    return (int) $row->num_descendants;
            }
            else {
                $node = $this->getNode($id);
                if (!is_null($node)) {
                    return ($node->nright - $node->nleft - 1) / 2;
                }
            }
            return -1;
        }
 
        // ... other code ...
    }
?>

Finding the number of children a node has is also fairly simple – all we need to do is count the number of nodes that have a parent_id equal to the ID of the passed node.

Listing 11 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Find the number of children a node has
         *
         * @param   int     $id     The ID of the node to search for. Pass 0 to count the first level items
         * @return  int             The number of descendants the node has, or -1 if the node isn't found.
         */
        function numChildren($id)
        {
            $query = sprintf('select count(*) as num_children from %s where %s = %d',
                             $this->table,
                             $this->fields['parent'],
                             $id);
            $result = pg_query($query);
            if ($row = pg_fetch_object($result))
                return (int) $row->num_children;
 
            return -1;
        }
 
        // ... other code ...
    }
?>

Whew. Now that we’ve gotten through all that – we just need the write the functions that build the tree data! Mind you, these are probably the most complicated functions in class. Anyway, on to it…

In This Article