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