ILIAS  trunk Revision v11.0_alpha-3011-gc6b235a2e85
class.ilNestedSetTree.php
Go to the documentation of this file.
1<?php
2
19declare(strict_types=1);
20
28{
29 protected ilTree $tree;
30 protected ilDBInterface $db;
31
35 public function __construct(ilTree $a_tree)
36 {
37 global $DIC;
38
39 $this->tree = $a_tree;
40 $this->db = $DIC->database();
41 }
42
43 protected function getTree(): \ilTree
44 {
45 return $this->tree;
46 }
47
52 public function getSubTreeIds(int $a_node_id): array
53 {
54 $query = 'SELECT s.child FROM ' .
55 $this->getTree()->getTreeTable() . ' s, ' .
56 $this->getTree()->getTreeTable() . ' t ' .
57 'WHERE t.child = %s ' .
58 'AND s.lft > t.lft ' .
59 'AND s.rgt < t.rgt ' .
60 'AND s.' . $this->getTree()->getTreePk() . ' = %s';
61
62 $res = $this->db->queryF(
63 $query,
64 array('integer', 'integer'),
65 array($a_node_id, $this->getTree()->getTreeId())
66 );
67 $childs = [];
68 while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
69 $childs[] = (int) $row->child;
70 }
71 return $childs;
72 }
73
77 public function getTrashSubTreeQuery(
78 array $a_node,
79 array $a_types,
80 bool $a_force_join_reference = true,
81 array $a_fields = []
82 ): string {
83 $type_str = '';
84 if (is_array($a_types)) {
85 if ($a_types) {
86 $type_str = "AND " . $this->db->in(
87 $this->getTree()->getObjectDataTable() . ".type",
88 $a_types,
89 false,
90 "text"
91 );
92 }
93 }
94
95 $join = '';
96 if ($type_str || $a_force_join_reference) {
97 $join = $this->getTree()->buildJoin();
98 }
99
100 $fields = '* ';
101 if (count($a_fields)) {
102 $fields = implode(',', $a_fields);
103 }
104
105 $query = 'SELECT ' .
106 $fields . ' ' .
107 "FROM " . $this->getTree()->getTreeTable() . " " .
108 $join . ' ' .
109 "WHERE " . $this->getTree()->getTreeTable() . '.lft ' .
110 'BETWEEN ' . $this->db->quote($a_node['lft'], 'integer') . ' ' .
111 'AND ' . $this->db->quote($a_node['rgt'], 'integer') . ' ' .
112 "AND " . $this->getTree()->getTreeTable() . "." . $this->getTree()->getTreePk() . ' < 0 ' .
113 $type_str . ' ' .
114 "ORDER BY " . $this->getTree()->getTreeTable() . ".lft";
115
116 return $query;
117 }
118
122 public function getSubTreeQuery(
123 array $a_node,
124 array $a_types = [],
125 bool $a_force_join_reference = true,
126 array $a_fields = []
127 ): string {
128 $type_str = '';
129 if (count($a_types)) {
130 if ($a_types) {
131 $type_str = "AND " . $this->db->in(
132 $this->getTree()->getObjectDataTable() . ".type",
133 $a_types,
134 false,
135 "text"
136 );
137 }
138 }
139
140
141 $join = '';
142 if ($type_str || $a_force_join_reference) {
143 $join = $this->getTree()->buildJoin();
144 }
145
146 $fields = '* ';
147 if (count($a_fields)) {
148 $fields = implode(',', $a_fields);
149 }
150
151 $query = 'SELECT ' .
152 $fields . ' ' .
153 "FROM " . $this->getTree()->getTreeTable() . " " .
154 $join . ' ' .
155 "WHERE " . $this->getTree()->getTreeTable() . '.lft ' .
156 'BETWEEN ' . $this->db->quote($a_node['lft'], 'integer') . ' ' .
157 'AND ' . $this->db->quote($a_node['rgt'], 'integer') . ' ' .
158 "AND " . $this->getTree()->getTreeTable() . "." . $this->getTree()->getTreePk() . " = " . $this->db->quote(
159 $this->getTree()->getTreeId(),
160 'integer'
161 ) . ' ' .
162 $type_str . ' ' .
163 "ORDER BY " . $this->getTree()->getTreeTable() . ".lft";
164 return $query;
165 }
166
170 public function getRelation(array $a_node_a, array $a_node_b): int
171 {
172 if ($a_node_a === [] || $a_node_b === []) {
174 }
175 if ($a_node_a['child'] == $a_node_b['child']) {
177 }
178 if ($a_node_a['lft'] < $a_node_b['lft'] && $a_node_a['rgt'] > $a_node_b['rgt']) {
180 }
181 if ($a_node_b['lft'] < $a_node_a['lft'] && $a_node_b['rgt'] > $a_node_a['rgt']) {
183 }
184
185 // if node is also parent of node b => sibling
186 if ($a_node_a['parent'] == $a_node_b['parent']) {
188 }
190 }
191
192 public function getPathIds(int $a_endnode, int $a_startnode = 0): array
193 {
194 return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
195 }
196
200 public function insertNode(int $a_node_id, int $a_parent_id, int $a_pos): void
201 {
202 $insert_node_callable = function (ilDBInterface $db) use ($a_node_id, $a_parent_id, $a_pos): void {
203 switch ($a_pos) {
205
206 // get left value of parent
207 $query = sprintf(
208 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
209 'WHERE child = %s ' .
210 'AND ' . $this->getTree()->getTreePk() . ' = %s ',
211 $this->db->quote($a_parent_id, 'integer'),
212 $this->db->quote($this->getTree()->getTreeId(), 'integer')
213 );
214
215 $res = $this->db->query($query);
216 $r = $this->db->fetchObject($res);
217
218 if ($r->parent === null) {
220 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
221 }
222
223 $left = $r->lft;
224 $lft = $left + 1;
225 $rgt = $left + 2;
226
227 if ($this->getTree()->__isMainTree()) {
228 $query = sprintf(
229 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
230 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
231 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ',
232 $this->db->quote($left, 'integer'),
233 $this->db->quote($left, 'integer')
234 );
235 $res = $this->db->manipulate($query);
236 } else {
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 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
242 $this->db->quote($left, 'integer'),
243 $this->db->quote($left, 'integer'),
244 $this->db->quote($this->getTree()->getTreeId(), 'integer')
245 );
246 $res = $this->db->manipulate($query);
247 }
248
249 break;
250
252 // Special treatment for trees with gaps
253 if ($this->getTree()->getGap() > 0) {
254 // get lft and rgt value of parent
255 $query = sprintf(
256 'SELECT rgt,lft,parent FROM ' . $this->getTree()->getTreeTable() . ' ' .
257 'WHERE child = %s ' .
258 'AND ' . $this->getTree()->getTreePk() . ' = %s',
259 $this->db->quote($a_parent_id, 'integer'),
260 $this->db->quote($this->getTree()->getTreeId(), 'integer')
261 );
262 $res = $this->db->query($query);
263 $r = $this->db->fetchAssoc($res);
264
265 if ($r['parent'] === null) {
267 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
268 }
269 $parentRgt = (int) $r['rgt'];
270 $parentLft = (int) $r['lft'];
271
272 // Get the available space, without taking children into account yet
273 $availableSpace = $parentRgt - $parentLft;
274 if ($availableSpace < 2) {
275 // If there is not enough space between parent lft and rgt, we don't need
276 // to look any further, because we must spread the tree.
277 $lft = $parentRgt;
278 } else {
279 // If there is space between parent lft and rgt, we need to check
280 // whether there is space left between the rightmost child of the
281 // parent and parent rgt.
282 if ($this->getTree()->__isMainTree()) {
283 $query = sprintf(
284 'SELECT MAX(rgt) max_rgt FROM ' . $this->getTree()->getTreeTable() . ' ' .
285 'WHERE parent = %s ',
286 $this->db->quote($a_parent_id, 'integer')
287 );
288 $res = $this->db->query($query);
289 $r = $this->db->fetchAssoc($res);
290 } else {
291 $query = sprintf(
292 'SELECT MAX(rgt) max_rgt FROM ' . $this->getTree()->getTreeTable() . ' ' .
293 'WHERE parent = %s ' .
294 'AND ' . $this->getTree()->getTreePk() . ' = %s',
295 $this->db->quote($a_parent_id, 'integer'),
296 $this->db->quote($this->getTree()->getTreeId(), 'integer')
297 );
298 $res = $this->db->query($query);
299 $r = $this->db->fetchAssoc($res);
300 }
301
302 if (isset($r['max_rgt'])) {
303 // If the parent has children, we compute the available space
304 // between rgt of the rightmost child and parent rgt.
305 $availableSpace = $parentRgt - $r['max_rgt'];
306 $lft = $r['max_rgt'] + 1;
307 } else {
308 // If the parent has no children, we know now, that we can
309 // add the new node at parent lft + 1 without having to spread
310 // the tree.
311 $lft = $parentLft + 1;
312 }
313 }
314 $rgt = $lft + 1;
315
316 // spread tree if there is not enough space to insert the new node
317 if ($availableSpace < 2) {
318 if ($this->getTree()->__isMainTree()) {
319 $query = sprintf(
320 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
321 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
322 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ',
323 $this->db->quote($parentRgt, 'integer'),
324 $this->db->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
325 $this->db->quote($parentRgt, 'integer'),
326 $this->db->quote((2 + $this->getTree()->getGap() * 2), 'integer')
327 );
328 $res = $this->db->manipulate($query);
329 } else {
330 $query = sprintf(
331 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
332 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
333 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
334 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
335 $this->db->quote($parentRgt, 'integer'),
336 $this->db->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
337 $this->db->quote($parentRgt, 'integer'),
338 $this->db->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
339 $this->db->quote($this->getTree()->getTreeId(), 'integer')
340 );
341 $res = $this->db->manipulate($query);
342 }
343 }
344 } // Treatment for trees without gaps
345 else {
346 // get right value of parent
347 if ($this->getTree()->__isMainTree()) {
348 $query = sprintf(
349 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
350 'WHERE child = %s ',
351 $this->db->quote($a_parent_id, 'integer')
352 );
353 $res = $this->db->query($query);
354 } else {
355 $query = sprintf(
356 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
357 'WHERE child = %s ' .
358 'AND ' . $this->getTree()->getTreePk() . ' = %s ',
359 $this->db->quote($a_parent_id, 'integer'),
360 $this->db->quote($this->getTree()->getTreeId(), 'integer')
361 );
362 $res = $this->db->query($query);
363 }
364 $r = $this->db->fetchObject($res);
365
366 if ($r->parent === null) {
368 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
369 }
370
371 $right = $r->rgt;
372 $lft = $right;
373 $rgt = $right + 1;
374
375 // spread tree
376 if ($this->getTree()->__isMainTree()) {
377 $query = sprintf(
378 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
379 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
380 'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ',
381 $this->db->quote($right, 'integer'),
382 $this->db->quote($right, 'integer')
383 );
384 $res = $this->db->manipulate($query);
385 } else {
386 $query = sprintf(
387 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
388 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
389 'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ' .
390 'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
391 $this->db->quote($right, 'integer'),
392 $this->db->quote($right, 'integer'),
393 $this->db->quote($this->getTree()->getTreeId(), 'integer')
394 );
395 $res = $this->db->manipulate($query);
396 }
397 }
398
399 break;
400
401 default:
402
403 // get right value of preceeding child
404 $query = sprintf(
405 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
406 'WHERE child = %s ' .
407 'AND ' . $this->getTree()->getTreePk() . ' = %s ',
408 $this->db->quote($a_pos, 'integer'),
409 $this->db->quote($this->getTree()->getTreeId(), 'integer')
410 );
411 $res = $this->db->query($query);
412 $r = $this->db->fetchObject($res);
413
414 // crosscheck parents of sibling and new node (must be identical)
415 if ($r->parent != $a_parent_id) {
417 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
418 }
419
420 $right = $r->rgt;
421 $lft = $right + 1;
422 $rgt = $right + 2;
423
424 if ($this->getTree()->__isMainTree()) {
425 $query = sprintf(
426 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
427 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
428 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ',
429 $this->db->quote($right, 'integer'),
430 $this->db->quote($right, 'integer')
431 );
432 $res = $this->db->manipulate($query);
433 } else {
434 $query = sprintf(
435 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
436 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
437 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
438 'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
439 $this->db->quote($right, 'integer'),
440 $this->db->quote($right, 'integer'),
441 $this->db->quote($this->getTree()->getTreeId(), 'integer')
442 );
443 $res = $this->db->manipulate($query);
444 }
445
446 break;
447 }
448
449 // get depth
450 $depth = $this->getTree()->getDepth($a_parent_id) + 1;
451
452 // insert node
453 $query = sprintf(
454 'INSERT INTO ' . $this->getTree()->getTreeTable() . ' (' . $this->getTree()->getTreePk() . ',child,parent,lft,rgt,depth) ' .
455 'VALUES (%s,%s,%s,%s,%s,%s)',
456 $this->db->quote($this->getTree()->getTreeId(), 'integer'),
457 $this->db->quote($a_node_id, 'integer'),
458 $this->db->quote($a_parent_id, 'integer'),
459 $this->db->quote($lft, 'integer'),
460 $this->db->quote($rgt, 'integer'),
461 $this->db->quote($depth, 'integer')
462 );
463 $res = $this->db->manipulate($query);
464 };
465
466 if ($this->getTree()->__isMainTree()) {
467 $ilAtomQuery = $this->db->buildAtomQuery();
468 $ilAtomQuery->addTableLock('tree');
469 $ilAtomQuery->addQueryCallable($insert_node_callable);
470 $ilAtomQuery->run();
471 } else {
472 $insert_node_callable($this->db);
473 }
474 }
475
479 public function deleteTree(int $a_node_id): void
480 {
481 $delete_tree_callable = function (ilDBInterface $db) use ($a_node_id): void {
482 // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
483 // (object_reference, object_data)
484 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
485 'WHERE child = ' . $this->db->quote($a_node_id, 'integer') . ' ' .
486 'AND ' . $this->getTree()->getTreePk() . ' = ' . $this->db->quote(
487 $this->getTree()->getTreeId(),
488 'integer'
489 );
490 $res = $this->db->query($query);
491 $node = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC);
492
493 if($node === null) {
494 return; //Nothing to delete. $node does not exists
495 }
496
497 // delete subtree
498 $query = sprintf(
499 'DELETE FROM ' . $this->getTree()->getTreeTable() . ' ' .
500 'WHERE lft BETWEEN %s AND %s ' .
501 'AND rgt BETWEEN %s AND %s ' .
502 'AND ' . $this->getTree()->getTreePk() . ' = %s',
503 $this->db->quote($node['lft'], 'integer'),
504 $this->db->quote($node['rgt'], 'integer'),
505 $this->db->quote($node['lft'], 'integer'),
506 $this->db->quote($node['rgt'], 'integer'),
507 $this->db->quote($node[$this->getTree()->getTreePk()], 'integer')
508 );
509 $res = $this->db->manipulate($query);
510
511 // Performance improvement: We only close the gap, if the node
512 // is not in a trash tree, and if the resulting gap will be
513 // larger than twice the gap value
514
515 $diff = $node["rgt"] - $node["lft"] + 1;
516 if (
517 $node[$this->getTree()->getTreePk()] >= 0 &&
518 $node['rgt'] - $node['lft'] >= $this->getTree()->getGap() * 2
519 ) {
520 if ($this->getTree()->__isMainTree()) {
521 $query = sprintf(
522 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
523 'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
524 'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ',
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 );
530 $res = $this->db->manipulate($query);
531 } else {
532 $query = sprintf(
533 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
534 'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
535 'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ' .
536 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
537 $this->db->quote($node['lft'], 'integer'),
538 $this->db->quote($diff, 'integer'),
539 $this->db->quote($node['lft'], 'integer'),
540 $this->db->quote($diff, 'integer'),
541 $this->db->quote($node[$this->getTree()->getTreePk()], 'integer')
542 );
543 $res = $this->db->manipulate($query);
544 }
545 }
546 };
547
548 // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
549 if ($this->getTree()->__isMainTree()) {
550 $ilAtomQuery = $this->db->buildAtomQuery();
551 $ilAtomQuery->addTableLock('tree');
552 $ilAtomQuery->addQueryCallable($delete_tree_callable);
553 $ilAtomQuery->run();
554 } else {
555 $delete_tree_callable($this->db);
556 }
557 }
558
562 public function moveToTrash(int $a_node_id): void
563 {
564 $move_to_trash_callable = function (ilDBInterface $db) use ($a_node_id): void {
565 $node = $this->getTree()->getNodeTreeData($a_node_id);
566
567 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' ' .
568 'SET tree = ' . $this->db->quote(-1 * $node['child'], 'integer') . ' ' .
569 'WHERE ' . $this->getTree()->getTreePk() . ' = ' . $this->db->quote(
570 $this->getTree()->getTreeId(),
571 'integer'
572 ) . ' ' .
573 'AND lft BETWEEN ' . $this->db->quote(
574 $node['lft'],
575 'integer'
576 ) . ' AND ' . $this->db->quote($node['rgt'], 'integer') . ' ';
577
578 $this->db->manipulate($query);
579 };
580
581 // use ilAtomQuery to lock tables if tree is main tree
582 // otherwise just call this closure without locking
583 if ($this->getTree()->__isMainTree()) {
584 $ilAtomQuery = $this->db->buildAtomQuery();
585 $ilAtomQuery->addTableLock("tree");
586 $ilAtomQuery->addQueryCallable($move_to_trash_callable);
587 $ilAtomQuery->run();
588 } else {
589 $move_to_trash_callable($this->db);
590 }
591 }
592
599 protected function getPathIdsUsingAdjacencyMap(int $a_endnode_id, int $a_startnode_id = 0): array
600 {
601 // The adjacency map algorithm is harder to implement than the nested sets algorithm.
602 // This algorithms performs an index search for each of the path element.
603 // This algorithms performs well for large trees which are not deeply nested.
604
605 // The $takeId variable is used, to determine if a given id shall be included in the path
606 $takeId = $a_startnode_id == 0;
607
608 $depth_cache = $this->getTree()->getDepthCache();
609 $parent_cache = $this->getTree()->getParentCache();
610
611 if (
612 $this->getTree()->__isMainTree() &&
613 isset($depth_cache[$a_endnode_id]) &&
614 isset($parent_cache[$a_endnode_id])) {
615 $nodeDepth = $depth_cache[$a_endnode_id];
616 $parentId = $parent_cache[$a_endnode_id];
617 } else {
618 $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
619 $parentId = $this->getTree()->getParentId($a_endnode_id);
620 }
621
622 // Fetch the node ids. For shallow depths we can fill in the id's directly.
623 $pathIds = array();
624
625 // backward compatible check for nodes not in tree
626 if (!$nodeDepth) {
627 return array();
628 } elseif ($nodeDepth == 1) {
629 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
630 if ($takeId) {
631 $pathIds[] = $a_endnode_id;
632 }
633 } elseif ($nodeDepth == 2) {
634 $takeId = $takeId || $parentId == $a_startnode_id;
635 if ($takeId) {
636 $pathIds[] = $parentId;
637 }
638 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
639 if ($takeId) {
640 $pathIds[] = $a_endnode_id;
641 }
642 } elseif ($nodeDepth == 3) {
643 $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
644 if ($takeId) {
645 $pathIds[] = $this->getTree()->getRootId();
646 }
647 $takeId = $takeId || $parentId == $a_startnode_id;
648 if ($takeId) {
649 $pathIds[] = $parentId;
650 }
651 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
652 if ($takeId) {
653 $pathIds[] = $a_endnode_id;
654 }
655 } elseif ($nodeDepth < 32) {
656 // Adjacency Map Tree performs better than
657 // Nested Sets Tree even for very deep trees.
658 // The following code construct nested self-joins
659 // Since we already know the root-id of the tree and
660 // we also know the id and parent id of the current node,
661 // we only need to perform $nodeDepth - 3 self-joins.
662 // We can further reduce the number of self-joins by 1
663 // by taking into account, that each row in table tree
664 // contains the id of itself and of its parent.
665 $qSelect = 't1.child c0';
666 $qJoin = '';
667 for ($i = 1; $i < $nodeDepth - 2; $i++) {
668 $qSelect .= ', t' . $i . '.parent c' . $i;
669 if ($this->getTree()->__isMainTree()) {
670 $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
671 't' . $i . '.child=t' . ($i - 1) . '.parent ';
672 } else {
673 $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
674 't' . $i . '.child=t' . ($i - 1) . '.parent AND ' .
675 't' . $i . '.' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId();
676 }
677 }
678
679 if ($this->getTree()->__isMainTree()) {
680 $types = array('integer');
681 $data = array($parentId);
682 $query = 'SELECT ' . $qSelect . ' ' .
683 'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
684 'WHERE t0.child = %s ';
685 } else {
686 $types = array('integer', 'integer');
687 $data = array($this->getTree()->getTreeId(), $parentId);
688 $query = 'SELECT ' . $qSelect . ' ' .
689 'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
690 'WHERE t0.' . $this->getTree()->getTreePk() . ' = %s ' .
691 'AND t0.child = %s ';
692 }
693
694 $this->db->setLimit(1, 0);
695 $res = $this->db->queryF($query, $types, $data);
696
697 if ($res->numRows() == 0) {
698 return array();
699 }
700
701 $row = $this->db->fetchAssoc($res);
702
703 $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
704 if ($takeId) {
705 $pathIds[] = $this->getTree()->getRootId();
706 }
707 for ($i = $nodeDepth - 4; $i >= 0; $i--) {
708 $takeId = $takeId || $row['c' . $i] == $a_startnode_id;
709 if ($takeId) {
710 $pathIds[] = (int) $row['c' . $i];
711 }
712 }
713 $takeId = $takeId || $parentId == $a_startnode_id;
714 if ($takeId) {
715 $pathIds[] = $parentId;
716 }
717 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
718 if ($takeId) {
719 $pathIds[] = $a_endnode_id;
720 }
721 } else {
722 // Fall back to nested sets tree for extremely deep tree structures
723 return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
724 }
725 return $pathIds;
726 }
727
733 protected function getPathIdsUsingNestedSets(int $a_endnode_id, int $a_startnode_id = 0): array
734 {
735 // The nested sets algorithm is very easy to implement.
736 // Unfortunately it always does a full table space scan to retrieve the path
737 // regardless whether indices on lft and rgt are set or not.
738 // (At least, this is what happens on MySQL 4.1).
739 // This algorithms performs well for small trees which are deeply nested.
740
741 if ($this->getTree()->__isMainTree()) {
742 $fields = array('integer');
743 $data = array($a_endnode_id);
744 $query = "SELECT T2.child " .
745 "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
746 "WHERE T1.child = %s " .
747 "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
748 "ORDER BY T2.depth";
749 } else {
750 $fields = array('integer', 'integer', 'integer');
751 $data = array($a_endnode_id, $this->getTree()->getTreeId(), $this->getTree()->getTreeId());
752 $query = "SELECT T2.child " .
753 "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
754 "WHERE T1.child = %s " .
755 "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
756 "AND T1." . $this->getTree()->getTreePk() . " = %s " .
757 "AND T2." . $this->getTree()->getTreePk() . " = %s " .
758 "ORDER BY T2.depth";
759 }
760
761 $res = $this->db->queryF($query, $fields, $data);
762
763 $takeId = $a_startnode_id == 0;
764 $pathIds = [];
765 while ($row = $this->db->fetchAssoc($res)) {
766 if ($takeId || $row['child'] == $a_startnode_id) {
767 $takeId = true;
768 $pathIds[] = (int) $row['child'];
769 }
770 }
771 return $pathIds;
772 }
773
777 public function moveTree(int $a_source_id, int $a_target_id, int $a_position): void
778 {
779 $move_tree_callable = function (ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position): void {
780 // Receive node infos for source and target
781 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
782 'WHERE ( child = %s OR child = %s ) ' .
783 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
784 $res = $this->db->queryF($query, array('integer', 'integer', 'integer'), array(
785 $a_source_id,
786 $a_target_id,
787 $this->getTree()->getTreeId()
788 ));
789
790 // Check in tree
791 if ($res->numRows() != 2) {
792 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
793 throw new InvalidArgumentException('Error moving subtree');
794 }
795 $source_lft = $target_lft = $source_rgt = $target_rgt = $source_depth = $target_depth = $source_parent = 0;
796 while ($row = $this->db->fetchObject($res)) {
797 if ($row->child == $a_source_id) {
798 $source_lft = $row->lft;
799 $source_rgt = $row->rgt;
800 $source_depth = $row->depth;
801 $source_parent = $row->parent;
802 } else {
803 $target_lft = $row->lft;
804 $target_rgt = $row->rgt;
805 $target_depth = $row->depth;
806 }
807 }
808
809 // Check target not child of source
810 if ($target_lft >= $source_lft && $target_rgt <= $source_rgt) {
811 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Target is child of source');
812 throw new InvalidArgumentException('Error moving subtree: target is child of source');
813 }
814
815 // Now spread the tree at the target location. After this update the table should be still in a consistent state.
816 // implementation for ilTree::POS_LAST_NODE
817 $spread_diff = $source_rgt - $source_lft + 1;
818 #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
819
820 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
821 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
822 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ';
823
824 if ($this->getTree()->__isMainTree()) {
825 $res = $this->db->manipulateF($query, array('integer', 'integer', 'integer', 'integer'), [
826 $target_rgt,
827 $spread_diff,
828 $target_rgt,
829 $spread_diff
830 ]);
831 } else {
832 $query .= ('WHERE ' . $this->getTree()->getTreePk() . ' = %s ');
833 $res = $this->db->manipulateF(
834 $query,
835 array('integer', 'integer', 'integer', 'integer', 'integer'),
836 array(
837 $target_rgt,
838 $spread_diff,
839 $target_rgt,
840 $spread_diff,
841 $this->getTree()->getTreeId()
842 )
843 );
844 }
845
846 // Maybe the source node has been updated, too.
847 // Check this:
848 if ($source_lft > $target_rgt) {
849 $where_offset = $spread_diff;
850 $move_diff = $target_rgt - $source_lft - $spread_diff;
851 } else {
852 $where_offset = 0;
853 $move_diff = $target_rgt - $source_lft;
854 }
855 $depth_diff = $target_depth - $source_depth + 1;
856
857 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
858 'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
859 'rgt = rgt + %s, ' .
860 'lft = lft + %s, ' .
861 'depth = depth + %s ' .
862 'WHERE lft >= %s ' .
863 'AND rgt <= %s ';
864
865 if ($this->getTree()->__isMainTree()) {
866 $res = $this->db->manipulateF(
867 $query,
868 array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'),
869 [
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 ]
878 );
879 } else {
880 $query .= 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
881 $res = $this->db->manipulateF(
882 $query,
883 array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'),
884 array(
885 $source_parent,
886 $a_target_id,
887 $move_diff,
888 $move_diff,
889 $depth_diff,
890 $source_lft + $where_offset,
891 $source_rgt + $where_offset,
892 $this->getTree()->getTreeId()
893 )
894 );
895 }
896
897 // done: close old gap
898 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
899 'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
900 'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ';
901
902 if ($this->getTree()->__isMainTree()) {
903 $res = $this->db->manipulateF($query, array('integer', 'integer', 'integer', 'integer'), [
904 $source_lft + $where_offset,
905 $spread_diff,
906 $source_rgt + $where_offset,
907 $spread_diff
908 ]);
909 } else {
910 $query .= ('WHERE ' . $this->getTree()->getTreePk() . ' = %s ');
911
912 $res = $this->db->manipulateF(
913 $query,
914 array('integer', 'integer', 'integer', 'integer', 'integer'),
915 array(
916 $source_lft + $where_offset,
917 $spread_diff,
918 $source_rgt + $where_offset,
919 $spread_diff,
920 $this->getTree()->getTreeId()
921 )
922 );
923 }
924 };
925
926 if ($this->getTree()->__isMainTree()) {
927 $ilAtomQuery = $this->db->buildAtomQuery();
928 $ilAtomQuery->addTableLock('tree');
929 $ilAtomQuery->addQueryCallable($move_tree_callable);
930 $ilAtomQuery->run();
931 } else {
932 $move_tree_callable($this->db);
933 }
934 }
935
940 public function getSubtreeInfo(int $a_endnode_id): array
941 {
942 $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, t2.parent parent, type " .
943 "FROM " . $this->getTree()->getTreeTable() . " t1 " .
944 "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) " .
945 "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
946 "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
947 "WHERE t1.child = " . $this->db->quote($a_endnode_id, 'integer') . " " .
948 "AND t1." . $this->getTree()->getTreePk() . " = " . $this->db->quote(
949 $this->getTree()->getTreeId(),
950 'integer'
951 ) . " " .
952 "AND t2." . $this->getTree()->getTreePk() . " = " . $this->db->quote(
953 $this->getTree()->getTreeId(),
954 'integer'
955 ) . " " .
956 "ORDER BY t2.lft";
957
958 $res = $this->db->query($query);
959 $nodes = array();
960 while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
961 $nodes[(int) $row->child]['lft'] = (int) $row->lft;
962 $nodes[(int) $row->child]['rgt'] = (int) $row->rgt;
963 $nodes[(int) $row->child]['child'] = (int) $row->child;
964 $nodes[(int) $row->child]['parent'] = (int) $row->parent;
965 $nodes[(int) $row->child]['type'] = (string) $row->type;
966 }
967 return $nodes;
968 }
969
975 public function validateParentRelations(): array
976 {
977 $query = 'select ' . $this->getTree()->getTreePk() .', child from ' . $this->getTree()->getTreeTable() . ' child where not exists ' .
978 '( ' .
979 'select child from ' . $this->getTree()->getTreeTable() . ' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) ' .
980 ')' .
981 'and ' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId() . ' and child <> 1';
982 $res = $this->db->query($query);
983
984 $failures = array();
985 while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
986 $failures[] = $row[$this->getTree()->getTreePk()];
987 }
988 return $failures;
989 }
990
995 public function getChildSequenceNumber(array $a_node, string $type = ""): int
996 {
997 if (!isset($a_node)) {
998 $message = "No node_id given!";
1000 throw new InvalidArgumentException($message);
1001 }
1002
1003 if ($type) {
1004 $query = 'SELECT count(*) cnt FROM ' . $this->getTree()->getTreeTable() . ' ' .
1005 $this->getTree()->buildJoin() .
1006 'WHERE lft <= %s ' .
1007 'AND type = %s ' .
1008 'AND parent = %s ' .
1009 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ';
1010
1011 $res = $this->db->queryF($query, array('integer', 'text', 'integer', 'integer'), array(
1012 $a_node['lft'],
1013 $type,
1014 $a_node['parent'],
1015 $this->getTree()->getTreeId()
1016 ));
1017 } else {
1018 $query = 'SELECT count(*) cnt FROM ' . $this->getTree()->getTreeTable() . ' ' .
1019 $this->getTree()->buildJoin() .
1020 'WHERE lft <= %s ' .
1021 'AND parent = %s ' .
1022 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ';
1023
1024 $res = $this->db->queryF($query, array('integer', 'integer', 'integer'), array(
1025 $a_node['lft'],
1026 $a_node['parent'],
1027 $this->getTree()->getTreeId()
1028 ));
1029 }
1030 $row = $this->db->fetchAssoc($res);
1031 return (int) $row["cnt"];
1032 }
1033
1039 public function fetchSuccessorNode(int $a_node_id, string $a_type = ""): ?array
1040 {
1041 // get lft value for current node
1042 $query = 'SELECT lft FROM ' . $this->getTree()->getTreeTable() . ' ' .
1043 'WHERE ' . $this->getTree()->getTreeTable() . '.child = %s ' .
1044 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ';
1045 $res = $this->db->queryF($query, array('integer', 'integer'), array(
1046 $a_node_id,
1047 $this->getTree()->getTreeId()
1048 ));
1049 $curr_node = $this->db->fetchAssoc($res);
1050
1051 if ($a_type) {
1052 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
1053 $this->getTree()->buildJoin() .
1054 'WHERE lft > %s ' .
1055 'AND ' . $this->getTree()->getObjectDataTable() . '.type = %s ' .
1056 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ' .
1057 'ORDER BY lft ';
1058 $this->db->setLimit(1, 0);
1059 $res = $this->db->queryF($query, array('integer', 'text', 'integer'), array(
1060 $curr_node['lft'],
1061 $a_type,
1062 $this->getTree()->getTreeId()
1063 ));
1064 } else {
1065 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
1066 $this->getTree()->buildJoin() .
1067 'WHERE lft > %s ' .
1068 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ' .
1069 'ORDER BY lft ';
1070 $this->db->setLimit(1, 0);
1071 $res = $this->db->queryF($query, array('integer', 'integer'), array(
1072 $curr_node['lft'],
1073 $this->getTree()->getTreeId()
1074 ));
1075 }
1076
1077 if ($res->numRows() < 1) {
1078 return null;
1079 } else {
1080 $row = $this->db->fetchAssoc($res);
1081 return $this->getTree()->fetchNodeData($row);
1082 }
1083 }
1084
1090 public function fetchPredecessorNode(int $a_node_id, string $a_type = ""): ?array
1091 {
1092 if (!isset($a_node_id)) {
1093 $message = "No node_id given!";
1095 throw new InvalidArgumentException($message);
1096 }
1097
1098 // get lft value for current node
1099 $query = 'SELECT lft FROM ' . $this->getTree()->getTreeTable() . ' ' .
1100 'WHERE ' . $this->getTree()->getTreeTable() . '.child = %s ' .
1101 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ';
1102 $res = $this->db->queryF($query, array('integer', 'integer'), array(
1103 $a_node_id,
1104 $this->getTree()->getTreeId()
1105 ));
1106
1107 $curr_node = $this->db->fetchAssoc($res);
1108
1109 if ($a_type) {
1110 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
1111 $this->getTree()->buildJoin() .
1112 'WHERE lft < %s ' .
1113 'AND ' . $this->getTree()->getObjectDataTable(). '.type = %s ' .
1114 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ' .
1115 'ORDER BY lft DESC';
1116 $this->db->setLimit(1, 0);
1117 $res = $this->db->queryF($query, array('integer', 'text', 'integer'), array(
1118 $curr_node['lft'],
1119 $a_type,
1120 $this->getTree()->getTreeId()
1121 ));
1122 } else {
1123 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
1124 $this->getTree()->buildJoin() .
1125 'WHERE lft < %s ' .
1126 'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ' .
1127 'ORDER BY lft DESC';
1128 $this->db->setLimit(1, 0);
1129 $res = $this->db->queryF($query, array('integer', 'integer'), array(
1130 $curr_node['lft'],
1131 $this->getTree()->getTreeId()
1132 ));
1133 }
1134
1135 if ($res->numRows() < 1) {
1136 return null;
1137 } else {
1138 $row = $this->db->fetchAssoc($res);
1139 return $this->getTree()->fetchNodeData($row);
1140 }
1141 }
1142}
Thrown if invalid tree strucutes are found.
static getLogger(string $a_component_id)
Get component logger.
Base class for nested set path based trees.
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...
moveTree(int $a_source_id, int $a_target_id, int $a_position)
Move a source subtree to target.
getSubTreeIds(int $a_node_id)
Get subtree ids @retutn int[].
getTrashSubTreeQuery(array $a_node, array $a_types, bool $a_force_join_reference=true, array $a_fields=[])
Get subtree query for trashed tree items.
getSubTreeQuery(array $a_node, array $a_types=[], bool $a_force_join_reference=true, array $a_fields=[])
Get subtree.
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...
deleteTree(int $a_node_id)
Delete tree.
fetchSuccessorNode(int $a_node_id, string $a_type="")
get node data of successor node
getChildSequenceNumber(array $a_node, string $type="")
get sequence number of node in sibling sequence
__construct(ilTree $a_tree)
Constructor.
getPathIds(int $a_endnode, int $a_startnode=0)
Get path ids from a startnode to a given endnode.
moveToTrash(int $a_node_id)
Move subtree to trash.
getSubtreeInfo(int $a_endnode_id)
getRelation(array $a_node_a, array $a_node_b)
Get relation of two nodes.
insertNode(int $a_node_id, int $a_parent_id, int $a_pos)
validateParentRelations()
Validate the parent relations of the tree implementation For nested set, validate the lft,...
fetchPredecessorNode(int $a_node_id, string $a_type="")
get node data of predecessor node
Tree class data representation in hierachical trees using the Nested Set Model with Gaps by Joe Celco...
const RELATION_EQUALS
const POS_LAST_NODE
const POS_FIRST_NODE
const RELATION_PARENT
const RELATION_NONE
const RELATION_SIBLING
const RELATION_CHILD
Interface ilDBInterface.
Interface for tree implementations Currrently nested set or materialized path.
$res
Definition: ltiservices.php:69
global $DIC
Definition: shib_login.php:26
$message
Definition: xapiexit.php:31