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 class CRM_Utils_Tree {
  74
  75   /**
  76    * Store the tree information as a string or array.
  77    * @var string|array
  78    */
  79   private $tree;
  80
  81   /**
  82    * Constructor for the tree.
  83    *
  84    * @param string $nodeName
  85    *
  86    * @internal param string $rootNode
  87    *
  88    * @return CRM_Utils_Tree
  89    */
  90   public function __construct($nodeName) {
  91     // create the root node
  92     $rootNode = &$this->createNode($nodeName);
  93
  94     // add the root node to the tree
  95     $this->tree['rootNode'] = &$rootNode;
  96   }
  97
  98   /**
  99    * Find a node that matches the given string.
 100    *
 101    * @param string $name
 102    *   Name of the node we are searching for.
 103    * @param array (ref) $parentNode which parent node should we search in ?
 104    *
 105    * @return array(ref) | false node if found else false
 106    */
 107   public function &findNode($name, &$parentNode) {
 108     // if no parent node specified, please start from root node
 109     if (!$parentNode) {
 110       $parentNode = &$this->tree['rootNode'];
 111     }
 112
 113     // first check the nodename of subtree itself
 114     if ($parentNode['name'] == $name) {
 115       return $parentNode;
 116     }
 117
 118     $falseRet = FALSE;
 119     // no children ? return false
 120     if ($this->isLeafNode($node)) {
 121       return $falseRet;
 122     }
 123
 124     // search children of the subtree
 125     foreach ($parentNode['children'] as $key => $childNode) {
 126       $cNode = &$parentNode['children'][$key];
 127       if ($node = &$this->findNode($name, $cNode)) {
 128         return $node;
 129       }
 130     }
 131
 132     // name does not match subtree or any of the children, negative result
 133     return $falseRet;
 134   }
 135
 136   /**
 137    * Check if node is a leaf node.
 138    *
 139    * Currently leaf nodes are strings and non-leaf nodes are arrays
 140    *
 141    * @param array $node node which needs to checked
 142    *
 143    * @return bool
 144    */
 145   public function isLeafNode(&$node) {
 146     return (count($node['children']) ? TRUE : FALSE);
 147   }
 148
 149   /**
 150    * Create a node.
 151    *
 152    * @param string $name
 153    *
 154    * @return array
 155    *   (ref)
 156    */
 157   public function &createNode($name) {
 158     $node['name'] = $name;
 159     $node['children'] = array();
 160     $node['data'] = array();
 161
 162     return $node;
 163   }
 164
 165   /**
 166    * Add node.
 167    *
 168    * @param string $parentName
 169    *   Name of the parent ?.
 170    * @param array (ref) $node - node to be added
 171    */
 172   public function addNode($parentName, &$node) {
 173     $temp = '';
 174     $parentNode = &$this->findNode($parentName, $temp);
 175
 176     $parentNode['children'][] = &$node;
 177   }
 178
 179   /**
 180    * Add Data.
 181    *
 182    * @param string $parentName Name of the parent ?.
 183    * @param string $childName - key to be used (optional)
 184    * @param mixed $data - data to be added
 185    */
 186   public function addData($parentName, $childName, $data) {
 187     $temp = '';
 188     if ($parentNode = &$this->findNode($parentName, $temp)) {
 189       foreach ($parentNode['children'] as $key => $childNode) {
 190         $cNode = &$parentNode['children'][$key];
 191         if ($cNode = &$this->findNode($childName, $parentNode)) {
 192           $cNode['data']['fKey'] = &$data;
 193         }
 194       }
 195     }
 196   }
 197
 198   /**
 199    * Get Tree.
 200    *
 201    * @return tree
 202    */
 203   public function getTree() {
 204     return $this->tree;
 205   }
 206
 207   /**
 208    * Print the tree.
 209    */
 210   public function display() {
 211     print_r($this->tree);
 212   }
 213
 214 }