CRM/Utils/Tree.php

   1 <?php
   2 /*
   3  +--------------------------------------------------------------------+
   4  | CiviCRM version 4.7                                                |
   5  +--------------------------------------------------------------------+
   6  | Copyright CiviCRM LLC (c) 2004-2015                                |
   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-2015
  32  */
  33
  34 /**
  35  * Manage simple Tree data structure.
  36  *
  37  * Example of Tree is
  38  *
  39  *                             'a'
  40  *                              |
  41  *    --------------------------------------------------------------
  42  *    |                 |                 |              |         |
  43  *   'b'               'c'               'd'            'e'       'f'
  44  *    |                 |         /-----/ |                        |
  45  *  -------------     ---------  /     --------     ------------------------
  46  *  |           |     |       | /      |      |     |           |          |
  47  * 'g'         'h'   'i'     'j'      'k'    'l'   'm'         'n'        'o'
  48  *                            |
  49  *                  ----------------------
  50  *                 |          |          |
  51  *                'p'        'q'        'r'
  52  *
  53  *
  54  *
  55  * From the above diagram we have
  56  *   'a'  - root node
  57  *   'b'  - child node
  58  *   'g'  - leaf node
  59  *   'j'  - node with multiple parents 'c' and 'd'
  60  *
  61  *
  62  * All nodes of the tree (including root and leaf node) contain the following properties
  63  *       Name      - what is the node name ?
  64  *       Children  - who are it's children
  65  *       Data      - any other auxiliary data
  66  *
  67  *
  68  * Internally all nodes are an array with the following keys
  69  *      'name' - string
  70  *      'children' - array
  71  *      'data' - array
  72  *
  73  *
  74  * @package CRM
  75  * @copyright CiviCRM LLC (c) 2004-2015
  76  * $Id: $
  77  *
  78  */
  79 class CRM_Utils_Tree {
  80
  81   /**
  82    * Store the tree information as a string or array.
  83    * @var string|array
  84    */
  85   private $tree;
  86
  87   /**
  88    * Constructor for the tree.
  89    *
  90    * @param string $nodeName
  91    *
  92    * @internal param string $rootNode
  93    *
  94    * @return CRM_Utils_Tree
  95    */
  96   public function __construct($nodeName) {
  97     // create the root node
  98     $rootNode = &$this->createNode($nodeName);
  99
 100     // add the root node to the tree
 101     $this->tree['rootNode'] = &$rootNode;
 102   }
 103
 104   /**
 105    * Find a node that matches the given string.
 106    *
 107    * @param string $name
 108    *   Name of the node we are searching for.
 109    * @param array (ref) $parentNode which parent node should we search in ?
 110    *
 111    * @return array(ref) | false node if found else false
 112    */
 113   public function &findNode($name, &$parentNode) {
 114     // if no parent node specified, please start from root node
 115     if (!$parentNode) {
 116       $parentNode = &$this->tree['rootNode'];
 117     }
 118
 119     // first check the nodename of subtree itself
 120     if ($parentNode['name'] == $name) {
 121       return $parentNode;
 122     }
 123
 124     $falseRet = FALSE;
 125     // no children ? return false
 126     if ($this->isLeafNode($node)) {
 127       return $falseRet;
 128     }
 129
 130     // search children of the subtree
 131     foreach ($parentNode['children'] as $key => $childNode) {
 132       $cNode = &$parentNode['children'][$key];
 133       if ($node = &$this->findNode($name, $cNode)) {
 134         return $node;
 135       }
 136     }
 137
 138     // name does not match subtree or any of the children, negative result
 139     return $falseRet;
 140   }
 141
 142   /**
 143    * Check if node is a leaf node.
 144    *
 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   public function addNode($parentName, &$node) {
 179     $temp = '';
 180     $parentNode = &$this->findNode($parentName, $temp);
 181
 182     $parentNode['children'][] = &$node;
 183   }
 184
 185   /**
 186    * Add Data.
 187    *
 188    * @param string $parentName Name of the parent ?.
 189    * @param string $childName - key to be used (optional)
 190    * @param mixed $data - data to be added
 191    */
 192   public function addData($parentName, $childName, $data) {
 193     $temp = '';
 194     if ($parentNode = &$this->findNode($parentName, $temp)) {
 195       foreach ($parentNode['children'] as $key => $childNode) {
 196         $cNode = &$parentNode['children'][$key];
 197         if ($cNode = &$this->findNode($childName, $parentNode)) {
 198           $cNode['data']['fKey'] = &$data;
 199         }
 200       }
 201     }
 202   }
 203
 204   /**
 205    * Get Tree.
 206    *
 207    * @return tree
 208    */
 209   public function getTree() {
 210     return $this->tree;
 211   }
 212
 213   /**
 214    * Print the tree.
 215    */
 216   public function display() {
 217     print_r($this->tree);
 218   }
 219
 220 }