Commit | Line | Data |
---|---|---|
6a488035 TO |
1 | <?php |
2 | /* | |
3 | +--------------------------------------------------------------------+ | |
4 | | CiviCRM version 4.3 | | |
5 | +--------------------------------------------------------------------+ | |
6 | | Copyright CiviCRM LLC (c) 2004-2013 | | |
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-2013 | |
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-2013 | |
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 $root | |
92 | * | |
93 | * @return CRM_Utils_Tree | |
94 | ||
95 | * @access public | |
96 | * | |
97 | */ | |
98 | public function __construct($nodeName) { | |
99 | // create the root node | |
100 | $rootNode = &$this->createNode($nodeName); | |
101 | ||
102 | // add the root node to the tree | |
103 | $this->tree['rootNode'] = &$rootNode; | |
104 | } | |
105 | ||
106 | /** | |
107 | * Find a node that matches the given string | |
108 | * | |
109 | * @param string $name 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 | * @access public | |
116 | */ | |
117 | //public function &findNode(&$parentNode, $name) | |
118 | public function &findNode($name, &$parentNode) { | |
119 | // if no parent node specified, please start from root node | |
120 | if (!$parentNode) { | |
121 | $parentNode = &$this->tree['rootNode']; | |
122 | } | |
123 | ||
124 | // first check the nodename of subtree itself | |
125 | if ($parentNode['name'] == $name) { | |
126 | return $parentNode; | |
127 | } | |
128 | ||
129 | $falseRet = FALSE; | |
130 | // no children ? return false | |
131 | if ($this->isLeafNode($node)) { | |
132 | return $falseRet; | |
133 | } | |
134 | ||
135 | // search children of the subtree | |
136 | foreach ($parentNode['children'] as $key => $childNode) { | |
137 | $cNode = &$parentNode['children'][$key]; | |
138 | if ($node = &$this->findNode($name, $cNode)) { | |
139 | return $node; | |
140 | } | |
141 | } | |
142 | ||
143 | // name does not match subtree or any of the children, negative result | |
144 | return $falseRet; | |
145 | } | |
146 | ||
147 | /** | |
148 | * Function to check if node is a leaf node. | |
149 | * Currently leaf nodes are strings and non-leaf nodes are arrays | |
150 | * | |
151 | * @param array( | |
152 | ref) $node node which needs to checked | |
153 | * | |
154 | * @return boolean | |
155 | * | |
156 | * @access public | |
157 | */ | |
158 | public function isLeafNode(&$node) { | |
159 | return (count($node['children']) ? TRUE : FALSE); | |
160 | } | |
161 | ||
162 | /** | |
163 | * Create a node | |
164 | * | |
165 | * @param string $name | |
166 | * | |
167 | * @return array (ref) | |
168 | * | |
169 | * @access public | |
170 | */ | |
171 | public function &createNode($name) { | |
172 | $node['name'] = $name; | |
173 | $node['children'] = array(); | |
174 | $node['data'] = array(); | |
175 | ||
176 | return $node; | |
177 | } | |
178 | ||
179 | /** | |
180 | * Add node | |
181 | * | |
182 | * @param string $parentName - name of the parent ? | |
183 | * @param array (ref) - node to be added | |
184 | * | |
185 | * @return none | |
186 | * | |
187 | * @access public | |
188 | */ | |
189 | public function addNode($parentName, &$node) { | |
190 | $temp = ''; | |
191 | $parentNode = &$this->findNode($parentName, $temp); | |
192 | ||
193 | $parentNode['children'][] = &$node; | |
194 | } | |
195 | ||
196 | /** | |
197 | * Add Data | |
198 | * | |
199 | * @param string $parentName - name of the parent ? | |
200 | * @param mixed - data to be added | |
201 | * @param string - key to be used (optional) | |
202 | * | |
203 | * @return none | |
204 | * | |
205 | * @access public | |
206 | */ | |
207 | public function addData($parentName, $childName, $data) { | |
208 | $temp = ''; | |
209 | if ($parentNode = &$this->findNode($parentName, $temp)) { | |
210 | foreach ($parentNode['children'] as $key => $childNode) { | |
211 | $cNode = &$parentNode['children'][$key]; | |
212 | if ($cNode = &$this->findNode($childName, $parentNode)) { | |
213 | $cNode['data']['fKey'] = &$data; | |
214 | } | |
215 | } | |
216 | } | |
217 | } | |
218 | ||
219 | /** | |
220 | * Get Tree | |
221 | * | |
222 | * @param none | |
223 | * | |
224 | * @return tree | |
225 | * | |
226 | * @access public | |
227 | */ | |
228 | public function getTree() { | |
229 | return $this->tree; | |
230 | } | |
231 | ||
232 | /** | |
233 | * print the tree | |
234 | * | |
235 | * @param none | |
236 | * | |
237 | * @return none | |
238 | * | |
239 | * @access public | |
240 | */ | |
241 | public function display() { | |
242 | print_r($this->tree); | |
243 | } | |
244 | } | |
245 |