Commit | Line | Data |
---|---|---|
6a488035 TO |
1 | <?php |
2 | /* | |
3 | +--------------------------------------------------------------------+ | |
39de6fd5 | 4 | | CiviCRM version 4.6 | |
6a488035 | 5 | +--------------------------------------------------------------------+ |
06b69b18 | 6 | | Copyright CiviCRM LLC (c) 2004-2014 | |
6a488035 TO |
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 | +--------------------------------------------------------------------+ | |
d25dd0ee | 26 | */ |
6a488035 TO |
27 | |
28 | /** | |
29 | * | |
30 | * @package CRM | |
06b69b18 | 31 | * @copyright CiviCRM LLC (c) 2004-2014 |
6a488035 TO |
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 | |
06b69b18 | 76 | * @copyright CiviCRM LLC (c) 2004-2014 |
6a488035 TO |
77 | * $Id: $ |
78 | * | |
79 | */ | |
80 | class CRM_Utils_Tree { | |
81 | ||
82 | /** | |
fe482240 | 83 | * Store the tree information as a string or array. |
6a488035 TO |
84 | * @var string|array |
85 | */ | |
86 | private $tree; | |
87 | ||
88 | /** | |
89 | * Constructor for the tree. | |
90 | * | |
100fef9d | 91 | * @param string $nodeName |
f4aaa82a | 92 | * |
c490a46a | 93 | * @internal param string $rootNode |
6a488035 TO |
94 | * |
95 | * @return CRM_Utils_Tree | |
6a488035 TO |
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 | /** | |
fe482240 | 106 | * Find a node that matches the given string. |
6a488035 | 107 | * |
77855840 TO |
108 | * @param string $name |
109 | * Name of the node we are searching for. | |
6a488035 TO |
110 | * @param array (ref) $parentNode which parent node should we search in ? |
111 | * | |
c301f76e | 112 | * @return array(ref) | false node if found else false |
6a488035 | 113 | */ |
6a488035 TO |
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 | /** | |
100fef9d | 144 | * Check if node is a leaf node. |
6a488035 TO |
145 | * Currently leaf nodes are strings and non-leaf nodes are arrays |
146 | * | |
c301f76e | 147 | * @param array $node node which needs to checked |
6a488035 | 148 | * |
c301f76e | 149 | * @return bool |
6a488035 TO |
150 | */ |
151 | public function isLeafNode(&$node) { | |
152 | return (count($node['children']) ? TRUE : FALSE); | |
153 | } | |
154 | ||
155 | /** | |
fe482240 | 156 | * Create a node. |
6a488035 TO |
157 | * |
158 | * @param string $name | |
159 | * | |
a6c01b45 CW |
160 | * @return array |
161 | * (ref) | |
6a488035 TO |
162 | */ |
163 | public function &createNode($name) { | |
353ffa53 | 164 | $node['name'] = $name; |
6a488035 | 165 | $node['children'] = array(); |
353ffa53 | 166 | $node['data'] = array(); |
6a488035 TO |
167 | |
168 | return $node; | |
169 | } | |
170 | ||
171 | /** | |
fe482240 | 172 | * Add node. |
6a488035 | 173 | * |
77855840 TO |
174 | * @param string $parentName |
175 | * Name of the parent ?. | |
c301f76e | 176 | * @param array (ref) $node - node to be added |
6a488035 | 177 | * |
355ba699 | 178 | * @return void |
6a488035 TO |
179 | */ |
180 | public function addNode($parentName, &$node) { | |
181 | $temp = ''; | |
182 | $parentNode = &$this->findNode($parentName, $temp); | |
183 | ||
184 | $parentNode['children'][] = &$node; | |
185 | } | |
186 | ||
187 | /** | |
fe482240 | 188 | * Add Data. |
6a488035 | 189 | * |
c301f76e | 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 | |
6a488035 | 193 | * |
355ba699 | 194 | * @return void |
6a488035 TO |
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 | /** | |
fe482240 | 209 | * Get Tree. |
6a488035 | 210 | * |
6a488035 | 211 | * @return tree |
6a488035 TO |
212 | */ |
213 | public function getTree() { | |
214 | return $this->tree; | |
215 | } | |
216 | ||
217 | /** | |
fe482240 | 218 | * Print the tree. |
6a488035 | 219 | * |
355ba699 | 220 | * @return void |
6a488035 TO |
221 | */ |
222 | public function display() { | |
223 | print_r($this->tree); | |
224 | } | |
96025800 | 225 | |
6a488035 | 226 | } |