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 | |
6a488035 TO |
72 | */ |
73 | class CRM_Utils_Tree { | |
74 | ||
75 | /** | |
fe482240 | 76 | * Store the tree information as a string or array. |
6a488035 TO |
77 | * @var string|array |
78 | */ | |
79 | private $tree; | |
80 | ||
81 | /** | |
82 | * Constructor for the tree. | |
83 | * | |
100fef9d | 84 | * @param string $nodeName |
f4aaa82a | 85 | * |
c490a46a | 86 | * @internal param string $rootNode |
6a488035 TO |
87 | * |
88 | * @return CRM_Utils_Tree | |
6a488035 TO |
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 | /** | |
fe482240 | 99 | * Find a node that matches the given string. |
6a488035 | 100 | * |
77855840 TO |
101 | * @param string $name |
102 | * Name of the node we are searching for. | |
6a488035 TO |
103 | * @param array (ref) $parentNode which parent node should we search in ? |
104 | * | |
c301f76e | 105 | * @return array(ref) | false node if found else false |
6a488035 | 106 | */ |
6a488035 TO |
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 | /** | |
100fef9d | 137 | * Check if node is a leaf node. |
b8c71ffa | 138 | * |
6a488035 TO |
139 | * Currently leaf nodes are strings and non-leaf nodes are arrays |
140 | * | |
c301f76e | 141 | * @param array $node node which needs to checked |
6a488035 | 142 | * |
c301f76e | 143 | * @return bool |
6a488035 TO |
144 | */ |
145 | public function isLeafNode(&$node) { | |
146 | return (count($node['children']) ? TRUE : FALSE); | |
147 | } | |
148 | ||
149 | /** | |
fe482240 | 150 | * Create a node. |
6a488035 TO |
151 | * |
152 | * @param string $name | |
153 | * | |
a6c01b45 CW |
154 | * @return array |
155 | * (ref) | |
6a488035 TO |
156 | */ |
157 | public function &createNode($name) { | |
353ffa53 | 158 | $node['name'] = $name; |
6a488035 | 159 | $node['children'] = array(); |
353ffa53 | 160 | $node['data'] = array(); |
6a488035 TO |
161 | |
162 | return $node; | |
163 | } | |
164 | ||
165 | /** | |
fe482240 | 166 | * Add node. |
6a488035 | 167 | * |
77855840 TO |
168 | * @param string $parentName |
169 | * Name of the parent ?. | |
c301f76e | 170 | * @param array (ref) $node - node to be added |
6a488035 TO |
171 | */ |
172 | public function addNode($parentName, &$node) { | |
173 | $temp = ''; | |
174 | $parentNode = &$this->findNode($parentName, $temp); | |
175 | ||
176 | $parentNode['children'][] = &$node; | |
177 | } | |
178 | ||
179 | /** | |
fe482240 | 180 | * Add Data. |
6a488035 | 181 | * |
c301f76e | 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 | |
6a488035 TO |
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 | /** | |
fe482240 | 199 | * Get Tree. |
6a488035 | 200 | * |
6a488035 | 201 | * @return tree |
6a488035 TO |
202 | */ |
203 | public function getTree() { | |
204 | return $this->tree; | |
205 | } | |
206 | ||
207 | /** | |
fe482240 | 208 | * Print the tree. |
6a488035 TO |
209 | */ |
210 | public function display() { | |
211 | print_r($this->tree); | |
212 | } | |
96025800 | 213 | |
6a488035 | 214 | } |