ILIAS  release_9 Revision v9.13-25-g2c18ec4c24f
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  // get right value of parent
332  if ($this->getTree()->__isMainTree()) {
333  $query = sprintf(
334  'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
335  'WHERE child = %s ',
336  $this->db->quote($a_parent_id, 'integer')
337  );
338  $res = $this->db->query($query);
339  } else {
340  $query = sprintf(
341  'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
342  'WHERE child = %s ' .
343  'AND ' . $this->getTree()->getTreePk() . ' = %s ',
344  $this->db->quote($a_parent_id, 'integer'),
345  $this->db->quote($this->getTree()->getTreeId(), 'integer')
346  );
347  $res = $this->db->query($query);
348  }
349  $r = $this->db->fetchObject($res);
350 
351  if ($r->parent === null) {
352  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
353  throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
354  }
355 
356  $right = $r->rgt;
357  $lft = $right;
358  $rgt = $right + 1;
359 
360  // spread tree
361  if ($this->getTree()->__isMainTree()) {
362  $query = sprintf(
363  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
364  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
365  'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ',
366  $this->db->quote($right, 'integer'),
367  $this->db->quote($right, 'integer')
368  );
369  $res = $this->db->manipulate($query);
370  } else {
371  $query = sprintf(
372  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
373  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
374  'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ' .
375  'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
376  $this->db->quote($right, 'integer'),
377  $this->db->quote($right, 'integer'),
378  $this->db->quote($this->getTree()->getTreeId(), 'integer')
379  );
380  $res = $this->db->manipulate($query);
381  }
382  }
383 
384  break;
385 
386  default:
387 
388  // get right value of preceeding child
389  $query = sprintf(
390  'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
391  'WHERE child = %s ' .
392  'AND ' . $this->getTree()->getTreePk() . ' = %s ',
393  $this->db->quote($a_pos, 'integer'),
394  $this->db->quote($this->getTree()->getTreeId(), 'integer')
395  );
396  $res = $this->db->query($query);
397  $r = $this->db->fetchObject($res);
398 
399  // crosscheck parents of sibling and new node (must be identical)
400  if ($r->parent != $a_parent_id) {
401  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
402  throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
403  }
404 
405  $right = $r->rgt;
406  $lft = $right + 1;
407  $rgt = $right + 2;
408 
409  if ($this->getTree()->__isMainTree()) {
410  $query = sprintf(
411  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
412  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
413  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ',
414  $this->db->quote($right, 'integer'),
415  $this->db->quote($right, 'integer')
416  );
417  $res = $this->db->manipulate($query);
418  } else {
419  $query = sprintf(
420  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
421  'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
422  'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
423  'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
424  $this->db->quote($right, 'integer'),
425  $this->db->quote($right, 'integer'),
426  $this->db->quote($this->getTree()->getTreeId(), 'integer')
427  );
428  $res = $this->db->manipulate($query);
429  }
430 
431  break;
432  }
433 
434  // get depth
435  $depth = $this->getTree()->getDepth($a_parent_id) + 1;
436 
437  // insert node
438  $query = sprintf(
439  'INSERT INTO ' . $this->getTree()->getTreeTable() . ' (' . $this->getTree()->getTreePk() . ',child,parent,lft,rgt,depth) ' .
440  'VALUES (%s,%s,%s,%s,%s,%s)',
441  $this->db->quote($this->getTree()->getTreeId(), 'integer'),
442  $this->db->quote($a_node_id, 'integer'),
443  $this->db->quote($a_parent_id, 'integer'),
444  $this->db->quote($lft, 'integer'),
445  $this->db->quote($rgt, 'integer'),
446  $this->db->quote($depth, 'integer')
447  );
448  $res = $this->db->manipulate($query);
449  };
450 
451  if ($this->getTree()->__isMainTree()) {
452  $ilAtomQuery = $this->db->buildAtomQuery();
453  $ilAtomQuery->addTableLock('tree');
454  $ilAtomQuery->addQueryCallable($insert_node_callable);
455  $ilAtomQuery->run();
456  } else {
457  $insert_node_callable($this->db);
458  }
459  }
460 
464  public function deleteTree(int $a_node_id): void
465  {
466  $delete_tree_callable = function (ilDBInterface $db) use ($a_node_id): void {
467  // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
468  // (object_reference, object_data)
469  $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
470  'WHERE child = ' . $this->db->quote($a_node_id, 'integer') . ' ' .
471  'AND ' . $this->getTree()->getTreePk() . ' = ' . $this->db->quote(
472  $this->getTree()->getTreeId(),
473  'integer'
474  );
475  $res = $this->db->query($query);
476  $node = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC);
477 
478  if($node === null) {
479  return; //Nothing to delete. $node does not exists
480  }
481 
482  // delete subtree
483  $query = sprintf(
484  'DELETE FROM ' . $this->getTree()->getTreeTable() . ' ' .
485  'WHERE lft BETWEEN %s AND %s ' .
486  'AND rgt BETWEEN %s AND %s ' .
487  'AND ' . $this->getTree()->getTreePk() . ' = %s',
488  $this->db->quote($node['lft'], 'integer'),
489  $this->db->quote($node['rgt'], 'integer'),
490  $this->db->quote($node['lft'], 'integer'),
491  $this->db->quote($node['rgt'], 'integer'),
492  $this->db->quote($node[$this->getTree()->getTreePk()], 'integer')
493  );
494  $res = $this->db->manipulate($query);
495 
496  // Performance improvement: We only close the gap, if the node
497  // is not in a trash tree, and if the resulting gap will be
498  // larger than twice the gap value
499 
500  $diff = $node["rgt"] - $node["lft"] + 1;
501  if (
502  $node[$this->getTree()->getTreePk()] >= 0 &&
503  $node['rgt'] - $node['lft'] >= $this->getTree()->getGap() * 2
504  ) {
505  if ($this->getTree()->__isMainTree()) {
506  $query = sprintf(
507  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
508  'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
509  'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ',
510  $this->db->quote($node['lft'], 'integer'),
511  $this->db->quote($diff, 'integer'),
512  $this->db->quote($node['lft'], 'integer'),
513  $this->db->quote($diff, 'integer')
514  );
515  $res = $this->db->manipulate($query);
516  } else {
517  $query = sprintf(
518  'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
519  'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
520  'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ' .
521  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
522  $this->db->quote($node['lft'], 'integer'),
523  $this->db->quote($diff, 'integer'),
524  $this->db->quote($node['lft'], 'integer'),
525  $this->db->quote($diff, 'integer'),
526  $this->db->quote($node[$this->getTree()->getTreePk()], 'integer')
527  );
528  $res = $this->db->manipulate($query);
529  }
530  }
531  };
532 
533  // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
534  if ($this->getTree()->__isMainTree()) {
535  $ilAtomQuery = $this->db->buildAtomQuery();
536  $ilAtomQuery->addTableLock('tree');
537  $ilAtomQuery->addQueryCallable($delete_tree_callable);
538  $ilAtomQuery->run();
539  } else {
540  $delete_tree_callable($this->db);
541  }
542  }
543 
547  public function moveToTrash(int $a_node_id): void
548  {
549  $move_to_trash_callable = function (ilDBInterface $db) use ($a_node_id): void {
550  $node = $this->getTree()->getNodeTreeData($a_node_id);
551 
552  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' ' .
553  'SET tree = ' . $this->db->quote(-1 * $node['child'], 'integer') . ' ' .
554  'WHERE ' . $this->getTree()->getTreePk() . ' = ' . $this->db->quote(
555  $this->getTree()->getTreeId(),
556  'integer'
557  ) . ' ' .
558  'AND lft BETWEEN ' . $this->db->quote(
559  $node['lft'],
560  'integer'
561  ) . ' AND ' . $this->db->quote($node['rgt'], 'integer') . ' ';
562 
563  $this->db->manipulate($query);
564  };
565 
566  // use ilAtomQuery to lock tables if tree is main tree
567  // otherwise just call this closure without locking
568  if ($this->getTree()->__isMainTree()) {
569  $ilAtomQuery = $this->db->buildAtomQuery();
570  $ilAtomQuery->addTableLock("tree");
571  $ilAtomQuery->addQueryCallable($move_to_trash_callable);
572  $ilAtomQuery->run();
573  } else {
574  $move_to_trash_callable($this->db);
575  }
576  }
577 
584  protected function getPathIdsUsingAdjacencyMap(int $a_endnode_id, int $a_startnode_id = 0): array
585  {
586  // The adjacency map algorithm is harder to implement than the nested sets algorithm.
587  // This algorithms performs an index search for each of the path element.
588  // This algorithms performs well for large trees which are not deeply nested.
589 
590  // The $takeId variable is used, to determine if a given id shall be included in the path
591  $takeId = $a_startnode_id == 0;
592 
593  $depth_cache = $this->getTree()->getDepthCache();
594  $parent_cache = $this->getTree()->getParentCache();
595 
596  if (
597  $this->getTree()->__isMainTree() &&
598  isset($depth_cache[$a_endnode_id]) &&
599  isset($parent_cache[$a_endnode_id])) {
600  $nodeDepth = $depth_cache[$a_endnode_id];
601  $parentId = $parent_cache[$a_endnode_id];
602  } else {
603  $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
604  $parentId = $this->getTree()->getParentId($a_endnode_id);
605  }
606 
607  // Fetch the node ids. For shallow depths we can fill in the id's directly.
608  $pathIds = array();
609 
610  // backward compatible check for nodes not in tree
611  if (!$nodeDepth) {
612  return array();
613  } elseif ($nodeDepth == 1) {
614  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
615  if ($takeId) {
616  $pathIds[] = $a_endnode_id;
617  }
618  } elseif ($nodeDepth == 2) {
619  $takeId = $takeId || $parentId == $a_startnode_id;
620  if ($takeId) {
621  $pathIds[] = $parentId;
622  }
623  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
624  if ($takeId) {
625  $pathIds[] = $a_endnode_id;
626  }
627  } elseif ($nodeDepth == 3) {
628  $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
629  if ($takeId) {
630  $pathIds[] = $this->getTree()->getRootId();
631  }
632  $takeId = $takeId || $parentId == $a_startnode_id;
633  if ($takeId) {
634  $pathIds[] = $parentId;
635  }
636  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
637  if ($takeId) {
638  $pathIds[] = $a_endnode_id;
639  }
640  } elseif ($nodeDepth < 32) {
641  // Adjacency Map Tree performs better than
642  // Nested Sets Tree even for very deep trees.
643  // The following code construct nested self-joins
644  // Since we already know the root-id of the tree and
645  // we also know the id and parent id of the current node,
646  // we only need to perform $nodeDepth - 3 self-joins.
647  // We can further reduce the number of self-joins by 1
648  // by taking into account, that each row in table tree
649  // contains the id of itself and of its parent.
650  $qSelect = 't1.child c0';
651  $qJoin = '';
652  for ($i = 1; $i < $nodeDepth - 2; $i++) {
653  $qSelect .= ', t' . $i . '.parent c' . $i;
654  if ($this->getTree()->__isMainTree()) {
655  $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
656  't' . $i . '.child=t' . ($i - 1) . '.parent ';
657  } else {
658  $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
659  't' . $i . '.child=t' . ($i - 1) . '.parent AND ' .
660  't' . $i . '.' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId();
661  }
662  }
663 
664  if ($this->getTree()->__isMainTree()) {
665  $types = array('integer');
666  $data = array($parentId);
667  $query = 'SELECT ' . $qSelect . ' ' .
668  'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
669  'WHERE t0.child = %s ';
670  } else {
671  $types = array('integer', 'integer');
672  $data = array($this->getTree()->getTreeId(), $parentId);
673  $query = 'SELECT ' . $qSelect . ' ' .
674  'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
675  'WHERE t0.' . $this->getTree()->getTreePk() . ' = %s ' .
676  'AND t0.child = %s ';
677  }
678 
679  $this->db->setLimit(1, 0);
680  $res = $this->db->queryF($query, $types, $data);
681 
682  if ($res->numRows() == 0) {
683  return array();
684  }
685 
686  $row = $this->db->fetchAssoc($res);
687 
688  $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
689  if ($takeId) {
690  $pathIds[] = $this->getTree()->getRootId();
691  }
692  for ($i = $nodeDepth - 4; $i >= 0; $i--) {
693  $takeId = $takeId || $row['c' . $i] == $a_startnode_id;
694  if ($takeId) {
695  $pathIds[] = (int) $row['c' . $i];
696  }
697  }
698  $takeId = $takeId || $parentId == $a_startnode_id;
699  if ($takeId) {
700  $pathIds[] = $parentId;
701  }
702  $takeId = $takeId || $a_endnode_id == $a_startnode_id;
703  if ($takeId) {
704  $pathIds[] = $a_endnode_id;
705  }
706  } else {
707  // Fall back to nested sets tree for extremely deep tree structures
708  return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
709  }
710  return $pathIds;
711  }
712 
718  public function getPathIdsUsingNestedSets(int $a_endnode_id, int $a_startnode_id = 0): array
719  {
720  // The nested sets algorithm is very easy to implement.
721  // Unfortunately it always does a full table space scan to retrieve the path
722  // regardless whether indices on lft and rgt are set or not.
723  // (At least, this is what happens on MySQL 4.1).
724  // This algorithms performs well for small trees which are deeply nested.
725 
726  if ($this->getTree()->__isMainTree()) {
727  $fields = array('integer');
728  $data = array($a_endnode_id);
729  $query = "SELECT T2.child " .
730  "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
731  "WHERE T1.child = %s " .
732  "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
733  "ORDER BY T2.depth";
734  } else {
735  $fields = array('integer', 'integer', 'integer');
736  $data = array($a_endnode_id, $this->getTree()->getTreeId(), $this->getTree()->getTreeId());
737  $query = "SELECT T2.child " .
738  "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
739  "WHERE T1.child = %s " .
740  "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
741  "AND T1." . $this->getTree()->getTreePk() . " = %s " .
742  "AND T2." . $this->getTree()->getTreePk() . " = %s " .
743  "ORDER BY T2.depth";
744  }
745 
746  $res = $this->db->queryF($query, $fields, $data);
747 
748  $takeId = $a_startnode_id == 0;
749  $pathIds = [];
750  while ($row = $this->db->fetchAssoc($res)) {
751  if ($takeId || $row['child'] == $a_startnode_id) {
752  $takeId = true;
753  $pathIds[] = (int) $row['child'];
754  }
755  }
756  return $pathIds;
757  }
758 
762  public function moveTree(int $a_source_id, int $a_target_id, int $a_position): void
763  {
764  $move_tree_callable = function (ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position): void {
765  // Receive node infos for source and target
766  $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
767  'WHERE ( child = %s OR child = %s ) ' .
768  'AND ' . $this->getTree()->getTreePk() . ' = %s ';
769  $res = $this->db->queryF($query, array('integer', 'integer', 'integer'), array(
770  $a_source_id,
771  $a_target_id,
772  $this->getTree()->getTreeId()
773  ));
774 
775  // Check in tree
776  if ($res->numRows() != 2) {
777  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
778  throw new InvalidArgumentException('Error moving subtree');
779  }
780  $source_lft = $target_lft = $source_rgt = $target_rgt = $source_depth = $target_depth = $source_parent = 0;
781  while ($row = $this->db->fetchObject($res)) {
782  if ($row->child == $a_source_id) {
783  $source_lft = $row->lft;
784  $source_rgt = $row->rgt;
785  $source_depth = $row->depth;
786  $source_parent = $row->parent;
787  } else {
788  $target_lft = $row->lft;
789  $target_rgt = $row->rgt;
790  $target_depth = $row->depth;
791  }
792  }
793 
794  // Check target not child of source
795  if ($target_lft >= $source_lft && $target_rgt <= $source_rgt) {
796  ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Target is child of source');
797  throw new InvalidArgumentException('Error moving subtree: target is child of source');
798  }
799 
800  // Now spread the tree at the target location. After this update the table should be still in a consistent state.
801  // implementation for ilTree::POS_LAST_NODE
802  $spread_diff = $source_rgt - $source_lft + 1;
803  #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
804 
805  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
806  'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
807  'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ';
808 
809  if ($this->getTree()->__isMainTree()) {
810  $res = $this->db->manipulateF($query, array('integer', 'integer', 'integer', 'integer'), [
811  $target_rgt,
812  $spread_diff,
813  $target_rgt,
814  $spread_diff
815  ]);
816  } else {
817  $query .= ('WHERE ' . $this->getTree()->getTreePk() . ' = %s ');
818  $res = $this->db->manipulateF(
819  $query,
820  array('integer', 'integer', 'integer', 'integer', 'integer'),
821  array(
822  $target_rgt,
823  $spread_diff,
824  $target_rgt,
825  $spread_diff,
826  $this->getTree()->getTreeId()
827  )
828  );
829  }
830 
831  // Maybe the source node has been updated, too.
832  // Check this:
833  if ($source_lft > $target_rgt) {
834  $where_offset = $spread_diff;
835  $move_diff = $target_rgt - $source_lft - $spread_diff;
836  } else {
837  $where_offset = 0;
838  $move_diff = $target_rgt - $source_lft;
839  }
840  $depth_diff = $target_depth - $source_depth + 1;
841 
842  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
843  'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
844  'rgt = rgt + %s, ' .
845  'lft = lft + %s, ' .
846  'depth = depth + %s ' .
847  'WHERE lft >= %s ' .
848  'AND rgt <= %s ';
849 
850  if ($this->getTree()->__isMainTree()) {
851  $res = $this->db->manipulateF(
852  $query,
853  array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'),
854  [
855  $source_parent,
856  $a_target_id,
857  $move_diff,
858  $move_diff,
859  $depth_diff,
860  $source_lft + $where_offset,
861  $source_rgt + $where_offset
862  ]
863  );
864  } else {
865  $query .= 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
866  $res = $this->db->manipulateF(
867  $query,
868  array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'),
869  array(
870  $source_parent,
871  $a_target_id,
872  $move_diff,
873  $move_diff,
874  $depth_diff,
875  $source_lft + $where_offset,
876  $source_rgt + $where_offset,
877  $this->getTree()->getTreeId()
878  )
879  );
880  }
881 
882  // done: close old gap
883  $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
884  'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
885  'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ';
886 
887  if ($this->getTree()->__isMainTree()) {
888  $res = $this->db->manipulateF($query, array('integer', 'integer', 'integer', 'integer'), [
889  $source_lft + $where_offset,
890  $spread_diff,
891  $source_rgt + $where_offset,
892  $spread_diff
893  ]);
894  } else {
895  $query .= ('WHERE ' . $this->getTree()->getTreePk() . ' = %s ');
896 
897  $res = $this->db->manipulateF(
898  $query,
899  array('integer', 'integer', 'integer', 'integer', 'integer'),
900  array(
901  $source_lft + $where_offset,
902  $spread_diff,
903  $source_rgt + $where_offset,
904  $spread_diff,
905  $this->getTree()->getTreeId()
906  )
907  );
908  }
909  };
910 
911  if ($this->getTree()->__isMainTree()) {
912  $ilAtomQuery = $this->db->buildAtomQuery();
913  $ilAtomQuery->addTableLock('tree');
914  $ilAtomQuery->addQueryCallable($move_tree_callable);
915  $ilAtomQuery->run();
916  } else {
917  $move_tree_callable($this->db);
918  }
919  }
920 
925  public function getSubtreeInfo(int $a_endnode_id): array
926  {
927  $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, t2.parent parent, type " .
928  "FROM " . $this->getTree()->getTreeTable() . " t1 " .
929  "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) " .
930  "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
931  "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
932  "WHERE t1.child = " . $this->db->quote($a_endnode_id, 'integer') . " " .
933  "AND t1." . $this->getTree()->getTreePk() . " = " . $this->db->quote(
934  $this->getTree()->getTreeId(),
935  'integer'
936  ) . " " .
937  "AND t2." . $this->getTree()->getTreePk() . " = " . $this->db->quote(
938  $this->getTree()->getTreeId(),
939  'integer'
940  ) . " " .
941  "ORDER BY t2.lft";
942 
943  $res = $this->db->query($query);
944  $nodes = array();
945  while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
946  $nodes[(int) $row->child]['lft'] = (int) $row->lft;
947  $nodes[(int) $row->child]['rgt'] = (int) $row->rgt;
948  $nodes[(int) $row->child]['child'] = (int) $row->child;
949  $nodes[(int) $row->child]['parent'] = (int) $row->parent;
950  $nodes[(int) $row->child]['type'] = (string) $row->type;
951  }
952  return $nodes;
953  }
954 
960  public function validateParentRelations(): array
961  {
962  $query = 'select ' . $this->getTree()->getTreePk() .', child from ' . $this->getTree()->getTreeTable() . ' child where not exists ' .
963  '( ' .
964  'select child from ' . $this->getTree()->getTreeTable() . ' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) ' .
965  ')' .
966  'and ' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId() . ' and child <> 1';
967  $res = $this->db->query($query);
968 
969  $failures = array();
970  while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
971  $failures[] = $row[$this->getTree()->getTreePk()];
972  }
973  return $failures;
974  }
975 }
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:90
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
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:464
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:762
ilNestedSetTree\getSubtreeInfo
getSubtreeInfo(int $a_endnode_id)
Definition: class.ilNestedSetTree.php:925
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:960
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:718
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:547
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:584
$r
$r
Definition: shib_logout.php:140