CRM/Utils/Tree.php

   1 <?php
   2 /*
   3  +--------------------------------------------------------------------+
   4  | CiviCRM version 4.6                                                |
   5  +--------------------------------------------------------------------+
   6  | Copyright CiviCRM LLC (c) 2004-2014                                |
   7  +--------------------------------------------------------------------+
   8  | This file is a part of CiviCRM.                                    |
   9  |                                                                    |
  10  | CiviCRM is free software; you can copy, modify, and distribute it  |
  11  | under the terms of the GNU Affero General Public License           |
  12  | Version 3, 19 November 2007 and the CiviCRM Licensing Exception.   |
  13  |                                                                    |
  14  | CiviCRM is distributed in the hope that it will be useful, but     |
  15  | WITHOUT ANY WARRANTY; without even the implied warranty of         |
  16  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.               |
  17  | See the GNU Affero General Public License for more details.        |
  18  |                                                                    |
  19  | You should have received a copy of the GNU Affero General Public   |
  20  | License and the CiviCRM Licensing Exception along                  |
  21  | with this program; if not, contact CiviCRM LLC                     |
  22  | at info[AT]civicrm[DOT]org. If you have questions about the        |
  23  | GNU Affero General Public License or the licensing of CiviCRM,     |
  24  | see the CiviCRM license FAQ at http://civicrm.org/licensing        |
  25  +--------------------------------------------------------------------+
  26 */
  27
  28 /**
  29  *
  30  * @package CRM
  31  * @copyright CiviCRM LLC (c) 2004-2014
  32  * $Id$
  33  *
  34  */
  35
  36 /**
  37  * Manage simple Tree data structure
  38  * example of Tree is
  39  *
  40  *                             'a'
  41  *                              |
  42  *    --------------------------------------------------------------
  43  *    |                 |                 |              |         |
  44  *   'b'               'c'               'd'            'e'       'f'
  45  *    |                 |         /-----/ |                        |
  46  *  -------------     ---------  /     --------     ------------------------
  47  *  |           |     |       | /      |      |     |           |          |
  48  * 'g'         'h'   'i'     'j'      'k'    'l'   'm'         'n'        'o'
  49  *                            |
  50  *                  ----------------------
  51  *                 |          |          |
  52  *                'p'        'q'        'r'
  53  *
  54  *
  55  *
  56  * From the above diagram we have
  57  *   'a'  - root node
  58  *   'b'  - child node
  59  *   'g'  - leaf node
  60  *   'j'  - node with multiple parents 'c' and 'd'
  61  *
  62  *
  63  * All nodes of the tree (including root and leaf node) contain the following properties
  64  *       Name      - what is the node name ?
  65  *       Children  - who are it's children
  66  *       Data      - any other auxillary data
  67  *
  68  *
  69  * Internally all nodes are an array with the following keys
  70  *      'name' - string
  71  *      'children' - array
  72  *      'data' - array
  73  *
  74  *
  75  * @package CRM
  76  * @copyright CiviCRM LLC (c) 2004-2014
  77  * $Id: $
  78  *
  79  */
  80 class CRM_Utils_Tree {
  81
  82   /**
  83    * Store the tree information as a string or array
  84    * @var string|array
  85    */
  86   private $tree;
  87
  88   /**
  89    * Constructor for the tree.
  90    *
  91    * @param string $nodeName
  92    *
  93    * @internal param string $rootNode
  94    *
  95    * @return CRM_Utils_Tree
  96    */
  97   public function __construct($nodeName) {
  98     // create the root node
  99     $rootNode = &$this->createNode($nodeName);
 100
 101     // add the root node to the tree
 102     $this->tree['rootNode'] = &$rootNode;
 103   }
 104
 105   /**
 106    * Find a node that matches the given string
 107    *
 108    * @param string $name
 109    *   Name of the node we are searching for.
 110    * @param array (ref) $parentNode which parent node should we search in ?
 111    *
 112    * @return array(
 113      ref) | false node if found else false
 114    *
 115    */
 116   //public function &findNode(&$parentNode, $name)
 117   public function &findNode($name, &$parentNode) {
 118     // if no parent node specified, please start from root node
 119     if (!$parentNode) {
 120       $parentNode = &$this->tree['rootNode'];
 121     }
 122
 123     // first check the nodename of subtree itself
 124     if ($parentNode['name'] == $name) {
 125       return $parentNode;
 126     }
 127
 128     $falseRet = FALSE;
 129     // no children ? return false
 130     if ($this->isLeafNode($node)) {
 131       return $falseRet;
 132     }
 133
 134     // search children of the subtree
 135     foreach ($parentNode['children'] as $key => $childNode) {
 136       $cNode = &$parentNode['children'][$key];
 137       if ($node = &$this->findNode($name, $cNode)) {
 138         return $node;
 139       }
 140     }
 141
 142     // name does not match subtree or any of the children, negative result
 143     return $falseRet;
 144   }
 145
 146   /**
 147    * Check if node is a leaf node.
 148    * Currently leaf nodes are strings and non-leaf nodes are arrays
 149    *
 150    * @param array(
 151      ref) $node node which needs to checked
 152    *
 153    * @return boolean
 154    *
 155    */
 156   public function isLeafNode(&$node) {
 157     return (count($node['children']) ? TRUE : FALSE);
 158   }
 159
 160   /**
 161    * Create a node
 162    *
 163    * @param string $name
 164    *
 165    * @return array (ref)
 166    *
 167    */
 168   public function &createNode($name) {
 169     $node['name']     = $name;
 170     $node['children'] = array();
 171     $node['data']     = array();
 172
 173     return $node;
 174   }
 175
 176   /**
 177    * Add node
 178    *
 179    * @param string $parentName
 180    *   Name of the parent ?.
 181    * @param array (ref) - node to be added
 182    *
 183    * @return void
 184    *
 185    */
 186   public function addNode($parentName, &$node) {
 187     $temp = '';
 188     $parentNode = &$this->findNode($parentName, $temp);
 189
 190     $parentNode['children'][] = &$node;
 191   }
 192
 193   /**
 194    * Add Data
 195    *
 196    * @param string $parentName
 197    *   Name of the parent ?.
 198    * @param mixed - data to be added
 199    * @param string - key to be used (optional)
 200    *
 201    * @return void
 202    *
 203    */
 204   public function addData($parentName, $childName, $data) {
 205     $temp = '';
 206     if ($parentNode = &$this->findNode($parentName, $temp)) {
 207       foreach ($parentNode['children'] as $key => $childNode) {
 208         $cNode = &$parentNode['children'][$key];
 209         if ($cNode = &$this->findNode($childName, $parentNode)) {
 210           $cNode['data']['fKey'] = &$data;
 211         }
 212       }
 213     }
 214   }
 215
 216   /**
 217    * Get Tree
 218    *
 219    * @param none
 220    *
 221    * @return tree
 222    *
 223    */
 224   public function getTree() {
 225     return $this->tree;
 226   }
 227
 228   /**
 229    * Print the tree
 230    *
 231    * @param none
 232    *
 233    * @return void
 234    *
 235    */
 236   public function display() {
 237     print_r($this->tree);
 238   }
 239 }