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 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();
  44         }
  45
  46         function load_tree() {
  47           $root = $this->_root;
  48           $tree = array();
  49           $tree_tmp = array();
  50
  51           //get the left and right value of the root node
  52           $sql = "SELECT * FROM " . $this->_table . " WHERE id='".$root."'";
  53
  54           if ($this->root_type == ROOT_TYPE_NAME) {
  55                 $sql = "SELECT * FROM " . $this->_table . " WHERE name='".$root."'";
  56           }
  57           $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
  58           $row = array();
  59
  60           if($result && !$result->EOF) {
  61             $row = $result->fields;
  62           }
  63           else {
  64                 $this->tree = array();
  65           }
  66
  67           // start with an empty right stack
  68           $right = array();
  69
  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();
  74
  75
  76           while ($result && !$result->EOF) {
  77             $ar = array();
  78             $row = $result->fields;
  79
  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
  82
  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']);
  86             }
  87             else {
  88               $this->_id_name[$row['id']] = array("id" => $row['id'], "name" => $row['name'], "parent" => $row['parent']);
  89             }
  90
  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);
  96               }
  97             }
  98
  99                 //set up necessary variables to then determine the chain of parents for each node
 100             $parent = $row['parent'];
 101             $loop = 0;
 102
 103             //this is a string that gets evaled below to create the array representing the tree
 104             $ar_string = "[\"".($row['id']) ."\"] = \$row[\"value\"]";
 105
 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'];
 112                 }
 113
 114                 $ar_string = '$ar' . $ar_string . ";";
 115                 //echo $ar_string;
 116
 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);
 120
 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);
 126
 127                 // add this node to the stack
 128                 $right[] = $row['rght'];
 129                 $result->MoveNext();
 130           }
 131
 132           $this->tree = $tree;
 133         }
 134
 135         /*
 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
 146         */
 147         function rebuild_tree($parent, $left = null) {
 148
 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());
 153
 154             if($result && !$result->EOF) {
 155                 $left = $result->fields['lft'];
 156             }
 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.");
 161             }
 162           }
 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());
 166
 167           // the right value of this node is the left value + 1
 168           $right = $left+1;
 169
 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();
 178           }
 179
 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());
 185
 186           // return the right value of this node + 1
 187           return $right+1;
 188         }
 189
 190
 191         /*
 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
 197         */
 198         function add_node($parent_id,$name,$value="") {
 199
 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());
 202
 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>");
 205           }
 206
 207           $sql = "SELECT * from " . $this->_table . " where id = '" . $parent_id . "'";
 208           $result = $this->_db->Execute($sql) or die("Error: " . $this->_db->ErrorMsg());
 209
 210           $next_right = 0;
 211
 212           if ($result && !$result->EOF) {
 213             $next_right = $result->fields['rght'];
 214           }
 215
 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());
 220
 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;
 227         }
 228
 229         /*
 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
 233         */
 234         function delete_node($id) {
 235
 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());
 239
 240           $left = 0;
 241           $right = 1;
 242           $new_parent = 0;
 243
 244           if ($result && !$result->EOF) {
 245             $left = $result->fields['lft'];
 246             $right = $result->fields['rght'];
 247             $new_parent = $result->fields['parent'];
 248           }
 249
 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());
 253
 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());
 257
 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());
 261
 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());
 267           }
 268
 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();
 273
 274           return true;
 275         }
 276
 277         function get_node_info($id) {
 278                 if(!empty($this->_id_name[$id])) {
 279                         return $this->_id_name[$id];
 280                 }
 281                 else {
 282                         return array();
 283                 }
 284         }
 285
 286         function get_node_name($id) {
 287                 if(!empty($this->_id_name[$id])) {
 288                         return $this->_id_name[$id]['name'];
 289                 }
 290                 else {
 291                         return false;
 292                 }
 293         }
 294
 295 }
 296
 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();
 304                }
 305                array_merge_2($array[$k], $v);
 306
 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;
 316                    }
 317                    $array[$k] = $v;
 318                }
 319            }
 320        }
 321    }
 322
 323
 324    function array_merge_n() {
 325        // Initialization of the resulting array:
 326        $array = array();
 327
 328        // Arrays to be merged (function's arguments):
 329        $arrays =& func_get_args();
 330
 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);
 335            }
 336        }
 337
 338        return $array;
 339    }
 340
 341
 342 /*
 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>";
 354 */
 355 ?>