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 | +--------------------------------------------------------------------+ | |
26 | */ | |
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 | /** | |
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 | * | |
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 | /** | |
106 | * Find a node that matches the given string | |
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 | * | |
112 | * @return array( | |
353ffa53 | 113 | * ref) | false node if found else false |
6a488035 TO |
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 | /** | |
100fef9d | 146 | * Check if node is a leaf node. |
6a488035 TO |
147 | * Currently leaf nodes are strings and non-leaf nodes are arrays |
148 | * | |
353ffa53 TO |
149 | * @param array ( |
150 | * ref) $node node which needs to checked | |
6a488035 TO |
151 | * |
152 | * @return boolean | |
6a488035 TO |
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 | * | |
a6c01b45 CW |
163 | * @return array |
164 | * (ref) | |
6a488035 TO |
165 | */ |
166 | public function &createNode($name) { | |
353ffa53 | 167 | $node['name'] = $name; |
6a488035 | 168 | $node['children'] = array(); |
353ffa53 | 169 | $node['data'] = array(); |
6a488035 TO |
170 | |
171 | return $node; | |
172 | } | |
173 | ||
174 | /** | |
175 | * Add node | |
176 | * | |
77855840 TO |
177 | * @param string $parentName |
178 | * Name of the parent ?. | |
179 | * @param array (ref) - node to be added | |
6a488035 | 180 | * |
355ba699 | 181 | * @return void |
6a488035 TO |
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 | * | |
77855840 TO |
193 | * @param string $parentName |
194 | * Name of the parent ?. | |
195 | * @param mixed - data to be added | |
196 | * @param string - key to be used (optional) | |
6a488035 | 197 | * |
355ba699 | 198 | * @return void |
6a488035 TO |
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 | |
6a488035 TO |
218 | */ |
219 | public function getTree() { | |
220 | return $this->tree; | |
221 | } | |
222 | ||
223 | /** | |
100fef9d | 224 | * Print the tree |
6a488035 TO |
225 | * |
226 | * @param none | |
227 | * | |
355ba699 | 228 | * @return void |
6a488035 TO |
229 | */ |
230 | public function display() { | |
231 | print_r($this->tree); | |
232 | } | |
233 | } |