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