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

Data Extraction Functions

Next up is writing the functions to extract the data from the tree.

Fetching a single node

This function returns the data for a single node. You may have use for this outside the class, but it is primarily used in other functions to find out nleft and nright data to search on for fetching larger portions of the tree (you will see this later in the other functions).

Listing 4 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Fetch the node data for the node identified by $id
         *
         * @param   int     $id     The ID of the node to fetch
         * @return  object          An object containing the node's
         *                          data, or null if node not found
         */
        function getNode($id)
        {
            $query = sprintf('select %s from %s where %s = %d', join(',', $this->_getFields()),
                                                                $this->table,
                                                                $this->fields['id'],
                                                                $id);
 
            $result = pg_query($query);
            if ($row = pg_fetch_object($result))
                return $row;
            return null;
        }
 
        // ... other code ...
    }
?>

All this function does is search the table for the given ID, returning the data if found, or null if not found.

Fetching portions of the tree

Next up is a function to retrieve larger portions of the tree. We can combine a number of features into the one function. For example, in this one function we’ll be able to retrieve the entire tree, a node’s descendants, or a node’s children.

Additionally, we’ll add an option to allows us to include the node in question as well as all it’s child/descendant data if required (there are certain occasions where it is useful to be able to do this).

Listing 5 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Fetch the descendants of a node, or if no node is specified, fetch the
         * entire tree. Optionally, only return child data instead of all descendant
         * data.
         *
         * @param   int     $id             The ID of the node to fetch descendant data for.
         *                                  Specify an invalid ID (e.g. 0) to retrieve all data.
         * @param   bool    $includeSelf    Whether or not to include the passed node in the
         *                                  the results. This has no meaning if fetching entire tree.
         * @param   bool    $childrenOnly   True if only returning children data. False if
         *                                  returning all descendant data
         * @return  array                   The descendants of the passed now
         */
        function getDescendants($id = 0, $includeSelf = false, $childrenOnly = false)
        {
            $idField = $this->fields['id'];
 
            $node = $this->getNode($id);
            if (is_null($node)) {
                $nleft = 0;
                $nright = 0;
                $parent_id = 0;
            }
            else {
                $nleft = $node->nleft;
                $nright = $node->nright;
                $parent_id = $node->$idField;
            }
 
            if ($childrenOnly) {
                if ($includeSelf) {
                    $query = sprintf('select %s from %s where %s = %d or %s = %d order by nleft',
                                     join(',', $this->_getFields()),
                                     $this->table,
                                     $this->fields['id'],
                                     $parent_id,
                                     $this->fields['parent'],
                                     $parent_id);
                }
                else {
                    $query = sprintf('select %s from %s where %s = %d order by nleft',
                                     join(',', $this->_getFields()),
                                     $this->table,
                                     $this->fields['parent'],
                                     $parent_id);
                }
            }
            else {
                if ($nleft > 0 && $includeSelf) {
                    $query = sprintf('select %s from %s where nleft >= %d and nright <= %d order by nleft',
                                     join(',', $this->_getFields()),
                                     $this->table,
                                     $nleft,
                                     $nright);
                }
                else if ($nleft > 0) {
                    $query = sprintf('select %s from %s where nleft > %d and nright < %d order by nleft',
                                     join(',', $this->_getFields()),
                                     $this->table,
                                     $nleft,
                                     $nright);
                }
                else {
                    $query = sprintf('select %s from %s order by nleft',
                                     join(',', $this->_getFields()),
                                     $this->table);
                }
            }
 
            $result = pg_query($query);
 
            $arr = array();
            while ($row = pg_fetch_object($result)) {
                $arr[$row->$idField] = $row;
            }
 
            return $arr;
        }
 
 
        // ... other code ...
    }
?>

This function might seem a bit daunting, because of all the different functionality it provides, but I’ll now go over it:

