ILIAS  release_7 Revision v7.30-3-g800a261c036
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 
68 
72  public function getTrashSubTreeQuery($a_node, $a_types, $a_force_join_reference = true, $a_fields = [])
73  {
74  global $DIC;
75 
76  $ilDB = $DIC->database();
77 
78  $type_str = '';
79  if (is_array($a_types)) {
80  if ($a_types) {
81  $type_str = "AND " . $ilDB->in($this->getTree()->getObjectDataTable() . ".type", $a_types, false, "text");
82  }
83  } elseif (strlen($a_types)) {
84  $type_str = "AND " . $this->getTree()->getObjectDataTable() . ".type = " . $ilDB->quote($a_types, "text");
85  }
86 
87  $join = '';
88  if ($type_str or $a_force_join_reference) {
89  $join = $this->getTree()->buildJoin();
90  }
91 
92  $fields = '* ';
93  if (count($a_fields)) {
94  $fields = implode(',', $a_fields);
95  }
96 
97  $query = 'SELECT ' .
98  $fields . ' ' .
99  "FROM " . $this->getTree()->getTreeTable() . " " .
100  $join . ' ' .
101  "WHERE " . $this->getTree()->getTreeTable() . '.lft ' .
102  'BETWEEN ' . $ilDB->quote($a_node['lft'], 'integer') . ' ' .
103  'AND ' . $ilDB->quote($a_node['rgt'], 'integer') . ' ' .
104  "AND " . $this->getTree()->getTreeTable() . "." . $this->getTree()->getTreePk() . ' < 0 ' .
105  $type_str . ' ' .
106  "ORDER BY " . $this->getTree()->getTreeTable() . ".lft";
107 
108  return $query;
109  }
110 
120  public function getSubTreeQuery($a_node, $a_types = '', $a_force_join_reference = true, $a_fields = array())
121  {
122  global $DIC;
123 
124  $ilDB = $DIC['ilDB'];
125 
126  $type_str = '';
127  if (is_array($a_types)) {
128  if ($a_types) {
129  $type_str = "AND " . $ilDB->in($this->getTree()->getObjectDataTable() . ".type", $a_types, false, "text");
130  }
131  } elseif (strlen($a_types)) {
132  $type_str = "AND " . $this->getTree()->getObjectDataTable() . ".type = " . $ilDB->quote($a_types, "text");
133  }
134 
135  $join = '';
136  if ($type_str or $a_force_join_reference) {
137  $join = $this->getTree()->buildJoin();
138  }
139 
140  $fields = '* ';
141  if (count($a_fields)) {
142  $fields = implode(',', $a_fields);
143  }
144 
145  $query = 'SELECT ' .
146  $fields . ' ' .
147  "FROM " . $this->getTree()->getTreeTable() . " " .
148  $join . ' ' .
149  "WHERE " . $this->getTree()->getTreeTable() . '.lft ' .
150  'BETWEEN ' . $ilDB->quote($a_node['lft'], 'integer') . ' ' .
151  'AND ' . $ilDB->quote($a_node['rgt'], 'integer') . ' ' .
152  "AND " . $this->getTree()->getTreeTable() . "." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
153  $type_str . ' ' .
154  "ORDER BY " . $this->getTree()->getTreeTable() . ".lft";
155 
156 
157  return $query;
158  }
159 
160 
167  public function getRelation($a_node_a, $a_node_b)
168  {
169  if ($a_node_a['child'] == $a_node_b['child']) {
170  return ilTree::RELATION_EQUALS;
171  }
172  if ($a_node_a['lft'] < $a_node_b['lft'] and $a_node_a['rgt'] > $a_node_b['rgt']) {
173  return ilTree::RELATION_PARENT;
174  }
175  if ($a_node_b['lft'] < $a_node_a['lft'] and $a_node_b['rgt'] > $a_node_a['rgt']) {
176  return ilTree::RELATION_CHILD;
177  }
178 
179  // if node is also parent of node b => sibling
180  if ($a_node_a['parent'] == $a_node_b['parent']) {
181  return ilTree::RELATION_SIBLING;
182  }
183  return ilTree::RELATION_NONE;
184  }
185 
192  public function getPathIds($a_endnode, $a_startnode = 0)
193  {
194  return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
195  }
196 
205  public function insertNode($a_node_id, $a_parent_id, $a_pos)
206  {
207  global $DIC;
208 
209  $ilDB = $DIC['ilDB'];
210 
211  $insert_node_callable = function (ilDBInterface $ilDB) use ($a_node_id, $a_parent_id, $a_pos) {
212  switch ($a_pos) {
213  case ilTree::POS_FIRST_NODE:
214 
215  // get left value of parent
216  $query = sprintf(
217  'SELECT * 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 
224  $res = $ilDB->query($query);
225  $r = $ilDB->fetchObject($res);
226 
227  if ($r->parent === null) {
228  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
229  throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
230  }
231 
232  $left = $r->lft;
233  $lft = $left + 1;
234  $rgt = $left + 2;
235 
236  if ($this->getTree()->__isMainTree()) {
237  $query = sprintf(
238  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
239  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
240  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ',
241  $ilDB->quote($left, 'integer'),
242  $ilDB->quote($left, 'integer')
243  );
244  $res = $ilDB->manipulate($query);
245  } else {
246  $query = sprintf(
247  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
248  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
249  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
250  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
251  $ilDB->quote($left, 'integer'),
252  $ilDB->quote($left, 'integer'),
253  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
254  );
255  $res = $ilDB->manipulate($query);
256  }
257 
258  break;
259 
260  case IL_LAST_NODE:
261  // Special treatment for trees with gaps
262  if ($this->getTree()->getGap() > 0) {
263  // get lft and rgt value of parent
264  $query = sprintf(
265  'SELECT rgt,lft,parent FROM ' . $this->getTree()->getTreeTable() . ' ' .
266  'WHERE child = %s ' .
267  'AND ' . $this->getTree()->getTreePk() . ' = %s',
268  $ilDB->quote($a_parent_id, 'integer'),
269  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
270  );
271  $res = $ilDB->query($query);
272  $r = $ilDB->fetchAssoc($res);
273 
274  if ($r['parent'] === null) {
275  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
276  throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
277  }
278  $parentRgt = $r['rgt'];
279  $parentLft = $r['lft'];
280 
281  // Get the available space, without taking children into account yet
282  $availableSpace = $parentRgt - $parentLft;
283  if ($availableSpace < 2) {
284  // If there is not enough space between parent lft and rgt, we don't need
285  // to look any further, because we must spread the tree.
286  $lft = $parentRgt;
287  } else {
288  // If there is space between parent lft and rgt, we need to check
289  // whether there is space left between the rightmost child of the
290  // parent and parent rgt.
291  if ($this->getTree()->__isMainTree()) {
292  $query = sprintf(
293  'SELECT MAX(rgt) max_rgt FROM ' . $this->getTree()->getTreeTable() . ' ' .
294  'WHERE parent = %s ',
295  $ilDB->quote($a_parent_id, 'integer')
296  );
297  $res = $ilDB->query($query);
298  $r = $ilDB->fetchAssoc($res);
299  } else {
300  $query = sprintf(
301  'SELECT MAX(rgt) max_rgt FROM ' . $this->getTree()->getTreeTable() . ' ' .
302  'WHERE parent = %s ' .
303  'AND ' . $this->getTree()->getTreePk() . ' = %s',
304  $ilDB->quote($a_parent_id, 'integer'),
305  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
306  );
307  $res = $ilDB->query($query);
308  $r = $ilDB->fetchAssoc($res);
309  }
310 
311  if (isset($r['max_rgt'])) {
312  // If the parent has children, we compute the available space
313  // between rgt of the rightmost child and parent rgt.
314  $availableSpace = $parentRgt - $r['max_rgt'];
315  $lft = $r['max_rgt'] + 1;
316  } else {
317  // If the parent has no children, we know now, that we can
318  // add the new node at parent lft + 1 without having to spread
319  // the tree.
320  $lft = $parentLft + 1;
321  }
322  }
323  $rgt = $lft + 1;
324 
325 
326  // spread tree if there is not enough space to insert the new node
327  if ($availableSpace < 2) {
328  if ($this->getTree()->__isMainTree()) {
329  $query = sprintf(
330  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
331  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
332  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ',
333  $ilDB->quote($parentRgt, 'integer'),
334  $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
335  $ilDB->quote($parentRgt, 'integer'),
336  $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer')
337  );
338  $res = $ilDB->manipulate($query);
339  } else {
340  $query = sprintf(
341  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
342  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
343  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
344  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
345  $ilDB->quote($parentRgt, 'integer'),
346  $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
347  $ilDB->quote($parentRgt, 'integer'),
348  $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
349  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
350  );
351  $res = $ilDB->manipulate($query);
352  }
353  }
354  }
355  // Treatment for trees without gaps
356  else {
357 
358  // get right value of parent
359  if ($this->getTree()->__isMainTree()) {
360  $query = sprintf(
361  'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
362  'WHERE child = %s ',
363  $ilDB->quote($a_parent_id, 'integer')
364  );
365  $res = $ilDB->query($query);
366  } else {
367  $query = sprintf(
368  'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
369  'WHERE child = %s ' .
370  'AND ' . $this->getTree()->getTreePk() . ' = %s ',
371  $ilDB->quote($a_parent_id, 'integer'),
372  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
373  );
374  $res = $ilDB->query($query);
375  }
376  $r = $ilDB->fetchObject($res);
377 
378  if ($r->parent === null) {
379  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
380  throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
381  }
382 
383  $right = $r->rgt;
384  $lft = $right;
385  $rgt = $right + 1;
386 
387  // spread tree
388  if ($this->getTree()->__isMainTree()) {
389  $query = sprintf(
390  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
391  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
392  'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ',
393  $ilDB->quote($right, 'integer'),
394  $ilDB->quote($right, 'integer')
395  );
396  $res = $ilDB->manipulate($query);
397  } else {
398  $query = sprintf(
399  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
400  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
401  'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ' .
402  'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
403  $ilDB->quote($right, 'integer'),
404  $ilDB->quote($right, 'integer'),
405  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
406  );
407  $res = $ilDB->manipulate($query);
408  }
409  }
410 
411  break;
412 
413  default:
414 
415  // get right value of preceeding child
416  $query = sprintf(
417  'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
418  'WHERE child = %s ' .
419  'AND ' . $this->getTree()->getTreePk() . ' = %s ',
420  $ilDB->quote($a_pos, 'integer'),
421  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
422  );
423  $res = $ilDB->query($query);
424  $r = $ilDB->fetchObject($res);
425 
426  // crosscheck parents of sibling and new node (must be identical)
427  if ($r->parent != $a_parent_id) {
428  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
429  throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
430  }
431 
432  $right = $r->rgt;
433  $lft = $right + 1;
434  $rgt = $right + 2;
435 
436  if ($this->getTree()->__isMainTree()) {
437  $query = sprintf(
438  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
439  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
440  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ',
441  $ilDB->quote($right, 'integer'),
442  $ilDB->quote($right, 'integer')
443  );
444  $res = $ilDB->manipulate($query);
445  } else {
446  $query = sprintf(
447  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
448  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
449  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
450  'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
451  $ilDB->quote($right, 'integer'),
452  $ilDB->quote($right, 'integer'),
453  $ilDB->quote($this->getTree()->getTreeId(), 'integer')
454  );
455  $res = $ilDB->manipulate($query);
456  }
457 
458  break;
459 
460  }
461 
462  // get depth
463  $depth = $this->getTree()->getDepth($a_parent_id) + 1;
464 
465  // insert node
466  $query = sprintf(
467  'INSERT INTO ' . $this->getTree()->getTreeTable() . ' (' . $this->getTree()->getTreePk() . ',child,parent,lft,rgt,depth) ' .
468  'VALUES (%s,%s,%s,%s,%s,%s)',
469  $ilDB->quote($this->getTree()->getTreeId(), 'integer'),
470  $ilDB->quote($a_node_id, 'integer'),
471  $ilDB->quote($a_parent_id, 'integer'),
472  $ilDB->quote($lft, 'integer'),
473  $ilDB->quote($rgt, 'integer'),
474  $ilDB->quote($depth, 'integer')
475  );
476  $res = $ilDB->manipulate($query);
477  };
478 
479  if ($this->getTree()->__isMainTree()) {
480  $ilAtomQuery = $ilDB->buildAtomQuery();
481  $ilAtomQuery->addTableLock('tree');
482  $ilAtomQuery->addQueryCallable($insert_node_callable);
483  $ilAtomQuery->run();
484  } else {
485  $insert_node_callable($ilDB);
486  }
487  }
488 
489 
495  public function deleteTree($a_node_id)
496  {
497  global $DIC;
498 
499  $ilDB = $DIC['ilDB'];
500 
501  $delete_tree_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
502 
503  // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
504  // (object_reference, object_data)
505  $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
506  'WHERE child = ' . $ilDB->quote($a_node_id, 'integer') . ' ' .
507  'AND ' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer');
508  $res = $ilDB->query($query);
509  $a_node = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC);
510 
511  // delete subtree
512  $query = sprintf(
513  'DELETE FROM ' . $this->getTree()->getTreeTable() . ' ' .
514  'WHERE lft BETWEEN %s AND %s ' .
515  'AND rgt BETWEEN %s AND %s ' .
516  'AND ' . $this->getTree()->getTreePk() . ' = %s',
517  $ilDB->quote($a_node['lft'], 'integer'),
518  $ilDB->quote($a_node['rgt'], 'integer'),
519  $ilDB->quote($a_node['lft'], 'integer'),
520  $ilDB->quote($a_node['rgt'], 'integer'),
521  $ilDB->quote($a_node[$this->getTree()->getTreePk()], 'integer')
522  );
523  $res = $ilDB->manipulate($query);
524 
525  // Performance improvement: We only close the gap, if the node
526  // is not in a trash tree, and if the resulting gap will be
527  // larger than twice the gap value
528 
529  $diff = $a_node["rgt"] - $a_node["lft"] + 1;
530  if (
531  $a_node[$this->getTree()->getTreePk()] >= 0 &&
532  $a_node['rgt'] - $a_node['lft'] >= $this->getTree()->getGap() * 2
533  ) {
534  if ($this->getTree()->__isMainTree()) {
535  $query = sprintf(
536  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
537  'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
538  'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ',
539  $ilDB->quote($a_node['lft'], 'integer'),
540  $ilDB->quote($diff, 'integer'),
541  $ilDB->quote($a_node['lft'], 'integer'),
542  $ilDB->quote($diff, 'integer')
543  );
544  $res = $ilDB->manipulate($query);
545  } else {
546  $query = sprintf(
547  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
548  'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
549  'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ' .
550  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
551  $ilDB->quote($a_node['lft'], 'integer'),
552  $ilDB->quote($diff, 'integer'),
553  $ilDB->quote($a_node['lft'], 'integer'),
554  $ilDB->quote($diff, 'integer'),
555  $ilDB->quote($a_node[$this->getTree()->getTreePk()], 'integer')
556  );
557  $res = $ilDB->manipulate($query);
558  }
559  }
560  };
561 
562  // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
563  if ($this->getTree()->__isMainTree()) {
564  $ilAtomQuery = $ilDB->buildAtomQuery();
565  $ilAtomQuery->addTableLock('tree');
566  $ilAtomQuery->addQueryCallable($delete_tree_callable);
567  $ilAtomQuery->run();
568  } else {
569  $delete_tree_callable($ilDB);
570  }
571 
572  return true;
573  }
574 
583  public function moveToTrash($a_node_id)
584  {
585  global $DIC;
586 
587  $ilDB = $DIC['ilDB'];
588 
589  $move_to_trash_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
590  $node = $this->getTree()->getNodeTreeData($a_node_id);
591 
592  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' ' .
593  'SET tree = ' . $ilDB->quote(-1 * $node['child'], 'integer') . ' ' .
594  'WHERE ' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
595  'AND lft BETWEEN ' . $ilDB->quote($node['lft'], 'integer') . ' AND ' . $ilDB->quote($node['rgt'], 'integer') . ' ';
596 
597  $ilDB->manipulate($query);
598  };
599 
600  // use ilAtomQuery to lock tables if tree is main tree
601  // otherwise just call this closure without locking
602  if ($this->getTree()->__isMainTree()) {
603  $ilAtomQuery = $ilDB->buildAtomQuery();
604  $ilAtomQuery->addTableLock("tree");
605 
606  $ilAtomQuery->addQueryCallable($move_to_trash_callable);
607 
608  $ilAtomQuery->run();
609  } else {
610  $move_to_trash_callable($ilDB);
611  }
612 
613  return true;
614  }
615 
616 
625  protected function getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id = 0)
626  {
627  global $DIC;
628 
629  $ilDB = $DIC['ilDB'];
630 
631  // The adjacency map algorithm is harder to implement than the nested sets algorithm.
632  // This algorithms performs an index search for each of the path element.
633  // This algorithms performs well for large trees which are not deeply nested.
634 
635  // The $takeId variable is used, to determine if a given id shall be included in the path
636  $takeId = $a_startnode_id == 0;
637 
638  $depth_cache = $this->getTree()->getDepthCache();
639  $parent_cache = $this->getTree()->getParentCache();
640 
641  if (
642  $this->getTree()->__isMainTree() &&
643  isset($depth_cache[$a_endnode_id]) &&
644  isset($parent_cache[$a_endnode_id])) {
645  $nodeDepth = $depth_cache[$a_endnode_id];
646  $parentId = $parent_cache[$a_endnode_id];
647  } else {
648  $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
649  $parentId = $this->getTree()->getParentId($a_endnode_id);
650  }
651 
652  // Fetch the node ids. For shallow depths we can fill in the id's directly.
653  $pathIds = array();
654 
655  // backward compatible check for nodes not in tree
656  if (!$nodeDepth) {
657  return array();
658  } elseif ($nodeDepth == 1) {
659  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
660  if ($takeId) {
661  $pathIds[] = $a_endnode_id;
662  }
663  } elseif ($nodeDepth == 2) {
664  $takeId = $takeId || $parentId == $a_startnode_id;
665  if ($takeId) {
666  $pathIds[] = $parentId;
667  }
668  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
669  if ($takeId) {
670  $pathIds[] = $a_endnode_id;
671  }
672  } elseif ($nodeDepth == 3) {
673  $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
674  if ($takeId) {
675  $pathIds[] = $this->getTree()->getRootId();
676  }
677  $takeId = $takeId || $parentId == $a_startnode_id;
678  if ($takeId) {
679  $pathIds[] = $parentId;
680  }
681  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
682  if ($takeId) {
683  $pathIds[] = $a_endnode_id;
684  }
685  } elseif ($nodeDepth < 32) {
686  // Adjacency Map Tree performs better than
687  // Nested Sets Tree even for very deep trees.
688  // The following code construct nested self-joins
689  // Since we already know the root-id of the tree and
690  // we also know the id and parent id of the current node,
691  // we only need to perform $nodeDepth - 3 self-joins.
692  // We can further reduce the number of self-joins by 1
693  // by taking into account, that each row in table tree
694  // contains the id of itself and of its parent.
695  $qSelect = 't1.child c0';
696  $qJoin = '';
697  for ($i = 1; $i < $nodeDepth - 2; $i++) {
698  $qSelect .= ', t' . $i . '.parent c' . $i;
699  if ($this->getTree()->__isMainTree()) {
700  $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
701  't' . $i . '.child=t' . ($i - 1) . '.parent ';
702  } else {
703  $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
704  't' . $i . '.child=t' . ($i - 1) . '.parent AND ' .
705  't' . $i . '.' . $this->getTree()->getTreePk() . ' = ' . (int) $this->getTree()->getTreeId();
706  }
707  }
708 
709 
710  if ($this->getTree()->__isMainTree()) {
711  $types = array('integer');
712  $data = array($parentId);
713  $query = 'SELECT ' . $qSelect . ' ' .
714  'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
715  'WHERE t0.child = %s ';
716  } else {
717  $types = array('integer','integer');
718  $data = array($this->getTree()->getTreeId(),$parentId);
719  $query = 'SELECT ' . $qSelect . ' ' .
720  'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
721  'WHERE t0.' . $this->getTree()->getTreePk() . ' = %s ' .
722  'AND t0.child = %s ';
723  }
724 
725  $ilDB->setLimit(1);
726  $res = $ilDB->queryF($query, $types, $data);
727 
728  if ($res->numRows() == 0) {
729  return array();
730  }
731 
732  $row = $ilDB->fetchAssoc($res);
733 
734  $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
735  if ($takeId) {
736  $pathIds[] = $this->getTree()->getRootId();
737  }
738  for ($i = $nodeDepth - 4; $i >= 0; $i--) {
739  $takeId = $takeId || $row['c' . $i] == $a_startnode_id;
740  if ($takeId) {
741  $pathIds[] = $row['c' . $i];
742  }
743  }
744  $takeId = $takeId || $parentId == $a_startnode_id;
745  if ($takeId) {
746  $pathIds[] = $parentId;
747  }
748  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
749  if ($takeId) {
750  $pathIds[] = $a_endnode_id;
751  }
752  } else {
753  // Fall back to nested sets tree for extremely deep tree structures
754  return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
755  }
756  return $pathIds;
757  }
758 
767  public function getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id = 0)
768  {
769  global $DIC;
770 
771  $ilDB = $DIC['ilDB'];
772 
773  // The nested sets algorithm is very easy to implement.
774  // Unfortunately it always does a full table space scan to retrieve the path
775  // regardless whether indices on lft and rgt are set or not.
776  // (At least, this is what happens on MySQL 4.1).
777  // This algorithms performs well for small trees which are deeply nested.
778 
779 
780  if ($this->getTree()->__isMainTree()) {
781  $fields = array('integer');
782  $data = array($a_endnode_id);
783  $query = "SELECT T2.child " .
784  "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
785  "WHERE T1.child = %s " .
786  "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
787  "ORDER BY T2.depth";
788  } else {
789  $fields = array('integer','integer','integer');
790  $data = array($a_endnode_id,$this->getTree()->getTreeId(),$this->getTree()->getTreeId());
791  $query = "SELECT T2.child " .
792  "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
793  "WHERE T1.child = %s " .
794  "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
795  "AND T1." . $this->getTree()->getTreePk() . " = %s " .
796  "AND T2." . $this->getTree()->getTreePk() . " = %s " .
797  "ORDER BY T2.depth";
798  }
799 
800  $res = $ilDB->queryF($query, $fields, $data);
801 
802  $takeId = $a_startnode_id == 0;
803  while ($row = $ilDB->fetchAssoc($res)) {
804  if ($takeId || $row['child'] == $a_startnode_id) {
805  $takeId = true;
806  $pathIds[] = $row['child'];
807  }
808  }
809  return $pathIds ? $pathIds : array();
810  }
811 
812 
821  public function moveTree($a_source_id, $a_target_id, $a_position)
822  {
823  global $DIC;
824 
825  $ilDB = $DIC['ilDB'];
826 
827  $move_tree_callable = function (ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position) {
828  // Receive node infos for source and target
829  $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
830  'WHERE ( child = %s OR child = %s ) ' .
831  'AND ' . $this->getTree()->getTreePk() . ' = %s ';
832  $res = $ilDB->queryF($query, array('integer', 'integer', 'integer'), array(
833  $a_source_id,
834  $a_target_id,
835  $this->getTree()->getTreeId()));
836 
837  // Check in tree
838  if ($res->numRows() != 2) {
839  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
840  throw new InvalidArgumentException('Error moving subtree');
841  }
842  while ($row = $ilDB->fetchObject($res)) {
843  if ($row->child == $a_source_id) {
844  $source_lft = $row->lft;
845  $source_rgt = $row->rgt;
846  $source_depth = $row->depth;
847  $source_parent = $row->parent;
848  } else {
849  $target_lft = $row->lft;
850  $target_rgt = $row->rgt;
851  $target_depth = $row->depth;
852  }
853  }
854 
855  // Check target not child of source
856  if ($target_lft >= $source_lft and $target_rgt <= $source_rgt) {
857  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Target is child of source');
858  throw new InvalidArgumentException('Error moving subtree: target is child of source');
859  }
860 
861  // Now spread the tree at the target location. After this update the table should be still in a consistent state.
862  // implementation for IL_LAST_NODE
863  $spread_diff = $source_rgt - $source_lft + 1;
864  #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
865 
866  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
867  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
868  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ';
869 
870  if ($this->getTree()->__isMainTree()) {
871  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer'), [
872  $target_rgt,
873  $spread_diff,
874  $target_rgt,
875  $spread_diff
876  ]);
877  } else {
878  $query .= ('WHERE ' . $this->getTree()->getTreePk() . ' = %s ');
879  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
880  $target_rgt,
881  $spread_diff,
882  $target_rgt,
883  $spread_diff,
884  $this->getTree()->getTreeId()));
885  }
886 
887 
888  // Maybe the source node has been updated, too.
889  // Check this:
890  if ($source_lft > $target_rgt) {
891  $where_offset = $spread_diff;
892  $move_diff = $target_rgt - $source_lft - $spread_diff;
893  } else {
894  $where_offset = 0;
895  $move_diff = $target_rgt - $source_lft;
896  }
897  $depth_diff = $target_depth - $source_depth + 1;
898 
899 
900  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
901  'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
902  'rgt = rgt + %s, ' .
903  'lft = lft + %s, ' .
904  'depth = depth + %s ' .
905  'WHERE lft >= %s ' .
906  'AND rgt <= %s ' ;
907 
908  if ($this->getTree()->__isMainTree()) {
909  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), [
910  $source_parent,
911  $a_target_id,
912  $move_diff,
913  $move_diff,
914  $depth_diff,
915  $source_lft + $where_offset,
916  $source_rgt + $where_offset
917  ]);
918  } else {
919  $query .= 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
920  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), array(
921  $source_parent,
922  $a_target_id,
923  $move_diff,
924  $move_diff,
925  $depth_diff,
926  $source_lft + $where_offset,
927  $source_rgt + $where_offset,
928  $this->getTree()->getTreeId()));
929  }
930 
931 
932  // done: close old gap
933  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
934  'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
935  'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' ;
936 
937  if ($this->getTree()->__isMainTree()) {
938  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer'), [
939  $source_lft + $where_offset,
940  $spread_diff,
941  $source_rgt + $where_offset,
942  $spread_diff
943  ]);
944  } else {
945  $query .= ('WHERE ' . $this->getTree()->getTreePk() . ' = %s ');
946 
947  $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
948  $source_lft + $where_offset,
949  $spread_diff,
950  $source_rgt + $where_offset,
951  $spread_diff,
952  $this->getTree()->getTreeId()));
953  }
954  };
955 
956 
957  if ($this->getTree()->__isMainTree()) {
958  $ilAtomQuery = $ilDB->buildAtomQuery();
959  $ilAtomQuery->addTableLock('tree');
960  $ilAtomQuery->addQueryCallable($move_tree_callable);
961  $ilAtomQuery->run();
962  } else {
963  $move_tree_callable($ilDB);
964  }
965  }
966 
973  public function getSubtreeInfo($a_endnode_id)
974  {
975  global $DIC;
976 
977  $ilDB = $DIC['ilDB'];
978 
979  $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type " .
980  "FROM " . $this->getTree()->getTreeTable() . " t1 " .
981  "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) " .
982  "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
983  "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
984  "WHERE t1.child = " . $ilDB->quote($a_endnode_id, 'integer') . " " .
985  "AND t1." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
986  "AND t2." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
987  "ORDER BY t2.lft";
988 
989 
990  $res = $ilDB->query($query);
991  $nodes = array();
992  while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
993  $nodes[$row->child]['lft'] = $row->lft;
994  $nodes[$row->child]['rgt'] = $row->rgt;
995  $nodes[$row->child]['child'] = $row->child;
996  $nodes[$row->child]['type'] = $row->type;
997  }
998  return (array) $nodes;
999  }
1000 
1004  public function validateParentRelations()
1005  {
1006  global $DIC;
1007 
1008  $ilDB = $DIC['ilDB'];
1009 
1010  $query = 'select child from ' . $this->getTree()->getTreeTable() . ' child where not exists ' .
1011  '( ' .
1012  'select child from ' . $this->getTree()->getTreeTable() . ' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) ' .
1013  ')' .
1014  'and ' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId() . ' and child <> 1';
1015  $res = $ilDB->query($query);
1016 
1017  $failures = array();
1018  while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
1019  $failures[] = $row[$this->getTree()->getTreePk()];
1020  }
1021  return $failures;
1022  }
1023 }
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:767
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:625
ilNestedSetTree\getPathIds
getPathIds($a_endnode, $a_startnode=0)
Get path ids.
Definition: class.ilNestedSetTree.php:192
$data
$data
Definition: storeScorm.php:23
ilNestedSetTree\getRelation
getRelation($a_node_a, $a_node_b)
Get relation.
Definition: class.ilNestedSetTree.php:167
ilNestedSetTree\getSubTreeIds
getSubTreeIds($a_node_id)
Get subtree ids.
Definition: class.ilNestedSetTree.php:43
ilTree\RELATION_PARENT
const RELATION_PARENT
Definition: class.ilTree.php:34
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:821
ilNestedSetTree\getTrashSubTreeQuery
getTrashSubTreeQuery($a_node, $a_types, $a_force_join_reference=true, $a_fields=[])
Get subtree query for trashed tree items.mixed
Definition: class.ilNestedSetTree.php:72
ilTree\POS_FIRST_NODE
const POS_FIRST_NODE
Definition: class.ilTree.php:30
ilNestedSetTree\insertNode
insertNode($a_node_id, $a_parent_id, $a_pos)
Insert tree node.
Definition: class.ilNestedSetTree.php:205
$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
$DIC
global $DIC
Definition: goto.php:24
$query
$query
Definition: proxy_ylocal.php:13
ilTree\RELATION_EQUALS
const RELATION_EQUALS
Definition: class.ilTree.php:36
ilTree\RELATION_CHILD
const RELATION_CHILD
Definition: class.ilTree.php:33
ilTree\RELATION_NONE
const RELATION_NONE
Definition: class.ilTree.php:37
ilNestedSetTree\getSubtreeInfo
getSubtreeInfo($a_endnode_id)
Get rbac subtree info type $ilDB.
Definition: class.ilNestedSetTree.php:973
ilNestedSetTree\deleteTree
deleteTree($a_node_id)
Delete a subtree.
Definition: class.ilNestedSetTree.php:495
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:120
$ilDB
global $ilDB
Definition: storeScorm2004.php:16
ilTree\RELATION_SIBLING
const RELATION_SIBLING
Definition: class.ilTree.php:35
ilNestedSetTree\validateParentRelations
validateParentRelations()
Validate the parent relations of the tree implementation For nested set, validate the lft...
Definition: class.ilNestedSetTree.php:1004
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:583
ilTreeImplementation
Interface for tree implementations Currrently nested set or materialize path.
Definition: interface.ilTreeImplementation.php:14
$i
$i
Definition: metadata.php:24