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