Commit | Line | Data |
---|---|---|
6a488035 TO |
1 | <?php |
2 | /* | |
3 | +--------------------------------------------------------------------+ | |
7e9e8871 | 4 | | CiviCRM version 4.7 | |
6a488035 | 5 | +--------------------------------------------------------------------+ |
e7112fa7 | 6 | | Copyright CiviCRM LLC (c) 2004-2015 | |
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 | |
e7112fa7 | 31 | * @copyright CiviCRM LLC (c) 2004-2015 |
6a488035 TO |
32 | */ |
33 | ||
34 | /** | |
b8c71ffa | 35 | * Manage simple Tree data structure. |
36 | * | |
37 | * Example of Tree is | |
6a488035 TO |
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 | |
b44e3f84 | 65 | * Data - any other auxiliary data |
6a488035 TO |
66 | * |
67 | * | |
68 | * Internally all nodes are an array with the following keys | |
69 | * 'name' - string | |
70 | * 'children' - array | |
71 | * 'data' - array | |
72 | * | |
73 | * | |
74 | * @package CRM | |
e7112fa7 | 75 | * @copyright CiviCRM LLC (c) 2004-2015 |
6a488035 TO |
76 | * $Id: $ |
77 | * | |
78 | */ | |
79 | class CRM_Utils_Tree { | |
80 | ||
81 | /** | |
fe482240 | 82 | * Store the tree information as a string or array. |
6a488035 TO |
83 | * @var string|array |
84 | */ | |
85 | private $tree; | |
86 | ||
87 | /** | |
88 | * Constructor for the tree. | |
89 | * | |
100fef9d | 90 | * @param string $nodeName |
f4aaa82a | 91 | * |
c490a46a | 92 | * @internal param string $rootNode |
6a488035 TO |
93 | * |
94 | * @return CRM_Utils_Tree | |
6a488035 TO |
95 | */ |
96 | public function __construct($nodeName) { | |
97 | // create the root node | |
98 | $rootNode = &$this->createNode($nodeName); | |
99 | ||
100 | // add the root node to the tree | |
101 | $this->tree['rootNode'] = &$rootNode; | |
102 | } | |
103 | ||
104 | /** | |
fe482240 | 105 | * Find a node that matches the given string. |
6a488035 | 106 | * |
77855840 TO |
107 | * @param string $name |
108 | * Name of the node we are searching for. | |
6a488035 TO |
109 | * @param array (ref) $parentNode which parent node should we search in ? |
110 | * | |
c301f76e | 111 | * @return array(ref) | false node if found else false |
6a488035 | 112 | */ |
6a488035 TO |
113 | public function &findNode($name, &$parentNode) { |
114 | // if no parent node specified, please start from root node | |
115 | if (!$parentNode) { | |
116 | $parentNode = &$this->tree['rootNode']; | |
117 | } | |
118 | ||
119 | // first check the nodename of subtree itself | |
120 | if ($parentNode['name'] == $name) { | |
121 | return $parentNode; | |
122 | } | |
123 | ||
124 | $falseRet = FALSE; | |
125 | // no children ? return false | |
126 | if ($this->isLeafNode($node)) { | |
127 | return $falseRet; | |
128 | } | |
129 | ||
130 | // search children of the subtree | |
131 | foreach ($parentNode['children'] as $key => $childNode) { | |
132 | $cNode = &$parentNode['children'][$key]; | |
133 | if ($node = &$this->findNode($name, $cNode)) { | |
134 | return $node; | |
135 | } | |
136 | } | |
137 | ||
138 | // name does not match subtree or any of the children, negative result | |
139 | return $falseRet; | |
140 | } | |
141 | ||
142 | /** | |
100fef9d | 143 | * Check if node is a leaf node. |
b8c71ffa | 144 | * |
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 TO |
177 | */ |
178 | public function addNode($parentName, &$node) { | |
179 | $temp = ''; | |
180 | $parentNode = &$this->findNode($parentName, $temp); | |
181 | ||
182 | $parentNode['children'][] = &$node; | |
183 | } | |
184 | ||
185 | /** | |
fe482240 | 186 | * Add Data. |
6a488035 | 187 | * |
c301f76e | 188 | * @param string $parentName Name of the parent ?. |
189 | * @param string $childName - key to be used (optional) | |
190 | * @param mixed $data - data to be added | |
6a488035 TO |
191 | */ |
192 | public function addData($parentName, $childName, $data) { | |
193 | $temp = ''; | |
194 | if ($parentNode = &$this->findNode($parentName, $temp)) { | |
195 | foreach ($parentNode['children'] as $key => $childNode) { | |
196 | $cNode = &$parentNode['children'][$key]; | |
197 | if ($cNode = &$this->findNode($childName, $parentNode)) { | |
198 | $cNode['data']['fKey'] = &$data; | |
199 | } | |
200 | } | |
201 | } | |
202 | } | |
203 | ||
204 | /** | |
fe482240 | 205 | * Get Tree. |
6a488035 | 206 | * |
6a488035 | 207 | * @return tree |
6a488035 TO |
208 | */ |
209 | public function getTree() { | |
210 | return $this->tree; | |
211 | } | |
212 | ||
213 | /** | |
fe482240 | 214 | * Print the tree. |
6a488035 TO |
215 | */ |
216 | public function display() { | |
217 | print_r($this->tree); | |
218 | } | |
96025800 | 219 | |
6a488035 | 220 | } |