ILIAS  Release_4_2_x_branch Revision 61807
 All Data Structures Namespaces Files Functions Variables Groups Pages
class.ilTree.php
Go to the documentation of this file.
1 <?php
2 /* Copyright (c) 1998-2009 ILIAS open source, Extended GPL, see docs/LICENSE */
3 
4 define("IL_LAST_NODE", -2);
5 define("IL_FIRST_NODE", -1);
6 
21 class ilTree
22 {
28  var $ilias;
29 
30 
36  var $log;
37 
43  var $root_id;
44 
50  var $tree_id;
51 
57  var $table_tree;
58 
64  var $table_obj_data;
65 
71  var $table_obj_reference;
72 
78  var $ref_pk;
79 
85  var $obj_pk;
86 
92  var $tree_pk;
93 
118  var $gap;
119 
120  protected $depth_cache = array();
121  protected $parent_cache = array();
122 
123 
130  function ilTree($a_tree_id, $a_root_id = 0)
131  {
132  global $ilDB,$ilErr,$ilias,$ilLog;
133 
134  // set db & error handler
135  $this->ilDB = $ilDB;
136 
137  if (!isset($ilErr))
138  {
139  $ilErr = new ilErrorHandling();
140  $ilErr->setErrorHandling(PEAR_ERROR_CALLBACK,array($ilErr,'errorHandler'));
141  }
142  else
143  {
144  $this->ilErr = $ilErr;
145  }
146 
147  $this->lang_code = "en";
148 
149  if (!isset($a_tree_id) or (func_num_args() == 0) )
150  {
151  $this->ilErr->raiseError(get_class($this)."::Constructor(): No tree_id given!",$this->ilErr->WARNING);
152  }
153 
154  if (func_num_args() > 2)
155  {
156  $this->ilErr->raiseError(get_class($this)."::Constructor(): Wrong parameter count!",$this->ilErr->WARNING);
157  }
158 
159  // CREATE LOGGER INSTANCE
160  $this->log = $ilLog;
161 
162  //init variables
163  if (empty($a_root_id))
164  {
165  $a_root_id = ROOT_FOLDER_ID;
166  }
167 
168  $this->tree_id = $a_tree_id;
169  $this->root_id = $a_root_id;
170  $this->table_tree = 'tree';
171  $this->table_obj_data = 'object_data';
172  $this->table_obj_reference = 'object_reference';
173  $this->ref_pk = 'ref_id';
174  $this->obj_pk = 'obj_id';
175  $this->tree_pk = 'tree';
176 
177  $this->use_cache = true;
178 
179  // If cache is activated, cache object translations to improve performance
180  $this->translation_cache = array();
181  $this->parent_type_cache = array();
182 
183  // By default, we create gaps in the tree sequence numbering for 50 nodes
184  $this->gap = 50;
185  }
186 
190  public function useCache($a_use = true)
191  {
192  $this->use_cache = $a_use;
193  }
194 
199  public function isCacheUsed()
200  {
201  return $this->__isMainTree() and $this->use_cache;
202  }
203 
208  function initLangCode()
209  {
210  global $ilUser;
211 
212  // lang_code is only required in $this->fetchnodedata
213  if (!is_object($ilUser))
214  {
215  $this->lang_code = "en";
216  }
217  else
218  {
219  $this->lang_code = $ilUser->getCurrentLanguage();
220  }
221  }
222 
223 
238  function setTableNames($a_table_tree,$a_table_obj_data,$a_table_obj_reference = "")
239  {
240  if (!isset($a_table_tree) or !isset($a_table_obj_data))
241  {
242  $this->ilErr->raiseError(get_class($this)."::setTableNames(): Missing parameter! ".
243  "tree table: ".$a_table_tree." object data table: ".$a_table_obj_data,$this->ilErr->WARNING);
244  }
245 
246  $this->table_tree = $a_table_tree;
247  $this->table_obj_data = $a_table_obj_data;
248  $this->table_obj_reference = $a_table_obj_reference;
249 
250  return true;
251  }
252 
259  function setReferenceTablePK($a_column_name)
260  {
261  if (!isset($a_column_name))
262  {
263  $this->ilErr->raiseError(get_class($this)."::setReferenceTablePK(): No column name given!",$this->ilErr->WARNING);
264  }
265 
266  $this->ref_pk = $a_column_name;
267  return true;
268  }
269 
276  function setObjectTablePK($a_column_name)
277  {
278  if (!isset($a_column_name))
279  {
280  $this->ilErr->raiseError(get_class($this)."::setObjectTablePK(): No column name given!",$this->ilErr->WARNING);
281  }
282 
283  $this->obj_pk = $a_column_name;
284  return true;
285  }
286 
293  function setTreeTablePK($a_column_name)
294  {
295  if (!isset($a_column_name))
296  {
297  $this->ilErr->raiseError(get_class($this)."::setTreeTablePK(): No column name given!",$this->ilErr->WARNING);
298  }
299 
300  $this->tree_pk = $a_column_name;
301  return true;
302  }
303 
309  function buildJoin()
310  {
311  if ($this->table_obj_reference)
312  {
313  // Use inner join instead of left join to improve performance
314  return "JOIN ".$this->table_obj_reference." ON ".$this->table_tree.".child=".$this->table_obj_reference.".".$this->ref_pk." ".
315  "JOIN ".$this->table_obj_data." ON ".$this->table_obj_reference.".".$this->obj_pk."=".$this->table_obj_data.".".$this->obj_pk." ";
316  }
317  else
318  {
319  // Use inner join instead of left join to improve performance
320  return "JOIN ".$this->table_obj_data." ON ".$this->table_tree.".child=".$this->table_obj_data.".".$this->obj_pk." ";
321  }
322  }
323 
332  function getChilds($a_node_id, $a_order = "", $a_direction = "ASC")
333  {
334  global $ilBench,$ilDB, $ilObjDataCache, $ilUser;
335 
336  if (!isset($a_node_id))
337  {
338  $message = get_class($this)."::getChilds(): No node_id given!";
339  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
340  }
341 
342  // init childs
343  $childs = array();
344 
345  // number of childs
346  $count = 0;
347 
348  // init order_clause
349  $order_clause = "";
350 
351  // set order_clause if sort order parameter is given
352  if (!empty($a_order))
353  {
354  $order_clause = "ORDER BY ".$a_order." ".$a_direction;
355  }
356  else
357  {
358  $order_clause = "ORDER BY ".$this->table_tree.".lft";
359  }
360 
361 
362  $query = sprintf('SELECT * FROM '.$this->table_tree.' '.
363  $this->buildJoin().
364  "WHERE parent = %s " .
365  "AND ".$this->table_tree.".".$this->tree_pk." = %s ".
366  $order_clause,
367  $ilDB->quote($a_node_id,'integer'),
368  $ilDB->quote($this->tree_id,'integer'));
369 
370  $res = $ilDB->query($query);
371 
372  if(!$count = $res->numRows())
373  {
374  return array();
375  }
376 
377  // get rows and object ids
378  $rows = array();
379  while($r = $ilDB->fetchAssoc($res))
380  {
381  $rows[] = $r;
382  $obj_ids[] = $r["obj_id"];
383  }
384 
385  // preload object translation information
386  if ($this->__isMainTree() && $this->isCacheUsed() && is_object($ilObjDataCache) &&
387  is_object($ilUser) && $this->lang_code == $ilUser->getLanguage() && !$this->oc_preloaded[$a_node_id])
388  {
389 // $ilObjDataCache->preloadTranslations($obj_ids, $this->lang_code);
390  $ilObjDataCache->preloadObjectCache($obj_ids, $this->lang_code);
391  $this->fetchTranslationFromObjectDataCache($obj_ids);
392  $this->oc_preloaded[$a_node_id] = true;
393  }
394 
395  foreach ($rows as $row)
396  {
397  $childs[] = $this->fetchNodeData($row);
398 
399  // Update cache of main tree
400  if ($this->__isMainTree())
401  {
402  #$GLOBALS['ilLog']->write(__METHOD__.': Storing in tree cache '.$row['child'].' = true');
403  $this->in_tree_cache[$row['child']] = $row['tree'] == 1;
404  }
405  }
406  $childs[$count - 1]["last"] = true;
407  return $childs;
408  }
409 
419  function getFilteredChilds($a_filter,$a_node,$a_order = "",$a_direction = "ASC")
420  {
421  $childs = $this->getChilds($a_node,$a_order,$a_direction);
422 
423  foreach($childs as $child)
424  {
425  if(!in_array($child["type"],$a_filter))
426  {
427  $filtered[] = $child;
428  }
429  }
430  return $filtered ? $filtered : array();
431  }
432 
433 
441  function getChildsByType($a_node_id,$a_type)
442  {
443  global $ilDB;
444 
445  if (!isset($a_node_id) or !isset($a_type))
446  {
447  $message = get_class($this)."::getChildsByType(): Missing parameter! node_id:".$a_node_id." type:".$a_type;
448  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
449  }
450 
451  if ($a_type=='rolf' && $this->table_obj_reference) {
452  // Performance optimization: A node can only have exactly one
453  // role folder as its child. Therefore we don't need to sort the
454  // results, and we can let the database know about the expected limit.
455  $ilDB->setLimit(1,0);
456  $query = sprintf("SELECT * FROM ".$this->table_tree." ".
457  $this->buildJoin().
458  "WHERE parent = %s ".
459  "AND ".$this->table_tree.".".$this->tree_pk." = %s ".
460  "AND ".$this->table_obj_data.".type = %s ",
461  $ilDB->quote($a_node_id,'integer'),
462  $ilDB->quote($this->tree_id,'integer'),
463  $ilDB->quote($a_type,'text'));
464  } else {
465  $query = sprintf("SELECT * FROM ".$this->table_tree." ".
466  $this->buildJoin().
467  "WHERE parent = %s ".
468  "AND ".$this->table_tree.".".$this->tree_pk." = %s ".
469  "AND ".$this->table_obj_data.".type = %s ".
470  "ORDER BY ".$this->table_tree.".lft",
471  $ilDB->quote($a_node_id,'integer'),
472  $ilDB->quote($this->tree_id,'integer'),
473  $ilDB->quote($a_type,'text'));
474  }
475  $res = $ilDB->query($query);
476 
477  // init childs
478  $childs = array();
479  while($row = $ilDB->fetchAssoc($res))
480  {
481  $childs[] = $this->fetchNodeData($row);
482  }
483 
484  return $childs ? $childs : array();
485  }
486 
487 
495  public function getChildsByTypeFilter($a_node_id,$a_types)
496  {
497  global $ilDB;
498 
499  if (!isset($a_node_id) or !$a_types)
500  {
501  $message = get_class($this)."::getChildsByType(): Missing parameter! node_id:".$a_node_id." type:".$a_types;
502  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
503  }
504 
505  $filter = ' ';
506  if($a_types)
507  {
508  $filter = 'AND '.$this->table_obj_data.'.type IN('.implode(',',ilUtil::quoteArray($a_types)).') ';
509  }
510 
511  $query = 'SELECT * FROM '.$this->table_tree.' '.
512  $this->buildJoin().
513  'WHERE parent = '.$ilDB->quote($a_node_id,'integer').' '.
514  'AND '.$this->table_tree.'.'.$this->tree_pk.' = '.$ilDB->quote($this->tree_id,'integer').' '.
515  $filter.
516  'ORDER BY '.$this->table_tree.'.lft';
517 
518  $res = $ilDB->query($query);
519  while($row = $ilDB->fetchAssoc($res))
520  {
521  $childs[] = $this->fetchNodeData($row);
522  }
523 
524  return $childs ? $childs : array();
525  }
526 
534  function insertNode($a_node_id, $a_parent_id, $a_pos = IL_LAST_NODE, $a_reset_deletion_date = false)
535  {
536  global $ilDB;
537 
538 //echo "+$a_node_id+$a_parent_id+";
539  // CHECK node_id and parent_id > 0 if in main tree
540  if($this->__isMainTree())
541  {
542  if($a_node_id <= 1 or $a_parent_id <= 0)
543  {
544  $message = sprintf('%s::insertNode(): Invalid parameters! $a_node_id: %s $a_parent_id: %s',
545  get_class($this),
546  $a_node_id,
547  $a_parent_id);
548  $this->log->write($message,$this->log->FATAL);
549  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
550  }
551  }
552 
553 
554  if (!isset($a_node_id) or !isset($a_parent_id))
555  {
556  $this->ilErr->raiseError(get_class($this)."::insertNode(): Missing parameter! ".
557  "node_id: ".$a_node_id." parent_id: ".$a_parent_id,$this->ilErr->WARNING);
558  }
559  if ($this->isInTree($a_node_id))
560  {
561  $this->ilErr->raiseError(get_class($this)."::insertNode(): Node ".$a_node_id." already in tree ".
562  $this->table_tree."!",$this->ilErr->WARNING);
563  }
564 
565  //
566  switch ($a_pos)
567  {
568  case IL_FIRST_NODE:
569 
570  if($this->__isMainTree())
571  {
572  #ilDB::_lockTables(array('tree' => 'WRITE'));
573  $ilDB->lockTables(
574  array(
575  0 => array('name' => $this->table_tree, 'type' => ilDB::LOCK_WRITE)));
576  }
577 
578  // get left value of parent
579  $query = sprintf('SELECT * FROM '.$this->table_tree.' '.
580  'WHERE child = %s '.
581  'AND '.$this->tree_pk.' = %s ',
582  $ilDB->quote($a_parent_id,'integer'),
583  $ilDB->quote($this->tree_id,'integer'));
584 
585  $res = $ilDB->query($query);
586  $r = $ilDB->fetchObject($res);
587 
588  if ($r->parent == NULL)
589  {
590  if($this->__isMainTree())
591  {
592  $ilDB->unlockTables();
593  }
594  $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".$a_parent_id." not found in ".
595  $this->table_tree."!",$this->ilErr->WARNING);
596  }
597 
598  $left = $r->lft;
599  $lft = $left + 1;
600  $rgt = $left + 2;
601 
602  // spread tree
603  $query = sprintf('UPDATE '.$this->table_tree.' SET '.
604  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
605  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END '.
606  'WHERE '.$this->tree_pk.' = %s ',
607  $ilDB->quote($left,'integer'),
608  $ilDB->quote($left,'integer'),
609  $ilDB->quote($this->tree_id,'integer'));
610  $res = $ilDB->manipulate($query);
611  break;
612 
613  case IL_LAST_NODE:
614  // Special treatment for trees with gaps
615  if ($this->gap > 0)
616  {
617  if($this->__isMainTree())
618  {
619  #ilDB::_lockTables(array('tree' => 'WRITE'));
620  $ilDB->lockTables(
621  array(
622  0 => array('name' => $this->table_tree, 'type' => ilDB::LOCK_WRITE)));
623 
624  }
625 
626  // get lft and rgt value of parent
627  $query = sprintf('SELECT rgt,lft,parent FROM '.$this->table_tree.' '.
628  'WHERE child = %s '.
629  'AND '.$this->tree_pk.' = %s',
630  $ilDB->quote($a_parent_id,'integer'),
631  $ilDB->quote($this->tree_id,'integer'));
632  $res = $ilDB->query($query);
633  $r = $ilDB->fetchAssoc($res);
634 
635  if ($r['parent'] == null)
636  {
637  if($this->__isMainTree())
638  {
639  $ilDB->unlockTables();
640  }
641  $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".
642  $a_parent_id." not found in ".$this->table_tree."!",$this->ilErr->WARNING);
643  }
644  $parentRgt = $r['rgt'];
645  $parentLft = $r['lft'];
646 
647  // Get the available space, without taking children into account yet
648  $availableSpace = $parentRgt - $parentLft;
649  if ($availableSpace < 2)
650  {
651  // If there is not enough space between parent lft and rgt, we don't need
652  // to look any further, because we must spread the tree.
653  $lft = $parentRgt;
654  }
655  else
656  {
657  // If there is space between parent lft and rgt, we need to check
658  // whether there is space left between the rightmost child of the
659  // parent and parent rgt.
660  $query = sprintf('SELECT MAX(rgt) max_rgt FROM '.$this->table_tree.' '.
661  'WHERE parent = %s '.
662  'AND '.$this->tree_pk.' = %s',
663  $ilDB->quote($a_parent_id,'integer'),
664  $ilDB->quote($this->tree_id,'integer'));
665  $res = $ilDB->query($query);
666  $r = $ilDB->fetchAssoc($res);
667 
668  if (isset($r['max_rgt']))
669  {
670  // If the parent has children, we compute the available space
671  // between rgt of the rightmost child and parent rgt.
672  $availableSpace = $parentRgt - $r['max_rgt'];
673  $lft = $r['max_rgt'] + 1;
674  }
675  else
676  {
677  // If the parent has no children, we know now, that we can
678  // add the new node at parent lft + 1 without having to spread
679  // the tree.
680  $lft = $parentLft + 1;
681  }
682  }
683  $rgt = $lft + 1;
684 
685 
686  // spread tree if there is not enough space to insert the new node
687  if ($availableSpace < 2)
688  {
689  //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
690  $query = sprintf('UPDATE '.$this->table_tree.' SET '.
691  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, '.
692  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END '.
693  'WHERE '.$this->tree_pk.' = %s ',
694  $ilDB->quote($parentRgt,'integer'),
695  $ilDB->quote((2 + $this->gap * 2),'integer'),
696  $ilDB->quote($parentRgt,'integer'),
697  $ilDB->quote((2 + $this->gap * 2),'integer'),
698  $ilDB->quote($this->tree_id,'integer'));
699  $res = $ilDB->manipulate($query);
700  }
701  else
702  {
703  //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') reusing gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.' for node '.$a_node_id.' '.$lft.'..'.$rgt);
704  }
705  }
706  // Treatment for trees without gaps
707  else
708  {
709  if($this->__isMainTree())
710  {
711  #ilDB::_lockTables(array('tree' => 'WRITE'));
712  $ilDB->lockTables(
713  array(
714  0 => array('name' => $this->table_tree, 'type' => ilDB::LOCK_WRITE)));
715 
716  }
717 
718  // get right value of parent
719  $query = sprintf('SELECT * FROM '.$this->table_tree.' '.
720  'WHERE child = %s '.
721  'AND '.$this->tree_pk.' = %s ',
722  $ilDB->quote($a_parent_id,'integer'),
723  $ilDB->quote($this->tree_id,'integer'));
724  $res = $ilDB->query($query);
725  $r = $ilDB->fetchObject($res);
726 
727  if ($r->parent == null)
728  {
729  if($this->__isMainTree())
730  {
731  $ilDB->unlockTables();
732  }
733  $this->ilErr->raiseError(get_class($this)."::insertNode(): Parent with ID ".
734  $a_parent_id." not found in ".$this->table_tree."!",$this->ilErr->WARNING);
735  }
736 
737  $right = $r->rgt;
738  $lft = $right;
739  $rgt = $right + 1;
740 
741  // spread tree
742  $query = sprintf('UPDATE '.$this->table_tree.' SET '.
743  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
744  'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END '.
745  'WHERE '.$this->tree_pk.' = %s',
746  $ilDB->quote($right,'integer'),
747  $ilDB->quote($right,'integer'),
748  $ilDB->quote($this->tree_id,'integer'));
749  $res = $ilDB->manipulate($query);
750  }
751 
752  break;
753 
754  default:
755 
756  // this code shouldn't be executed
757  if($this->__isMainTree())
758  {
759  #ilDB::_lockTables(array('tree' => 'WRITE'));
760  $ilDB->lockTables(
761  array(
762  0 => array('name' => $this->table_tree, 'type' => ilDB::LOCK_WRITE)));
763 
764  }
765 
766  // get right value of preceeding child
767  $query = sprintf('SELECT * FROM '.$this->table_tree.' '.
768  'WHERE child = %s '.
769  'AND '.$this->tree_pk.' = %s ',
770  $ilDB->quote($a_pos,'integer'),
771  $ilDB->quote($this->tree_id,'integer'));
772  $res = $ilDB->query($query);
773  $r = $ilDB->fetchObject($res);
774 
775  // crosscheck parents of sibling and new node (must be identical)
776  if ($r->parent != $a_parent_id)
777  {
778  if($this->__isMainTree())
779  {
780  $ilDB->unlockTables();
781  }
782  $this->ilErr->raiseError(get_class($this)."::insertNode(): Parents mismatch! ".
783  "new node parent: ".$a_parent_id." sibling parent: ".$r->parent,$this->ilErr->WARNING);
784  }
785 
786  $right = $r->rgt;
787  $lft = $right + 1;
788  $rgt = $right + 2;
789 
790  // update lft/rgt values
791  $query = sprintf('UPDATE '.$this->table_tree.' SET '.
792  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
793  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END '.
794  'WHERE '.$this->tree_pk.' = %s',
795  $ilDB->quote($right,'integer'),
796  $ilDB->quote($right,'integer'),
797  $ilDB->quote($this->tree_id,'integer'));
798  $res = $ilDB->manipulate($query);
799  break;
800 
801  }
802 
803  // get depth
804  $depth = $this->getDepth($a_parent_id) + 1;
805 
806  // insert node
807  //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') inserting node:'.$a_node_id.' parent:'.$a_parent_id." ".$lft."..".$rgt." depth:".$depth);
808  $query = sprintf('INSERT INTO '.$this->table_tree.' ('.$this->tree_pk.',child,parent,lft,rgt,depth) '.
809  'VALUES (%s,%s,%s,%s,%s,%s)',
810  $ilDB->quote($this->tree_id,'integer'),
811  $ilDB->quote($a_node_id,'integer'),
812  $ilDB->quote($a_parent_id,'integer'),
813  $ilDB->quote($lft,'integer'),
814  $ilDB->quote($rgt,'integer'),
815  $ilDB->quote($depth,'integer'));
816  $res = $ilDB->manipulate($query);
817 
818  // Finally unlock tables and update cache
819  if($this->__isMainTree())
820  {
821  #$GLOBALS['ilLog']->write(__METHOD__.': Storing in tree cache '.$a_node_id.' = true');
822  $this->in_tree_cache[$a_node_id] = true;
823  $ilDB->unlockTables();
824  }
825 
826  // reset deletion date
827  if ($a_reset_deletion_date)
828  {
829  ilObject::_resetDeletedDate($a_node_id);
830  }
831  }
832 
845  public function getFilteredSubTree($a_node_id,$a_filter = array())
846  {
847  $node = $this->getNodeData($a_node_id);
848 
849  $first = true;
850  $depth = 0;
851  foreach($this->getSubTree($node) as $subnode)
852  {
853  if($depth and $subnode['depth'] > $depth)
854  {
855  continue;
856  }
857  if(!$first and in_array($subnode['type'],$a_filter))
858  {
859  $depth = $subnode['depth'];
860  $first = false;
861  continue;
862  }
863  $depth = 0;
864  $first = false;
865  $filtered[] = $subnode;
866  }
867  return $filtered ? $filtered : array();
868  }
869 
875  public function getSubTreeIds($a_ref_id)
876  {
877  global $ilDB;
878 
879  $query = 'SELECT s.child FROM '.$this->table_tree.' s, '.$this->table_tree.' t '.
880  'WHERE t.child = %s '.
881  'AND s.lft > t.lft '.
882  'AND s.rgt < t.rgt '.
883  'AND s.'.$this->tree_pk.' = %s';
884 
885  $res = $ilDB->queryF(
886  $query,
887  array('integer','integer'),
888  array($a_ref_id,$this->tree_id)
889  );
890  while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
891  {
892  $childs[] = $row->child;
893  }
894  return $childs ? $childs : array();
895  }
896 
897 
906  function getSubTree($a_node,$a_with_data = true, $a_type = "")
907  {
908  global $ilDB;
909 
910  if (!is_array($a_node))
911  {
912  $this->ilErr->raiseError(get_class($this)."::getSubTree(): Wrong datatype for node_data! ",$this->ilErr->WARNING);
913  }
914 
915  if($a_node['lft'] < 1 or $a_node['rgt'] < 2)
916  {
917  $message = sprintf('%s::getSubTree(): Invalid node given! $a_node["lft"]: %s $a_node["rgt"]: %s',
918  get_class($this),
919  $a_node['lft'],
920  $a_node['rgt']);
921 
922  $this->log->write($message,$this->log->FATAL);
923 
924  if (DEVMODE == 1)
925  {
926  try
927  {
928  throw new Exception("e");
929  }
930  catch(Exception $e)
931  {
932  echo $e->getTraceAsString();
933  exit;
934  }
935  }
936 
937  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
938  }
939 
940 
941  $fields = array('integer','integer','integer');
942  $data = array($a_node['lft'],$a_node['rgt'],$this->tree_id);
943  $type_str = '';
944 
945  if (is_array($a_type))
946  {
947  $type_str = "AND ".$ilDB->in($this->table_obj_data.".type", $a_type, false, "text");
948  }
949  else if(strlen($a_type))
950  {
951  //$fields[] = 'text';
952  //$data[] = $a_type;
953  $type_str = "AND ".$this->table_obj_data.".type = ".
954  $ilDB->quote($a_type, "text");
955  }
956 
957  $query = "SELECT * FROM ".$this->table_tree." ".
958  $this->buildJoin().
959  "WHERE ".$this->table_tree.".lft BETWEEN %s AND %s ".
960  "AND ".$this->table_tree.".".$this->tree_pk." = %s ".
961  $type_str.
962  "ORDER BY ".$this->table_tree.".lft";
963  $res = $ilDB->queryF($query,$fields,$data);
964  while($row = $ilDB->fetchAssoc($res))
965  {
966  if($a_with_data)
967  {
968  $subtree[] = $this->fetchNodeData($row);
969  }
970  else
971  {
972  $subtree[] = $row['child'];
973  }
974  if($this->__isMainTree())
975  {
976  #$GLOBALS['ilLog']->write(__METHOD__.': Storing in tree cache '.$a_node_id.' = true');
977  $this->in_tree_cache[$row['child']] = true;
978  }
979  }
980 
981  return $subtree ? $subtree : array();
982  }
983 
992  function getSubTreeTypes($a_node,$a_filter = 0)
993  {
994  $a_filter = $a_filter ? $a_filter : array();
995 
996  foreach($this->getSubtree($this->getNodeData($a_node)) as $node)
997  {
998  if(in_array($node["type"],$a_filter))
999  {
1000  continue;
1001  }
1002  $types["$node[type]"] = $node["type"];
1003  }
1004  return $types ? $types : array();
1005  }
1006 
1012  function deleteTree($a_node)
1013  {
1014  global $ilDB;
1015 
1016  if (!is_array($a_node))
1017  {
1018  $this->ilErr->raiseError(get_class($this)."::deleteTree(): Wrong datatype for node_data! ",$this->ilErr->WARNING);
1019  }
1020  if($this->__isMainTree() and $a_node[$this->tree_pk] === 1)
1021  {
1022  if($a_node['lft'] <= 1 or $a_node['rgt'] <= 2)
1023  {
1024  $message = sprintf('%s::deleteTree(): Invalid parameters given: $a_node["lft"]: %s, $a_node["rgt"] %s',
1025  get_class($this),
1026  $a_node['lft'],
1027  $a_node['rgt']);
1028 
1029  $this->log->write($message,$this->log->FATAL);
1030  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
1031  }
1032  else if(!$this->__checkDelete($a_node))
1033  {
1034  $message = sprintf('%s::deleteTree(): Check delete failed: $a_node["lft"]: %s, $a_node["rgt"] %s',
1035  get_class($this),
1036  $a_node['lft'],
1037  $a_node['rgt']);
1038  $this->log->write($message,$this->log->FATAL);
1039  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
1040  }
1041 
1042  }
1043  $diff = $a_node["rgt"] - $a_node["lft"] + 1;
1044 
1045 
1046  // LOCKED ###########################################################
1047  // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
1048  if($this->__isMainTree())
1049  {
1050  #ilDB::_lockTables(array('tree' => 'WRITE'));
1051  $ilDB->lockTables(
1052  array(
1053  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
1054 
1055  }
1056 
1057  $query = sprintf('SELECT * FROM '.$this->table_tree.' '.
1058  'WHERE child = %s '.
1059  'AND '.$this->tree_pk.' = %s ',
1060  $ilDB->quote($a_node['child'],'integer'),
1061  $ilDB->quote($a_node[$this->tree_pk],'integer'));
1062  $res = $ilDB->query($query);
1063  while($row = $ilDB->fetchObject($res))
1064  {
1065  $a_node['lft'] = $row->lft;
1066  $a_node['rgt'] = $row->rgt;
1067  $diff = $a_node["rgt"] - $a_node["lft"] + 1;
1068  }
1069 
1070  // delete subtree
1071  $query = sprintf('DELETE FROM '.$this->table_tree.' '.
1072  'WHERE lft BETWEEN %s AND %s '.
1073  'AND rgt BETWEEN %s AND %s '.
1074  'AND '.$this->tree_pk.' = %s',
1075  $ilDB->quote($a_node['lft'],'integer'),
1076  $ilDB->quote($a_node['rgt'],'integer'),
1077  $ilDB->quote($a_node['lft'],'integer'),
1078  $ilDB->quote($a_node['rgt'],'integer'),
1079  $ilDB->quote($a_node[$this->tree_pk],'integer'));
1080  $res = $ilDB->manipulate($query);
1081 
1082  // Performance improvement: We only close the gap, if the node
1083  // is not in a trash tree, and if the resulting gap will be
1084  // larger than twice the gap value
1085  if ($a_node[$this->tree_pk] >= 0 && $a_node['rgt'] - $a_node['lft'] >= $this->gap * 2)
1086  {
1087  //$this->log->write('ilTree.deleteTree('.$a_node['child'].') closing gap at '.$a_node['lft'].'...'.$a_node['rgt']);
1088  // close gaps
1089  $query = sprintf('UPDATE '.$this->table_tree.' SET '.
1090  'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, '.
1091  'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END '.
1092  'WHERE '.$this->tree_pk.' = %s ',
1093  $ilDB->quote($a_node['lft'],'integer'),
1094  $ilDB->quote($diff,'integer'),
1095  $ilDB->quote($a_node['lft'],'integer'),
1096  $ilDB->quote($diff,'integer'),
1097  $ilDB->quote($a_node[$this->tree_pk],'integer'));
1098 
1099  $res = $ilDB->manipulate($query);
1100  }
1101  else
1102  {
1103  //$this->log->write('ilTree.deleteTree('.$a_node['child'].') leaving gap open '.$a_node['lft'].'...'.$a_node['rgt']);
1104  }
1105 
1106  if($this->__isMainTree())
1107  {
1108  #$GLOBALS['ilLog']->write(__METHOD__.': Resetting in tree cache ');
1109  $ilDB->unlockTables();
1110  $this->in_tree_cache = array();
1111  }
1112  // LOCKED ###########################################################
1113  }
1114 
1125  function getPathFull($a_endnode_id, $a_startnode_id = 0)
1126  {
1127  $pathIds =& $this->getPathId($a_endnode_id, $a_startnode_id);
1128 
1129  // We retrieve the full path in a single query to improve performance
1130  global $ilDB;
1131 
1132  // Abort if no path ids were found
1133  if (count($pathIds) == 0)
1134  {
1135  return null;
1136  }
1137 
1138  $inClause = 'child IN (';
1139  for ($i=0; $i < count($pathIds); $i++)
1140  {
1141  if ($i > 0) $inClause .= ',';
1142  $inClause .= $ilDB->quote($pathIds[$i],'integer');
1143  }
1144  $inClause .= ')';
1145 
1146  $q = 'SELECT * '.
1147  'FROM '.$this->table_tree.' '.
1148  $this->buildJoin().' '.
1149  'WHERE '.$inClause.' '.
1150  'AND '.$this->table_tree.'.'.$this->tree_pk.' = '.$this->ilDB->quote($this->tree_id,'integer').' '.
1151  'ORDER BY depth';
1152  $r = $ilDB->query($q);
1153 
1154  $pathFull = array();
1155  while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
1156  {
1157  $pathFull[] = $this->fetchNodeData($row);
1158 
1159  // Update cache
1160  if ($this->__isMainTree())
1161  {
1162  #$GLOBALS['ilLog']->write(__METHOD__.': Storing in tree cache '.$row['child']);
1163  $this->in_tree_cache[$row['child']] = $row['tree'] == 1;
1164  }
1165  }
1166  return $pathFull;
1167  }
1176  function getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id = 0)
1177  {
1178  global $ilDB;
1179 
1180  // The nested sets algorithm is very easy to implement.
1181  // Unfortunately it always does a full table space scan to retrieve the path
1182  // regardless whether indices on lft and rgt are set or not.
1183  // (At least, this is what happens on MySQL 4.1).
1184  // This algorithms performs well for small trees which are deeply nested.
1185 
1186  if (!isset($a_endnode_id))
1187  {
1188  $this->ilErr->raiseError(get_class($this)."::getPathId(): No endnode_id given! ",$this->ilErr->WARNING);
1189  }
1190 
1191  $fields = array('integer','integer','integer');
1192  $data = array($a_endnode_id,$this->tree_id,$this->tree_id);
1193 
1194  $query = "SELECT T2.child ".
1195  "FROM ".$this->table_tree." T1, ".$this->table_tree." T2 ".
1196  "WHERE T1.child = %s ".
1197  "AND T1.lft BETWEEN T2.lft AND T2.rgt ".
1198  "AND T1.".$this->tree_pk." = %s ".
1199  "AND T2.".$this->tree_pk." = %s ".
1200  "ORDER BY T2.depth";
1201  $res = $ilDB->queryF($query,$fields,$data);
1202 
1203  $takeId = $a_startnode_id == 0;
1204  while($row = $ilDB->fetchAssoc($res))
1205  {
1206  if ($takeId || $row['child'] == $a_startnode_id)
1207  {
1208  $takeId = true;
1209  $pathIds[] = $row['child'];
1210  }
1211  }
1212  return $pathIds ? $pathIds : array();
1213  }
1214 
1223  function getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id = 0)
1224  {
1225  // The adjacency map algorithm is harder to implement than the nested sets algorithm.
1226  // This algorithms performs an index search for each of the path element.
1227  // This algorithms performs well for large trees which are not deeply nested.
1228 
1229  // The $takeId variable is used, to determine if a given id shall be included in the path
1230  $takeId = $a_startnode_id == 0;
1231 
1232  if (!isset($a_endnode_id))
1233  {
1234  $this->ilErr->raiseError(get_class($this)."::getPathId(): No endnode_id given! ",$this->ilErr->WARNING);
1235  }
1236 
1237  global $log, $ilDB;
1238 
1239  if ($this->__isMainTree() && isset($this->depth_cache[$a_endnode_id])
1240  && isset($this->parent_cache[$a_endnode_id]))
1241  {
1242  $nodeDepth = $this->depth_cache[$a_endnode_id];
1243  $parentId = $this->parent_cache[$a_endnode_id];
1244  }
1245  else
1246  {
1247  $types = array('integer','integer');
1248  $data = array($a_endnode_id,$this->tree_id);
1249  $query = 'SELECT t.depth, t.parent '.
1250  'FROM '.$this->table_tree.' t '.
1251  'WHERE child = %s '.
1252  'AND '.$this->tree_pk.' = %s ';
1253  $res = $ilDB->queryF($query,$types,$data);
1254 
1255  if($res->numRows() == 0)
1256  {
1257  return array();
1258  }
1259 
1260  $row = $ilDB->fetchAssoc($res);
1261  $nodeDepth = $row['depth'];
1262  $parentId = $row['parent'];
1263  }
1264 
1265  //$this->writelog('getIdsUsingAdjacencyMap depth='.$nodeDepth);
1266 
1267  // Fetch the node ids. For shallow depths we can fill in the id's directly.
1268  $pathIds = array();
1269  if ($nodeDepth == 1)
1270  {
1271  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
1272  if ($takeId) $pathIds[] = $a_endnode_id;
1273  }
1274  else if ($nodeDepth == 2)
1275  {
1276  $takeId = $takeId || $parentId == $a_startnode_id;
1277  if ($takeId) $pathIds[] = $parentId;
1278  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
1279  if ($takeId) $pathIds[] = $a_endnode_id;
1280  }
1281  else if ($nodeDepth == 3)
1282  {
1283  $takeId = $takeId || $this->root_id == $a_startnode_id;
1284  if ($takeId) $pathIds[] = $this->root_id;
1285  $takeId = $takeId || $parentId == $a_startnode_id;
1286  if ($takeId) $pathIds[] = $parentId;
1287  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
1288  if ($takeId) $pathIds[] = $a_endnode_id;
1289  }
1290  else if ($nodeDepth < 32)
1291  {
1292  // Adjacency Map Tree performs better than
1293  // Nested Sets Tree even for very deep trees.
1294  // The following code construct nested self-joins
1295  // Since we already know the root-id of the tree and
1296  // we also know the id and parent id of the current node,
1297  // we only need to perform $nodeDepth - 3 self-joins.
1298  // We can further reduce the number of self-joins by 1
1299  // by taking into account, that each row in table tree
1300  // contains the id of itself and of its parent.
1301  $qSelect = 't1.child c0';
1302  $qJoin = '';
1303  for ($i = 1; $i < $nodeDepth - 2; $i++)
1304  {
1305  $qSelect .= ', t'.$i.'.parent c'.$i;
1306  $qJoin .= ' JOIN '.$this->table_tree.' t'.$i.' ON '.
1307  't'.$i.'.child=t'.($i - 1).'.parent AND '.
1308  't'.$i.'.'.$this->tree_pk.' = '.(int) $this->tree_id;
1309  }
1310 
1311  $types = array('integer','integer');
1312  $data = array($this->tree_id,$parentId);
1313  $query = 'SELECT '.$qSelect.' '.
1314  'FROM '.$this->table_tree.' t0 '.$qJoin.' '.
1315  'WHERE t0.'.$this->tree_pk.' = %s '.
1316  'AND t0.child = %s ';
1317 
1318  $ilDB->setLimit(1);
1319  $res = $ilDB->queryF($query,$types,$data);
1320 
1321  if ($res->numRows() == 0)
1322  {
1323  return array();
1324  }
1325  $row = $ilDB->fetchAssoc($res);
1326 
1327  $takeId = $takeId || $this->root_id == $a_startnode_id;
1328  if ($takeId) $pathIds[] = $this->root_id;
1329  for ($i = $nodeDepth - 4; $i >=0; $i--)
1330  {
1331  $takeId = $takeId || $row['c'.$i] == $a_startnode_id;
1332  if ($takeId) $pathIds[] = $row['c'.$i];
1333  }
1334  $takeId = $takeId || $parentId == $a_startnode_id;
1335  if ($takeId) $pathIds[] = $parentId;
1336  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
1337  if ($takeId) $pathIds[] = $a_endnode_id;
1338  }
1339  else
1340  {
1341  // Fall back to nested sets tree for extremely deep tree structures
1342  return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
1343  }
1344 
1345  return $pathIds;
1346  }
1347 
1354  function preloadDepthParent($a_node_ids)
1355  {
1356  global $ilDB;
1357 
1358  if (!$this->__isMainTree() || !is_array($a_node_ids) || !$this->isCacheUsed())
1359  {
1360  return;
1361  }
1362 
1363  $res = $ilDB->query('SELECT t.depth, t.parent, t.child '.
1364  'FROM '.$this->table_tree.' t '.
1365  'WHERE '.$ilDB->in("child", $a_node_ids, false, "integer").
1366  'AND '.$this->tree_pk.' = '.$ilDB->quote($this->tree_id, "integer"));
1367  while ($row = $ilDB->fetchAssoc($res))
1368  {
1369  $this->depth_cache[$row["child"]] = $row["depth"];
1370  $this->parent_cache[$row["child"]] = $row["parent"];
1371  }
1372  }
1373 
1382  function getPathId($a_endnode_id, $a_startnode_id = 0)
1383  {
1384  // path id cache
1385  if ($this->isCacheUsed() && isset($this->path_id_cache[$a_endnode_id][$a_startnode_id]))
1386  {
1387 //echo "<br>getPathIdhit";
1388  return $this->path_id_cache[$a_endnode_id][$a_startnode_id];
1389  }
1390 //echo "<br>miss";
1391 
1392  $pathIds =& $this->getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id);
1393 
1394  if($this->__isMainTree())
1395  {
1396  $this->path_id_cache[$a_endnode_id][$a_startnode_id] = $pathIds;
1397  }
1398  return $pathIds;
1399  }
1400 
1401  // BEGIN WebDAV: getNodePathForTitlePath function added
1419  function getNodePathForTitlePath($titlePath, $a_startnode_id = null)
1420  {
1421  global $ilDB, $log;
1422  //$log->write('getNodePathForTitlePath('.implode('/',$titlePath));
1423 
1424  // handle empty title path
1425  if ($titlePath == null || count($titlePath) == 0)
1426  {
1427  if ($a_startnode_id == 0)
1428  {
1429  return null;
1430  }
1431  else
1432  {
1433  return $this->getNodePath($a_startnode_id);
1434  }
1435  }
1436 
1437  // fetch the node path up to the startnode
1438  if ($a_startnode_id != null && $a_startnode_id != 0)
1439  {
1440  // Start using the node path to the root of the relative path
1441  $nodePath = $this->getNodePath($a_startnode_id);
1442  $parent = $a_startnode_id;
1443  }
1444  else
1445  {
1446  // Start using the root of the tree
1447  $nodePath = array();
1448  $parent = 0;
1449  }
1450 
1451 
1452  // Convert title path into Unicode Normal Form C
1453  // This is needed to ensure that we can compare title path strings with
1454  // strings from the database.
1455  require_once('include/Unicode/UtfNormal.php');
1456  include_once './Services/Utilities/classes/class.ilStr.php';
1457  $inClause = 'd.title IN (';
1458  for ($i=0; $i < count($titlePath); $i++)
1459  {
1460  $titlePath[$i] = ilStr::strToLower(UtfNormal::toNFC($titlePath[$i]));
1461  if ($i > 0) $inClause .= ',';
1462  $inClause .= $ilDB->quote($titlePath[$i],'text');
1463  }
1464  $inClause .= ')';
1465 
1466  // Fetch all rows that are potential path elements
1467  if ($this->table_obj_reference)
1468  {
1469  $joinClause = 'JOIN '.$this->table_obj_reference.' r ON t.child = r.'.$this->ref_pk.' '.
1470  'JOIN '.$this->table_obj_data.' d ON r.'.$this->obj_pk.' = d.'.$this->obj_pk;
1471  }
1472  else
1473  {
1474  $joinClause = 'JOIN '.$this->table_obj_data.' d ON t.child = d.'.$this->obj_pk;
1475  }
1476  // The ORDER BY clause in the following SQL statement ensures that,
1477  // in case of a multiple objects with the same title, always the Object
1478  // with the oldest ref_id is chosen.
1479  // This ensure, that, if a new object with the same title is added,
1480  // WebDAV clients can still work with the older object.
1481  $q = 'SELECT t.depth, t.parent, t.child, d.'.$this->obj_pk.' obj_id, d.type, d.title '.
1482  'FROM '.$this->table_tree.' t '.
1483  $joinClause.' '.
1484  'WHERE '.$inClause.' '.
1485  'AND t.depth <= '.(count($titlePath)+count($nodePath)).' '.
1486  'AND t.tree = 1 '.
1487  'ORDER BY t.depth, t.child ASC';
1488  $r = $ilDB->query($q);
1489 
1490  $rows = array();
1491  while ($row = $r->fetchRow(DB_FETCHMODE_ASSOC))
1492  {
1493  $row['title'] = UtfNormal::toNFC($row['title']);
1494  $row['ref_id'] = $row['child'];
1495  $rows[] = $row;
1496  }
1497 
1498  // Extract the path elements from the fetched rows
1499  for ($i = 0; $i < count($titlePath); $i++) {
1500  $pathElementFound = false;
1501  foreach ($rows as $row) {
1502  if ($row['parent'] == $parent &&
1503  ilStr::strToLower($row['title']) == $titlePath[$i])
1504  {
1505  // FIXME - We should test here, if the user has
1506  // 'visible' permission for the object.
1507  $nodePath[] = $row;
1508  $parent = $row['child'];
1509  $pathElementFound = true;
1510  break;
1511  }
1512  }
1513  // Abort if we haven't found a path element for the current depth
1514  if (! $pathElementFound)
1515  {
1516  //$log->write('ilTree.getNodePathForTitlePath('.var_export($titlePath,true).','.$a_startnode_id.'):null');
1517  return null;
1518  }
1519  }
1520  // Return the node path
1521  //$log->write('ilTree.getNodePathForTitlePath('.var_export($titlePath,true).','.$a_startnode_id.'):'.var_export($nodePath,true));
1522  return $nodePath;
1523  }
1524  // END WebDAV: getNodePathForTitlePath function added
1525  // END WebDAV: getNodePath function added
1542  function getNodePath($a_endnode_id, $a_startnode_id = 0)
1543  {
1544  global $ilDB;
1545 
1546  $pathIds = $this->getPathId($a_endnode_id, $a_startnode_id);
1547 
1548  // Abort if no path ids were found
1549  if (count($pathIds) == 0)
1550  {
1551  return null;
1552  }
1553 
1554 
1555  $types = array();
1556  $data = array();
1557  for ($i = 0; $i < count($pathIds); $i++)
1558  {
1559  $types[] = 'integer';
1560  $data[] = $pathIds[$i];
1561  }
1562 
1563  $query = 'SELECT t.depth,t.parent,t.child,d.obj_id,d.type,d.title '.
1564  'FROM '.$this->table_tree.' t '.
1565  'JOIN '.$this->table_obj_reference.' r ON r.ref_id = t.child '.
1566  'JOIN '.$this->table_obj_data.' d ON d.obj_id = r.obj_id '.
1567  'WHERE '.$ilDB->in('t.child',$data,false,'integer').' '.
1568  'ORDER BY t.depth ';
1569 
1570  $res = $ilDB->queryF($query,$types,$data);
1571 
1572  $titlePath = array();
1573  while ($row = $ilDB->fetchAssoc($res))
1574  {
1575  $titlePath[] = $row;
1576  }
1577  return $titlePath;
1578  }
1579  // END WebDAV: getNodePath function added
1580 
1587  function checkTree()
1588  {
1589  global $ilDB;
1590 
1591  $types = array('integer');
1592  $query = 'SELECT lft,rgt FROM '.$this->table_tree.' '.
1593  'WHERE '.$this->tree_pk.' = %s ';
1594 
1595  $res = $ilDB->queryF($query,$types,array($this->tree_id));
1596  while ($row = $ilDB->fetchObject($res))
1597  {
1598  $lft[] = $row->lft;
1599  $rgt[] = $row->rgt;
1600  }
1601 
1602  $all = array_merge($lft,$rgt);
1603  $uni = array_unique($all);
1604 
1605  if (count($all) != count($uni))
1606  {
1607  $message = sprintf('%s::checkTree(): Tree is corrupted!',
1608  get_class($this));
1609 
1610  $this->log->write($message,$this->log->FATAL);
1611  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
1612  }
1613 
1614  return true;
1615  }
1616 
1620  function checkTreeChilds($a_no_zero_child = true)
1621  {
1622  global $ilDB;
1623 
1624  $query = 'SELECT * FROM '.$this->table_tree.' '.
1625  'WHERE '.$this->tree_pk.' = %s '.
1626  'ORDER BY lft';
1627  $r1 = $ilDB->queryF($query,array('integer'),array($this->tree_id));
1628 
1629  while ($row = $ilDB->fetchAssoc($r1))
1630  {
1631 //echo "tree:".$row[$this->tree_pk].":lft:".$row["lft"].":rgt:".$row["rgt"].":child:".$row["child"].":<br>";
1632  if (($row["child"] == 0) && $a_no_zero_child)
1633  {
1634  $this->ilErr->raiseError(get_class($this)."::checkTreeChilds(): Tree contains child with ID 0!",$this->ilErr->WARNING);
1635  }
1636 
1637  if ($this->table_obj_reference)
1638  {
1639  // get object reference data
1640  $query = 'SELECT * FROM '.$this->table_obj_reference.' WHERE '.$this->ref_pk.' = %s ';
1641  $r2 = $ilDB->queryF($query,array('integer'),array($row['child']));
1642 
1643 //echo "num_childs:".$r2->numRows().":<br>";
1644  if ($r2->numRows() == 0)
1645  {
1646  $this->ilErr->raiseError(get_class($this)."::checkTree(): No Object-to-Reference entry found for ID ".
1647  $row["child"]."!",$this->ilErr->WARNING);
1648  }
1649  if ($r2->numRows() > 1)
1650  {
1651  $this->ilErr->raiseError(get_class($this)."::checkTree(): More Object-to-Reference entries found for ID ".
1652  $row["child"]."!",$this->ilErr->WARNING);
1653  }
1654 
1655  // get object data
1656  $obj_ref = $ilDB->fetchAssoc($r2);
1657 
1658  $query = 'SELECT * FROM '.$this->table_obj_data.' WHERE '.$this->obj_pk.' = %s';
1659  $r3 = $ilDB->queryF($query,array('integer'),array($obj_ref[$this->obj_pk]));
1660  if ($r3->numRows() == 0)
1661  {
1662  $this->ilErr->raiseError(get_class($this)."::checkTree(): No child found for ID ".
1663  $obj_ref[$this->obj_pk]."!",$this->ilErr->WARNING);
1664  }
1665  if ($r3->numRows() > 1)
1666  {
1667  $this->ilErr->raiseError(get_class($this)."::checkTree(): More childs found for ID ".
1668  $obj_ref[$this->obj_pk]."!",$this->ilErr->WARNING);
1669  }
1670 
1671  }
1672  else
1673  {
1674  // get only object data
1675  $query = 'SELECT * FROM '.$this->table_obj_data.' WHERE '.$this->obj_pk.' = %s';
1676  $r2 = $ilDB->queryF($query,array('integer'),array($row['child']));
1677 //echo "num_childs:".$r2->numRows().":<br>";
1678  if ($r2->numRows() == 0)
1679  {
1680  $this->ilErr->raiseError(get_class($this)."::checkTree(): No child found for ID ".
1681  $row["child"]."!",$this->ilErr->WARNING);
1682  }
1683  if ($r2->numRows() > 1)
1684  {
1685  $this->ilErr->raiseError(get_class($this)."::checkTree(): More childs found for ID ".
1686  $row["child"]."!",$this->ilErr->WARNING);
1687  }
1688  }
1689  }
1690 
1691  return true;
1692  }
1693 
1699  function getMaximumDepth()
1700  {
1701  global $ilDB;
1702 
1703  $query = 'SELECT MAX(depth) depth FROM '.$this->table_tree;
1704  $res = $ilDB->query($query);
1705 
1706  $row = $ilDB->fetchAssoc($res);
1707  return $row['depth'];
1708  }
1709 
1716  function getDepth($a_node_id)
1717  {
1718  global $ilDB;
1719 
1720  if ($a_node_id)
1721  {
1722  $query = 'SELECT depth FROM '.$this->table_tree.' '.
1723  'WHERE child = %s '.
1724  'AND '.$this->tree_pk.' = %s ';
1725  $res = $ilDB->queryF($query,array('integer','integer'),array($a_node_id,$this->tree_id));
1726  $row = $ilDB->fetchObject($res);
1727 
1728  return $row->depth;
1729  }
1730  else
1731  {
1732  return 1;
1733  }
1734  }
1735 
1736 
1744  // BEGIN WebDAV: Pass tree id to this method
1745  //function getNodeData($a_node_id)
1746  function getNodeData($a_node_id, $a_tree_pk = null)
1747  // END PATCH WebDAV: Pass tree id to this method
1748  {
1749  global $ilDB;
1750 
1751  if (!isset($a_node_id))
1752  {
1753  $GLOBALS['ilLog']->logStack();
1754  $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
1755  }
1756  if($this->__isMainTree())
1757  {
1758  if($a_node_id < 1)
1759  {
1760  $message = sprintf('%s::getNodeData(): No valid parameter given! $a_node_id: %s',
1761  get_class($this),
1762  $a_node_id);
1763 
1764  $this->log->write($message,$this->log->FATAL);
1765  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
1766  }
1767  }
1768 
1769  // BEGIN WebDAV: Pass tree id to this method
1770  $query = 'SELECT * FROM '.$this->table_tree.' '.
1771  $this->buildJoin().
1772  'WHERE '.$this->table_tree.'.child = %s '.
1773  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s ';
1774  $res = $ilDB->queryF($query,array('integer','integer'),array(
1775  $a_node_id,
1776  $a_tree_pk === null ? $this->tree_id : $a_tree_pk));
1777  // END WebDAV: Pass tree id to this method
1778  $row = $ilDB->fetchAssoc($res);
1779  $row[$this->tree_pk] = $this->tree_id;
1780 
1781  return $this->fetchNodeData($row);
1782  }
1783 
1791  function fetchNodeData($a_row)
1792  {
1793  global $objDefinition, $lng, $ilBench,$ilDB;
1794 
1795  //$ilBench->start("Tree", "fetchNodeData_getRow");
1796  $data = $a_row;
1797  $data["desc"] = $a_row["description"]; // for compability
1798  //$ilBench->stop("Tree", "fetchNodeData_getRow");
1799 
1800  // multilingual support systemobjects (sys) & categories (db)
1801  //$ilBench->start("Tree", "fetchNodeData_readDefinition");
1802  if (is_object($objDefinition))
1803  {
1804  $translation_type = $objDefinition->getTranslationType($data["type"]);
1805  }
1806  //$ilBench->stop("Tree", "fetchNodeData_readDefinition");
1807 
1808  if ($translation_type == "sys")
1809  {
1810  //$ilBench->start("Tree", "fetchNodeData_getLangData");
1811  if ($data["type"] == "rolf" and $data["obj_id"] != ROLE_FOLDER_ID)
1812  {
1813  $data["description"] = $lng->txt("obj_".$data["type"]."_local_desc").$data["title"].$data["desc"];
1814  $data["desc"] = $lng->txt("obj_".$data["type"]."_local_desc").$data["title"].$data["desc"];
1815  $data["title"] = $lng->txt("obj_".$data["type"]."_local");
1816  }
1817  else
1818  {
1819  $data["title"] = $lng->txt("obj_".$data["type"]);
1820  $data["description"] = $lng->txt("obj_".$data["type"]."_desc");
1821  $data["desc"] = $lng->txt("obj_".$data["type"]."_desc");
1822  }
1823  //$ilBench->stop("Tree", "fetchNodeData_getLangData");
1824  }
1825  elseif ($translation_type == "db")
1826  {
1827 
1828  // Try to retrieve object translation from cache
1829  if ($this->isCacheUsed() &&
1830  array_key_exists($data["obj_id"].'.'.$lang_code, $this->translation_cache)) {
1831 
1832  $key = $data["obj_id"].'.'.$lang_code;
1833  $data["title"] = $this->translation_cache[$key]['title'];
1834  $data["description"] = $this->translation_cache[$key]['description'];
1835  $data["desc"] = $this->translation_cache[$key]['desc'];
1836  }
1837  else
1838  {
1839  // Object translation is not in cache, read it from database
1840  //$ilBench->start("Tree", "fetchNodeData_getTranslation");
1841  $query = 'SELECT title,description FROM object_translation '.
1842  'WHERE obj_id = %s '.
1843  'AND lang_code = %s '.
1844  'AND NOT lang_default = %s';
1845 
1846  $res = $ilDB->queryF($query,array('integer','text','integer'),array(
1847  $data['obj_id'],
1848  $this->lang_code,
1849  1));
1850  $row = $ilDB->fetchObject($res);
1851 
1852  if ($row)
1853  {
1854  $data["title"] = $row->title;
1855  $data["description"] = ilUtil::shortenText($row->description,MAXLENGTH_OBJ_DESC,true);
1856  $data["desc"] = $row->description;
1857  }
1858  //$ilBench->stop("Tree", "fetchNodeData_getTranslation");
1859 
1860  // Store up to 1000 object translations in cache
1861  if ($this->isCacheUsed() && count($this->translation_cache) < 1000)
1862  {
1863  $key = $data["obj_id"].'.'.$lang_code;
1864  $this->translation_cache[$key] = array();
1865  $this->translation_cache[$key]['title'] = $data["title"] ;
1866  $this->translation_cache[$key]['description'] = $data["description"];
1867  $this->translation_cache[$key]['desc'] = $data["desc"];
1868  }
1869  }
1870  }
1871 
1872  // TODO: Handle this switch by module.xml definitions
1873  if($data['type'] == 'crsr' or $data['type'] == 'catr')
1874  {
1875  include_once('./Services/ContainerReference/classes/class.ilContainerReference.php');
1876  $data['title'] = ilContainerReference::_lookupTargetTitle($data['obj_id']);
1877  }
1878 
1879  return $data ? $data : array();
1880  }
1881 
1887  protected function fetchTranslationFromObjectDataCache($a_obj_ids)
1888  {
1889  global $ilObjDataCache;
1890 
1891  if ($this->isCacheUsed() && is_array($a_obj_ids) && is_object($ilObjDataCache))
1892  {
1893  foreach ($a_obj_ids as $id)
1894  {
1895  $this->translation_cache[$id.'.']['title'] = $ilObjDataCache->lookupTitle($id);
1896  $this->translation_cache[$id.'.']['description'] = $ilObjDataCache->lookupDescription($id);;
1897  $this->translation_cache[$id.'.']['desc'] =
1898  $this->translation_cache[$id.'.']['description'];
1899  }
1900  }
1901  }
1902 
1903 
1911  function isInTree($a_node_id)
1912  {
1913  global $ilDB;
1914 
1915  if (!isset($a_node_id))
1916  {
1917  return false;
1918  #$this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
1919  }
1920 
1921  // is in tree cache
1922  if ($this->isCacheUsed() && isset($this->in_tree_cache[$a_node_id]))
1923  {
1924  #$GLOBALS['ilLog']->write(__METHOD__.': Using in tree cache '.$a_node_id);
1925 //echo "<br>in_tree_hit";
1926  return $this->in_tree_cache[$a_node_id];
1927  }
1928 
1929  $query = 'SELECT * FROM '.$this->table_tree.' '.
1930  'WHERE '.$this->table_tree.'.child = %s '.
1931  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s';
1932 
1933  $res = $ilDB->queryF($query,array('integer','integer'),array(
1934  $a_node_id,
1935  $this->tree_id));
1936 
1937  if ($res->numRows() > 0)
1938  {
1939  if($this->__isMainTree())
1940  {
1941  #$GLOBALS['ilLog']->write(__METHOD__.': Storing in tree cache '.$a_node_id.' = true');
1942  $this->in_tree_cache[$a_node_id] = true;
1943  }
1944  return true;
1945  }
1946  else
1947  {
1948  if($this->__isMainTree())
1949  {
1950  #$GLOBALS['ilLog']->write(__METHOD__.': Storing in tree cache '.$a_node_id.' = false');
1951  $this->in_tree_cache[$a_node_id] = false;
1952  }
1953  return false;
1954  }
1955  }
1956 
1963  function getParentNodeData($a_node_id)
1964  {
1965  global $ilDB;
1966  global $ilLog;
1967 
1968  if (!isset($a_node_id))
1969  {
1970  $ilLog->logStack();
1971  $this->ilErr->raiseError(get_class($this)."::getParentNodeData(): No node_id given! ",$this->ilErr->WARNING);
1972  }
1973 
1974  if ($this->table_obj_reference)
1975  {
1976  // Use inner join instead of left join to improve performance
1977  $innerjoin = "JOIN ".$this->table_obj_reference." ON v.child=".$this->table_obj_reference.".".$this->ref_pk." ".
1978  "JOIN ".$this->table_obj_data." ON ".$this->table_obj_reference.".".$this->obj_pk."=".$this->table_obj_data.".".$this->obj_pk." ";
1979  }
1980  else
1981  {
1982  // Use inner join instead of left join to improve performance
1983  $innerjoin = "JOIN ".$this->table_obj_data." ON v.child=".$this->table_obj_data.".".$this->obj_pk." ";
1984  }
1985 
1986  $query = 'SELECT * FROM '.$this->table_tree.' s, '.$this->table_tree.' v '.
1987  $innerjoin.
1988  'WHERE s.child = %s '.
1989  'AND s.parent = v.child '.
1990  'AND s.lft > v.lft '.
1991  'AND s.rgt < v.rgt '.
1992  'AND s.'.$this->tree_pk.' = %s '.
1993  'AND v.'.$this->tree_pk.' = %s';
1994  $res = $ilDB->queryF($query,array('integer','integer','integer'),array(
1995  $a_node_id,
1996  $this->tree_id,
1997  $this->tree_id));
1998  $row = $ilDB->fetchAssoc($res);
1999  return $this->fetchNodeData($row);
2000  }
2001 
2009  function isGrandChild($a_startnode_id,$a_querynode_id)
2010  {
2011  global $ilDB;
2012 
2013  if (!isset($a_startnode_id) or !isset($a_querynode_id))
2014  {
2015  return false;
2016  }
2017 
2018  $query = 'SELECT * FROM '.$this->table_tree.' s, '.$this->table_tree.' v '.
2019  'WHERE s.child = %s '.
2020  'AND v.child = %s '.
2021  'AND s.'.$this->tree_pk.' = %s '.
2022  'AND v.'.$this->tree_pk.' = %s '.
2023  'AND v.lft BETWEEN s.lft AND s.rgt '.
2024  'AND v.rgt BETWEEN s.lft AND s.rgt';
2025  $res = $ilDB->queryF(
2026  $query,
2027  array('integer','integer','integer','integer'),
2028  array(
2029  $a_startnode_id,
2030  $a_querynode_id,
2031  $this->tree_id,
2032  $this->tree_id));
2033 
2034  return $res->numRows();
2035  }
2036 
2045  function addTree($a_tree_id,$a_node_id = -1)
2046  {
2047  global $ilDB;
2048 
2049  // FOR SECURITY addTree() IS NOT ALLOWED ON MAIN TREE
2050  if($this->__isMainTree())
2051  {
2052  $message = sprintf('%s::addTree(): Operation not allowed on main tree! $a_tree_if: %s $a_node_id: %s',
2053  get_class($this),
2054  $a_tree_id,
2055  $a_node_id);
2056  $this->log->write($message,$this->log->FATAL);
2057  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2058  }
2059 
2060  if (!isset($a_tree_id))
2061  {
2062  $this->ilErr->raiseError(get_class($this)."::addTree(): No tree_id given! ",$this->ilErr->WARNING);
2063  }
2064 
2065  if ($a_node_id <= 0)
2066  {
2067  $a_node_id = $a_tree_id;
2068  }
2069 
2070  $query = 'INSERT INTO '.$this->table_tree.' ('.
2071  $this->tree_pk.', child,parent,lft,rgt,depth) '.
2072  'VALUES '.
2073  '(%s,%s,%s,%s,%s,%s)';
2074  $res = $ilDB->manipulateF($query,array('integer','integer','integer','integer','integer','integer'),array(
2075  $a_tree_id,
2076  $a_node_id,
2077  0,
2078  1,
2079  2,
2080  1));
2081 
2082  return true;
2083  }
2084 
2092  function getNodeDataByType($a_type)
2093  {
2094  global $ilDB;
2095 
2096  if (!isset($a_type) or (!is_string($a_type)))
2097  {
2098  $this->ilErr->raiseError(get_class($this)."::getNodeDataByType(): Type not given or wrong datatype!",$this->ilErr->WARNING);
2099  }
2100 
2101  $data = array(); // node_data
2102  $row = ""; // fetched row
2103  $left = ""; // tree_left
2104  $right = ""; // tree_right
2105 
2106  $query = 'SELECT * FROM '.$this->table_tree.' '.
2107  'WHERE '.$this->tree_pk.' = %s '.
2108  'AND parent = %s ';
2109  $res = $ilDB->queryF($query,array('integer','integer'),array(
2110  $this->tree_id,
2111  0));
2112 
2113  while ($row = $ilDB->fetchObject($res))
2114  {
2115  $left = $row->lft;
2116  $right = $row->rgt;
2117  }
2118 
2119  $query = 'SELECT * FROM '.$this->table_tree.' '.
2120  $this->buildJoin().
2121  'WHERE '.$this->table_obj_data.'.type = %s '.
2122  'AND '.$this->table_tree.'.lft BETWEEN %s AND %s '.
2123  'AND '.$this->table_tree.'.rgt BETWEEN %s AND %s '.
2124  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s ';
2125  $res = $ilDB->queryF($query,array('text','integer','integer','integer','integer','integer'),array(
2126  $a_type,
2127  $left,
2128  $right,
2129  $left,
2130  $right,
2131  $this->tree_id));
2132 
2133  while($row = $ilDB->fetchAssoc($res))
2134  {
2135  $data[] = $this->fetchNodeData($row);
2136  }
2137 
2138  return $data;
2139  }
2140 
2148  function removeTree($a_tree_id)
2149  {
2150  global $ilDB;
2151 
2152  // OPERATION NOT ALLOWED ON MAIN TREE
2153  if($this->__isMainTree())
2154  {
2155  $message = sprintf('%s::removeTree(): Operation not allowed on main tree! $a_tree_if: %s',
2156  get_class($this),
2157  $a_tree_id);
2158  $this->log->write($message,$this->log->FATAL);
2159  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2160  }
2161  if (!$a_tree_id)
2162  {
2163  $this->ilErr->raiseError(get_class($this)."::removeTree(): No tree_id given! Action aborted",$this->ilErr->MESSAGE);
2164  }
2165 
2166  $query = 'DELETE FROM '.$this->table_tree.
2167  ' WHERE '.$this->tree_pk.' = %s ';
2168  $res = $ilDB->manipulateF($query,array('integer'),array($a_tree_id));
2169  return true;
2170  }
2171 
2179  function saveSubTree($a_node_id, $a_set_deleted = false)
2180  {
2181  global $ilDB;
2182 
2183  if (!$a_node_id)
2184  {
2185  $message = sprintf('%s::saveSubTree(): No valid parameter given! $a_node_id: %s',
2186  get_class($this),
2187  $a_node_id);
2188  $this->log->write($message,$this->log->FATAL);
2189  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2190  }
2191 
2192  // LOCKED ###############################################
2193  if($this->__isMainTree())
2194  {
2195  $ilDB->lockTables(
2196  array(
2197  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE),
2198  1 => array('name' => 'object_reference', 'type' => ilDB::LOCK_WRITE)));
2199 
2200  #ilDB::_lockTables(array('tree' => 'WRITE',
2201  # 'object_reference' => 'WRITE'));
2202 
2203  }
2204 
2205  // GET LEFT AND RIGHT VALUE
2206  $query = 'SELECT * FROM '.$this->table_tree.' '.
2207  'WHERE '.$this->tree_pk.' = %s '.
2208  'AND child = %s ';
2209  $res = $ilDB->queryF($query,array('integer','integer'),array(
2210  $this->tree_id,
2211  $a_node_id));
2212 
2213  while($row = $ilDB->fetchObject($res))
2214  {
2215  $lft = $row->lft;
2216  $rgt = $row->rgt;
2217  }
2218 
2219  // GET ALL SUBNODES
2220  $query = 'SELECT child FROM '.$this->table_tree.' '.
2221  'WHERE '.$this->tree_pk.' = %s '.
2222  'AND lft BETWEEN %s AND %s ';
2223  $res = $ilDB->queryF($query,array('integer','integer','integer'),array(
2224  $this->tree_id,
2225  $lft,
2226  $rgt));
2227 
2228  $subnodes = array();
2229  while($row = $ilDB->fetchAssoc($res))
2230  {
2231  $subnodes[] = $row['child'];
2232  }
2233 
2234  if(!count($subnodes))
2235  {
2236  // possibly already deleted
2237 
2238  // Unlock locked tables before returning
2239  if($this->__isMainTree())
2240  {
2241  $ilDB->unlockTables();
2242  }
2243 
2244  return false;
2245  }
2246 
2247  // SAVE SUBTREE
2248  foreach($subnodes as $child)
2249  {
2250  // set node as deleted
2251  if ($a_set_deleted)
2252  {
2253  // TODO: new method that expects an array of ids
2254  ilObject::_setDeletedDate($child);
2255  }
2256  }
2257 
2258  // Set the nodes deleted (negative tree id)
2259  $query = 'UPDATE '.$this->table_tree.' '.
2260  'SET tree = %s '.
2261  'WHERE '.$this->tree_pk.' = %s '.
2262  'AND lft BETWEEN %s AND %s ';
2263  $res = $ilDB->manipulateF($query,array('integer','integer','integer','integer'),array(
2264  -$a_node_id,
2265  $this->tree_id,
2266  $lft,
2267  $rgt));
2268 
2269  if($this->__isMainTree())
2270  {
2271  $ilDB->unlockTables();
2272  }
2273 
2274  // LOCKED ###############################################
2275  return true;
2276  }
2277 
2281  function isDeleted($a_node_id)
2282  {
2283  return $this->isSaved($a_node_id);
2284  }
2285 
2289  function isSaved($a_node_id)
2290  {
2291  global $ilDB;
2292 
2293  // is saved cache
2294  if ($this->isCacheUsed() && isset($this->is_saved_cache[$a_node_id]))
2295  {
2296 //echo "<br>issavedhit";
2297  return $this->is_saved_cache[$a_node_id];
2298  }
2299 
2300  $query = 'SELECT '.$this->tree_pk.' FROM '.$this->table_tree.' '.
2301  'WHERE child = %s ';
2302  $res = $ilDB->queryF($query,array('integer'),array($a_node_id));
2303  $row = $ilDB->fetchAssoc($res);
2304 
2305  if ($row[$this->tree_pk] < 0)
2306  {
2307  if($this->__isMainTree())
2308  {
2309  $this->is_saved_cache[$a_node_id] = true;
2310  }
2311  return true;
2312  }
2313  else
2314  {
2315  if($this->__isMainTree())
2316  {
2317  $this->is_saved_cache[$a_node_id] = false;
2318  }
2319  return false;
2320  }
2321  }
2322 
2329  function preloadDeleted($a_node_ids)
2330  {
2331  global $ilDB;
2332 
2333  if (!is_array($a_node_ids) || !$this->isCacheUsed())
2334  {
2335  return;
2336  }
2337 
2338  $query = 'SELECT '.$this->tree_pk.', child FROM '.$this->table_tree.' '.
2339  'WHERE '.$ilDB->in("child", $a_node_ids, false, "integer");
2340 
2341  $res = $ilDB->query($query);
2342  while ($row = $ilDB->fetchAssoc($res))
2343  {
2344  if ($row[$this->tree_pk] < 0)
2345  {
2346  if($this->__isMainTree())
2347  {
2348  $this->is_saved_cache[$row["child"]] = true;
2349  }
2350  }
2351  else
2352  {
2353  if($this->__isMainTree())
2354  {
2355  $this->is_saved_cache[$row["child"]] = false;
2356  }
2357  }
2358  }
2359  }
2360 
2361 
2368  function getSavedNodeData($a_parent_id)
2369  {
2370  global $ilDB;
2371 
2372  if (!isset($a_parent_id))
2373  {
2374  $this->ilErr->raiseError(get_class($this)."::getSavedNodeData(): No node_id given!",$this->ilErr->WARNING);
2375  }
2376 
2377  $query = 'SELECT * FROM '.$this->table_tree.' '.
2378  $this->buildJoin().
2379  'WHERE '.$this->table_tree.'.'.$this->tree_pk.' < %s '.
2380  'AND '.$this->table_tree.'.parent = %s';
2381  $res = $ilDB->queryF($query,array('integer','integer'),array(
2382  0,
2383  $a_parent_id));
2384 
2385  while($row = $ilDB->fetchAssoc($res))
2386  {
2387  $saved[] = $this->fetchNodeData($row);
2388  }
2389 
2390  return $saved ? $saved : array();
2391  }
2392 
2399  function getParentId($a_node_id)
2400  {
2401  global $ilDB;
2402 
2403  if (!isset($a_node_id))
2404  {
2405  $this->ilErr->raiseError(get_class($this)."::getParentId(): No node_id given! ",$this->ilErr->WARNING);
2406  }
2407 
2408  $query = 'SELECT parent FROM '.$this->table_tree.' '.
2409  'WHERE child = %s '.
2410  'AND '.$this->tree_pk.' = %s ';
2411  $res = $ilDB->queryF($query,array('integer','integer'),array(
2412  $a_node_id,
2413  $this->tree_id));
2414 
2415  $row = $ilDB->fetchObject($res);
2416  return $row->parent;
2417  }
2418 
2425  function getLeftValue($a_node_id)
2426  {
2427  global $ilDB;
2428 
2429  if (!isset($a_node_id))
2430  {
2431  $this->ilErr->raiseError(get_class($this)."::getLeftValued(): No node_id given! ",$this->ilErr->WARNING);
2432  }
2433 
2434  $query = 'SELECT lft FROM '.$this->table_tree.' '.
2435  'WHERE child = %s '.
2436  'AND '.$this->tree_pk.' = %s ';
2437  $res = $ilDB->queryF($query,array('integer','integer'),array(
2438  $a_node_id,
2439  $this->tree_id));
2440  $row = $ilDB->fetchObject($res);
2441  return $row->lft;
2442  }
2443 
2450  function getChildSequenceNumber($a_node, $type = "")
2451  {
2452  global $ilDB;
2453 
2454  if (!isset($a_node))
2455  {
2456  $this->ilErr->raiseError(get_class($this)."::getChildSequenceNumber(): No node_id given! ",$this->ilErr->WARNING);
2457  }
2458 
2459  if($type)
2460  {
2461  $query = 'SELECT count(*) cnt FROM '.$this->table_tree.' '.
2462  $this->buildJoin().
2463  'WHERE lft <= %s '.
2464  'AND type = %s '.
2465  'AND parent = %s '.
2466  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s ';
2467 
2468  $res = $ilDB->queryF($query,array('integer','text','integer','integer'),array(
2469  $a_node['lft'],
2470  $type,
2471  $a_node['parent'],
2472  $this->tree_id));
2473  }
2474  else
2475  {
2476  $query = 'SELECT count(*) cnt FROM '.$this->table_tree.' '.
2477  $this->buildJoin().
2478  'WHERE lft <= %s '.
2479  'AND parent = %s '.
2480  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s ';
2481 
2482  $res = $ilDB->queryF($query,array('integer','integer','integer'),array(
2483  $a_node['lft'],
2484  $a_node['parent'],
2485  $this->tree_id));
2486 
2487  }
2488  $row = $ilDB->fetchAssoc($res);
2489  return $row["cnt"];
2490  }
2491 
2498  function readRootId()
2499  {
2500  global $ilDB;
2501 
2502  $query = 'SELECT child FROM '.$this->table_tree.' '.
2503  'WHERE parent = %s '.
2504  'AND '.$this->tree_pk.' = %s ';
2505  $res = $ilDB->queryF($query,array('integer','integer'),array(
2506  0,
2507  $this->tree_id));
2508  $row = $ilDB->fetchObject($res);
2509  $this->root_id = $row->child;
2510  return $this->root_id;
2511  }
2512 
2518  function getRootId()
2519  {
2520  return $this->root_id;
2521  }
2522  function setRootId($a_root_id)
2523  {
2524  $this->root_id = $a_root_id;
2525  }
2526 
2532  function getTreeId()
2533  {
2534  return $this->tree_id;
2535  }
2536 
2542  function setTreeId($a_tree_id)
2543  {
2544  $this->tree_id = $a_tree_id;
2545  }
2546 
2554  function fetchSuccessorNode($a_node_id, $a_type = "")
2555  {
2556  global $ilDB;
2557 
2558  if (!isset($a_node_id))
2559  {
2560  $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
2561  }
2562 
2563  // get lft value for current node
2564  $query = 'SELECT lft FROM '.$this->table_tree.' '.
2565  'WHERE '.$this->table_tree.'.child = %s '.
2566  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s ';
2567  $res = $ilDB->queryF($query,array('integer','integer'),array(
2568  $a_node_id,
2569  $this->tree_id));
2570 
2571  $curr_node = $ilDB->fetchAssoc($res);
2572 
2573  if($a_type)
2574  {
2575  $query = 'SELECT * FROM '.$this->table_tree.' '.
2576  $this->buildJoin().
2577  'WHERE lft > %s '.
2578  'AND '.$this->table_obj_data.'.type = %s '.
2579  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s '.
2580  'ORDER BY lft ';
2581  $ilDB->setLimit(1);
2582  $res = $ilDB->queryF($query,array('integer','text','integer'),array(
2583  $curr_node['lft'],
2584  $a_type,
2585  $this->tree_id));
2586  }
2587  else
2588  {
2589  $query = 'SELECT * FROM '.$this->table_tree.' '.
2590  $this->buildJoin().
2591  'WHERE lft > %s '.
2592  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s '.
2593  'ORDER BY lft ';
2594  $ilDB->setLimit(1);
2595  $res = $ilDB->queryF($query,array('integer','integer'),array(
2596  $curr_node['lft'],
2597  $this->tree_id));
2598  }
2599 
2600  if ($res->numRows() < 1)
2601  {
2602  return false;
2603  }
2604  else
2605  {
2606  $row = $ilDB->fetchAssoc($res);
2607  return $this->fetchNodeData($row);
2608  }
2609  }
2610 
2618  function fetchPredecessorNode($a_node_id, $a_type = "")
2619  {
2620  global $ilDB;
2621 
2622  if (!isset($a_node_id))
2623  {
2624  $this->ilErr->raiseError(get_class($this)."::getNodeData(): No node_id given! ",$this->ilErr->WARNING);
2625  }
2626 
2627  // get lft value for current node
2628  $query = 'SELECT lft FROM '.$this->table_tree.' '.
2629  'WHERE '.$this->table_tree.'.child = %s '.
2630  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s ';
2631  $res = $ilDB->queryF($query,array('integer','integer'),array(
2632  $a_node_id,
2633  $this->tree_id));
2634 
2635  $curr_node = $ilDB->fetchAssoc($res);
2636 
2637  if($a_type)
2638  {
2639  $query = 'SELECT * FROM '.$this->table_tree.' '.
2640  $this->buildJoin().
2641  'WHERE lft < %s '.
2642  'AND '.$this->table_obj_data.'.type = %s '.
2643  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s '.
2644  'ORDER BY lft DESC';
2645  $ilDB->setLimit(1);
2646  $res = $ilDB->queryF($query,array('integer','text','integer'),array(
2647  $curr_node['lft'],
2648  $a_type,
2649  $this->tree_id));
2650  }
2651  else
2652  {
2653  $query = 'SELECT * FROM '.$this->table_tree.' '.
2654  $this->buildJoin().
2655  'WHERE lft < %s '.
2656  'AND '.$this->table_tree.'.'.$this->tree_pk.' = %s '.
2657  'ORDER BY lft DESC';
2658  $ilDB->setLimit(1);
2659  $res = $ilDB->queryF($query,array('integer','integer'),array(
2660  $curr_node['lft'],
2661  $this->tree_id));
2662  }
2663 
2664  if ($res->numRows() < 1)
2665  {
2666  return false;
2667  }
2668  else
2669  {
2670  $row = $ilDB->fetchAssoc($res);
2671  return $this->fetchNodeData($row);
2672  }
2673  }
2674 
2683  function renumber($node_id = 1, $i = 1)
2684  {
2685  global $ilDB;
2686 
2687  // LOCKED ###################################
2688  if($this->__isMainTree())
2689  {
2690  /*
2691  ilDB::_lockTables(array($this->table_tree => 'WRITE',
2692  $this->table_obj_data => 'WRITE',
2693  $this->table_obj_reference => 'WRITE',
2694  'object_translation' => 'WRITE',
2695  'object_data od' => 'WRITE',
2696  'container_reference cr' => 'WRITE'));
2697  */
2698  $ilDB->lockTables(
2699  array(
2700  0 => array('name' => $this->table_tree, 'type' => ilDB::LOCK_WRITE),
2701  1 => array('name' => $this->table_obj_data, 'type' => ilDB::LOCK_WRITE),
2702  2 => array('name' => $this->table_obj_reference, 'type' => ilDB::LOCK_WRITE),
2703  3 => array('name' => 'object_translation', 'type' => ilDB::LOCK_WRITE),
2704  4 => array('name' => 'object_data', 'type' => ilDB::LOCK_WRITE, 'alias' => 'od'),
2705  5 => array('name' => 'container_reference', 'type' => ilDB::LOCK_WRITE, 'alias' => 'cr')
2706  ));
2707  }
2708  $return = $this->__renumber($node_id,$i);
2709  if($this->__isMainTree())
2710  {
2711  $ilDB->unlockTables();
2712  }
2713  // LOCKED ###################################
2714  return $return;
2715  }
2716 
2717  // PRIVATE
2727  function __renumber($node_id = 1, $i = 1)
2728  {
2729  global $ilDB;
2730 
2731  $query = 'UPDATE '.$this->table_tree.' SET lft = %s WHERE child = %s';
2732  $res = $ilDB->manipulateF($query,array('integer','integer'),array(
2733  $i,
2734  $node_id));
2735 
2736  $childs = $this->getChilds($node_id);
2737 
2738  foreach ($childs as $child)
2739  {
2740  $i = $this->__renumber($child["child"],$i+1);
2741  }
2742  $i++;
2743 
2744  // Insert a gap at the end of node, if the node has children
2745  if (count($childs) > 0)
2746  {
2747  $i += $this->gap * 2;
2748  }
2749 
2750 
2751  $query = 'UPDATE '.$this->table_tree.' SET rgt = %s WHERE child = %s';
2752  $res = $ilDB->manipulateF($query,array('integer','integer'),array(
2753  $i,
2754  $node_id));
2755  return $i;
2756  }
2757 
2758 
2769  function checkForParentType($a_ref_id,$a_type,$a_exclude_source_check = false)
2770  {
2771  // #12577
2772  $cache_key = $a_ref_id.'.'.$a_type.'.'.((int)$a_exclude_source_check);
2773 
2774  // Try to return a cached result
2775  if($this->isCacheUsed() &&
2776  array_key_exists($cache_key, $this->parent_type_cache))
2777  {
2778  return $this->parent_type_cache[$cache_key];
2779  }
2780 
2781  // Store up to 1000 results in cache
2782  $do_cache = ($this->__isMainTree() && count($this->parent_type_cache) < 1000);
2783 
2784  // ref_id is not in tree
2785  if(!$this->isInTree($a_ref_id))
2786  {
2787  if($do_cache)
2788  {
2789  $this->parent_type_cache[$cache_key] = false;
2790  }
2791  return false;
2792  }
2793 
2794  $path = array_reverse($this->getPathFull($a_ref_id));
2795 
2796  // remove first path entry as it is requested node
2797  if($a_exclude_source_check)
2798  {
2799  array_shift($path);
2800  }
2801 
2802  foreach($path as $node)
2803  {
2804  // found matching parent
2805  if($node["type"] == $a_type)
2806  {
2807  if($do_cache)
2808  {
2809  $this->parent_type_cache[$cache_key] = $node["child"];
2810  }
2811  return $node["child"];
2812  }
2813  }
2814 
2815  if($do_cache)
2816  {
2817  $this->parent_type_cache[$cache_key] = false;
2818  }
2819  return 0;
2820  }
2821 
2831  function _removeEntry($a_tree,$a_child,$a_db_table = "tree")
2832  {
2833  global $ilDB,$ilLog,$ilErr;
2834 
2835  if($a_db_table === 'tree')
2836  {
2837  if($a_tree == 1 and $a_child == ROOT_FOLDER_ID)
2838  {
2839  $message = sprintf('%s::_removeEntry(): Tried to delete root node! $a_tree: %s $a_child: %s',
2840  get_class($this),
2841  $a_tree,
2842  $a_child);
2843  $ilLog->write($message,$ilLog->FATAL);
2844  $ilErr->raiseError($message,$ilErr->WARNING);
2845  }
2846  }
2847 
2848  $query = 'DELETE FROM '.$a_db_table.' '.
2849  'WHERE tree = %s '.
2850  'AND child = %s ';
2851  $res = $ilDB->manipulateF($query,array('integer','integer'),array(
2852  $a_tree,
2853  $a_child));
2854 
2855  }
2856 
2857  // PRIVATE METHODS
2864  function __isMainTree()
2865  {
2866  return $this->table_tree === 'tree';
2867  }
2868 
2877  function __checkDelete($a_node)
2878  {
2879  global $ilDB;
2880 
2881  // get subtree by lft,rgt
2882  $query = 'SELECT * FROM '.$this->table_tree.' '.
2883  'WHERE lft >= %s '.
2884  'AND rgt <= %s '.
2885  'AND '.$this->tree_pk.' = %s ';
2886  $res = $ilDB->queryF($query,array('integer','integer','integer'),array(
2887  $a_node['lft'],
2888  $a_node['rgt'],
2889  $a_node[$this->tree_pk]));
2890 
2891  $counter = (int) $lft_childs = array();
2892  while($row = $ilDB->fetchObject($res))
2893  {
2894  $lft_childs[$row->child] = $row->parent;
2895  ++$counter;
2896  }
2897 
2898  // CHECK FOR DUPLICATE CHILD IDS
2899  if($counter != count($lft_childs))
2900  {
2901  $message = sprintf('%s::__checkTree(): Duplicate entries for "child" in maintree! $a_node_id: %s',
2902  get_class($this),
2903  $a_node['child']);
2904  $this->log->write($message,$this->log->FATAL);
2905  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2906  }
2907 
2908  // GET SUBTREE BY PARENT RELATION
2909  $parent_childs = array();
2910  $this->__getSubTreeByParentRelation($a_node['child'],$parent_childs);
2911  $this->__validateSubtrees($lft_childs,$parent_childs);
2912 
2913  return true;
2914  }
2915 
2916  function __getSubTreeByParentRelation($a_node_id,&$parent_childs)
2917  {
2918  global $ilDB;
2919 
2920  // GET PARENT ID
2921  $query = 'SELECT * FROM '.$this->table_tree.' '.
2922  'WHERE child = %s '.
2923  'AND tree = %s ';
2924  $res = $ilDB->queryF($query,array('integer','integer'),array(
2925  $a_node_id,
2926  $this->tree_id));
2927 
2928  $counter = 0;
2929  while($row = $ilDB->fetchObject($res))
2930  {
2931  $parent_childs[$a_node_id] = $row->parent;
2932  ++$counter;
2933  }
2934  // MULTIPLE ENTRIES
2935  if($counter > 1)
2936  {
2937  $message = sprintf('%s::__getSubTreeByParentRelation(): Multiple entries in maintree! $a_node_id: %s',
2938  get_class($this),
2939  $a_node_id);
2940  $this->log->write($message,$this->log->FATAL);
2941  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2942  }
2943 
2944  // GET ALL CHILDS
2945  $query = 'SELECT * FROM '.$this->table_tree.' '.
2946  'WHERE parent = %s ';
2947  $res = $ilDB->queryF($query,array('integer'),array($a_node_id));
2948 
2949  while($row = $ilDB->fetchObject($res))
2950  {
2951  // RECURSION
2952  $this->__getSubTreeByParentRelation($row->child,$parent_childs);
2953  }
2954  return true;
2955  }
2956 
2957  function __validateSubtrees(&$lft_childs,$parent_childs)
2958  {
2959  // SORT BY KEY
2960  ksort($lft_childs);
2961  ksort($parent_childs);
2962 
2963  if(count($lft_childs) != count($parent_childs))
2964  {
2965  $message = sprintf('%s::__validateSubtrees(): (COUNT) Tree is corrupted! Left/Right subtree does not comply .'.
2966  'with parent relation',
2967  get_class($this));
2968  $this->log->write($message,$this->log->FATAL);
2969  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2970  }
2971 
2972  foreach($lft_childs as $key => $value)
2973  {
2974  if($parent_childs[$key] != $value)
2975  {
2976  $message = sprintf('%s::__validateSubtrees(): (COMPARE) Tree is corrupted! Left/Right subtree does not comply '.
2977  'with parent relation',
2978  get_class($this));
2979  $this->log->write($message,$this->log->FATAL);
2980  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2981  }
2982  if($key == ROOT_FOLDER_ID)
2983  {
2984  $message = sprintf('%s::__validateSubtrees(): (ROOT_FOLDER) Tree is corrupted! Tried to delete root folder',
2985  get_class($this));
2986  $this->log->write($message,$this->log->FATAL);
2987  $this->ilErr->raiseError($message,$this->ilErr->WARNING);
2988  }
2989  }
2990  return true;
2991  }
2992 
3002  public function moveTree($a_source_id,$a_target_id,$a_location = IL_LAST_NODE)
3003  {
3004  global $ilDB;
3005 
3006  if($this->__isMainTree())
3007  {
3008  #ilDB::_lockTables(array('tree' => 'WRITE'));
3009  $ilDB->lockTables(
3010  array(
3011  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
3012 
3013  }
3014  // Receive node infos for source and target
3015  $query = 'SELECT * FROM '.$this->table_tree.' '.
3016  'WHERE ( child = %s OR child = %s ) '.
3017  'AND tree = %s ';
3018  $res = $ilDB->queryF($query,array('integer','integer','integer'),array(
3019  $a_source_id,
3020  $a_target_id,
3021  $this->tree_id));
3022 
3023  // Check in tree
3024  if($res->numRows() != 2)
3025  {
3026  if($this->__isMainTree())
3027  {
3028  $ilDB->unlockTables();
3029  }
3030  $this->log->write(__METHOD__.' Objects not found in tree!',$this->log->FATAL);
3031  $this->ilErr->raiseError('Error moving node',$this->ilErr->WARNING);
3032  }
3033  while($row = $ilDB->fetchObject($res))
3034  {
3035  if($row->child == $a_source_id)
3036  {
3037  $source_lft = $row->lft;
3038  $source_rgt = $row->rgt;
3039  $source_depth = $row->depth;
3040  $source_parent = $row->parent;
3041  }
3042  else
3043  {
3044  $target_lft = $row->lft;
3045  $target_rgt = $row->rgt;
3046  $target_depth = $row->depth;
3047  }
3048  }
3049 
3050  #var_dump("<pre>",$source_lft,$source_rgt,$source_depth,$target_lft,$target_rgt,$target_depth,"<pre>");
3051  // Check target not child of source
3052  if($target_lft >= $source_lft and $target_rgt <= $source_rgt)
3053  {
3054  if($this->__isMainTree())
3055  {
3056  $ilDB->unlockTables();
3057  }
3058  $this->log->write(__METHOD__.' Target is child of source',$this->log->FATAL);
3059  $this->ilErr->raiseError('Error moving node',$this->ilErr->WARNING);
3060  }
3061 
3062  // Now spread the tree at the target location. After this update the table should be still in a consistent state.
3063  // implementation for IL_LAST_NODE
3064  $spread_diff = $source_rgt - $source_lft + 1;
3065  #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
3066 
3067  $query = 'UPDATE '.$this->table_tree.' SET '.
3068  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, '.
3069  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END '.
3070  'WHERE tree = %s ';
3071  $res = $ilDB->manipulateF($query,array('integer','integer','integer','integer','integer'),array(
3072  $target_rgt,
3073  $spread_diff,
3074  $target_rgt,
3075  $spread_diff,
3076  $this->tree_id));
3077 
3078  // Maybe the source node has been updated, too.
3079  // Check this:
3080  if($source_lft > $target_rgt)
3081  {
3082  $where_offset = $spread_diff;
3083  $move_diff = $target_rgt - $source_lft - $spread_diff;
3084  }
3085  else
3086  {
3087  $where_offset = 0;
3088  $move_diff = $target_rgt - $source_lft;
3089  }
3090  $depth_diff = $target_depth - $source_depth + 1;
3091 
3092 
3093  $query = 'UPDATE '.$this->table_tree.' SET '.
3094  'parent = CASE WHEN parent = %s THEN %s ELSE parent END, '.
3095  'rgt = rgt + %s, '.
3096  'lft = lft + %s, '.
3097  'depth = depth + %s '.
3098  'WHERE lft >= %s '.
3099  'AND rgt <= %s '.
3100  'AND tree = %s ';
3101  $res = $ilDB->manipulateF($query,
3102  array('integer','integer','integer','integer','integer','integer','integer','integer'),
3103  array(
3104  $source_parent,
3105  $a_target_id,
3106  $move_diff,
3107  $move_diff,
3108  $depth_diff,
3109  $source_lft + $where_offset,
3110  $source_rgt + $where_offset,
3111  $this->tree_id));
3112 
3113  // done: close old gap
3114  $query = 'UPDATE '.$this->table_tree.' SET '.
3115  'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, '.
3116  'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END '.
3117  'WHERE tree = %s ';
3118 
3119  $res = $ilDB->manipulateF($query,
3120  array('integer','integer','integer','integer','integer'),
3121  array(
3122  $source_lft + $where_offset,
3123  $spread_diff,
3124  $source_rgt +$where_offset,
3125  $spread_diff,
3126  $this->tree_id));
3127 
3128  if($this->__isMainTree())
3129  {
3130  $ilDB->unlockTables();
3131  }
3132  return true;
3133  }
3134 
3142  public function getRbacSubtreeInfo($a_endnode_id)
3143  {
3144  global $ilDB;
3145 
3146  $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type ".
3147  "FROM ".$this->table_tree." t1 ".
3148  "JOIN ".$this->table_tree." t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) ".
3149  "JOIN ".$this->table_obj_reference." obr ON t2.child = obr.ref_id ".
3150  "JOIN ".$this->table_obj_data." obd ON obr.obj_id = obd.obj_id ".
3151  "WHERE t1.child = ".$ilDB->quote($a_endnode_id,'integer')." ".
3152  "AND t1.".$this->tree_pk." = ".$ilDB->quote($this->tree_id,'integer')." ".
3153  "AND t2.".$this->tree_pk." = ".$ilDB->quote($this->tree_id,'integer')." ".
3154  "ORDER BY t2.lft";
3155 
3156  $res = $ilDB->query($query);
3157  while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
3158  {
3159  $nodes[$row->child]['lft'] = $row->lft;
3160  $nodes[$row->child]['rgt'] = $row->rgt;
3161  $nodes[$row->child]['child']= $row->child;
3162  $nodes[$row->child]['type'] = $row->type;
3163 
3164  }
3165  return (array) $nodes;
3166  }
3167 } // END class.tree
3168 ?>