Implementing An N-Level Nested Tree In PHP And PostgreSQL, Part 2
Tree Building Functions
The final set of functions we need to implement are the functions that build the tree data. That is, they generate the nleft, nright and nlevel values. For all sibling nodes (i.e. nodes with the same parent), we order them using the sort field you passed into the constructor.
First things first
We need to introduce a new function here that extracts tree data. The difference between this function and the getDescendants() function is that this one does extra processing to store within each node a reference to each child node.
We won’t implement the same extended functionality here as getDescendants(), but if you find this function useful, you may want to implement this functionality (i.e. changing it so you can fetch the descendants of any node instead of the entire tree).
Additionally, here is where we sort the data by the passed in sort field.
class NestedTree { // ... other code ... /** * Fetch the tree data, nesting within each node references to the node's children * * @return array The tree with the node's child data */ function getTreeWithChildren() { $idField = $this->fields['id']; $parentField = $this->fields['parent']; $query = sprintf('select %s from %s order by %s', join(',', $this->_getFields()), $this->table, $this->fields['sort']); $result = pg_query($query); // create a root node to hold child data about first level items $root = new stdClass; $root->$idField = 0; $root->children = array(); $arr = array($root); // populate the array and create an empty children array while ($row = pg_fetch_object($result)) { $arr[$row->$idField] = $row; $arr[$row->$idField]->children = array(); } // now process the array and build the child data foreach ($arr as $id => $row) { if (isset($row->$parentField)) $arr[$row->$parentField]->children[$id] = $id; } return $arr; } // ... other code ... }
The last line might look a bit complicated. We’re using “variable variables” here as in other parts of the class, as it makes the class much more reusable as we don’t have to hard-code the column names.
Basically in that line, we’re looping over each element in the array, finding its parent_id, and adding the item’s ID to children array of that parent.
Get it? Good!
Generating and saving the tree data
There’s just two more functions to go — one function is our entry point to rebuilding the tree — it generates the tree data using the second function, then runs SQL to update the tree.
The second function is a recursive array which keeps a running track of the nleft/nright value and assigns it to each row.
class NestedTree { // ... other code ... /** * Rebuilds the tree data and saves it to the database */ function rebuild() { $data = $this->getTreeWithChildren(); $n = 0; // need a variable to hold the running n tally $level = 0; // need a variable to hold the running level tally // invoke the recursive function. Start it processing // on the fake "root node" generated in getTreeWithChildren(). // because this node doesn't really exist in the database, we // give it an initial nleft value of 0 and an nlevel of 0. $this->_generateTreeData($data, 0, 0, $n); // at this point the the root node will have nleft of 0, nlevel of 0 // and nright of (tree size * 2 + 1) foreach ($data as $id => $row) { // skip the root node if ($id == 0) continue; $query = sprintf('update %s set nlevel = %d, nleft = %d, nright = %d where %s = %d', $this->table, $row->nlevel, $row->nleft, $row->nright, $this->fields['id'], $id); pg_query($query); } } /** * Generate the tree data. A single call to this generates the n-values for * 1 node in the tree. This function assigns the passed in n value as the * node's nleft value. It then processes all the node's children (which * in turn recursively processes that node's children and so on), and when * it is finally done, it takes the update n-value and assigns it as its * nright value. Because it is passed as a reference, the subsequent changes * in subrequests are held over to when control is returned so the nright * can be assigned. * * @param array &$arr A reference to the data array, since we need to * be able to update the data in it * @param int $id The ID of the current node to process * @param int $level The nlevel to assign to the current node * @param int &$n A reference to the running tally for the n-value */ function _generateTreeData(&$arr, $id, $level, &$n) { $arr[$id]->nlevel = $level; $arr[$id]->nleft = $n++; // loop over the node's children and process their data // before assigning the nright value foreach ($arr[$id]->children as $child_id) { $this->_generateTreeData($arr, $child_id, $level + 1, $n); } $arr[$id]->nright = $n++; } // ... other code ... }
These functions are somewhat complicated. Rather than reiterating what the comments say, it might be best just to study those comments, and if you’re not familiar with references or recursive functions, try to understand these as not understanding these will make the above functions difficult to understand.