Updated acknowledgements
[openemr.git] / library / classes / Tree.class.php
bloba76afc4e1768188f63801222fde4f0f5c0d8d239
1 <?php
3 define("ROOT_TYPE_ID",1);
4 define("ROOT_TYPE_NAME",2);
6 /**
7 * class Tree
8 * This class is a clean implementation of a modified preorder tree traversal hierachy to relational model
9 * Don't use this class directly as it won't work, extend it and set the $this->_table variable, currently
10 * this class needs its own sequence per table. MPTT uses a lot of self referential parent child relationships
11 * and having ids that are more or less sequential makes human reading, fixing and reconstruction much easier.
14 class Tree {
17 * This is the name of the table this tree is stored in
18 * @var string
20 var $_table;
23 * This is a lookup table so that you can get a node name or parent id from its id
24 * @var array
26 var $_id_name;
29 * This is a db abstraction object compatible with ADODB
30 * @var object the constructor expects it to be available as $GLOBALS['adodb']['db']
32 var $_db;
35 * The constructor takes a value and a flag determining if the value is the id of a the desired root node or the name
36 * @param mixed $root name or id of desired root node
37 * @param int $root_type optional flag indicating if $root is a name or id, defaults to id
39 function Tree($root,$root_type = ROOT_TYPE_ID) {
40 $this->_db = $GLOBALS['adodb']['db'];
41 $this->_root = mysql_real_escape_string($root);
42 $this->_root_type = mysql_real_escape_string($root_type);
43 $this->load_tree();
46 function load_tree() {
47 $root = $this->_root;
48 $tree = array();
49 $tree_tmp = array();
51 //get the left and right value of the root node
52 $sql = "SELECT * FROM " . $this->_table . " WHERE id='".$root."'";
54 if ($this->root_type == ROOT_TYPE_NAME) {
55 $sql = "SELECT * FROM " . $this->_table . " WHERE name='".$root."'";
57 $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
58 $row = array();
60 if($result && !$result->EOF) {
61 $row = $result->fields;
63 else {
64 $this->tree = array();
67 // start with an empty right stack
68 $right = array();
70 // now, retrieve all descendants of the root node
71 $sql = "SELECT * FROM " . $this->_table . " WHERE lft BETWEEN " . $row['lft'] . " AND " . $row['rght'] . " ORDER BY parent,name ASC;";
72 $result = $this->_db->Execute($sql);
73 $this->_id_name = array();
76 while ($result && !$result->EOF) {
77 $ar = array();
78 $row = $result->fields;
80 //create a lookup table of id to name for every node that will end up in this tree, this is used
81 //by the array building code below to find the chain of parents for each node
83 // ADDED below by BM on 06-2009 to translate categories, if applicable
84 if ($this->_table == "categories") {
85 $this->_id_name[$row['id']] = array("id" => $row['id'], "name" => xl_document_category($row['name']), "parent" => $row['parent']);
87 else {
88 $this->_id_name[$row['id']] = array("id" => $row['id'], "name" => $row['name'], "parent" => $row['parent']);
91 // only check stack if there is one
92 if (count($right)>0) {
93 // check if we should remove a node from the stack
94 while ($right[count($right)-1]<$row['rght']) {
95 array_pop($right);
99 //set up necessary variables to then determine the chain of parents for each node
100 $parent = $row['parent'];
101 $loop = 0;
103 //this is a string that gets evaled below to create the array representing the tree
104 $ar_string = "[\"".($row['id']) ."\"] = \$row[\"value\"]";
106 //if parent is 0 then the node has no parents, the number of nodes in the id_name lookup always includes any nodes
107 //that could be the parent of any future node in the record set, the order is deterministic because of the algorithm
108 while($parent != 0 && $loop < count($this->_id_name)) {
109 $ar_string = "[\"" . ($this->_id_name[$parent]['id']) . "\"]" . $ar_string;
110 $loop++;
111 $parent = $this->_id_name[$parent]['parent'];
114 $ar_string = '$ar' . $ar_string . ";";
115 //echo $ar_string;
117 //now eval the string to create the tree array
118 //there must be a more efficient way to do this than eval?
119 eval($ar_string);
121 //merge the evaled array with all of the already exsiting tree elements,
122 //merge recursive is used so that no keys are replaced in other words a key
123 //with a specific value will not be replace but instead that value will be turned into an array
124 //consisting of the previous value and the new value
125 $tree = array_merge_n($tree,$ar);
127 // add this node to the stack
128 $right[] = $row['rght'];
129 $result->MoveNext();
132 $this->tree = $tree;
136 * This function completely rebuilds a tree starting from parent to ensure that all of its preorder values
137 * are integrous.
138 * Upside is that it fixes any kind of goofiness, downside is that it is recursive and consequently
139 * exponentially expensive with the size of the tree.
140 * On adds and deletes the tree does dynamic updates as appropriate to maintain integrity of the algorithm,
141 * however you can still force it to do goofy things and afterwards you will need this function to fix it.
142 * If you need to do a huge number of adds or deletes it will be much faster to act directly on the db and then
143 * call this to fix the mess than to use the add and delete functions.
144 * @param int $parent id of the node you would like to rebuild all nodes below
145 * @param int $left optional proper left value of the node you are rebuilding below, then used recursively
147 function rebuild_tree($parent, $left = null) {
149 //if no left is supplied assume the existing left is proper
150 if ($left == null) {
151 $sql = "SELECT lft FROM " . $this->_table . " WHERE id='" . $parent . "';";
152 $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
154 if($result && !$result->EOF) {
155 $left = $result->fields['lft'];
157 else {
158 //the node you are rebuilding below if goofed up and you didn't supply a proper value
159 //nothing we can do so error
160 die("Error: The node you are rebuilding from could not be found, please supply an existing node id.");
163 // get all children of this node
164 $sql = "SELECT id FROM " . $this->_table . " WHERE parent='" . $parent . "' ORDER BY id;";
165 $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
167 // the right value of this node is the left value + 1
168 $right = $left+1;
170 while ($result && !$result->EOF) {
171 $row = $result->fields;
172 // recursive execution of this function for each
173 // child of this node
174 // $right is the current right value, which is
175 // incremented by the rebuild_tree function
176 $right = $this->rebuild_tree($row['id'], $right);
177 $result->MoveNext();
180 // we've got the left value, and now that we've processed
181 // the children of this node we also know the right value
182 $sql = "UPDATE " . $this->_table . " SET lft=".$left.", rght=".$right." WHERE id='".$parent."';";
183 //echo $sql . "<br>";
184 $this->_db->Execute($sql) or die("Error: $sql" . $this->_db->ErrorMsg());
186 // return the right value of this node + 1
187 return $right+1;
192 * Call this to add a new node to the tree
193 * @param int $parent id of the node you would like the new node to have as its parent
194 * @param string $name the name of the new node, it will be used to reference its value in the tree array
195 * @param string $value optional value this node is to contain
196 * @return int id of newly added node
198 function add_node($parent_id,$name,$value="") {
200 $sql = "SELECT * from " . $this->_table . " where parent = '" . $parent_id . "' and name='" . $name . "'";
201 $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
203 if ($result && !$result->EOF) {
204 die("You cannot add a node with the name '" . $name ."' because one already exists under parent " . $parent_id . "<br>");
207 $sql = "SELECT * from " . $this->_table . " where id = '" . $parent_id . "'";
208 $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
210 $next_right = 0;
212 if ($result && !$result->EOF) {
213 $next_right = $result->fields['rght'];
216 $sql = "UPDATE " . $this->_table . " SET rght=rght+2 WHERE rght>=" . $next_right;
217 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
218 $sql = "UPDATE " . $this->_table . " SET lft=lft+2 WHERE lft>=" . $next_right;
219 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
221 $id = $this->_db->GenID($this->_table . "_seq");
222 $sql = "INSERT INTO " . $this->_table . " SET name='" . $name . "', value='" . $value . "', lft='" . $next_right . "', rght='" . ($next_right + 1) . "', parent='" . $parent_id . "', id='" . $id . "'";
223 $this->_db->Execute($sql) or die("Error: $sql :: " . $this->_db->ErrorMsg());
224 //$this->rebuild_tree(1,1);
225 $this->load_tree();
226 return $id;
230 * Call this to delete a node from the tree, the nodes children (and their children, etc) will become children
231 * of the deleted nodes parent
232 * @param int $id id of the node you want to delete
234 function delete_node($id) {
236 $sql = "SELECT * from " . $this->_table . " where id = '" . $id . "'";
237 //echo $sql . "<br>";
238 $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
240 $left = 0;
241 $right = 1;
242 $new_parent = 0;
244 if ($result && !$result->EOF) {
245 $left = $result->fields['lft'];
246 $right = $result->fields['rght'];
247 $new_parent = $result->fields['parent'];
250 $sql = "UPDATE " . $this->_table . " SET rght=rght-2 WHERE rght>" . $right;
251 //echo $sql . "<br>";
252 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
254 $sql = "UPDATE " . $this->_table . " SET lft=lft-2 WHERE lft>" . $right;
255 //echo $sql . "<br>";
256 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
258 $sql = "UPDATE " . $this->_table . " SET lft=lft-1, rght=rght-1 WHERE lft>" . $left . " and rght < " . $right;
259 //echo $sql . "<br>";
260 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
262 //only update the childrens parent setting if the node has children
263 if ($right > ($left +1)) {
264 $sql = "UPDATE " . $this->_table . " SET parent='" . $new_parent . "' WHERE parent='" . $id . "'";
265 //echo $sql . "<br>";
266 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
269 $sql = "DELETE FROM " . $this->_table . " where id='" . $id . "'";
270 //echo $sql . "<br>";
271 $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
272 $this->load_tree();
274 return true;
277 function get_node_info($id) {
278 if(!empty($this->_id_name[$id])) {
279 return $this->_id_name[$id];
281 else {
282 return array();
286 function get_node_name($id) {
287 if(!empty($this->_id_name[$id])) {
288 return $this->_id_name[$id]['name'];
290 else {
291 return false;
297 function array_merge_2(&$array, &$array_i) {
298 // For each element of the array (key => value):
299 foreach ($array_i as $k => $v) {
300 // If the value itself is an array, the process repeats recursively:
301 if (is_array($v)) {
302 if (!isset($array[$k])) {
303 $array[$k] = array();
305 array_merge_2($array[$k], $v);
307 // Else, the value is assigned to the current element of the resulting array:
308 } else {
309 if (isset($array[$k]) && is_array($array[$k])) {
310 $array[$k][0] = $v;
311 } else {
312 if (isset($array) && !is_array($array)) {
313 $temp = $array;
314 $array = array();
315 $array[0] = $temp;
317 $array[$k] = $v;
324 function array_merge_n() {
325 // Initialization of the resulting array:
326 $array = array();
328 // Arrays to be merged (function's arguments):
329 $arrays =& func_get_args();
331 // Merging of each array with the resulting one:
332 foreach ($arrays as $array_i) {
333 if (is_array($array_i)) {
334 array_merge_2($array, $array_i);
338 return $array;
343 $db = $GLOBALS['adodb']['db'];
344 $sql = "USE document;";
345 $db->Execute($sql);
346 $t = new Tree(1);
347 echo "<pre>";
348 print_r($t->tree);
349 //$nid = $t->add_node(0,"test node2","test value");
350 //$t->add_node($nid,"test child","another value");
351 //$t->add_node($nid,"test child");
352 print_r($t->tree);
353 echo "</pre>";