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