[Sommaire] [Imprimer]

   1  <?php
   2  // +-----------------------------------------------------------------------+
   3  // | Copyright (c) 2002-2003, Richard Heyes                                |
   4  // | All rights reserved.                                                  |
   5  // |                                                                       |
   6  // | Redistribution and use in source and binary forms, with or without    |
   7  // | modification, are permitted provided that the following conditions    |
   8  // | are met:                                                              |
   9  // |                                                                       |
  10  // | o Redistributions of source code must retain the above copyright      |
  11  // |   notice, this list of conditions and the following disclaimer.       |
  12  // | o Redistributions in binary form must reproduce the above copyright   |
  13  // |   notice, this list of conditions and the following disclaimer in the |
  14  // |   documentation and/or other materials provided with the distribution.|
  15  // | o The names of the authors may not be used to endorse or promote      |
  16  // |   products derived from this software without specific prior written  |
  17  // |   permission.                                                         |
  18  // |                                                                       |
  19  // | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS   |
  20  // | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT     |
  21  // | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
  22  // | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT  |
  23  // | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
  24  // | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT      |
  25  // | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
  26  // | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
  27  // | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT   |
  28  // | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
  29  // | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.  |
  30  // |                                                                       |
  31  // +-----------------------------------------------------------------------+
  32  // | Author: Richard Heyes <richard@phpguru.org>                           |
  33  // +-----------------------------------------------------------------------+
  34  
  35  /**
  36  * An OO tree class based on various things, including the MS treeview control
  37  * If you use this class and wish to show your appreciation then visit my
  38  * wishlist here:   http://www.amazon.co.uk/exec/obidos/wishlist/S8H2UOGMPZK6
  39  *
  40  * Structure of one of these trees:
  41  *
  42  *  Tree Object
  43  *    |
  44  *    +- Tree_NodeCollection object (nodes property)
  45  *          |
  46  *          +- Array of Tree_Node objects (nodes property)
  47  *
  48  * Usage:
  49  *   $tree = &new Tree();
  50  *   $node  = &$tree->nodes->addNode(new Tree_Node('1'));
  51  *   $node2 = &$tree->nodes->addNode(new Tree_Node('2'));
  52  *   $node3 = &$tree->nodes->addNode(new Tree_Node('3'));
  53  *   $node4 = &$node3->nodes->addNode(new Tree_Node('3_1'));
  54  *   $tree->nodes->removeNodeAt(0);
  55  *   print_r($tree);
  56  * 
  57  * The data for a node is supplied by giving it as the argument to the Tree_Node
  58  * constructor. You can retreive the data by using a nodes getTag() method, and alter
  59  * it using the setTag() method.
  60  *
  61  * Public methods for Tree class:
  62  *   hasChildren()                                            Returns whether this tree has child nodes or not
  63  *   &createFromList(array data [, string separator])         (static) Returns a tree structure create from the supplied list
  64  *   &createFromMySQL(array $params)                          (static) Returns a tree structure created using a common DB storage technique
  65  *   &createFromXMLTree(object $xmlTree [, bool $ignoreRoot]) (static) Returns a tree structure created using an PEAR::XML_Tree object
  66  *   &merge(object &$tree [, ...])                            Merges two or more Tree/Tree_Node objects. Can be used statically or not.
  67  *
  68  * Public methods for Tree_Node class:
  69  *   setTag(mixed tag)                                 Sets the tag data
  70  *   getTag()                                          Retreives the tag data
  71  *   &prevSibling()                                    Retreives a reference to the previous sibling node
  72  *   &nextSibling()                                    Retreives a reference to the next sibling node
  73  *   remove()                                          Removes this node from the collection
  74  *   &getTree()                                        Returns the encompassing Tree object
  75  *   &getParent()                                      Returns the parent Tree_Node object if any
  76  *   hasChildren()                                     Returns whether this node has child nodes or not
  77  *   depth()                                           Returns the depth of this node in the tree (zero based)
  78  *   isChildOf()                                       Returns whether this node is a direct child of the given node/tree
  79  *   moveTo()                                          Moves this node to be a child of the given node/tree
  80  *   copyTo()                                          Copies this node to a new child of the given node/tree
  81  *   
  82  * Public variables for Tree_Node class:
  83  *   $nodes
  84  *
  85  * Public methods for Tree_NodeCollection class:
  86  *   &addNode(Tree_Node node)                           Adds a node to the collection
  87  *   &firstNode()                                       Retreives a reference to the first node in the collection
  88  *   &lastNode()                                        Retreives a reference to the last node in the collection
  89  *   &removeNodeAt(int index)                           Removes the node at the specified index (nodes are re-ordered)
  90  *   removeNode(Tree_Node node [, boolean search])      Removes the given node (nodes are re-ordered)
  91  *   indexOf(Tree_Node node)                            Retreives the index of the given node
  92  *   getNodeCount([boolean recurse])                    Retreives the number of nodes in the collection, optionally recursing
  93  *   getFlatList()                                      Retrieves an indexed array of the nodes from top to bottom, left to right
  94  *   traverse(callback function)                        Traverses the tree supply each node to the callback function
  95  *   search(mixed searchData [, bool strict])           Basic search function for searching the Trees' "tag" data
  96  *   moveTo()                                           Moves the nodes in this collection to the given node/tree
  97  *   copyTo()                                           Copies the nodes in this collection to the given node/tree
  98  */
  99  
 100  class Tree
 101  {
 102      /**
 103      * UID counter
 104      * @var integer
 105      */
 106      var $uidCounter;
 107      
 108      /**
 109      * Child nodes
 110      * @var object
 111      */
 112      var $nodes;
 113  
 114      /**
 115      * Content hash
 116      * @var array
 117      */
 118      var $content;
 119  
 120      /**
 121      * Constructor
 122      */
 123      function Tree()
 124      {
 125          $this->nodes = new Tree_NodeCollection($this);
 126          $this->uidCounter = 0;
 127          $this->content = array();
 128      }
 129  
 130      function &getRootNode()
 131      {
 132          return $this;
 133      }
 134      
 135  	function getChildrenCount()
 136      {
 137          return count($this->nodes->nodes);
 138      }
 139      
 140      function &getNodeByID($id)
 141      {
 142          $result = null;
 143          if ($id)
 144          {
 145              debug_buffer('start findNodeByTag');
 146              $ref = null;
 147              $result =& $this->findNodeByTag($id, $ref);
 148              debug_buffer('end findNodeByTag');
 149          }
 150          return $result;
 151      }
 152      
 153      function &sureGetNodeByID($id)
 154      {
 155          return $this->getNodeByID($id);
 156      }
 157      
 158      function &getNodeByAlias($alias)
 159      {
 160          $result = null;
 161          global $gCms;
 162          $contentops =& $gCms->GetContentOperations();
 163          $id = $contentops->GetPageIDFromAlias($alias);
 164          if ($id)
 165          {
 166              $result =& $this->getNodeById($id);
 167          }
 168          return $result;
 169      }
 170      
 171      function &sureGetNodeByAlias($alias)
 172      {
 173          return $this->getNodeByAlias($alias);
 174      }
 175      
 176      function &getNodeByHierarchy($position)
 177      {
 178          $result = null;
 179          global $gCms;
 180          $contentops =& $gCms->GetContentOperations();
 181          $id = $contentops->GetPageIDFromHierarchy($position);
 182          if ($id)
 183          {
 184              $result =& $this->getNodeById($id);
 185          }
 186          return $result;
 187      }
 188      
 189      /**
 190      * Returns true/false as to whether this node
 191      * has any child nodes or not.
 192      *
 193      * @return bool Any child nodes or not
 194      */
 195  	function hasChildren()
 196      {
 197          return !empty($this->nodes->nodes);
 198      }
 199      
 200      /**
 201      * Returns all the child nodes for this
 202      * node.
 203      *
 204      * @return array All of the child nodes
 205      */
 206      function &getChildren()
 207      {
 208          return $this->nodes->nodes;
 209      }
 210      
 211      function &getFlatList()
 212      {
 213          return $this->nodes->getFlatList();
 214      }
 215      function &getFlattenedChildren()
 216      {
 217          return $this->nodes->getFlatList();
 218      }
 219      
 220      /**
 221      * Returns a node anywhere in the tree given a tag name.
 222      * A null is returned if the node isn't found.
 223      * 
 224      * @return object The found node
 225      */
 226      function &findNodeByTag($tagname, &$col)
 227      {
 228          if ($col == null)
 229              $col = $this;
 230          
 231          $result = null;
 232          
 233          for ($i = 0; $i < count($col->nodes->nodes); $i++)
 234          {
 235              if ($col->nodes->nodes[$i]->getTag() == $tagname)
 236                  return $col->nodes->nodes[$i];
 237              $result =& $this->findNodeByTag($tagname, $col->nodes->nodes[$i]);
 238              if ($result)
 239                  break;
 240          }
 241          
 242          return $result;
 243      }
 244      
 245      /**
 246      * Creates a tree structure from a list of items.
 247      * Items must be separated using the supplied separator.
 248      * Eg:    array('foo',
 249      *              'foo/bar',
 250      *              'foo/bar/jello',
 251      *              'foo/bar/jello2',
 252      *              'foo/bar2/jello')
 253      *
 254      * Would create a structure thus:
 255      *   foo
 256      *    +-bar
 257      *    |  +-jello
 258      *    |  +-jello2
 259      *    +-bar2
 260      *       +-jello
 261      * 
 262      * Example code:
 263      *   $list = array('Foo/Bar/blaat', 'Foo', 'Foo/Bar', 'Foo/Bar/Jello', 'Foo/Bar/Jello2', 'Foo/Bar2/Jello/Jello2');
 264      *   $tree = Tree::createFromList($list);
 265      *
 266      * @param  array  $data      The list as an indexed array
 267      * @param  string $separator The separator to use
 268      * @return object            A tree structure (Tree object)
 269      */
 270      function &createFromList($data, $separator = '/')
 271      {
 272          $nodeList = array();
 273          $tree     =& new Tree();
 274  
 275          for ($i=0; $i<count($data); $i++) {
 276              $pathParts = explode($separator, $data[$i]);
 277  
 278              // If only one part then add it as a root node if
 279              // it's not already present.
 280              if (count($pathParts) == 1) {
 281                  if (!empty($nodeList[$pathParts[0]])) {
 282                      continue;
 283                  } else {
 284                      $nodeList[$pathParts[0]] = &new Tree_Node(array($pathParts[0], $data[$i]));
 285                      $tree->nodes->addNode($nodeList[$pathParts[0]]);
 286                  }
 287  
 288              // Multiple parts means each part/parent combination
 289              // needs checking to see if it needs adding.
 290              } else {
 291                  $parentObj = &$tree;
 292  
 293                  for ($j=0; $j<count($pathParts); $j++) {
 294                      $currentPath = implode($separator, array_slice($pathParts, 0, $j + 1));
 295                      if (!empty($nodeList[$currentPath])) {
 296                          // Update parent object to be the existing node
 297                          $parentObj = &$nodeList[$currentPath];
 298                          continue;
 299                      } else {
 300                          $nodeList[$currentPath] = &new Tree_Node(array($pathParts[$j], $currentPath));
 301                          // Update parent object to be the new node
 302                          $parentObj = &$parentObj->nodes->addNode($nodeList[$currentPath]);
 303                      }
 304                  }
 305              }
 306          }
 307          
 308          return $tree;
 309      }
 310  
 311      
 312      /**
 313      * Merges two or more tree structures into one. Can take either 
 314      * Tree objects or Tree_Node objects as arguments to merge. This merge
 315      * simply means the nodes from the second+ argument(s) are added to
 316      * the first.
 317      *
 318      * @param object $tree The Tree/Tree_Node object to merge subsequent
 319      *                     Tree/Tree_Node objects with.
 320      * @param ...          Any number of Tree or Tree_Node objects to be merged
 321      *                     with the first argument.
 322      * @return object      Resulting merged Tree/Tree_Node object
 323      */
 324      function &merge(&$tree)
 325      {
 326          $args = func_get_args();
 327          array_shift($args);
 328  
 329          for ($i=0; $i<count($args); $i++) {
 330              for ($j=0; $j<count($args[$i]->nodes->nodes); $j++) {
 331                  $tree->nodes->addNode($args[$i]->nodes->nodes[$j]);
 332              }
 333          }
 334          
 335          return $tree;
 336      }
 337  }
 338  
 339  
 340  /**
 341  * A node class to complement the above
 342  * tree class
 343  */
 344  class Tree_Node
 345  {
 346      /**
 347      * The data that this node holds
 348      * @var mixed
 349      */
 350      var $tag;
 351  
 352      /**
 353      * Parent node
 354      * @var object
 355      */
 356      var $parent;
 357      
 358      /**
 359      * The master Tree object
 360      * @var object
 361      */
 362      var $tree;
 363      
 364      /**
 365      * The nodes collection
 366      * @var object
 367      */
 368      var $nodes;
 369  
 370      /**
 371      * Constructor
 372      *
 373      * @param mixed $tag The data that this node represents
 374      */
 375      function Tree_Node($tag = null)
 376      {
 377          $this->parent = null;
 378          $this->nodes  = new Tree_NodeCollection($this);
 379  
 380          if (!is_null($tag)) {
 381              $this->tag = $tag;
 382          }
 383      }
 384  
 385      /**
 386      * Gets the underlying content of this node
 387      */
 388      function &getContent()
 389      {
 390          //TODO: Lookup node in tree's list
 391          //      Pull it from the db if it's not loaded already
 392          //      Lots of room for optimization here
 393          $content = null;
 394          
 395          $tree =& $this->getTree();
 396          if (isset($tree->content[$this->getTag()]))
 397          {
 398              $content =& $tree->content[$this->getTag()];
 399          }
 400          else
 401          {
 402              //Basic one.  Just try to load it separately
 403              //into our list.  Get the props, since a one timer
 404              //will probably have some property shown
 405              global $gCms;
 406              $contentops =& $gCms->GetContentOperations();
 407              $content =& $contentops->LoadContentFromId($this->getTag(), true);
 408              $tree->content[$this->getTag()] =& $content;
 409          }
 410          return $content;
 411      }
 412      
 413      /**
 414      * Sets the tag data
 415      *
 416      * @param mixed $tag The data to set the tag to
 417      */
 418      function setTag($tag)
 419      {
 420          $this->tag = $tag;
 421      }
 422      
 423      /**
 424      * Returns the tag data
 425      *
 426      * @return mixed The tag data
 427      */
 428      function getTag()
 429      {
 430          return $this->tag[0];
 431      }
 432  
 433      /**
 434      * Sets the nodes UID
 435      * 
 436      * @param integer $uid The UID
 437      */
 438      function setUID(&$uid)
 439      {
 440          $this->uid = ++$uid;
 441  
 442          // Set uid for child nodes
 443          for ($i=0; $i<count($this->nodes->nodes); $i++) {
 444              $this->nodes->nodes[$i]->setUID($uid);
 445          }
 446      }
 447  
 448      /**
 449      * Returns the node UID
 450      * 
 451      * @return integer The UID
 452      */
 453      function getUID()
 454      {
 455          return $this->uid;
 456      }
 457  
 458      /**
 459      * Returns the previous child node in the parents node array,
 460      * or null if this node is the first.
 461      *
 462      * @return object A reference to the previous node in the parent
 463      *                node collection
 464      */
 465      function &prevSibling()
 466      {
 467          if (!empty($this->parent)) {
 468              $parentObj = &$this->parent;
 469          } else {
 470              $parentObj = &$this->tree;
 471          }
 472  
 473          $myIndex = $parentObj->nodes->indexOf($this);
 474  
 475          if ($myIndex > 0) {
 476              return $parentObj->nodes->nodes[$myIndex - 1];
 477          }
 478  
 479          return null;
 480      }
 481  
 482      /**
 483      * Returns the next child node in the parents node array,
 484      * or null if this node is the last.
 485      *
 486      * @return object A reference to the next node in the parent
 487      *                node collection.
 488      */
 489      function &nextSibling()
 490      {
 491          if (!empty($this->parent)) {
 492              $parentObj = &$this->parent;
 493          } else {
 494              $parentObj = &$this->tree;
 495          }
 496  
 497          $myIndex = $parentObj->nodes->indexOf($this);
 498  
 499          if ($myIndex < ($parentObj->nodes->getNodeCount() - 1)) {
 500              return $parentObj->nodes->nodes[$myIndex + 1];
 501          }
 502  
 503          return null;
 504      }
 505  
 506  	function getSiblingCount()
 507      {
 508          if (!empty($this->parent)) {
 509              $parentObj = &$this->parent;
 510          } else {
 511              $parentObj = &$this->tree;
 512          }
 513          
 514          return $parentObj->nodes->getNodeCount();
 515      }
 516      
 517      /**
 518      * Removes this node from its' parent. If this
 519      * node has no parent (ie its not been added to
 520      * a Tree or Tree_Node object) then this method
 521      * will do nothing.
 522      */
 523      function remove()
 524      {
 525          if (!is_null($this->parent)) {
 526              $this->parent->nodes->removeNode($this);
 527          } elseif (!is_null($this->tree)) {
 528              $this->tree->nodes->removeNode($this);
 529          } else {
 530              return false;
 531          }
 532      }
 533  
 534      /**
 535      * Sets the master Tree object for this
 536      * node.
 537      *
 538      * @param object $tree The Tree object reference
 539      */
 540      function setTree(&$tree)
 541      {
 542          $this->tree = &$tree;
 543  
 544          // Set tree for child nodes
 545          for ($i=0; $i<count($this->nodes->nodes); $i++) {
 546              $this->nodes->nodes[$i]->setTree($tree);
 547          }
 548      }
 549      
 550      /**
 551      * Returns the tree object which this node is attached
 552      * to (if any).
 553      *
 554      * @return object The encompassing Tree object
 555      */
 556      function &getTree()
 557      {
 558          return $this->tree;
 559      }
 560  
 561      /**
 562      * Sets the parent node of the node.
 563      *
 564      * @param object $node The parent node
 565      */
 566      function setParent(&$node)
 567      {
 568          $this->parent = &$node;
 569      }
 570      
 571      /**
 572      * Returns the parent node if any
 573      *
 574      * @return object The parent Tree_Node object
 575      */
 576      function &getParent()
 577      {
 578          return $this->parent;
 579      }
 580      
 581      /**
 582      * Returns the parent node if any -- backwards compatible
 583      * with the old hierarchy manager code.
 584      *
 585      * @return object The parent Tree_Node object
 586      */
 587      function &getParentNode()
 588      {
 589          return $this->parent;
 590      }
 591      
 592      /**
 593      * Returns true/false as to whether this node
 594      * has any child nodes or not.
 595      *
 596      * @return bool Any child nodes or not
 597      */
 598  	function hasChildren()
 599      {
 600          return !empty($this->nodes->nodes);
 601      }
 602      
 603      /**
 604      * Returns all the child nodes for this
 605      * node.
 606      *
 607      * @return array All of the child nodes
 608      */
 609      function &getChildren()
 610      {
 611          //TODO: Write a bit here that pulls back all
 612          //children in one shot if they're not already loaded
 613          if ($this->hasChildren()) {
 614              $node =& $this->nodes->nodes[0];
 615              $checkid = $node->getTag();
 616              $tree =& $this->getTree();
 617              if (!isset($tree->content[$checkid])) {
 618                  global $gCms;
 619                  $contentops =& $gCms->GetContentOperations();
 620                  $contentops->LoadChildrenIntoTree($this->getTag(), $this->tree);
 621              }
 622          }
 623          return $this->nodes->nodes;
 624      }
 625      
 626  	function getChildrenCount()
 627      {
 628          return count($this->nodes->nodes);
 629      }
 630      
 631      /**
 632      * Returns the depth in the tree of this node
 633      * This is a zero based indicator, so root nodes
 634      * will have a depth of 0 (zero).
 635      *
 636      * @return integer The depth of the node
 637      */
 638  	function depth()
 639      {
 640          $depth = 0;
 641          $currLevel = &$this;
 642  
 643          while ($currLevel->parent) {
 644              $depth++;
 645              $currLevel = &$currLevel->parent;
 646          }
 647          
 648          return $depth;
 649      }
 650      
 651      /**
 652      * Returns the depth in the tree.  This is to make this backwards
 653      * compatible with the old hierarchy manager.
 654      *
 655      * @return integer The depth of the node.
 656      */
 657  	function getLevel()
 658      {
 659          return $this->depth();
 660      }
 661      
 662      /**
 663      * Returns true/false as to whether this node is a child
 664      * of the given node.
 665      *
 666      * @param  object $parent The suspected parent Tree_Node object
 667      * @return bool           Whether this node is a child of the suspected parent
 668      */
 669  	function isChildOf($parent)
 670      {
 671          return $this->parent->uid === $parent->uid;
 672      }
 673      
 674      /**
 675      * Moves this node to a new parent. All child nodes will
 676      * be retained.
 677      *
 678      * @param object $newParent The new parent Tree_Node or Tree object
 679      */
 680  	function moveTo(&$newParent)
 681      {
 682          // Somewhat nasty code
 683          $newParent->nodes->nodes[] = &$this;
 684  
 685          if ($this->parent) {
 686              unset($this->parent->nodes->nodes[$this->parent->nodes->indexOf($this)]);
 687              $this->parent->nodes->nodes = array_values($this->parent->nodes->nodes);
 688          } else {
 689              unset($this->tree->nodes->nodes[$this->tree->nodes->indexOf($this)]);
 690              $this->tree->nodes->nodes = array_values($this->tree->nodes->nodes);
 691          }
 692  
 693          if (strcasecmp(get_class($newParent), 'Tree_Node') == 0) {
 694              $this->parent = &$newParent;
 695          } else {
 696              unset($this->parent);
 697          }
 698      }
 699      
 700      /**
 701      * Copies this node to a new parent. This copies the node
 702      * to the new parent node/tree and all its child nodes (ie
 703      * a deep copy). Technically, new nodes are created with copies
 704      * of the tag data, since this is for all intents and purposes
 705      * the only thing that needs copying.
 706      *
 707      * @param  object $newParent The new parent Tree_Node or Tree object
 708      * @return object            The new node
 709      */
 710      function &copyTo(&$newParent)
 711      {
 712          $newNode = &$newParent->nodes->addNode(new Tree_node($this->getTag()));
 713  
 714          for ($i=0; $i<count($this->nodes->nodes); $i++) {
 715              $this->nodes->nodes[$i]->copyTo($newNode);
 716          }
 717          
 718          return $newNode;
 719      }
 720  }
 721  
 722  /**
 723  * A class to represent a collection of child nodes
 724  */
 725  class Tree_NodeCollection
 726  {
 727      /**
 728      * An array of child nodes
 729      * @var array
 730      */
 731      var $nodes;
 732      
 733      /**
 734      * The containing node/tree object
 735      * @var object
 736      */
 737      var $container;
 738      
 739      /**
 740      * Whether the container is a tree object or not
 741      * @var boolean
 742      */
 743      var $containerIsTree;
 744      
 745      /**
 746      * Whether the container is a tree node object or not
 747      * @var boolean
 748      */
 749      var $containerIsNode;
 750      
 751      /**
 752      * Temporary holder for the found node used in the
 753      * search function.
 754      * @var object
 755      */
 756      var $searchFoundNode;
 757  
 758      /**
 759      * Constructor
 760      */
 761      function Tree_NodeCollection(&$container)
 762      {
 763          $this->nodes = array();
 764          $this->container = &$container;
 765          $this->containerIsTree = (strtolower(get_class($container)) == 'tree');
 766          $this->containerIsNode = (strtolower(get_class($container)) == 'tree_node');
 767      }
 768  
 769      /**
 770      * Adds a node to this node
 771      *
 772      * @param  object $node The Tree_Node object
 773      * @return object       A reference to the new node inside the tree
 774      */
 775      function &addNode(&$node)
 776      {
 777          // Container is a node
 778          if ($this->containerIsNode) {
 779              $node->setParent($this->container);
 780              
 781              if (!empty($this->container->tree)) {
 782                  $node->setTree($this->container->tree);
 783              }
 784              
 785              if (!empty($this->container->uid)) {
 786                  $node->setUID($this->container->tree->uidCounter);
 787              }
 788  
 789          // Container is a tree
 790          } else {
 791              $node->setTree($this->container);
 792              $node->setUID($this->container->uidCounter);
 793          }
 794  
 795          $this->nodes[] = &$node;
 796  
 797          return $node;
 798      }
 799  
 800      /**
 801      * Returns the first node in this particular collection
 802      *
 803      * @return object The first node. NULL if no nodes.
 804      */
 805      function &firstNode()
 806      {
 807          if (!empty($this->nodes)) {
 808              return $this->nodes[0];
 809          }
 810          
 811          return null;
 812      }
 813      
 814      /**
 815      * Returns the last node in this particular collection
 816      *
 817      * @return object The last node. NULL if no nodes.
 818      */
 819      function &lastNode()
 820      {
 821          if (!empty($this->nodes)) {
 822              return $this->nodes[count($this->nodes) - 1];
 823          }
 824  
 825          return null;
 826      }
 827  
 828      /**
 829      * Removes a node from the child nodes array at the
 830      * specified (zero based) index.
 831      *
 832      * @parm   integer $index The index to remove
 833      * @return object         The node that was removed, or null
 834      *                        if this index did not exist
 835      */
 836      function &removeNodeAt($index)
 837      {
 838          $node = null;
 839          if (!empty($this->nodes[$index])) {
 840              $node = &$this->nodes[$index];
 841  
 842              // Unset parent, tree and uid values
 843              unset($node->uid);
 844              unset($node->parent);
 845              unset($node->tree);
 846              unset($this->nodes[$index]);
 847              $this->nodes = array_values($this->nodes);
 848          }
 849  
 850          return $node;
 851      }
 852      
 853      /**
 854      * Removes a node from the child nodes array by using
 855      * the unique ID stored in each instance
 856      *
 857      * @param  object $node   The node to remove
 858      * @param  bool   $search Whether to search child nodes
 859      * @return bool           True/False
 860      */
 861      function removeNode(&$node, $search = false)
 862      {
 863          for ($i=0; $i<count($this->nodes); $i++) {
 864              if ($this->nodes[$i]->getUID() == $node->getUID()) {
 865  
 866                  // Unset parent, tree and uid values
 867                  unset($node->uid);
 868                  unset($node->parent);
 869                  unset($node->tree);
 870                  unset($this->nodes[$i]);
 871                  $this->nodes = @array_values($this->nodes);
 872                  return true;
 873              } elseif ($search AND !empty($this->nodes[$i]->nodes)) {
 874                  $searchNodes[] = $i;
 875              }
 876          }
 877          
 878          if ($search AND !empty($searchNodes)) {
 879              foreach ($searchNodes as $index) {
 880                  if ($this->nodes[$index]->removeNode($node, true)) {
 881                      return true;
 882                  }
 883              }
 884          }
 885  
 886          return false;
 887      }
 888      
 889      /**
 890      * Returns the index in the nodes array at which
 891      * the given node resides. Used in the prev/next Sibling
 892      * methods.
 893      *
 894      * @param  object $node The node to return the index of
 895      * @return integer      The index of the node or null if
 896      *                      not found.
 897      */
 898      function indexOf($node)
 899      {
 900          for ($i=0; $i<count($this->nodes); $i++) {
 901              if ($this->nodes[$i]->getUID() == $node->getUID()) {
 902                  return $i;
 903              }
 904          }
 905          
 906          return null;
 907      }
 908      
 909      /**
 910      * Returns the number of child nodes in this node/tree.
 911      * Optionally searches the tree and returns the cumulative count.
 912      *
 913      * @param  bool    $search Search tree for nodecount too
 914      * @return integer         The number of nodes found
 915      */
 916      function getNodeCount($search = false)
 917      {
 918          if ($search) {
 919              $count = count($this->nodes);
 920              for ($i=0; $i<count($this->nodes); $i++) {
 921                  $count += $this->nodes[$i]->nodes->getNodeCount(true);
 922              }
 923              
 924              return $count;
 925          } else {
 926              $count = count($this->nodes);
 927              return $count;
 928          }
 929      }
 930      
 931      /**
 932      * Returns a flat list of the node collection. This array contains references
 933      * to the nodes.
 934      *
 935      * @return array Flat list of the nodes from top to bottom, left to right.
 936      */
 937      function &getFlatList()
 938      {
 939          $return = array();
 940  
 941          for ($i=0; $i<count($this->nodes); $i++) {
 942              $return[] = &$this->nodes[$i];
 943              
 944              if (!empty($this->nodes[$i]->nodes)) {
 945                  $return = array_merge($return, $this->nodes[$i]->nodes->getFlatList());
 946              }
 947          }
 948          
 949          return $return;
 950      }
 951      
 952      /**
 953      * Traverses the node collection applying a function to each and every node.
 954      * The function name given (though this can be anything you can supply to 
 955      * call_user_func(), not just a name) should take a single argument which is the
 956      * node object (Tree_Node class). You can then access the nodes data by using
 957      * the getTag() method. The traversal goes from top to bottom, left to right
 958      * (ie same order as what you get from getFlatList()).
 959      *
 960      * ** The node is passed by reference to the function! **
 961      *
 962      * @param callback $function The callback function to use
 963      */
 964      function traverse($function)
 965      {
 966          for ($i=0; $i<count($this->nodes); $i++) {
 967              call_user_func($function, array(&$this->nodes[$i]));
 968              
 969              // Recurse
 970              if (!empty($this->nodes[$i])) {
 971                  $this->nodes[$i]->nodes->traverse($function);
 972              }
 973          }
 974      }
 975      
 976      /**
 977      * Searches the node collection for a node with a tag matching
 978      * what you supply. This is a simply "tag == your data" comparison, (=== if strict option is applied)
 979      * and more advanced comparisons can be made using the traverse() method.
 980      * This function returns null if nothing is found, and a reference to the
 981      * first found node if a match is made.
 982      *
 983      * @param  mixed $data   Data to try to find and match
 984      * @param  mixed $strict Whether to use === or simply == to compare
 985      * @return mixed         Null if no match, a reference to the first found node
 986      *                       if a match is made.
 987      */
 988      function &search(&$data, $strict = false)
 989      {
 990          static $searchData;
 991          static $comparisonType;
 992          
 993          $result = null;
 994  
 995          if (is_object($data) AND strcasecmp(get_class($data), 'Tree_Node') == 0) {
 996              // Inside traversion
 997              if (empty($this->searchFoundNode) AND ($comparisonType ? ($data->getTag() === $searchData) : ($data->getTag() == $searchData))) {
 998                  $this->searchFoundNode = &$data;
 999              }
1000              return $result;
1001  
1002          } else {
1003              // Start traversing
1004              $searchData     = $data;
1005              $comparisonType = $strict;
1006              
1007              $this->traverse(array(&$this, 'search'));
1008          }
1009  
1010          if (!empty($this->searchFoundNode)) {
1011              $node = &$this->searchFoundNode;
1012              unset($this->searchFoundNode);
1013              return $node;
1014          }
1015  
1016          return $result;
1017      }
1018      
1019      /**
1020      * Moves the nodes in this collection (not the collection itself)
1021      * to the given new parent.
1022      *
1023      * @param object $newParent The new parent Tree_Node or Tree object
1024      */
1025  	function moveTo(&$newParent)
1026      {
1027          while (!empty($this->nodes)) {
1028              $this->nodes[0]->moveTo($newParent);
1029          }
1030      }
1031      
1032      /**
1033      * Copies the nodes in this collection (not the collection itself)
1034      * to the given new parent.
1035      *
1036      * @param object $newParent The new parent Tree_Node or Tree object
1037      */
1038  	function copyTo(&$newParent)
1039      {
1040          for ($i=0; $i<count($this->nodes); $i++) {
1041              $this->nodes[$i]->copyTo($newParent);
1042          }
1043      }
1044  }
1045  ?>