library/classes/Tree.class.php

   1 <?php
   2
   3 define("ROOT_TYPE_ID", 1);
   4 define("ROOT_TYPE_NAME", 2);
   5
   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.
  12  */
  13
  14 class Tree
  15 {
  16     /*
  17     *   This is the name of the table this tree is stored in
  18     *   @var string
  19     */
  20     var $_table;
  21
  22     /*
  23     *   This is a lookup table so that you can get a node name or parent id from its id
  24     *   @var array
  25     */
  26     var $_id_name;
  27
  28     /*
  29     *   This is a db abstraction object compatible with ADODB
  30     *   @var object the constructor expects it to be available as $GLOBALS['adodb']['db']
  31     */
  32     var $_db;
  33
  34     /*
  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
  38     */
  39     function __construct($root, $root_type = ROOT_TYPE_ID)
  40     {
  41         $this->_db = $GLOBALS['adodb']['db'];
  42         $this->_root = $root;
  43         $this->_root_type = $root_type;
  44         $this->load_tree();
  45     }
  46
  47     function load_tree()
  48     {
  49         $root = $this->_root;
  50         $tree = array();
  51         $tree_tmp = array();
  52
  53         //get the left and right value of the root node
  54         $sql = "SELECT * FROM " . $this->_table . " WHERE id=?";
  55
  56         if ($this->_root_type == ROOT_TYPE_NAME) {
  57             $sql = "SELECT * FROM " . $this->_table . " WHERE name=?";
  58         }
  59
  60         $result = $this->_db->Execute($sql, [$root]) or die("Error: " . text($this->_db->ErrorMsg()));
  61         $row = array();
  62
  63         if ($result && !$result->EOF) {
  64             $row = $result->fields;
  65         } else {
  66             $this->tree = array();
  67         }
  68
  69         // start with an empty right stack
  70         $right = array();
  71
  72         // now, retrieve all descendants of the root node
  73         $sql = "SELECT * FROM " . $this->_table . " WHERE lft BETWEEN ? AND ? ORDER BY parent,name ASC;";
  74         $result = $this->_db->Execute($sql, [$row['lft'], $row['rght']]);
  75         $this->_id_name = array();
  76
  77
  78         while ($result && !$result->EOF) {
  79             $ar = array();
  80             $row = $result->fields;
  81
  82             //create a lookup table of id to name for every node that will end up in this tree, this is used
  83             //by the array building code below to find the chain of parents for each node
  84
  85             // ADDED below by BM on 06-2009 to translate categories, if applicable
  86             if ($this->_table == "categories") {
  87                 $this->_id_name[$row['id']] = array("id" => $row['id'], "name" => xl_document_category($row['name']),
  88                 "parent" => $row['parent'], "value" => $row['value'], "aco_spec" => $row['aco_spec']);
  89             } else {
  90                 $this->_id_name[$row['id']] = array("id" => $row['id'], "name" => $row['name'], "parent" => $row['parent']);
  91             }
  92
  93             // only check stack if there is one
  94             if (count($right) > 0) {
  95                 // check if we should remove a node from the stack
  96                 while ($right[count($right) - 1] < $row['rght']) {
  97                     array_pop($right);
  98                 }
  99             }
 100
 101             //set up necessary variables to then determine the chain of parents for each node
 102             $parent = $row['parent'];
 103             $loop = 0;
 104
 105             //this is a string that gets evaled below to create the array representing the tree
 106             $ar_string = "[\"" . ($row['id']) . "\"] = \$row[\"value\"]";
 107
 108             //if parent is 0 then the node has no parents, the number of nodes in the id_name lookup always includes any nodes
 109             //that could be the parent of any future node in the record set, the order is deterministic because of the algorithm
 110             while ($parent != 0 && $loop < count($this->_id_name)) {
 111                 $ar_string = "[\"" . ($this->_id_name[$parent]['id']) . "\"]" . $ar_string;
 112                 $loop++;
 113                 $parent = $this->_id_name[$parent]['parent'];
 114             }
 115
 116             $ar_string = '$ar' . $ar_string . ";";
 117             //echo $ar_string;
 118
 119             //now eval the string to create the tree array
 120             //there must be a more efficient way to do this than eval?
 121             eval($ar_string);
 122
 123             //merge the evaled array with all of the already exsiting tree elements,
 124             //merge recursive is used so that no keys are replaced in other words a key
 125             //with a specific value will not be replace but instead that value will be turned into an array
 126             //consisting of the previous value and the new value
 127             $tree = array_merge_n($tree, $ar);
 128
 129             // add this node to the stack
 130             $right[] = $row['rght'];
 131             $result->MoveNext();
 132         }
 133
 134         $this->tree = $tree;
 135     }
 136
 137     /*
 138     *   This function completely rebuilds a tree starting from parent to ensure that all of its preorder values
 139     *   are integrous.
 140     *   Upside is that it fixes any kind of goofiness, downside is that it is recursive and consequently
 141     *   exponentially expensive with the size of the tree.
 142     *   On adds and deletes the tree does dynamic updates as appropriate to maintain integrity of the algorithm,
 143     *   however you can still force it to do goofy things and afterwards you will need this function to fix it.
 144     *   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
 145     *   call this to fix the mess than to use the add and delete functions.
 146     *   @param int $parent id of the node you would like to rebuild all nodes below
 147     *   @param int $left optional proper left value of the node you are rebuilding below, then used recursively
 148     */
 149     function rebuild_tree($parent, $left = null)
 150     {
 151
 152         //if no left is supplied assume the existing left is proper
 153         if ($left == null) {
 154             $sql = "SELECT lft FROM " . $this->_table . " WHERE id=?;";
 155             $result = $this->_db->Execute($sql, [$parent]) or die("Error: " . text($this->_db->ErrorMsg()));
 156
 157             if ($result && !$result->EOF) {
 158                 $left = $result->fields['lft'];
 159             } else {
 160                 //the node you are rebuilding below if goofed up and you didn't supply a proper value
 161                 //nothing we can do so error
 162                 die("Error: The node you are rebuilding from could not be found, please supply an existing node id.");
 163             }
 164         }
 165
 166         // get all children of this node
 167         $sql = "SELECT id FROM " . $this->_table . " WHERE parent=? ORDER BY id;";
 168         $result = $this->_db->Execute($sql, [$parent]) or die("Error: " . text($this->_db->ErrorMsg()));
 169
 170         // the right value of this node is the left value + 1
 171         $right = $left + 1;
 172
 173         while ($result && !$result->EOF) {
 174             $row = $result->fields;
 175             // recursive execution of this function for each
 176             // child of this node
 177             // $right is the current right value, which is
 178             // incremented by the rebuild_tree function
 179             $right = $this->rebuild_tree($row['id'], $right);
 180             $result->MoveNext();
 181         }
 182
 183         // we've got the left value, and now that we've processed
 184         // the children of this node we also know the right value
 185         $sql = "UPDATE " . $this->_table . " SET lft=?, rght=? WHERE id=?;";
 186         //echo $sql . "<br />";
 187         $this->_db->Execute($sql, [$left, $right, $parent]) or die("Error: " . text($sql) . " " . text($this->_db->ErrorMsg()));
 188
 189         // return the right value of this node + 1
 190         return $right + 1;
 191     }
 192
 193
 194     /*
 195     *   Call this to add a new node to the tree
 196     *   @param int $parent id of the node you would like the new node to have as its parent
 197     *   @param string $name the name of the new node, it will be used to reference its value in the tree array
 198     *   @param string $value optional value this node is to contain
 199     *   @param string $aco_spec optional ACO value in section|value format
 200     *   @return int id of newly added node
 201     */
 202     function add_node($parent_id, $name, $value = "", $aco_spec = "patients|docs")
 203     {
 204
 205         $sql = "SELECT * from " . $this->_table . " where parent = ? and name=?";
 206         $result = $this->_db->Execute($sql, [$parent_id, $name]) or die("Error: " . text($this->_db->ErrorMsg()));
 207
 208         if ($result && !$result->EOF) {
 209             die("You cannot add a node with the name '" . text($name) . "' because one already exists under parent " . text($parent_id) . "<br />");
 210         }
 211
 212         $sql = "SELECT * from " . $this->_table . " where id = ?";
 213         $result = $this->_db->Execute($sql, [$parent_id]) or die("Error: " . text($this->_db->ErrorMsg()));
 214
 215         $next_right = 0;
 216
 217         if ($result && !$result->EOF) {
 218             $next_right = $result->fields['rght'];
 219         }
 220
 221         $sql = "UPDATE " . $this->_table . " SET rght=rght+2 WHERE rght>=?";
 222         $this->_db->Execute($sql, [$next_right]) or die("Error: " . text($this->_db->ErrorMsg()));
 223         $sql = "UPDATE " . $this->_table . " SET lft=lft+2 WHERE lft>=?";
 224         $this->_db->Execute($sql, [$next_right]) or die("Error: " . text($this->_db->ErrorMsg()));
 225
 226         $id = $this->_db->GenID($this->_table . "_seq");
 227         $sql = "INSERT INTO " . $this->_table . " SET name=?, value=?, aco_spec=?, lft=?, rght=?, parent=?, id=?";
 228         $this->_db->Execute($sql, [$name, $value, $aco_spec, $next_right, ($next_right + 1), $parent_id, $id]) or die("Error: " . text($sql) . " :: " . text($this->_db->ErrorMsg()));
 229       //$this->rebuild_tree(1,1);
 230         $this->load_tree();
 231         return $id;
 232     }
 233
 234     /*
 235     *   Call this to modify a node's attributes.
 236     *   @param int $id id of the node to change
 237     *   @param string $name the new name of the new node
 238     *   @param string $value optional value this node is to contain
 239     *   @param string $aco_spec optional ACO value in section|value format
 240     *   @return int same as input id
 241     */
 242     function edit_node($id, $name, $value = "", $aco_spec = "patients|docs")
 243     {
 244         $sql = "SELECT c2.id FROM " . $this->_table . " AS c1, " . $this->_table . " AS c2 WHERE " .
 245         "c1.id = ? AND c2.id != c1.id AND c2.parent = c1.parent AND c2.name = ?";
 246         $result = $this->_db->Execute($sql, [$id, $name]) or die(xlt('Error') . ": " . text($this->_db->ErrorMsg()));
 247         if ($result && !$result->EOF) {
 248               die(xlt('This name already exists under this parent.') . "<br />");
 249         }
 250
 251         $sql = "UPDATE " . $this->_table . " SET name = ?, value = ?, aco_spec = ? WHERE id = ?";
 252         $this->_db->Execute($sql, [$name, $value, $aco_spec, $id]) or die(xlt('Error') . ": " . text($this->_db->ErrorMsg()));
 253         $this->load_tree();
 254         return $id;
 255     }
 256
 257     /*
 258     *   Call this to delete a node from the tree, the nodes children (and their children, etc) will become children
 259     *   of the deleted nodes parent
 260     *   @param int $id id of the node you want to delete
 261     */
 262     function delete_node($id)
 263     {
 264
 265         $sql = "SELECT * from " . $this->_table . " where id = ?";
 266         //echo $sql . "<br />";
 267         $result = $this->_db->Execute($sql, [$id]) or die("Error: " . text($this->_db->ErrorMsg()));
 268
 269         $left = 0;
 270         $right = 1;
 271         $new_parent = 0;
 272
 273         if ($result && !$result->EOF) {
 274             $left = $result->fields['lft'];
 275             $right = $result->fields['rght'];
 276             $new_parent = $result->fields['parent'];
 277         }
 278
 279         $sql = "UPDATE " . $this->_table . " SET rght=rght-2 WHERE rght>?";
 280         //echo $sql . "<br />";
 281         $this->_db->Execute($sql, [$right]) or die("Error: " . text($this->_db->ErrorMsg()));
 282
 283         $sql = "UPDATE " . $this->_table . " SET lft=lft-2 WHERE lft>?";
 284         //echo $sql . "<br />";
 285         $this->_db->Execute($sql, [$right]) or die("Error: " . text($this->_db->ErrorMsg()));
 286
 287         $sql = "UPDATE " . $this->_table . " SET lft=lft-1, rght=rght-1 WHERE lft>? and rght < ?";
 288         //echo $sql . "<br />";
 289         $this->_db->Execute($sql, [$left, $right]) or die("Error: " . text($this->_db->ErrorMsg()));
 290
 291         //only update the childrens parent setting if the node has children
 292         if ($right > ($left + 1)) {
 293             $sql = "UPDATE " . $this->_table . " SET parent=? WHERE parent=?";
 294             //echo $sql . "<br />";
 295             $this->_db->Execute($sql, [$new_parent, $id]) or die("Error: " . text($this->_db->ErrorMsg()));
 296         }
 297
 298         $sql = "DELETE FROM " . $this->_table . " where id=?";
 299         //echo $sql . "<br />";
 300         $this->_db->Execute($sql, [$id]) or die("Error: " . text($this->_db->ErrorMsg()));
 301         $this->load_tree();
 302
 303         return true;
 304     }
 305
 306     function get_node_info($id)
 307     {
 308         if (!empty($this->_id_name[$id])) {
 309             return $this->_id_name[$id];
 310         } else {
 311             return array();
 312         }
 313     }
 314
 315     function get_node_name($id)
 316     {
 317         if (!empty($this->_id_name[$id])) {
 318             return $this->_id_name[$id]['name'];
 319         } else {
 320             return false;
 321         }
 322     }
 323 }
 324
 325 function array_merge_2(&$array, &$array_i)
 326 {
 327        // For each element of the array (key => value):
 328     foreach ($array_i as $k => $v) {
 329         // If the value itself is an array, the process repeats recursively:
 330         if (is_array($v)) {
 331             if (!isset($array[$k])) {
 332                 $array[$k] = array();
 333             }
 334
 335             array_merge_2($array[$k], $v);
 336
 337            // Else, the value is assigned to the current element of the resulting array:
 338         } else {
 339             if (isset($array[$k]) && is_array($array[$k])) {
 340                 $array[$k][0] = $v;
 341             } else {
 342                 if (isset($array) && !is_array($array)) {
 343                     $temp = $array;
 344                     $array = array();
 345                     $array[0] = $temp;
 346                 }
 347
 348                 $array[$k] = $v;
 349             }
 350         }
 351     }
 352 }
 353
 354
 355 function array_merge_n()
 356 {
 357     // Initialization of the resulting array:
 358     $array = array();
 359
 360     // Arrays to be merged (function's arguments):
 361     $arrays = func_get_args();
 362
 363     // Merging of each array with the resulting one:
 364     foreach ($arrays as $array_i) {
 365         if (is_array($array_i)) {
 366             array_merge_2($array, $array_i);
 367         }
 368     }
 369
 370     return $array;
 371 }