ILIAS  release_5-4 Revision v5.4.26-12-gabc799a52e6
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
77 public function getSubTreeQuery($a_node, $a_types = '', $a_force_join_reference = true, $a_fields = array())
78 {
79 global $DIC;
80
81 $ilDB = $DIC['ilDB'];
82
83 $type_str = '';
84 if (is_array($a_types)) {
85 if ($a_types) {
86 $type_str = "AND " . $ilDB->in($this->getTree()->getObjectDataTable() . ".type", $a_types, false, "text");
87 }
88 } elseif (strlen($a_types)) {
89 $type_str = "AND " . $this->getTree()->getObjectDataTable() . ".type = " . $ilDB->quote($a_types, "text");
90 }
91
92 $join = '';
93 if ($type_str or $a_force_join_reference) {
94 $join = $this->getTree()->buildJoin();
95 }
96
97 $fields = '* ';
98 if (count($a_fields)) {
99 $fields = implode(',', $a_fields);
100 }
101
102 $query = 'SELECT ' .
103 $fields . ' ' .
104 "FROM " . $this->getTree()->getTreeTable() . " " .
105 $join . ' ' .
106 "WHERE " . $this->getTree()->getTreeTable() . '.lft ' .
107 'BETWEEN ' . $ilDB->quote($a_node['lft'], 'integer') . ' ' .
108 'AND ' . $ilDB->quote($a_node['rgt'], 'integer') . ' ' .
109 "AND " . $this->getTree()->getTreeTable() . "." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
110 $type_str . ' ' .
111 "ORDER BY " . $this->getTree()->getTreeTable() . ".lft";
112
113 #ilLoggerFactory::getLogger('tree')->debug('-----------------: '. $query);
114
115 return $query;
116 }
117
118
125 public function getRelation($a_node_a, $a_node_b)
126 {
127 if ($a_node_a['child'] == $a_node_b['child']) {
128 ilLoggerFactory::getLogger('tree')->debug('EQUALS');
129 return ilTree::RELATION_EQUALS;
130 }
131 if ($a_node_a['lft'] < $a_node_b['lft'] and $a_node_a['rgt'] > $a_node_b['rgt']) {
132 ilLoggerFactory::getLogger('tree')->debug('PARENT');
133 return ilTree::RELATION_PARENT;
134 }
135 if ($a_node_b['lft'] < $a_node_a['lft'] and $a_node_b['rgt'] > $a_node_a['rgt']) {
136 ilLoggerFactory::getLogger('tree')->debug('CHILD');
137 return ilTree::RELATION_CHILD;
138 }
139
140 // if node is also parent of node b => sibling
141 if ($a_node_a['parent'] == $a_node_b['parent']) {
142 ilLoggerFactory::getLogger('tree')->debug('SIBLING');
143 return ilTree::RELATION_SIBLING;
144 }
145 ilLoggerFactory::getLogger('tree')->debug('NONE');
146 return ilTree::RELATION_NONE;
147 }
148
155 public function getPathIds($a_endnode, $a_startnode = 0)
156 {
157 return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
158 }
159
168 public function insertNode($a_node_id, $a_parent_id, $a_pos)
169 {
170 global $DIC;
171
172 $ilDB = $DIC['ilDB'];
173
174 $insert_node_callable = function (ilDBInterface $ilDB) use ($a_node_id, $a_parent_id, $a_pos) {
175 switch ($a_pos) {
176 case ilTree::POS_FIRST_NODE:
177
178 // get left value of parent
179 $query = sprintf(
180 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
181 'WHERE child = %s ' .
182 'AND ' . $this->getTree()->getTreePk() . ' = %s ',
183 $ilDB->quote($a_parent_id, 'integer'),
184 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
185 );
186
187 $res = $ilDB->query($query);
188 $r = $ilDB->fetchObject($res);
189
190 if ($r->parent === null) {
191 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
192 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
193 }
194
195 $left = $r->lft;
196 $lft = $left + 1;
197 $rgt = $left + 2;
198
199 // spread tree
200 $query = sprintf(
201 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
202 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
203 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
204 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
205 $ilDB->quote($left, 'integer'),
206 $ilDB->quote($left, 'integer'),
207 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
208 );
209 $res = $ilDB->manipulate($query);
210 break;
211
212 case IL_LAST_NODE:
213 // Special treatment for trees with gaps
214 if ($this->getTree()->getGap() > 0) {
215 // get lft and rgt value of parent
216 $query = sprintf(
217 'SELECT rgt,lft,parent 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 $res = $ilDB->query($query);
224 $r = $ilDB->fetchAssoc($res);
225
226 if ($r['parent'] === null) {
227 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
228 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
229 }
230 $parentRgt = $r['rgt'];
231 $parentLft = $r['lft'];
232
233 // Get the available space, without taking children into account yet
234 $availableSpace = $parentRgt - $parentLft;
235 if ($availableSpace < 2) {
236 // If there is not enough space between parent lft and rgt, we don't need
237 // to look any further, because we must spread the tree.
238 $lft = $parentRgt;
239 } else {
240 // If there is space between parent lft and rgt, we need to check
241 // whether there is space left between the rightmost child of the
242 // parent and parent rgt.
243 $query = sprintf(
244 'SELECT MAX(rgt) max_rgt FROM ' . $this->getTree()->getTreeTable() . ' ' .
245 'WHERE parent = %s ' .
246 'AND ' . $this->getTree()->getTreePk() . ' = %s',
247 $ilDB->quote($a_parent_id, 'integer'),
248 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
249 );
250 $res = $ilDB->query($query);
251 $r = $ilDB->fetchAssoc($res);
252
253 if (isset($r['max_rgt'])) {
254 // If the parent has children, we compute the available space
255 // between rgt of the rightmost child and parent rgt.
256 $availableSpace = $parentRgt - $r['max_rgt'];
257 $lft = $r['max_rgt'] + 1;
258 } else {
259 // If the parent has no children, we know now, that we can
260 // add the new node at parent lft + 1 without having to spread
261 // the tree.
262 $lft = $parentLft + 1;
263 }
264 }
265 $rgt = $lft + 1;
266
267
268 // spread tree if there is not enough space to insert the new node
269 if ($availableSpace < 2) {
270 //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
271 $query = sprintf(
272 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
273 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
274 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
275 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
276 $ilDB->quote($parentRgt, 'integer'),
277 $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
278 $ilDB->quote($parentRgt, 'integer'),
279 $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
280 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
281 );
282 $res = $ilDB->manipulate($query);
283 }
284 }
285 // Treatment for trees without gaps
286 else {
287
288 // get right value of parent
289 $query = sprintf(
290 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
291 'WHERE child = %s ' .
292 'AND ' . $this->getTree()->getTreePk() . ' = %s ',
293 $ilDB->quote($a_parent_id, 'integer'),
294 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
295 );
296 $res = $ilDB->query($query);
297 $r = $ilDB->fetchObject($res);
298
299 if ($r->parent === null) {
300 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
301 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
302 }
303
304 $right = $r->rgt;
305 $lft = $right;
306 $rgt = $right + 1;
307
308 // spread tree
309 $query = sprintf(
310 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
311 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
312 'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ' .
313 'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
314 $ilDB->quote($right, 'integer'),
315 $ilDB->quote($right, 'integer'),
316 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
317 );
318 $res = $ilDB->manipulate($query);
319 }
320
321 break;
322
323 default:
324
325 // get right value of preceeding child
326 $query = sprintf(
327 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
328 'WHERE child = %s ' .
329 'AND ' . $this->getTree()->getTreePk() . ' = %s ',
330 $ilDB->quote($a_pos, 'integer'),
331 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
332 );
333 $res = $ilDB->query($query);
334 $r = $ilDB->fetchObject($res);
335
336 // crosscheck parents of sibling and new node (must be identical)
337 if ($r->parent != $a_parent_id) {
338 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
339 throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
340 }
341
342 $right = $r->rgt;
343 $lft = $right + 1;
344 $rgt = $right + 2;
345
346 // update lft/rgt values
347 $query = sprintf(
348 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
349 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
350 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
351 'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
352 $ilDB->quote($right, 'integer'),
353 $ilDB->quote($right, 'integer'),
354 $ilDB->quote($this->getTree()->getTreeId(), 'integer')
355 );
356 $res = $ilDB->manipulate($query);
357 break;
358
359 }
360
361 // get depth
362 $depth = $this->getTree()->getDepth($a_parent_id) + 1;
363
364 // insert node
365 $query = sprintf(
366 'INSERT INTO ' . $this->getTree()->getTreeTable() . ' (' . $this->getTree()->getTreePk() . ',child,parent,lft,rgt,depth) ' .
367 'VALUES (%s,%s,%s,%s,%s,%s)',
368 $ilDB->quote($this->getTree()->getTreeId(), 'integer'),
369 $ilDB->quote($a_node_id, 'integer'),
370 $ilDB->quote($a_parent_id, 'integer'),
371 $ilDB->quote($lft, 'integer'),
372 $ilDB->quote($rgt, 'integer'),
373 $ilDB->quote($depth, 'integer')
374 );
375 $res = $ilDB->manipulate($query);
376 };
377
378 if ($this->getTree()->__isMainTree()) {
379 $ilAtomQuery = $ilDB->buildAtomQuery();
380 $ilAtomQuery->addTableLock('tree');
381 $ilAtomQuery->addQueryCallable($insert_node_callable);
382 $ilAtomQuery->run();
383 } else {
384 $insert_node_callable($ilDB);
385 }
386 }
387
388
394 public function deleteTree($a_node_id)
395 {
396 global $DIC;
397
398 $ilDB = $DIC['ilDB'];
399
400 $delete_tree_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
401
402 // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
403 // (object_reference, object_data)
404 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
405 'WHERE child = ' . $ilDB->quote($a_node_id, 'integer') . ' ' .
406 'AND ' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer');
407 $res = $ilDB->query($query);
408 $a_node = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC);
409
410 // delete subtree
411 $query = sprintf(
412 'DELETE FROM ' . $this->getTree()->getTreeTable() . ' ' .
413 'WHERE lft BETWEEN %s AND %s ' .
414 'AND rgt BETWEEN %s AND %s ' .
415 'AND ' . $this->getTree()->getTreePk() . ' = %s',
416 $ilDB->quote($a_node['lft'], 'integer'),
417 $ilDB->quote($a_node['rgt'], 'integer'),
418 $ilDB->quote($a_node['lft'], 'integer'),
419 $ilDB->quote($a_node['rgt'], 'integer'),
420 $ilDB->quote($a_node[$this->getTree()->getTreePk()], 'integer')
421 );
422 $res = $ilDB->manipulate($query);
423
424 // Performance improvement: We only close the gap, if the node
425 // is not in a trash tree, and if the resulting gap will be
426 // larger than twice the gap value
427
428 $diff = $a_node["rgt"] - $a_node["lft"] + 1;
429 if (
430 $a_node[$this->getTree()->getTreePk()] >= 0 &&
431 $a_node['rgt'] - $a_node['lft'] >= $this->getTree()->getGap() * 2
432 ) {
433 // close gaps
434 $query = sprintf(
435 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
436 'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
437 'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ' .
438 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
439 $ilDB->quote($a_node['lft'], 'integer'),
440 $ilDB->quote($diff, 'integer'),
441 $ilDB->quote($a_node['lft'], 'integer'),
442 $ilDB->quote($diff, 'integer'),
443 $ilDB->quote($a_node[$this->getTree()->getTreePk()], 'integer')
444 );
445
446 $res = $ilDB->manipulate($query);
447 }
448 };
449
450 // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
451 if ($this->getTree()->__isMainTree()) {
452 $ilAtomQuery = $ilDB->buildAtomQuery();
453 $ilAtomQuery->addTableLock('tree');
454 $ilAtomQuery->addQueryCallable($delete_tree_callable);
455 $ilAtomQuery->run();
456 } else {
457 $delete_tree_callable($ilDB);
458 }
459
460 return true;
461 }
462
471 public function moveToTrash($a_node_id)
472 {
473 global $DIC;
474
475 $ilDB = $DIC['ilDB'];
476
477 $move_to_trash_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
478 $node = $this->getTree()->getNodeTreeData($a_node_id);
479
480 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' ' .
481 'SET tree = ' . $ilDB->quote(-1 * $node['child'], 'integer') . ' ' .
482 'WHERE ' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
483 'AND lft BETWEEN ' . $ilDB->quote($node['lft'], 'integer') . ' AND ' . $ilDB->quote($node['rgt'], 'integer') . ' ';
484
485 $ilDB->manipulate($query);
486 };
487
488 // use ilAtomQuery to lock tables if tree is main tree
489 // otherwise just call this closure without locking
490 if ($this->getTree()->__isMainTree()) {
491 $ilAtomQuery = $ilDB->buildAtomQuery();
492 $ilAtomQuery->addTableLock("tree");
493
494 $ilAtomQuery->addQueryCallable($move_to_trash_callable);
495
496 $ilAtomQuery->run();
497 } else {
498 $move_to_trash_callable($ilDB);
499 }
500
501 return true;
502 }
503
504
513 protected function getPathIdsUsingAdjacencyMap($a_endnode_id, $a_startnode_id = 0)
514 {
515 global $DIC;
516
517 $ilDB = $DIC['ilDB'];
518
519 // The adjacency map algorithm is harder to implement than the nested sets algorithm.
520 // This algorithms performs an index search for each of the path element.
521 // This algorithms performs well for large trees which are not deeply nested.
522
523 // The $takeId variable is used, to determine if a given id shall be included in the path
524 $takeId = $a_startnode_id == 0;
525
526 $depth_cache = $this->getTree()->getDepthCache();
527 $parent_cache = $this->getTree()->getParentCache();
528
529 if (
530 $this->getTree()->__isMainTree() &&
531 isset($depth_cache[$a_endnode_id]) &&
532 isset($parent_cache[$a_endnode_id])) {
533 $nodeDepth = $depth_cache[$a_endnode_id];
534 $parentId = $parent_cache[$a_endnode_id];
535 } else {
536 $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
537 $parentId = $this->getTree()->getParentId($a_endnode_id);
538 }
539
540 // Fetch the node ids. For shallow depths we can fill in the id's directly.
541 $pathIds = array();
542
543 // backward compatible check for nodes not in tree
544 if (!$nodeDepth) {
545 return array();
546 } elseif ($nodeDepth == 1) {
547 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
548 if ($takeId) {
549 $pathIds[] = $a_endnode_id;
550 }
551 } elseif ($nodeDepth == 2) {
552 $takeId = $takeId || $parentId == $a_startnode_id;
553 if ($takeId) {
554 $pathIds[] = $parentId;
555 }
556 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
557 if ($takeId) {
558 $pathIds[] = $a_endnode_id;
559 }
560 } elseif ($nodeDepth == 3) {
561 $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
562 if ($takeId) {
563 $pathIds[] = $this->getTree()->getRootId();
564 }
565 $takeId = $takeId || $parentId == $a_startnode_id;
566 if ($takeId) {
567 $pathIds[] = $parentId;
568 }
569 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
570 if ($takeId) {
571 $pathIds[] = $a_endnode_id;
572 }
573 } elseif ($nodeDepth < 32) {
574 // Adjacency Map Tree performs better than
575 // Nested Sets Tree even for very deep trees.
576 // The following code construct nested self-joins
577 // Since we already know the root-id of the tree and
578 // we also know the id and parent id of the current node,
579 // we only need to perform $nodeDepth - 3 self-joins.
580 // We can further reduce the number of self-joins by 1
581 // by taking into account, that each row in table tree
582 // contains the id of itself and of its parent.
583 $qSelect = 't1.child c0';
584 $qJoin = '';
585 for ($i = 1; $i < $nodeDepth - 2; $i++) {
586 $qSelect .= ', t' . $i . '.parent c' . $i;
587 $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
588 't' . $i . '.child=t' . ($i - 1) . '.parent AND ' .
589 't' . $i . '.' . $this->getTree()->getTreePk() . ' = ' . (int) $this->getTree()->getTreeId();
590 }
591
592 $types = array('integer','integer');
593 $data = array($this->getTree()->getTreeId(),$parentId);
594 $query = 'SELECT ' . $qSelect . ' ' .
595 'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
596 'WHERE t0.' . $this->getTree()->getTreePk() . ' = %s ' .
597 'AND t0.child = %s ';
598
599 $ilDB->setLimit(1);
600 $res = $ilDB->queryF($query, $types, $data);
601
602 if ($res->numRows() == 0) {
603 return array();
604 }
605
606 $row = $ilDB->fetchAssoc($res);
607
608 $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
609 if ($takeId) {
610 $pathIds[] = $this->getTree()->getRootId();
611 }
612 for ($i = $nodeDepth - 4; $i >= 0; $i--) {
613 $takeId = $takeId || $row['c' . $i] == $a_startnode_id;
614 if ($takeId) {
615 $pathIds[] = $row['c' . $i];
616 }
617 }
618 $takeId = $takeId || $parentId == $a_startnode_id;
619 if ($takeId) {
620 $pathIds[] = $parentId;
621 }
622 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
623 if ($takeId) {
624 $pathIds[] = $a_endnode_id;
625 }
626 } else {
627 // Fall back to nested sets tree for extremely deep tree structures
628 return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
629 }
630 return $pathIds;
631 }
632
641 public function getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id = 0)
642 {
643 global $DIC;
644
645 $ilDB = $DIC['ilDB'];
646
647 // The nested sets algorithm is very easy to implement.
648 // Unfortunately it always does a full table space scan to retrieve the path
649 // regardless whether indices on lft and rgt are set or not.
650 // (At least, this is what happens on MySQL 4.1).
651 // This algorithms performs well for small trees which are deeply nested.
652
653 $fields = array('integer','integer','integer');
654 $data = array($a_endnode_id,$this->getTree()->getTreeId(),$this->getTree()->getTreeId());
655
656 $query = "SELECT T2.child " .
657 "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
658 "WHERE T1.child = %s " .
659 "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
660 "AND T1." . $this->getTree()->getTreePk() . " = %s " .
661 "AND T2." . $this->getTree()->getTreePk() . " = %s " .
662 "ORDER BY T2.depth";
663
664 $res = $ilDB->queryF($query, $fields, $data);
665
666 $takeId = $a_startnode_id == 0;
667 while ($row = $ilDB->fetchAssoc($res)) {
668 if ($takeId || $row['child'] == $a_startnode_id) {
669 $takeId = true;
670 $pathIds[] = $row['child'];
671 }
672 }
673 return $pathIds ? $pathIds : array();
674 }
675
676
685 public function moveTree($a_source_id, $a_target_id, $a_position)
686 {
687 global $DIC;
688
689 $ilDB = $DIC['ilDB'];
690
691 $move_tree_callable = function (ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position) {
692 // Receive node infos for source and target
693 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
694 'WHERE ( child = %s OR child = %s ) ' .
695 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
696 $res = $ilDB->queryF($query, array('integer', 'integer', 'integer'), array(
697 $a_source_id,
698 $a_target_id,
699 $this->getTree()->getTreeId()));
700
701 // Check in tree
702 if ($res->numRows() != 2) {
703 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
704 throw new InvalidArgumentException('Error moving subtree');
705 }
706 while ($row = $ilDB->fetchObject($res)) {
707 if ($row->child == $a_source_id) {
708 $source_lft = $row->lft;
709 $source_rgt = $row->rgt;
710 $source_depth = $row->depth;
711 $source_parent = $row->parent;
712 } else {
713 $target_lft = $row->lft;
714 $target_rgt = $row->rgt;
715 $target_depth = $row->depth;
716 }
717 }
718
719 // Check target not child of source
720 if ($target_lft >= $source_lft and $target_rgt <= $source_rgt) {
721 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Target is child of source');
722 throw new InvalidArgumentException('Error moving subtree: target is child of source');
723 }
724
725 // Now spread the tree at the target location. After this update the table should be still in a consistent state.
726 // implementation for IL_LAST_NODE
727 $spread_diff = $source_rgt - $source_lft + 1;
728 #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
729
730 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
731 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
732 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
733 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
734 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
735 $target_rgt,
736 $spread_diff,
737 $target_rgt,
738 $spread_diff,
739 $this->getTree()->getTreeId()));
740
741 // Maybe the source node has been updated, too.
742 // Check this:
743 if ($source_lft > $target_rgt) {
744 $where_offset = $spread_diff;
745 $move_diff = $target_rgt - $source_lft - $spread_diff;
746 } else {
747 $where_offset = 0;
748 $move_diff = $target_rgt - $source_lft;
749 }
750 $depth_diff = $target_depth - $source_depth + 1;
751
752
753 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
754 'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
755 'rgt = rgt + %s, ' .
756 'lft = lft + %s, ' .
757 'depth = depth + %s ' .
758 'WHERE lft >= %s ' .
759 'AND rgt <= %s ' .
760 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
761 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), array(
762 $source_parent,
763 $a_target_id,
764 $move_diff,
765 $move_diff,
766 $depth_diff,
767 $source_lft + $where_offset,
768 $source_rgt + $where_offset,
769 $this->getTree()->getTreeId()));
770
771 // done: close old gap
772 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
773 'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
774 'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' .
775 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
776
777 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
778 $source_lft + $where_offset,
779 $spread_diff,
780 $source_rgt + $where_offset,
781 $spread_diff,
782 $this->getTree()->getTreeId()));
783 };
784
785
786 if ($this->getTree()->__isMainTree()) {
787 $ilAtomQuery = $ilDB->buildAtomQuery();
788 $ilAtomQuery->addTableLock('tree');
789 $ilAtomQuery->addQueryCallable($move_tree_callable);
790 $ilAtomQuery->run();
791 } else {
792 $move_tree_callable($ilDB);
793 }
794 }
795
802 public function getSubtreeInfo($a_endnode_id)
803 {
804 global $DIC;
805
806 $ilDB = $DIC['ilDB'];
807
808 $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type " .
809 "FROM " . $this->getTree()->getTreeTable() . " t1 " .
810 "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) " .
811 "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
812 "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
813 "WHERE t1.child = " . $ilDB->quote($a_endnode_id, 'integer') . " " .
814 "AND t1." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
815 "AND t2." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
816 "ORDER BY t2.lft";
817
818 ilLoggerFactory::getLogger('tree')->debug($query);
819
820
821 $res = $ilDB->query($query);
822 $nodes = array();
823 while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
824 $nodes[$row->child]['lft'] = $row->lft;
825 $nodes[$row->child]['rgt'] = $row->rgt;
826 $nodes[$row->child]['child'] = $row->child;
827 $nodes[$row->child]['type'] = $row->type;
828 }
829 return (array) $nodes;
830 }
831
835 public function validateParentRelations()
836 {
837 global $DIC;
838
839 $ilDB = $DIC['ilDB'];
840
841 $query = 'select child from ' . $this->getTree()->getTreeTable() . ' child where not exists ' .
842 '( ' .
843 'select child from ' . $this->getTree()->getTreeTable() . ' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) ' .
844 ')' .
845 'and ' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId() . ' and child <> 1';
846 $res = $ilDB->query($query);
847
848 ilLoggerFactory::getLogger('tree')->debug($query);
849
850 $failures = array();
851 while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
852 $failures[] = $row[$this->getTree()->getTreePk()];
853 }
854 return $failures;
855 }
856}
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:471
ilNestedSetTree\getRelation
getRelation($a_node_a, $a_node_b)
Get relation.
Definition: class.ilNestedSetTree.php:125
ilNestedSetTree\insertNode
insertNode($a_node_id, $a_parent_id, $a_pos)
Insert tree node.
Definition: class.ilNestedSetTree.php:168
ilNestedSetTree\getPathIds
getPathIds($a_endnode, $a_startnode=0)
Get path ids.
Definition: class.ilNestedSetTree.php:155
ilNestedSetTree\getTree
getTree()
Get tree object.
Definition: class.ilNestedSetTree.php:33
ilNestedSetTree\deleteTree
deleteTree($a_node_id)
Delete a subtree.
Definition: class.ilNestedSetTree.php:394
ilNestedSetTree\getSubTreeQuery
getSubTreeQuery($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
Get subtree.
Definition: class.ilNestedSetTree.php:77
ilNestedSetTree\moveTree
moveTree($a_source_id, $a_target_id, $a_position)
Move source subtree to target.
Definition: class.ilNestedSetTree.php:685
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:513
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:802
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:641
ilNestedSetTree\validateParentRelations
validateParentRelations()
Validate the parent relations of the tree implementation For nested set, validate the lft,...
Definition: class.ilNestedSetTree.php:835
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:33
ilTree\POS_FIRST_NODE
const POS_FIRST_NODE
Definition: class.ilTree.php:27
ilTree\RELATION_PARENT
const RELATION_PARENT
Definition: class.ilTree.php:31
ilTree\RELATION_NONE
const RELATION_NONE
Definition: class.ilTree.php:34
ilTree\RELATION_SIBLING
const RELATION_SIBLING
Definition: class.ilTree.php:32
ilTree\RELATION_CHILD
const RELATION_CHILD
Definition: class.ilTree.php:30
$i
$i
Definition: disco.tpl.php:19
$r
$r
Definition: example_031.php:79
ilDBInterface
Interface ilDBInterface.
Definition: interface.ilDBInterface.php:10
ilTreeImplementation
Interface for tree implementations Currrently nested set or materialize path.
Definition: interface.ilTreeImplementation.php:15
$row
$row
Definition: migrateto20.php:360
$query
$query
Definition: proxy_ylocal.php:13
$DIC
global $DIC
Definition: saml.php:7
$res
foreach($_POST as $key=> $value) $res
Definition: save_question_post_data.php:15
$ilDB
global $ilDB
Definition: storeScorm2004.php:19
$data
$data
Definition: bench.php:6