Subversion Repositories phpLibraryV2

<?php

include_once( 'DBQuery.class.php' );

/* 

   class reads a database table and converts it to an Hierarchical hash (aka, parent/child).

   Table structure is assume to be:

      create table menu (

         id        int unsigned not null,

         parent_id int unsigned not null default 0,

         other columns below

      )

   where id is a unique identifier and parent_id is points to id in another row (zero indicating it is a top level)

   NOTE: column names may be changed. Also, while it is assumed id and parent_id are int's, it is quite likely it will

         work with other column types, including varchar

   Uses include any parent/child relationship, to an arbitrary depth. See class DBMenu for one example

   This class was written to be generic. The algorithm used attempts to not take advantage of any special language 

   capabilities, and should be generic. However, various languages can optimize this capability by using capabilities unique

   to the language in question. For an example, see David North's PERL implementation which utilizes references to allow for

   a single pass to convert from an array to a Hierarchical structure. Taking advantage of this allows his script to run

   use no additional memory (this algorithm will double the amount of memory used for the initial array) and does in a single

   iterative pass what the recursive function copyChildren does.

*/

class DBHierarchicalHash {

   protected $tableName; // table name that data will be read from

   protected $keyField;  // name of the primary id field in table

   protected $parentFieldName; // name of the field used to point to the parent of the current row

   protected $rootNodevalue; // the value (default 0) of the indicator that a row has no parent. THIS MUST NOT EXIST in the id column of the table

   protected $inputRecords; // storage for the records read in.

   public function __construct( $tableName, $keyField = 'id', $parentFieldName = 'parent_id', $rootNodeValue = 0 ) {

      // standard variable load

      $this->tableName = $tableName;

      $this->keyField = $keyField;

      $this->parentFieldName = $parentFieldName;

      $this->rootNodevalue = $rootNodeValue;

      // load the data from the database into memory

      // upon completion, will have data in a single hash of hashes (not hiearchy)

      // will also create an emtpy entry for "element 0"

      $this->loadData();

      // find the children of each node

      $this->findChildren();

      // now that we know who all the children are, let's actually make them part of the structure

      $this->inputRecords = $this->copyChildren($this->inputRecords[$this->rootNodevalue]);

      // all we care about are the children of the root node, so simply assign that to inputRecords

      $this->inputRecords = $this->inputRecords['children'];

   } // function __construct

   /*

      Goes through each node and reverses the "who is my parent" to the parent's "who are my children"

      It does not populate the children; it simply creates an empty array for each child to be processed

      later.

   */

   private function findChildren () {

      // following loop takes inputRecords and creates (empty) elements for each child

      foreach ($this->inputRecords as $key => $values) { // go through every node

         if ( isset ($this->inputRecords[$key][$this->parentFieldName]) ) { // if it has a parent

            // tell parent about itself

            $this->inputRecords[$values[$this->parentFieldName]]['children'][$key] = array();

         }

      }

   } // function findChildren

   /* 

      simply returns inputRecords for processing by calling routine. This is the goal of this class, to create

      this structure from the database structure defined above

   */

   public function toHash () {

      return $this->inputRecords;

   } // function toHash

   /* 

      loads data from database. The column defined in $this->keyField will become the index into the hash, and all

      additional columns will simply be added to the array pointed by it.

      An additional entry in the table will be created with $this->rootNodeValue as its index, to allow root level

      items to have a parent.

   */

   private function loadData ( ) {

      $inputRows = new DBQuery( "select * from $this->tableName" );

      $inputRows->run();

//      $inputRows = $inputRows['data']; // we only care about the data

      $this->inputRecords = array(); // initialize inputRecords to empty

      // main loop, will read the query results in one row at a time

      foreach ( $inputRows->returnData as $thisRow ) {

         foreach ($thisRow as $key => $values) { // copy each value

            if ($key != $this->keyField) { // unless it is the key field

               // this is more complex as a parent of null might be used. Thus, we check for a null and, if

               // it is used, we set it to the rootNodeValue

               if ($key == $this->parentFieldName && ! $thisRow[$key] ) {

                  $this->inputRecords[$thisRow[$this->keyField]][$key] = $this->rootNodevalue;

               } else {

                  $this->inputRecords[$thisRow[$this->keyField]][$key] = $thisRow[$key];

               }

            }

         }

      }

      $this->inputRecords[$this->rootNodevalue] = array(); // create our empty root node

   } // function loadData

   # populates the hiearchy created in load

   # NOTE: if the current node also has children, it will recursively do those

   # main call is &copyChildren( rootNode )

   private function copyChildren($currentNode) {

      # for each child

      //print "Looking at: "; print_r($currentNode);

      if ( isset($currentNode['children']) ) {

         foreach ($currentNode['children'] as $key => $values) {

            # copy any children of this child table that may exist

            $this->inputRecords[$key] = $this->copyChildren( $this->inputRecords[$key] );

            # copy each value from the node to this sub-node

            foreach ($this->inputRecords[$key] as $child => $childValue) {

               if ($child != $this->parentFieldName ) {

                  $currentNode['children'][$key][$child] = $childValue;

               }

            }

         }

      }

      return $currentNode;

   } // function copyChildren

} // class DBHierarchicalHash

?>