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