Firstly, we try to fetch the node data. If the node isn’t found, we set the parent_id to 0 and the nleft and nright values to 0. The parent_id is set to 0 because top level nodes (i.e. those without a parent) have their parent_id field set to 0. The nleft and nright are set to 0 because nodes in our nested tree don’t use values of 0 for these fields. That way, by testing if these values are 0, we know whether or not to use them.

Next up, there are five different SQL queries:

  1. This fetches all nodes that have parent_id set to the passed in node’s ID. In the case of an invalid node being passed, this will search for a parent_id of 0, which will pick up all the first level nodes. Also, this will select the passed in node with all its children.
  2. This does the same as the previous query, but doesn’t include the passed in node.
  3. This query selects all the nodes below the passed in node. It does this by checking that its nleft is greater than the node’s, and nright is less than the node's. The reason we use a “greater than or equals” and “less than or equals” is because the includeSelf option is set, meaning it should return the passed in node too.
  4. This query is identical to the above query, except it uses “greater than” and “less than” (i.e. without the “or equal”), since it is not including the passed in node.
  5. This query is fetching the same data as the previous two nodes, except the passed in node was not found, so it has to return the entire table, hence we don’t need to search on the nleft and nright values.

If this doesn’t make sense, refer to part one in this series as it covers the theory behind searching on nleft/nright values.

The array of data that was found is then returned.

On a final note, we index the array with the value of the ID. This comes down to personal preference – I do this because it’s easy to quickly find a row of data in the array, without having to search the entire array.

An extra utility function

We can provide a wrapper to the above getDescendants() function to just fetch children. You may prefer not to do this but it just gives the class a cleaner interface.

Listing 6 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Fetch the children of a node, or if no node is specified, fetch the
         * top level items.
         *
         * @param   int     $id             The ID of the node to fetch child data for.
         * @param   bool    $includeSelf    Whether or not to include the passed node in the
         *                                  the results.
         * @return  array                   The children of the passed node
         */
        function getChildren($id = 0, $includeSelf = false)
        {
            return $this->getDescendants($id, $includeSelf, true);
        }
 
 
        // ... other code ...
    }
?>

Fetching a node’s path

This function allows us to fetch all the nodes that lead down to a specified node. You can see an example of the results from this by looking at the breadcrumbs navigation for PhpRiot.

It’s amazing with the nested tree model how easy this is – it’s just a matter of negating the test on the nleft and nright data (compared to the getDescendants() method)!

Listing 7 NestedTree.class.php
<?php
    class NestedTree
    {
        // ... other code ...
 
        /**
         * Fetch the path to a node. If an invalid node is passed, an empty array is returned.
         * If a top level node is passed, an array containing on that node is included (if
         * 'includeSelf' is set to true, otherwise an empty array)
         *
         * @param   int     $id             The ID of the node to fetch child data for.
         * @param   bool    $includeSelf    Whether or not to include the passed node in the
         *                                  the results.
         * @return  array                   An array of each node to passed node
         */
        function getPath($id = 0, $includeSelf = false)
        {
            $node = $this->getNode($id);
            if (is_null($node))
                return array();
 
            if ($includeSelf) {
                $query = sprintf('select %s from %s where nleft <= %d and nright >= %d order by nlevel',
                                 join(',', $this->_getFields()),
                                 $this->table,
                                 $node->nleft,
                                 $node->nright);
            }
            else {
                $query = sprintf('select %s from %s where nleft < %d and nright > %d order by nlevel',
                                 join(',', $this->_getFields()),
                                 $this->table,
                                 $node->nleft,
                                 $node->nright);
            }
 
            $result = pg_query($query);
 
            $arr = array();
            while ($row = pg_fetch_object($result)) {
                $arr[$row->$idField] = $row;
            }
 
            return $arr;
        }
 
        // ... other code ...
    }
?>

As you can see this works very similarly to getDescendants(), except the nleft and nright tests are changed. The difference between the two queries here are based on whether to include the passed node.

In my experience, you will generally set $includeSelf to true when using this function.

In This Article