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(ref) | false node if found else false
 113    */
 114   public function &findNode($name, &$parentNode) {
 115     // if no parent node specified, please start from root node
 116     if (!$parentNode) {
 117       $parentNode = &$this->tree['rootNode'];
 118     }
 119
 120     // first check the nodename of subtree itself
 121     if ($parentNode['name'] == $name) {
 122       return $parentNode;
 123     }
 124
 125     $falseRet = FALSE;
 126     // no children ? return false
 127     if ($this->isLeafNode($node)) {
 128       return $falseRet;
 129     }
 130
 131     // search children of the subtree
 132     foreach ($parentNode['children'] as $key => $childNode) {
 133       $cNode = &$parentNode['children'][$key];
 134       if ($node = &$this->findNode($name, $cNode)) {
 135         return $node;
 136       }
 137     }
 138
 139     // name does not match subtree or any of the children, negative result
 140     return $falseRet;
 141   }
 142
 143   /**
 144    * Check if node is a leaf node.
 145    * Currently leaf nodes are strings and non-leaf nodes are arrays
 146    *
 147    * @param array $node node which needs to checked
 148    *
 149    * @return bool
 150    */
 151   public function isLeafNode(&$node) {
 152     return (count($node['children']) ? TRUE : FALSE);
 153   }
 154
 155   /**
 156    * Create a node.
 157    *
 158    * @param string $name
 159    *
 160    * @return array
 161    *   (ref)
 162    */
 163   public function &createNode($name) {
 164     $node['name'] = $name;
 165     $node['children'] = array();
 166     $node['data'] = array();
 167
 168     return $node;
 169   }
 170
 171   /**
 172    * Add node.
 173    *
 174    * @param string $parentName
 175    *   Name of the parent ?.
 176    * @param array (ref) $node - node to be added
 177    *
 178    * @return void
 179    */
 180   public function addNode($parentName, &$node) {
 181     $temp = '';
 182     $parentNode = &$this->findNode($parentName, $temp);
 183
 184     $parentNode['children'][] = &$node;
 185   }
 186
 187   /**
 188    * Add Data.
 189    *
 190    * @param string $parentName Name of the parent ?.
 191    * @param string $childName - key to be used (optional)
 192    * @param mixed $data - data to be added
 193    *
 194    * @return void
 195    */
 196   public function addData($parentName, $childName, $data) {
 197     $temp = '';
 198     if ($parentNode = &$this->findNode($parentName, $temp)) {
 199       foreach ($parentNode['children'] as $key => $childNode) {
 200         $cNode = &$parentNode['children'][$key];
 201         if ($cNode = &$this->findNode($childName, $parentNode)) {
 202           $cNode['data']['fKey'] = &$data;
 203         }
 204       }
 205     }
 206   }
 207
 208   /**
 209    * Get Tree.
 210    *
 211    * @return tree
 212    */
 213   public function getTree() {
 214     return $this->tree;
 215   }
 216
 217   /**
 218    * Print the tree.
 219    *
 220    * @return void
 221    */
 222   public function display() {
 223     print_r($this->tree);
 224   }
 225
 226 }