ILIAS  release_5-1 Revision 5.0.0-5477-g43f3e3fab5f
class.ilNestedSetTree.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 include_once './Services/Tree/interfaces/interface.ilTreeImplementation.php';
5 
16 class ilNestedSetTree implements ilTreeImplementation
17 {
18  private $tree = NULL;
19 
24  public function __construct(ilTree $a_tree)
25  {
26  $this->tree = $a_tree;
27  }
28 
33  public function getTree()
34  {
35  return $this->tree;
36  }
37 
42  public function getSubTreeIds($a_node_id)
43  {
44  global $ilDB;
45 
46  $query = 'SELECT s.child FROM '.
47  $this->getTree()->getTreeTable().' s, '.
48  $this->getTree()->getTreeTable().' t '.
49  'WHERE t.child = %s '.
50  'AND s.lft > t.lft '.
51  'AND s.rgt < t.rgt '.
52  'AND s.'.$this->getTree()->getTreePk().' = %s';
53 
54  $res = $ilDB->queryF(
55  $query,
56  array('integer','integer'),
57  array($a_node_id,$this->getTree()->getTreeId())
58  );
59  while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
60  {
61  $childs[] = $row->child;
62  }
63  return $childs ? $childs : array();
64  }
65 
72  public function getSubTreeQuery($a_node, $a_types = '', $a_force_join_reference = true, $a_fields = array())
73  {
74  global $ilDB;
75 
76  $type_str = '';
77  if (is_array($a_types))
78  {
79  if($a_types)
80  {
81  $type_str = "AND ".$ilDB->in($this->getTree()->getObjectDataTable().".type", $a_types, false, "text");
82  }
83  }
84  else if(strlen($a_types))
85  {
86  $type_str = "AND ".$this->getTree()->getObjectDataTable().".type = ".$ilDB->quote($a_types, "text");
87  }
88 
89  $join = '';
90  if($type_str or $a_force_join_reference)
91  {
92  $join = $this->getTree()->buildJoin();
93  }
94 
95  $fields = '* ';
96  if(count($a_fields))
97  {
98  $fields = implode(',',$a_fields);
99  }
100 
101  $query = 'SELECT '.
102  $fields.' '.
103  "FROM ".$this->getTree()->getTreeTable()." ".
104  $join.' '.
105  "WHERE ".$this->getTree()->getTreeTable().'.lft '.
106  'BETWEEN '.$ilDB->quote($a_node['lft'],'integer').' '.
107  'AND '.$ilDB->quote($a_node['rgt'],'integer').' '.
108  "AND ".$this->getTree()->getTreeTable().".".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer').' '.
109  $type_str.' '.
110  "ORDER BY ".$this->getTree()->getTreeTable().".lft";
111 
112  #$GLOBALS['ilLog']->write(__METHOD__.'-----------------: '. $query);
113 
114  return $query;
115  }
116 
117 
123  public function getRelation($a_node_a, $a_node_b)
124  {
125  if($a_node_a['child'] == $a_node_b['child'])
126  {
127  $GLOBALS['ilLog']->write(__METHOD__.': EQUALS');
128  return ilTree::RELATION_EQUALS;
129  }
130  if($a_node_a['lft'] < $a_node_b['lft'] and $a_node_a['rgt'] > $a_node_b['rgt'])
131  {
132  $GLOBALS['ilLog']->write(__METHOD__.': PARENT');
133  return ilTree::RELATION_PARENT;
134  }
135  if($a_node_b['lft'] < $a_node_a['lft'] and $a_node_b['rgt'] > $a_node_a['rgt'])
136  {
137  $GLOBALS['ilLog']->write(__METHOD__.': CHILD');
138  return ilTree::RELATION_CHILD;
139  }
140 
141  // if node is also parent of node b => sibling
142  if($a_node_a['parent'] == $a_node_b['parent'])
143  {
144  $GLOBALS['ilLog']->write(__METHOD__.': SIBLING');
145  return ilTree::RELATION_SIBLING;
146  }
147  $GLOBALS['ilLog']->write(__METHOD__.': NONE');
148  return ilTree::RELATION_NONE;
149  }
150 
156  public function getPathIds($a_endnode, $a_startnode = 0)
157  {
158  return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
159  }
160 
167  public function insertNode($a_node_id, $a_parent_id, $a_pos)
168  {
169  global $ilDB;
170 
171  // LOCKED ###############################
172  if($this->getTree()->__isMainTree())
173  {
174  $ilDB->lockTables(
175  array(
176  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
177  }
178  switch ($a_pos)
179  {
180  case ilTree::POS_FIRST_NODE:
181 
182  // get left value of parent
183  $query = sprintf('SELECT * FROM '.$this->getTree()->getTreeTable().' '.
184  'WHERE child = %s '.
185  'AND '.$this->getTree()->getTreePk().' = %s ',
186  $ilDB->quote($a_parent_id,'integer'),
187  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
188 
189  $res = $ilDB->query($query);
190  $r = $ilDB->fetchObject($res);
191 
192  if ($r->parent == NULL)
193  {
194  if($this->getTree()->__isMainTree())
195  {
196  $ilDB->unlockTables();
197  }
198  $GLOBALS['ilLog']->logStack();
199  throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
200  }
201 
202  $left = $r->lft;
203  $lft = $left + 1;
204  $rgt = $left + 2;
205 
206  // spread tree
207  $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
208  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
209  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END '.
210  'WHERE '.$this->getTree()->getTreePk().' = %s ',
211  $ilDB->quote($left,'integer'),
212  $ilDB->quote($left,'integer'),
213  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
214  $res = $ilDB->manipulate($query);
215  break;
216 
217  case IL_LAST_NODE:
218  // Special treatment for trees with gaps
219  if ($this->getTree()->getGap() > 0)
220  {
221  // get lft and rgt value of parent
222  $query = sprintf('SELECT rgt,lft,parent FROM '.$this->getTree()->getTreeTable().' '.
223  'WHERE child = %s '.
224  'AND '.$this->getTree()->getTreePk().' = %s',
225  $ilDB->quote($a_parent_id,'integer'),
226  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
227  $res = $ilDB->query($query);
228  $r = $ilDB->fetchAssoc($res);
229 
230  if ($r['parent'] == null)
231  {
232  if($this->getTree()->__isMainTree())
233  {
234  $ilDB->unlockTables();
235  }
236  $GLOBALS['ilLog']->logStack();
237  throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
238  }
239  $parentRgt = $r['rgt'];
240  $parentLft = $r['lft'];
241 
242  // Get the available space, without taking children into account yet
243  $availableSpace = $parentRgt - $parentLft;
244  if ($availableSpace < 2)
245  {
246  // If there is not enough space between parent lft and rgt, we don't need
247  // to look any further, because we must spread the tree.
248  $lft = $parentRgt;
249  }
250  else
251  {
252  // If there is space between parent lft and rgt, we need to check
253  // whether there is space left between the rightmost child of the
254  // parent and parent rgt.
255  $query = sprintf('SELECT MAX(rgt) max_rgt FROM '.$this->getTree()->getTreeTable().' '.
256  'WHERE parent = %s '.
257  'AND '.$this->getTree()->getTreePk().' = %s',
258  $ilDB->quote($a_parent_id,'integer'),
259  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
260  $res = $ilDB->query($query);
261  $r = $ilDB->fetchAssoc($res);
262 
263  if (isset($r['max_rgt']))
264  {
265  // If the parent has children, we compute the available space
266  // between rgt of the rightmost child and parent rgt.
267  $availableSpace = $parentRgt - $r['max_rgt'];
268  $lft = $r['max_rgt'] + 1;
269  }
270  else
271  {
272  // If the parent has no children, we know now, that we can
273  // add the new node at parent lft + 1 without having to spread
274  // the tree.
275  $lft = $parentLft + 1;
276  }
277  }
278  $rgt = $lft + 1;
279 
280 
281  // spread tree if there is not enough space to insert the new node
282  if ($availableSpace < 2)
283  {
284  //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
285  $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
286  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, '.
287  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END '.
288  'WHERE '.$this->getTree()->getTreePk().' = %s ',
289  $ilDB->quote($parentRgt,'integer'),
290  $ilDB->quote((2 + $this->getTree()->getGap() * 2),'integer'),
291  $ilDB->quote($parentRgt,'integer'),
292  $ilDB->quote((2 + $this->getTree()->getGap() * 2),'integer'),
293  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
294  $res = $ilDB->manipulate($query);
295  }
296  }
297  // Treatment for trees without gaps
298  else
299  {
300 
301  // get right value of parent
302  $query = sprintf('SELECT * FROM '.$this->getTree()->getTreeTable().' '.
303  'WHERE child = %s '.
304  'AND '.$this->getTree()->getTreePk().' = %s ',
305  $ilDB->quote($a_parent_id,'integer'),
306  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
307  $res = $ilDB->query($query);
308  $r = $ilDB->fetchObject($res);
309 
310  if ($r->parent == null)
311  {
312  if($this->getTree()->__isMainTree())
313  {
314  $ilDB->unlockTables();
315  }
316  $GLOBALS['ilLog']->logStack();
317  throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
318  }
319 
320  $right = $r->rgt;
321  $lft = $right;
322  $rgt = $right + 1;
323 
324  // spread tree
325  $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
326  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
327  'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END '.
328  'WHERE '.$this->getTree()->getTreePk().' = %s',
329  $ilDB->quote($right,'integer'),
330  $ilDB->quote($right,'integer'),
331  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
332  $res = $ilDB->manipulate($query);
333  }
334 
335  break;
336 
337  default:
338 
339  // get right value of preceeding child
340  $query = sprintf('SELECT * FROM '.$this->getTree()->getTreeTable().' '.
341  'WHERE child = %s '.
342  'AND '.$this->getTree()->getTreePk().' = %s ',
343  $ilDB->quote($a_pos,'integer'),
344  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
345  $res = $ilDB->query($query);
346  $r = $ilDB->fetchObject($res);
347 
348  // crosscheck parents of sibling and new node (must be identical)
349  if ($r->parent != $a_parent_id)
350  {
351  if($this->getTree()->__isMainTree())
352  {
353  $ilDB->unlockTables();
354  }
355  $GLOBALS['ilLog']->logStack();
356  throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
357  }
358 
359  $right = $r->rgt;
360  $lft = $right + 1;
361  $rgt = $right + 2;
362 
363  // update lft/rgt values
364  $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
365  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
366  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END '.
367  'WHERE '.$this->getTree()->getTreePk().' = %s',
368  $ilDB->quote($right,'integer'),
369  $ilDB->quote($right,'integer'),
370  $ilDB->quote($this->getTree()->getTreeId(),'integer'));
371  $res = $ilDB->manipulate($query);
372  break;
373 
374  }
375 
376  // get depth
377  $depth = $this->getTree()->getDepth($a_parent_id) + 1;
378 
379  // insert node
380  $query = sprintf('INSERT INTO '.$this->getTree()->getTreeTable().' ('.$this->getTree()->getTreePk().',child,parent,lft,rgt,depth) '.
381  'VALUES (%s,%s,%s,%s,%s,%s)',
382  $ilDB->quote($this->getTree()->getTreeId(),'integer'),
383  $ilDB->quote($a_node_id,'integer'),
384  $ilDB->quote($a_parent_id,'integer'),
385  $ilDB->quote($lft,'integer'),
386  $ilDB->quote($rgt,'integer'),
387  $ilDB->quote($depth,'integer'));
388  $res = $ilDB->manipulate($query);
389 
390  // Finally unlock tables and update cache
391  if($this->getTree()->__isMainTree())
392  {
393  $ilDB->unlockTables();
394  }
395  }
396 
397 
402  public function deleteTree($a_node_id)
403  {
404  global $ilDB;
405 
406  // LOCKED ###########################################################
407  // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
408  if($this->getTree()->__isMainTree())
409  {
410  $ilDB->lockTables(
411  array(
412  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
413  }
414 
415  // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
416  // (object_reference, object_data)
417  $query = 'SELECT * FROM '.$this->getTree()->getTreeTable().' '.
418  'WHERE child = '.$ilDB->quote($a_node_id,'integer').' '.
419  'AND '.$this->getTree()->getTreePk().' = '.$ilDB->quote($this->getTree()->getTreeId(),'integer');
420  $res = $ilDB->query($query);
421  $a_node = $res->fetchRow(DB_FETCHMODE_ASSOC);
422 
423  // delete subtree
424  $query = sprintf('DELETE FROM '.$this->getTree()->getTreeTable().' '.
425  'WHERE lft BETWEEN %s AND %s '.
426  'AND rgt BETWEEN %s AND %s '.
427  'AND '.$this->getTree()->getTreePk().' = %s',
428  $ilDB->quote($a_node['lft'],'integer'),
429  $ilDB->quote($a_node['rgt'],'integer'),
430  $ilDB->quote($a_node['lft'],'integer'),
431  $ilDB->quote($a_node['rgt'],'integer'),
432  $ilDB->quote($a_node[$this->getTree()->getTreePk()],'integer'));
433  $res = $ilDB->manipulate($query);
434 
435  // Performance improvement: We only close the gap, if the node
436  // is not in a trash tree, and if the resulting gap will be
437  // larger than twice the gap value
438 
439  $diff = $a_node["rgt"] - $a_node["lft"] + 1;
440  if(
441  $a_node[$this->getTree()->getTreePk()] >= 0 &&
442  $a_node['rgt'] - $a_node['lft'] >= $this->getTree()->getGap() * 2
443  )
444  {
445  // close gaps
446  $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
447  'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, '.
448  'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END '.
449  'WHERE '.$this->getTree()->getTreePk().' = %s ',
450  $ilDB->quote($a_node['lft'],'integer'),
451  $ilDB->quote($diff,'integer'),
452  $ilDB->quote($a_node['lft'],'integer'),
453  $ilDB->quote($diff,'integer'),
454  $ilDB->quote($a_node[$this->getTree()->getTreePk()],'integer'));
455 
456  $res = $ilDB->manipulate($query);
457  }
458 
459  if($this->getTree()->__isMainTree())
460  {
461  $ilDB->unlockTables();
462  }
463  // LOCKED ###########################################################
464  return true;
465  }
466 
473  public function moveToTrash($a_node_id)
474  {
475  global $ilDB;
476 
477  $node = $this->getTree()->getNodeTreeData($a_node_id);
478 
479  $query = 'UPDATE '.$this->getTree()->getTreeTable().' '.
480  'SET tree = '.$ilDB->quote(-1 * $node['child'],'integer').' '.
481  'WHERE '.$this->getTree()->getTreePk().' = '.$ilDB->quote($this->getTree()->getTreeId(),'integer').' '.
482  'AND lft BETWEEN '.$ilDB->quote($node['lft'],'integer').' AND '.$ilDB->quote($node['rgt'],'integer').' ';
483 
484  $ilDB->manipulate($query);
485  return true;
486  }
487 
488 
497  protected function getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id = 0)
498  {
499  global $ilDB;
500 
501  // The adjacency map algorithm is harder to implement than the nested sets algorithm.
502  // This algorithms performs an index search for each of the path element.
503  // This algorithms performs well for large trees which are not deeply nested.
504 
505  // The $takeId variable is used, to determine if a given id shall be included in the path
506  $takeId = $a_startnode_id == 0;
507 
508  $depth_cache = $this->getTree()->getDepthCache();
509  $parent_cache = $this->getTree()->getParentCache();
510 
511  if(
512  $this->getTree()->__isMainTree() &&
513  isset($depth_cache[$a_endnode_id]) &&
514  isset($parent_cache[$a_endnode_id]))
515  {
516  $nodeDepth = $depth_cache[$a_endnode_id];
517  $parentId = $parent_cache[$a_endnode_id];
518  }
519  else
520  {
521  $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
522  $parentId = $this->getTree()->getParentId($a_endnode_id);
523  }
524 
525  // Fetch the node ids. For shallow depths we can fill in the id's directly.
526  $pathIds = array();
527 
528  // backward compatible check for nodes not in tree
529  if(!$nodeDepth )
530  {
531  return array();
532  }
533  else if ($nodeDepth == 1)
534  {
535  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
536  if ($takeId) $pathIds[] = $a_endnode_id;
537  }
538  else if ($nodeDepth == 2)
539  {
540  $takeId = $takeId || $parentId == $a_startnode_id;
541  if ($takeId) $pathIds[] = $parentId;
542  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
543  if ($takeId) $pathIds[] = $a_endnode_id;
544  }
545  else if ($nodeDepth == 3)
546  {
547  $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
548  if ($takeId) $pathIds[] = $this->getTree()->getRootId();
549  $takeId = $takeId || $parentId == $a_startnode_id;
550  if ($takeId) $pathIds[] = $parentId;
551  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
552  if ($takeId) $pathIds[] = $a_endnode_id;
553  }
554  else if ($nodeDepth < 32)
555  {
556  // Adjacency Map Tree performs better than
557  // Nested Sets Tree even for very deep trees.
558  // The following code construct nested self-joins
559  // Since we already know the root-id of the tree and
560  // we also know the id and parent id of the current node,
561  // we only need to perform $nodeDepth - 3 self-joins.
562  // We can further reduce the number of self-joins by 1
563  // by taking into account, that each row in table tree
564  // contains the id of itself and of its parent.
565  $qSelect = 't1.child c0';
566  $qJoin = '';
567  for ($i = 1; $i < $nodeDepth - 2; $i++)
568  {
569  $qSelect .= ', t'.$i.'.parent c'.$i;
570  $qJoin .= ' JOIN '.$this->getTree()->getTreeTable().' t'.$i.' ON '.
571  't'.$i.'.child=t'.($i - 1).'.parent AND '.
572  't'.$i.'.'.$this->getTree()->getTreePk().' = '.(int) $this->getTree()->getTreeId();
573  }
574 
575  $types = array('integer','integer');
576  $data = array($this->getTree()->getTreeId(),$parentId);
577  $query = 'SELECT '.$qSelect.' '.
578  'FROM '.$this->getTree()->getTreeTable().' t0 '.$qJoin.' '.
579  'WHERE t0.'.$this->getTree()->getTreePk().' = %s '.
580  'AND t0.child = %s ';
581 
582  $ilDB->setLimit(1);
583  $res = $ilDB->queryF($query,$types,$data);
584 
585  if ($res->numRows() == 0)
586  {
587  return array();
588  }
589 
590  $row = $ilDB->fetchAssoc($res);
591 
592  $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
593  if ($takeId) $pathIds[] = $this->getTree()->getRootId();
594  for ($i = $nodeDepth - 4; $i >=0; $i--)
595  {
596  $takeId = $takeId || $row['c'.$i] == $a_startnode_id;
597  if ($takeId) $pathIds[] = $row['c'.$i];
598  }
599  $takeId = $takeId || $parentId == $a_startnode_id;
600  if ($takeId) $pathIds[] = $parentId;
601  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
602  if ($takeId) $pathIds[] = $a_endnode_id;
603  }
604  else
605  {
606  // Fall back to nested sets tree for extremely deep tree structures
607  return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
608  }
609  return $pathIds;
610  }
611 
620  public function getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id = 0)
621  {
622  global $ilDB;
623 
624  // The nested sets algorithm is very easy to implement.
625  // Unfortunately it always does a full table space scan to retrieve the path
626  // regardless whether indices on lft and rgt are set or not.
627  // (At least, this is what happens on MySQL 4.1).
628  // This algorithms performs well for small trees which are deeply nested.
629 
630  $fields = array('integer','integer','integer');
631  $data = array($a_endnode_id,$this->getTree()->getTreeId(),$this->getTree()->getTreeId());
632 
633  $query = "SELECT T2.child ".
634  "FROM ".$this->getTree()->getTreeTable()." T1, ".$this->getTree()->getTreeTable()." T2 ".
635  "WHERE T1.child = %s ".
636  "AND T1.lft BETWEEN T2.lft AND T2.rgt ".
637  "AND T1.".$this->getTree()->getTreePk()." = %s ".
638  "AND T2.".$this->getTree()->getTreePk()." = %s ".
639  "ORDER BY T2.depth";
640 
641  $res = $ilDB->queryF($query,$fields,$data);
642 
643  $takeId = $a_startnode_id == 0;
644  while($row = $ilDB->fetchAssoc($res))
645  {
646  if ($takeId || $row['child'] == $a_startnode_id)
647  {
648  $takeId = true;
649  $pathIds[] = $row['child'];
650  }
651  }
652  return $pathIds ? $pathIds : array();
653  }
654 
655 
662  public function moveTree($a_source_id, $a_target_id, $a_position)
663  {
664  global $ilDB;
665 
666  if ($this->getTree()->__isMainTree())
667  {
668  $ilDB->lockTables(
669  array(
670  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
671  }
672  // Receive node infos for source and target
673  $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
674  'WHERE ( child = %s OR child = %s ) ' .
675  'AND ' . $this->getTree()->getTreePk() . ' = %s ';
676  $res = $ilDB->queryF($query, array('integer', 'integer', 'integer'), array(
677  $a_source_id,
678  $a_target_id,
679  $this->getTree()->getTreeId()));
680 
681  // Check in tree
682  if ($res->numRows() != 2)
683  {
684  if ($this->getTree()->__isMainTree())
685  {
686  $ilDB->unlockTables();
687  }
688  $GLOBALS['ilLog']->logStack();
689  $GLOBALS['ilLog']->write(__METHOD__.': Objects not found in tree');
690  throw new InvalidArgumentException('Error moving subtree');
691  }
692  while ($row = $ilDB->fetchObject($res))
693  {
694  if ($row->child == $a_source_id)
695  {
696  $source_lft = $row->lft;
697  $source_rgt = $row->rgt;
698  $source_depth = $row->depth;
699  $source_parent = $row->parent;
700  }
701  else
702  {
703  $target_lft = $row->lft;
704  $target_rgt = $row->rgt;
705  $target_depth = $row->depth;
706  }
707  }
708 
709  // Check target not child of source
710  if ($target_lft >= $source_lft and $target_rgt <= $source_rgt)
711  {
712  if ($this->getTree()->__isMainTree())
713  {
714  $ilDB->unlockTables();
715  }
716  $GLOBALS['ilLog']->logStack();
717  $GLOBALS['ilLog']->write(__METHOD__.': Target is child of source');
718  throw new ilInvalidArgumentException('Error moving subtree: target is child of source');
719  }
720 
721  // Now spread the tree at the target location. After this update the table should be still in a consistent state.
722  // implementation for IL_LAST_NODE
723  $spread_diff = $source_rgt - $source_lft + 1;
724  #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
725 
726  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
727  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
728  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
729  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
730  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
731  $target_rgt,
732  $spread_diff,
733  $target_rgt,
734  $spread_diff,
735  $this->getTree()->getTreeId()));
736 
737  // Maybe the source node has been updated, too.
738  // Check this:
739  if ($source_lft > $target_rgt)
740  {
741  $where_offset = $spread_diff;
742  $move_diff = $target_rgt - $source_lft - $spread_diff;
743  }
744  else
745  {
746  $where_offset = 0;
747  $move_diff = $target_rgt - $source_lft;
748  }
749  $depth_diff = $target_depth - $source_depth + 1;
750 
751 
752  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
753  'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
754  'rgt = rgt + %s, ' .
755  'lft = lft + %s, ' .
756  'depth = depth + %s ' .
757  'WHERE lft >= %s ' .
758  'AND rgt <= %s ' .
759  'AND ' . $this->getTree()->getTreePk() . ' = %s ';
760  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), array(
761  $source_parent,
762  $a_target_id,
763  $move_diff,
764  $move_diff,
765  $depth_diff,
766  $source_lft + $where_offset,
767  $source_rgt + $where_offset,
768  $this->getTree()->getTreeId()));
769 
770  // done: close old gap
771  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
772  'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
773  'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' .
774  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
775 
776  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
777  $source_lft + $where_offset,
778  $spread_diff,
779  $source_rgt + $where_offset,
780  $spread_diff,
781  $this->getTree()->getTreeId()));
782 
783  if ($this->getTree()->__isMainTree())
784  {
785  $ilDB->unlockTables();
786  }
787  }
788 
795  public function getSubtreeInfo($a_endnode_id)
796  {
797  global $ilDB;
798 
799  $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type ".
800  "FROM ".$this->getTree()->getTreeTable()." t1 ".
801  "JOIN ".$this->getTree()->getTreeTable()." t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) ".
802  "JOIN ".$this->getTree()->getTableReference()." obr ON t2.child = obr.ref_id ".
803  "JOIN ".$this->getTree()->getObjectDataTable()." obd ON obr.obj_id = obd.obj_id ".
804  "WHERE t1.child = ".$ilDB->quote($a_endnode_id,'integer')." ".
805  "AND t1.".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer')." ".
806  "AND t2.".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer')." ".
807  "ORDER BY t2.lft";
808 
809  $GLOBALS['ilLog']->write(__METHOD__.': '.$query);
810 
811 
812  $res = $ilDB->query($query);
813  $nodes = array();
814  while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
815  {
816  $nodes[$row->child]['lft'] = $row->lft;
817  $nodes[$row->child]['rgt'] = $row->rgt;
818  $nodes[$row->child]['child']= $row->child;
819  $nodes[$row->child]['type'] = $row->type;
820 
821  }
822  return (array) $nodes;
823  }
824 
828  public function validateParentRelations()
829  {
830  global $ilDB;
831 
832  $query = 'select child from '.$this->getTree()->getTreeTable().' child where not exists '.
833  '( '.
834  'select child from '.$this->getTree()->getTreeTable().' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) '.
835  ')'.
836  'and '.$this->getTree()->getTreePk().' = '.$this->getTree()->getTreeId().' and child <> 1';
837  $res = $ilDB->query($query);
838 
839  ilLoggerFactory::getLogger('tree')->debug($query);
840 
841  $failures = array();
842  while($row = $res->fetchRow(DB_FETCHMODE_ASSOC))
843  {
844  $failures[] = $row[$this->getTree()->getTreePk()];
845  }
846  return $failures;
847  }
848 
849 }
850 ?>
ilInvalidTreeStructureException
Thrown if invalid tree strucutes are found.
Definition: class.ilInvalidTreeStructureException.php:16
ilNestedSetTree\getPathIdsUsingNestedSets
getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id=0)
get path from a given startnode to a given endnode if startnode is not given the rootnode is startnod...
Definition: class.ilNestedSetTree.php:620
ilNestedSetTree\getPathIdsUsingAdjacencyMap
getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id=0)
get path from a given startnode to a given endnode if startnode is not given the rootnode is startnod...
Definition: class.ilNestedSetTree.php:497
ilNestedSetTree\getPathIds
getPathIds($a_endnode, $a_startnode=0)
Get path ids.
Definition: class.ilNestedSetTree.php:156
ilNestedSetTree\getRelation
getRelation($a_node_a, $a_node_b)
Get relation.
Definition: class.ilNestedSetTree.php:123
ilNestedSetTree\getSubTreeIds
getSubTreeIds($a_node_id)
Get subtree ids.
Definition: class.ilNestedSetTree.php:42
ilTree\RELATION_PARENT
const RELATION_PARENT
Definition: class.ilTree.php:31
ilNestedSetTree\getTree
getTree()
Get tree object.
Definition: class.ilNestedSetTree.php:33
ilNestedSetTree
Base class for nested set path based trees.
Definition: class.ilNestedSetTree.php:16
ilNestedSetTree\moveTree
moveTree($a_source_id, $a_target_id, $a_position)
Move source subtree to target.
Definition: class.ilNestedSetTree.php:662
DB_FETCHMODE_OBJECT
const DB_FETCHMODE_OBJECT
Definition: class.ilDB.php:11
ilTree\POS_FIRST_NODE
const POS_FIRST_NODE
Definition: class.ilTree.php:27
ilNestedSetTree\insertNode
insertNode($a_node_id, $a_parent_id, $a_pos)
Insert tree node.
Definition: class.ilNestedSetTree.php:167
$r
$r
Definition: example_031.php:79
$data
$data
Definition: example_011.php:126
ilNestedSetTree\__construct
__construct(ilTree $a_tree)
Constructor.
Definition: class.ilNestedSetTree.php:24
DB_FETCHMODE_ASSOC
const DB_FETCHMODE_ASSOC
Definition: class.ilDB.php:10
ilDB\LOCK_WRITE
const LOCK_WRITE
Definition: class.ilDB.php:30
ilTree\RELATION_EQUALS
const RELATION_EQUALS
Definition: class.ilTree.php:33
ilTree\RELATION_CHILD
const RELATION_CHILD
Definition: class.ilTree.php:30
ilTree\RELATION_NONE
const RELATION_NONE
Definition: class.ilTree.php:34
ilTree
Tree class data representation in hierachical trees using the Nested Set Model with Gaps by Joe Celco...
Definition: class.ilTree.php:24
ilNestedSetTree\getSubtreeInfo
getSubtreeInfo($a_endnode_id)
Get rbac subtree info type $ilDB.
Definition: class.ilNestedSetTree.php:795
ilNestedSetTree\deleteTree
deleteTree($a_node_id)
Delete a subtree.
Definition: class.ilNestedSetTree.php:402
IL_LAST_NODE
const IL_LAST_NODE
Definition: class.ilTree.php:4
ilNestedSetTree\getSubTreeQuery
getSubTreeQuery($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
Get subtree.
Definition: class.ilNestedSetTree.php:72
$ilDB
global $ilDB
Definition: storeScorm2004.php:16
ilTree\RELATION_SIBLING
const RELATION_SIBLING
Definition: class.ilTree.php:32
ilNestedSetTree\validateParentRelations
validateParentRelations()
Validate the parent relations of the tree implementation For nested set, validate the lft...
Definition: class.ilNestedSetTree.php:828
ilLoggerFactory\getLogger
static getLogger($a_component_id)
Get component logger.
Definition: class.ilLoggerFactory.php:82
$GLOBALS
$GLOBALS['PHPCAS_CLIENT']
This global variable is used by the interface class phpCAS.
Definition: CAS.php:276
ilNestedSetTree\moveToTrash
moveToTrash($a_node_id)
Move to trash.
Definition: class.ilNestedSetTree.php:473
ilTreeImplementation
Interface for tree implementations Currrently nested set or materialize path.
Definition: interface.ilTreeImplementation.php:14