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