3 define("ROOT_TYPE_ID", 1);
4 define("ROOT_TYPE_NAME", 2);
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.
17 * This is the name of the table this tree is stored in
23 * This is a lookup table so that you can get a node name or parent id from its id
29 * This is a db abstraction object compatible with ADODB
30 * @var object the constructor expects it to be available as $GLOBALS['adodb']['db']
39 * The constructor takes a value and a flag determining if the value is the id of a the desired root node or the name
40 * @param mixed $root name or id of desired root node
41 * @param int $root_type optional flag indicating if $root is a name or id, defaults to id
43 function __construct($root, $root_type = ROOT_TYPE_ID
)
45 $this->_db
= $GLOBALS['adodb']['db'];
47 $this->_root_type
= $root_type;
51 function should_translate_name()
56 function get_translated_name($name)
67 //get the left and right value of the root node
68 $sql = "SELECT * FROM " . $this->_table
. " WHERE id=?";
70 if ($this->_root_type
== ROOT_TYPE_NAME
) {
71 $sql = "SELECT * FROM " . $this->_table
. " WHERE name=?";
74 $result = $this->_db
->Execute($sql, [$root]) or die("Error: " . text($this->_db
->ErrorMsg()));
77 if ($result && !$result->EOF
) {
78 $row = $result->fields
;
80 $this->tree
= array();
83 // start with an empty right stack
86 // now, retrieve all descendants of the root node
87 $sql = "SELECT * FROM " . $this->_table
. " WHERE lft BETWEEN ? AND ? ORDER BY parent,name ASC;";
88 $result = $this->_db
->Execute($sql, [$row['lft'], $row['rght']]);
89 $this->_id_name
= array();
92 while ($result && !$result->EOF
) {
94 $row = $result->fields
;
96 //create a lookup table of id to name for every node that will end up in this tree, this is used
97 //by the array building code below to find the chain of parents for each node
99 foreach ($row as $key => $value) {
100 $id_name[$key] = $value;
103 // now handle any translations if needed
104 if ($this->should_translate_name()) {
105 $id_name['name'] = $this->get_translated_name($id_name['name']);
107 $this->_id_name
[$id_name['id']] = $id_name;
109 // only check stack if there is one
110 if (count($right) > 0) {
111 // check if we should remove a node from the stack
112 while ($right[count($right) - 1] < $row['rght']) {
117 //set up necessary variables to then determine the chain of parents for each node
118 $parent = $row['parent'];
121 //this is a string that gets evaled below to create the array representing the tree
122 $ar_string = "[\"" . ($row['id']) . "\"] = \$row[\"value\"]";
124 //if parent is 0 then the node has no parents, the number of nodes in the id_name lookup always includes any nodes
125 //that could be the parent of any future node in the record set, the order is deterministic because of the algorithm
126 while ($parent != 0 && $loop < count($this->_id_name
)) {
127 $ar_string = "[\"" . ($this->_id_name
[$parent]['id']) . "\"]" . $ar_string;
129 $parent = $this->_id_name
[$parent]['parent'];
132 $ar_string = '$ar' . $ar_string . ";";
135 //now eval the string to create the tree array
136 //there must be a more efficient way to do this than eval?
137 // TODO: refactor this eval out... there's tons of ways to construct trees w/o needing to do eval code.
138 // not sure how many nodes they needed to account for, but our category heirarchy has to be less than a few
139 // thousand records. An n-ary tree w/ pointers would accomplish this very quickly w/o the potential of sneaking a eval
140 // code execution into our category database names.
141 // There could be tens of thousands of documents, However, leaf nodes which are documents will not have any
142 // sub-chilsren and so we don't have to deal with this whole left/right nonsense and only need a parent node
143 // which we sort by document name order.
146 //merge the evaled array with all of the already exsiting tree elements,
147 //merge recursive is used so that no keys are replaced in other words a key
148 //with a specific value will not be replace but instead that value will be turned into an array
149 //consisting of the previous value and the new value
150 $tree = array_merge_n($tree, $ar);
152 // add this node to the stack
153 $right[] = $row['rght'];
161 * This function completely rebuilds a tree starting from parent to ensure that all of its preorder values
163 * Upside is that it fixes any kind of goofiness, downside is that it is recursive and consequently
164 * exponentially expensive with the size of the tree.
165 * On adds and deletes the tree does dynamic updates as appropriate to maintain integrity of the algorithm,
166 * however you can still force it to do goofy things and afterwards you will need this function to fix it.
167 * 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
168 * call this to fix the mess than to use the add and delete functions.
169 * @param int $parent id of the node you would like to rebuild all nodes below
170 * @param int $left optional proper left value of the node you are rebuilding below, then used recursively
172 function rebuild_tree($parent, $left = null)
175 //if no left is supplied assume the existing left is proper
177 $sql = "SELECT lft FROM " . $this->_table
. " WHERE id=?;";
178 $result = $this->_db
->Execute($sql, [$parent]) or die("Error: " . text($this->_db
->ErrorMsg()));
180 if ($result && !$result->EOF
) {
181 $left = $result->fields
['lft'];
183 //the node you are rebuilding below if goofed up and you didn't supply a proper value
184 //nothing we can do so error
185 die("Error: The node you are rebuilding from could not be found, please supply an existing node id.");
189 // get all children of this node
190 $sql = "SELECT id FROM " . $this->_table
. " WHERE parent=? ORDER BY id;";
191 $result = $this->_db
->Execute($sql, [$parent]) or die("Error: " . text($this->_db
->ErrorMsg()));
193 // the right value of this node is the left value + 1
196 while ($result && !$result->EOF
) {
197 $row = $result->fields
;
198 // recursive execution of this function for each
199 // child of this node
200 // $right is the current right value, which is
201 // incremented by the rebuild_tree function
202 $right = $this->rebuild_tree($row['id'], $right);
206 // we've got the left value, and now that we've processed
207 // the children of this node we also know the right value
208 $sql = "UPDATE " . $this->_table
. " SET lft=?, rght=? WHERE id=?;";
209 //echo $sql . "<br />";
210 $this->_db
->Execute($sql, [$left, $right, $parent]) or die("Error: " . text($sql) . " " . text($this->_db
->ErrorMsg()));
212 // return the right value of this node + 1
218 * Call this to add a new node to the tree
219 * @param int $parent id of the node you would like the new node to have as its parent
220 * @param string $name the name of the new node, it will be used to reference its value in the tree array
221 * @param string $value optional value this node is to contain
222 * @param string $aco_spec optional ACO value in section|value format
223 * @param string $codes optional Medical codes to use (LOINC, SNOMED, etc) for this node.
224 * @return int id of newly added node
226 function add_node($parent_id, $name, $value = "", $aco_spec = "patients|docs", $codes = "")
229 $sql = "SELECT * from " . $this->_table
. " where parent = ? and name=?";
230 $result = $this->_db
->Execute($sql, [$parent_id, $name]) or die("Error: " . text($this->_db
->ErrorMsg()));
232 if ($result && !$result->EOF
) {
233 die("You cannot add a node with the name '" . text($name) . "' because one already exists under parent " . text($parent_id) . "<br />");
236 $sql = "SELECT * from " . $this->_table
. " where id = ?";
237 $result = $this->_db
->Execute($sql, [$parent_id]) or die("Error: " . text($this->_db
->ErrorMsg()));
241 if ($result && !$result->EOF
) {
242 $next_right = $result->fields
['rght'];
245 $sql = "UPDATE " . $this->_table
. " SET rght=rght+2 WHERE rght>=?";
246 $this->_db
->Execute($sql, [$next_right]) or die("Error: " . text($this->_db
->ErrorMsg()));
247 $sql = "UPDATE " . $this->_table
. " SET lft=lft+2 WHERE lft>=?";
248 $this->_db
->Execute($sql, [$next_right]) or die("Error: " . text($this->_db
->ErrorMsg()));
250 $id = $this->_db
->GenID($this->_table
. "_seq");
251 $sql = "INSERT INTO " . $this->_table
. " SET name=?, value=?, aco_spec=?, codes=?, lft=?, rght=?, parent=?, id=?";
252 $this->_db
->Execute($sql, [$name, $value, $aco_spec, $codes, $next_right, ($next_right +
1), $parent_id, $id]) or die("Error: " . text($sql) . " :: " . text($this->_db
->ErrorMsg()));
253 //$this->rebuild_tree(1,1);
259 * Call this to modify a node's attributes.
260 * @param int $id id of the node to change
261 * @param string $name the new name of the new node
262 * @param string $value optional value this node is to contain
263 * @param string $aco_spec optional ACO value in section|value format
264 * @param string $codes optional Medical codes to use (LOINC, SNOMED, etc) for this node.
265 * @return int same as input id
267 function edit_node($id, $name, $value = "", $aco_spec = "patients|docs", $codes = "")
269 $sql = "SELECT c2.id FROM " . $this->_table
. " AS c1, " . $this->_table
. " AS c2 WHERE " .
270 "c1.id = ? AND c2.id != c1.id AND c2.parent = c1.parent AND c2.name = ?";
271 $result = $this->_db
->Execute($sql, [$id, $name]) or die(xlt('Error') . ": " . text($this->_db
->ErrorMsg()));
272 if ($result && !$result->EOF
) {
273 die(xlt('This name already exists under this parent.') . "<br />");
276 $sql = "UPDATE " . $this->_table
. " SET name = ?, value = ?, aco_spec = ?, codes = ? WHERE id = ?";
277 $this->_db
->Execute($sql, [$name, $value, $aco_spec, $codes, $id]) or die(xlt('Error') . ": " . text($this->_db
->ErrorMsg()));
283 * Call this to delete a node from the tree, the nodes children (and their children, etc) will become children
284 * of the deleted nodes parent
285 * @param int $id id of the node you want to delete
287 function delete_node($id)
290 $sql = "SELECT * from " . $this->_table
. " where id = ?";
291 //echo $sql . "<br />";
292 $result = $this->_db
->Execute($sql, [$id]) or die("Error: " . text($this->_db
->ErrorMsg()));
298 if ($result && !$result->EOF
) {
299 $left = $result->fields
['lft'];
300 $right = $result->fields
['rght'];
301 $new_parent = $result->fields
['parent'];
304 $sql = "UPDATE " . $this->_table
. " SET rght=rght-2 WHERE rght>?";
305 //echo $sql . "<br />";
306 $this->_db
->Execute($sql, [$right]) or die("Error: " . text($this->_db
->ErrorMsg()));
308 $sql = "UPDATE " . $this->_table
. " SET lft=lft-2 WHERE lft>?";
309 //echo $sql . "<br />";
310 $this->_db
->Execute($sql, [$right]) or die("Error: " . text($this->_db
->ErrorMsg()));
312 $sql = "UPDATE " . $this->_table
. " SET lft=lft-1, rght=rght-1 WHERE lft>? and rght < ?";
313 //echo $sql . "<br />";
314 $this->_db
->Execute($sql, [$left, $right]) or die("Error: " . text($this->_db
->ErrorMsg()));
316 //only update the childrens parent setting if the node has children
317 if ($right > ($left +
1)) {
318 $sql = "UPDATE " . $this->_table
. " SET parent=? WHERE parent=?";
319 //echo $sql . "<br />";
320 $this->_db
->Execute($sql, [$new_parent, $id]) or die("Error: " . text($this->_db
->ErrorMsg()));
323 $sql = "DELETE FROM " . $this->_table
. " where id=?";
324 //echo $sql . "<br />";
325 $this->_db
->Execute($sql, [$id]) or die("Error: " . text($this->_db
->ErrorMsg()));
331 function get_node_info($id)
333 if (!empty($this->_id_name
[$id])) {
334 return $this->_id_name
[$id];
340 function get_node_name($id)
342 if (!empty($this->_id_name
[$id])) {
343 return $this->_id_name
[$id]['name'];
350 function array_merge_2(&$array, &$array_i)
352 // For each element of the array (key => value):
353 foreach ($array_i as $k => $v) {
354 // If the value itself is an array, the process repeats recursively:
356 if (!isset($array[$k])) {
357 $array[$k] = array();
360 array_merge_2($array[$k], $v);
362 // Else, the value is assigned to the current element of the resulting array:
364 if (isset($array[$k]) && is_array($array[$k])) {
367 if (isset($array) && !is_array($array)) {
380 function array_merge_n()
382 // Initialization of the resulting array:
385 // Arrays to be merged (function's arguments):
386 $arrays = func_get_args();
388 // Merging of each array with the resulting one:
389 foreach ($arrays as $array_i) {
390 if (is_array($array_i)) {
391 array_merge_2($array, $array_i);