ILIAS  release_5-2 Revision v5.2.25-18-g3f80b828510
Public Member Functions | Protected Member Functions | Private Attributes
ilNestedSetTree Class Reference
Services/Tree

Base class for nested set path based trees. More...

+ Inheritance diagram for ilNestedSetTree:
+ Collaboration diagram for ilNestedSetTree:

Public Member Functions

 __construct (ilTree $a_tree)
 Constructor. More...
 
 getTree ()
 Get tree object. More...
 
 getSubTreeIds ($a_node_id)
 Get subtree ids. More...
 
 getSubTreeQuery ($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
 Get subtree. More...
 
 getRelation ($a_node_a, $a_node_b)
 Get relation. More...
 
 getPathIds ($a_endnode, $a_startnode=0)
 Get path ids. More...
 
 insertNode ($a_node_id, $a_parent_id, $a_pos)
 Insert tree node. More...
 
 deleteTree ($a_node_id)
 Delete a subtree. More...
 
 moveToTrash ($a_node_id)
 Move to trash. More...
 
 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 startnode @access public More...
 
 moveTree ($a_source_id, $a_target_id, $a_position)
 Move source subtree to target. More...
 
 getSubtreeInfo ($a_endnode_id)
 Get rbac subtree info @global type $ilDB. More...
 
 validateParentRelations ()
 Validate the parent relations of the tree implementation For nested set, validate the lft, rgt against child <-> parent For materialized path validate path against child <-> parent. More...
 
 getSubTreeIds ($a_node_id)
 Get subtree ids for a specific node. More...
 
 getSubTreeQuery ($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
 Get subtree. More...
 
 getRelation ($a_node_a, $a_node_b)
 Get relation of two nodes. More...
 
 getPathIds ($a_endnode, $a_startnode=0)
 Get path ids from a startnode to a given endnode. More...
 
 insertNode ($a_node_id, $a_parent_id, $a_pos)
 
 deleteTree ($a_node_id)
 Delete tree. More...
 
 moveToTrash ($a_node_id)
 Move subtree to trash. More...
 
 moveTree ($a_source_id, $a_target_id, $a_position)
 Move a source subtree to target. More...
 
 getSubtreeInfo ($a_endnode_id)
 Get subtree info lft, rgt, path, child, type. More...
 
 validateParentRelations ()
 Validate the parent relations of the tree implementation For nested set, validate the lft, rgt against child <-> parent For materialized path validate path against child <-> parent. More...
 

Protected Member Functions

 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 startnode @access public More...
 

Private Attributes

 $tree = NULL
 

Detailed Description

Base class for nested set path based trees.

Author
Stefan Meyer meyer.nosp@m.@lei.nosp@m.fos.c.nosp@m.om
Version
$Id$

Definition at line 16 of file class.ilNestedSetTree.php.

Constructor & Destructor Documentation

◆ __construct()

ilNestedSetTree::__construct ( ilTree  $a_tree)

Constructor.

Parameters
ilTree$a_tree

Definition at line 24 of file class.ilNestedSetTree.php.

25 {
26 $this->tree = $a_tree;
27 }

Member Function Documentation

◆ deleteTree()

ilNestedSetTree::deleteTree (   $a_node_id)

Delete a subtree.

Parameters
int$a_node_id
Returns
bool

Implements ilTreeImplementation.

Definition at line 396 of file class.ilNestedSetTree.php.

397 {
398 global $ilDB;
399
400 $delete_tree_callable = function(ilDBInterface $ilDB) use($a_node_id)
401 {
402
403 // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
404 // (object_reference, object_data)
405 $query = 'SELECT * FROM '.$this->getTree()->getTreeTable().' '.
406 'WHERE child = '.$ilDB->quote($a_node_id,'integer').' '.
407 'AND '.$this->getTree()->getTreePk().' = '.$ilDB->quote($this->getTree()->getTreeId(),'integer');
408 $res = $ilDB->query($query);
409 $a_node = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC);
410
411 // delete subtree
412 $query = sprintf('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 $res = $ilDB->manipulate($query);
422
423 // Performance improvement: We only close the gap, if the node
424 // is not in a trash tree, and if the resulting gap will be
425 // larger than twice the gap value
426
427 $diff = $a_node["rgt"] - $a_node["lft"] + 1;
428 if(
429 $a_node[$this->getTree()->getTreePk()] >= 0 &&
430 $a_node['rgt'] - $a_node['lft'] >= $this->getTree()->getGap() * 2
431 )
432 {
433 // close gaps
434 $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
435 'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, '.
436 'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END '.
437 'WHERE '.$this->getTree()->getTreePk().' = %s ',
438 $ilDB->quote($a_node['lft'],'integer'),
439 $ilDB->quote($diff,'integer'),
440 $ilDB->quote($a_node['lft'],'integer'),
441 $ilDB->quote($diff,'integer'),
442 $ilDB->quote($a_node[$this->getTree()->getTreePk()],'integer'));
443
444 $res = $ilDB->manipulate($query);
445 }
446
447 };
448
449 // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
450 if($this->getTree()->__isMainTree())
451 {
452 $ilAtomQuery = $ilDB->buildAtomQuery();
453 $ilAtomQuery->addTableLock('tree');
454 $ilAtomQuery->addQueryCallable($delete_tree_callable);
455 $ilAtomQuery->run();
456 }
457 else{
458 $delete_tree_callable($ilDB);
459 }
460
461 return true;
462 }
sprintf
sprintf('%.4f', $callTime)
Definition: 01pharSimple.php:87
ilNestedSetTree\getTree
getTree()
Get tree object.
Definition: class.ilNestedSetTree.php:33
ilDBInterface
Interface ilDBInterface.
Definition: interface.ilDBInterface.php:9
$ilDB
global $ilDB
Definition: storeScorm2004.php:19

References $ilDB, $query, $res, ilDBConstants\FETCHMODE_ASSOC, getTree(), and sprintf.

+ Here is the call graph for this function:

◆ getPathIds()

ilNestedSetTree::getPathIds (   $a_endnode,
  $a_startnode = 0 
)

Get path ids.

Parameters
int$a_endnode
int$a_startnode
Returns
int[]

Implements ilTreeImplementation.

Definition at line 162 of file class.ilNestedSetTree.php.

163 {
164 return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
165 }
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:516

References getPathIdsUsingAdjacencyMap().

+ Here is the call graph for this function:

◆ getPathIdsUsingAdjacencyMap()

ilNestedSetTree::getPathIdsUsingAdjacencyMap (   $a_endnode_id,
  $a_startnode_id = 0 
)
protected

get path from a given startnode to a given endnode if startnode is not given the rootnode is startnode @access public

Parameters
integernode_id of endnode
integernode_id of startnode (optional)
Returns
array all path ids from startnode to endnode

Definition at line 516 of file class.ilNestedSetTree.php.

517 {
518 global $ilDB;
519
520 // The adjacency map algorithm is harder to implement than the nested sets algorithm.
521 // This algorithms performs an index search for each of the path element.
522 // This algorithms performs well for large trees which are not deeply nested.
523
524 // The $takeId variable is used, to determine if a given id shall be included in the path
525 $takeId = $a_startnode_id == 0;
526
527 $depth_cache = $this->getTree()->getDepthCache();
528 $parent_cache = $this->getTree()->getParentCache();
529
530 if(
531 $this->getTree()->__isMainTree() &&
532 isset($depth_cache[$a_endnode_id]) &&
533 isset($parent_cache[$a_endnode_id]))
534 {
535 $nodeDepth = $depth_cache[$a_endnode_id];
536 $parentId = $parent_cache[$a_endnode_id];
537 }
538 else
539 {
540 $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
541 $parentId = $this->getTree()->getParentId($a_endnode_id);
542 }
543
544 // Fetch the node ids. For shallow depths we can fill in the id's directly.
545 $pathIds = array();
546
547 // backward compatible check for nodes not in tree
548 if(!$nodeDepth )
549 {
550 return array();
551 }
552 else if ($nodeDepth == 1)
553 {
554 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
555 if ($takeId) $pathIds[] = $a_endnode_id;
556 }
557 else if ($nodeDepth == 2)
558 {
559 $takeId = $takeId || $parentId == $a_startnode_id;
560 if ($takeId) $pathIds[] = $parentId;
561 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
562 if ($takeId) $pathIds[] = $a_endnode_id;
563 }
564 else if ($nodeDepth == 3)
565 {
566 $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
567 if ($takeId) $pathIds[] = $this->getTree()->getRootId();
568 $takeId = $takeId || $parentId == $a_startnode_id;
569 if ($takeId) $pathIds[] = $parentId;
570 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
571 if ($takeId) $pathIds[] = $a_endnode_id;
572 }
573 else if ($nodeDepth < 32)
574 {
575 // Adjacency Map Tree performs better than
576 // Nested Sets Tree even for very deep trees.
577 // The following code construct nested self-joins
578 // Since we already know the root-id of the tree and
579 // we also know the id and parent id of the current node,
580 // we only need to perform $nodeDepth - 3 self-joins.
581 // We can further reduce the number of self-joins by 1
582 // by taking into account, that each row in table tree
583 // contains the id of itself and of its parent.
584 $qSelect = 't1.child c0';
585 $qJoin = '';
586 for ($i = 1; $i < $nodeDepth - 2; $i++)
587 {
588 $qSelect .= ', t'.$i.'.parent c'.$i;
589 $qJoin .= ' JOIN '.$this->getTree()->getTreeTable().' t'.$i.' ON '.
590 't'.$i.'.child=t'.($i - 1).'.parent AND '.
591 't'.$i.'.'.$this->getTree()->getTreePk().' = '.(int) $this->getTree()->getTreeId();
592 }
593
594 $types = array('integer','integer');
595 $data = array($this->getTree()->getTreeId(),$parentId);
596 $query = 'SELECT '.$qSelect.' '.
597 'FROM '.$this->getTree()->getTreeTable().' t0 '.$qJoin.' '.
598 'WHERE t0.'.$this->getTree()->getTreePk().' = %s '.
599 'AND t0.child = %s ';
600
601 $ilDB->setLimit(1);
602 $res = $ilDB->queryF($query,$types,$data);
603
604 if ($res->numRows() == 0)
605 {
606 return array();
607 }
608
609 $row = $ilDB->fetchAssoc($res);
610
611 $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
612 if ($takeId) $pathIds[] = $this->getTree()->getRootId();
613 for ($i = $nodeDepth - 4; $i >=0; $i--)
614 {
615 $takeId = $takeId || $row['c'.$i] == $a_startnode_id;
616 if ($takeId) $pathIds[] = $row['c'.$i];
617 }
618 $takeId = $takeId || $parentId == $a_startnode_id;
619 if ($takeId) $pathIds[] = $parentId;
620 $takeId = $takeId || $a_endnode_id == $a_startnode_id;
621 if ($takeId) $pathIds[] = $a_endnode_id;
622 }
623 else
624 {
625 // Fall back to nested sets tree for extremely deep tree structures
626 return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
627 }
628 return $pathIds;
629 }
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:639

References $data, $ilDB, $query, $res, $row, getPathIdsUsingNestedSets(), and getTree().

Referenced by getPathIds().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getPathIdsUsingNestedSets()

ilNestedSetTree::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 startnode @access public

Parameters
integernode_id of endnode
integernode_id of startnode (optional)
Returns
array all path ids from startnode to endnode

Definition at line 639 of file class.ilNestedSetTree.php.

640 {
641 global $ilDB;
642
643 // The nested sets algorithm is very easy to implement.
644 // Unfortunately it always does a full table space scan to retrieve the path
645 // regardless whether indices on lft and rgt are set or not.
646 // (At least, this is what happens on MySQL 4.1).
647 // This algorithms performs well for small trees which are deeply nested.
648
649 $fields = array('integer','integer','integer');
650 $data = array($a_endnode_id,$this->getTree()->getTreeId(),$this->getTree()->getTreeId());
651
652 $query = "SELECT T2.child ".
653 "FROM ".$this->getTree()->getTreeTable()." T1, ".$this->getTree()->getTreeTable()." T2 ".
654 "WHERE T1.child = %s ".
655 "AND T1.lft BETWEEN T2.lft AND T2.rgt ".
656 "AND T1.".$this->getTree()->getTreePk()." = %s ".
657 "AND T2.".$this->getTree()->getTreePk()." = %s ".
658 "ORDER BY T2.depth";
659
660 $res = $ilDB->queryF($query,$fields,$data);
661
662 $takeId = $a_startnode_id == 0;
663 while($row = $ilDB->fetchAssoc($res))
664 {
665 if ($takeId || $row['child'] == $a_startnode_id)
666 {
667 $takeId = true;
668 $pathIds[] = $row['child'];
669 }
670 }
671 return $pathIds ? $pathIds : array();
672 }

References $data, $ilDB, $query, $res, $row, and getTree().

Referenced by getPathIdsUsingAdjacencyMap().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ getRelation()

ilNestedSetTree::getRelation (   $a_node_a,
  $a_node_b 
)

Get relation.

Parameters
type$a_node_a
type$a_node_b
Returns
int

Implements ilTreeImplementation.

Definition at line 128 of file class.ilNestedSetTree.php.

129 {
130 if($a_node_a['child'] == $a_node_b['child'])
131 {
132 ilLoggerFactory::getLogger('tree')->debug('EQUALS');
133 return ilTree::RELATION_EQUALS;
134 }
135 if($a_node_a['lft'] < $a_node_b['lft'] and $a_node_a['rgt'] > $a_node_b['rgt'])
136 {
137 ilLoggerFactory::getLogger('tree')->debug('PARENT');
138 return ilTree::RELATION_PARENT;
139 }
140 if($a_node_b['lft'] < $a_node_a['lft'] and $a_node_b['rgt'] > $a_node_a['rgt'])
141 {
142 ilLoggerFactory::getLogger('tree')->debug('CHILD');
143 return ilTree::RELATION_CHILD;
144 }
145
146 // if node is also parent of node b => sibling
147 if($a_node_a['parent'] == $a_node_b['parent'])
148 {
149 ilLoggerFactory::getLogger('tree')->debug('SIBLING');
150 return ilTree::RELATION_SIBLING;
151 }
152 ilLoggerFactory::getLogger('tree')->debug('NONE');
153 return ilTree::RELATION_NONE;
154 }
ilLoggerFactory\getLogger
static getLogger($a_component_id)
Get component logger.
Definition: class.ilLoggerFactory.php:82
ilTree\RELATION_EQUALS
const RELATION_EQUALS
Definition: class.ilTree.php:33
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

References ilLoggerFactory\getLogger(), ilTree\RELATION_CHILD, ilTree\RELATION_EQUALS, ilTree\RELATION_NONE, ilTree\RELATION_PARENT, and ilTree\RELATION_SIBLING.

+ Here is the call graph for this function:

◆ getSubTreeIds()

ilNestedSetTree::getSubTreeIds (   $a_node_id)

Get subtree ids.

Parameters
type$a_node_id
Returns
int[]

Implements ilTreeImplementation.

Definition at line 43 of file class.ilNestedSetTree.php.

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 {
62 $childs[] = $row->child;
63 }
64 return $childs ? $childs : array();
65 }

References $ilDB, $query, $res, $row, ilDBConstants\FETCHMODE_OBJECT, and getTree().

+ Here is the call graph for this function:

◆ getSubtreeInfo()

ilNestedSetTree::getSubtreeInfo (   $a_endnode_id)

Get rbac subtree info @global type $ilDB.

Parameters
type$a_endnode_id
Returns
array

Implements ilTreeImplementation.

Definition at line 812 of file class.ilNestedSetTree.php.

813 {
814 global $ilDB;
815
816 $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type ".
817 "FROM ".$this->getTree()->getTreeTable()." t1 ".
818 "JOIN ".$this->getTree()->getTreeTable()." t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) ".
819 "JOIN ".$this->getTree()->getTableReference()." obr ON t2.child = obr.ref_id ".
820 "JOIN ".$this->getTree()->getObjectDataTable()." obd ON obr.obj_id = obd.obj_id ".
821 "WHERE t1.child = ".$ilDB->quote($a_endnode_id,'integer')." ".
822 "AND t1.".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer')." ".
823 "AND t2.".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer')." ".
824 "ORDER BY t2.lft";
825
826 ilLoggerFactory::getLogger('tree')->debug($query);
827
828
829 $res = $ilDB->query($query);
830 $nodes = array();
831 while($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT))
832 {
833 $nodes[$row->child]['lft'] = $row->lft;
834 $nodes[$row->child]['rgt'] = $row->rgt;
835 $nodes[$row->child]['child']= $row->child;
836 $nodes[$row->child]['type'] = $row->type;
837
838 }
839 return (array) $nodes;
840 }

References $ilDB, $query, $res, $row, ilDBConstants\FETCHMODE_OBJECT, ilLoggerFactory\getLogger(), and getTree().

+ Here is the call graph for this function:

◆ getSubTreeQuery()

ilNestedSetTree::getSubTreeQuery (   $a_node,
  $a_types = '',
  $a_force_join_reference = true,
  $a_fields = array() 
)

Get subtree.

Parameters
type$a_node
string$a_types
bool$a_force_join_reference
array$a_fields
Returns
string query

Implements ilTreeImplementation.

Definition at line 76 of file class.ilNestedSetTree.php.

77 {
78 global $ilDB;
79
80 $type_str = '';
81 if (is_array($a_types))
82 {
83 if($a_types)
84 {
85 $type_str = "AND ".$ilDB->in($this->getTree()->getObjectDataTable().".type", $a_types, false, "text");
86 }
87 }
88 else if(strlen($a_types))
89 {
90 $type_str = "AND ".$this->getTree()->getObjectDataTable().".type = ".$ilDB->quote($a_types, "text");
91 }
92
93 $join = '';
94 if($type_str or $a_force_join_reference)
95 {
96 $join = $this->getTree()->buildJoin();
97 }
98
99 $fields = '* ';
100 if(count($a_fields))
101 {
102 $fields = implode(',',$a_fields);
103 }
104
105 $query = 'SELECT '.
106 $fields.' '.
107 "FROM ".$this->getTree()->getTreeTable()." ".
108 $join.' '.
109 "WHERE ".$this->getTree()->getTreeTable().'.lft '.
110 'BETWEEN '.$ilDB->quote($a_node['lft'],'integer').' '.
111 'AND '.$ilDB->quote($a_node['rgt'],'integer').' '.
112 "AND ".$this->getTree()->getTreeTable().".".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer').' '.
113 $type_str.' '.
114 "ORDER BY ".$this->getTree()->getTreeTable().".lft";
115
116 #ilLoggerFactory::getLogger('tree')->debug('-----------------: '. $query);
117
118 return $query;
119 }

References $ilDB, $query, and getTree().

+ Here is the call graph for this function:

◆ getTree()

ilNestedSetTree::getTree ( )

Get tree object.

Returns
ilTree $tree

Definition at line 33 of file class.ilNestedSetTree.php.

34 {
35 return $this->tree;
36 }

References $tree.

Referenced by deleteTree(), getPathIdsUsingAdjacencyMap(), getPathIdsUsingNestedSets(), getSubTreeIds(), getSubtreeInfo(), getSubTreeQuery(), insertNode(), moveToTrash(), moveTree(), and validateParentRelations().

+ Here is the caller graph for this function:

◆ insertNode()

ilNestedSetTree::insertNode (   $a_node_id,
  $a_parent_id,
  $a_pos 
)

Insert tree node.

Parameters
type$a_node_id
type$a_parent_id
type$a_pos
Exceptions
ilInvalidTreeStructureException

Implements ilTreeImplementation.

Definition at line 175 of file class.ilNestedSetTree.php.

176 {
177 global $ilDB;
178
179 $insert_node_callable = function(ilDBInterface $ilDB) use($a_node_id, $a_parent_id, $a_pos)
180 {
181 switch ($a_pos)
182 {
183 case ilTree::POS_FIRST_NODE:
184
185 // get left value of parent
186 $query = sprintf('SELECT * FROM '.$this->getTree()->getTreeTable().' '.
187 'WHERE child = %s '.
188 'AND '.$this->getTree()->getTreePk().' = %s ',
189 $ilDB->quote($a_parent_id,'integer'),
190 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
191
192 $res = $ilDB->query($query);
193 $r = $ilDB->fetchObject($res);
194
195 if ($r->parent == NULL)
196 {
197 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
198 throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
199 }
200
201 $left = $r->lft;
202 $lft = $left + 1;
203 $rgt = $left + 2;
204
205 // spread tree
206 $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
207 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
208 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END '.
209 'WHERE '.$this->getTree()->getTreePk().' = %s ',
210 $ilDB->quote($left,'integer'),
211 $ilDB->quote($left,'integer'),
212 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
213 $res = $ilDB->manipulate($query);
214 break;
215
216 case IL_LAST_NODE:
217 // Special treatment for trees with gaps
218 if ($this->getTree()->getGap() > 0)
219 {
220 // get lft and rgt value of parent
221 $query = sprintf('SELECT rgt,lft,parent FROM '.$this->getTree()->getTreeTable().' '.
222 'WHERE child = %s '.
223 'AND '.$this->getTree()->getTreePk().' = %s',
224 $ilDB->quote($a_parent_id,'integer'),
225 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
226 $res = $ilDB->query($query);
227 $r = $ilDB->fetchAssoc($res);
228
229 if ($r['parent'] == null)
230 {
231 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
232 throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
233 }
234 $parentRgt = $r['rgt'];
235 $parentLft = $r['lft'];
236
237 // Get the available space, without taking children into account yet
238 $availableSpace = $parentRgt - $parentLft;
239 if ($availableSpace < 2)
240 {
241 // If there is not enough space between parent lft and rgt, we don't need
242 // to look any further, because we must spread the tree.
243 $lft = $parentRgt;
244 }
245 else
246 {
247 // If there is space between parent lft and rgt, we need to check
248 // whether there is space left between the rightmost child of the
249 // parent and parent rgt.
250 $query = sprintf('SELECT MAX(rgt) max_rgt FROM '.$this->getTree()->getTreeTable().' '.
251 'WHERE parent = %s '.
252 'AND '.$this->getTree()->getTreePk().' = %s',
253 $ilDB->quote($a_parent_id,'integer'),
254 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
255 $res = $ilDB->query($query);
256 $r = $ilDB->fetchAssoc($res);
257
258 if (isset($r['max_rgt']))
259 {
260 // If the parent has children, we compute the available space
261 // between rgt of the rightmost child and parent rgt.
262 $availableSpace = $parentRgt - $r['max_rgt'];
263 $lft = $r['max_rgt'] + 1;
264 }
265 else
266 {
267 // If the parent has no children, we know now, that we can
268 // add the new node at parent lft + 1 without having to spread
269 // the tree.
270 $lft = $parentLft + 1;
271 }
272 }
273 $rgt = $lft + 1;
274
275
276 // spread tree if there is not enough space to insert the new node
277 if ($availableSpace < 2)
278 {
279 //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
280 $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
281 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, '.
282 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END '.
283 'WHERE '.$this->getTree()->getTreePk().' = %s ',
284 $ilDB->quote($parentRgt,'integer'),
285 $ilDB->quote((2 + $this->getTree()->getGap() * 2),'integer'),
286 $ilDB->quote($parentRgt,'integer'),
287 $ilDB->quote((2 + $this->getTree()->getGap() * 2),'integer'),
288 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
289 $res = $ilDB->manipulate($query);
290 }
291 }
292 // Treatment for trees without gaps
293 else
294 {
295
296 // get right value of parent
297 $query = sprintf('SELECT * FROM '.$this->getTree()->getTreeTable().' '.
298 'WHERE child = %s '.
299 'AND '.$this->getTree()->getTreePk().' = %s ',
300 $ilDB->quote($a_parent_id,'integer'),
301 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
302 $res = $ilDB->query($query);
303 $r = $ilDB->fetchObject($res);
304
305 if ($r->parent == null)
306 {
307 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
308 throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
309 }
310
311 $right = $r->rgt;
312 $lft = $right;
313 $rgt = $right + 1;
314
315 // spread tree
316 $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
317 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
318 'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END '.
319 'WHERE '.$this->getTree()->getTreePk().' = %s',
320 $ilDB->quote($right,'integer'),
321 $ilDB->quote($right,'integer'),
322 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
323 $res = $ilDB->manipulate($query);
324 }
325
326 break;
327
328 default:
329
330 // get right value of preceeding child
331 $query = sprintf('SELECT * FROM '.$this->getTree()->getTreeTable().' '.
332 'WHERE child = %s '.
333 'AND '.$this->getTree()->getTreePk().' = %s ',
334 $ilDB->quote($a_pos,'integer'),
335 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
336 $res = $ilDB->query($query);
337 $r = $ilDB->fetchObject($res);
338
339 // crosscheck parents of sibling and new node (must be identical)
340 if ($r->parent != $a_parent_id)
341 {
342 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
343 throw new ilInvalidTreeStructureException('Parent with id '. $a_parent_id.' not found in tree');
344 }
345
346 $right = $r->rgt;
347 $lft = $right + 1;
348 $rgt = $right + 2;
349
350 // update lft/rgt values
351 $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
352 'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, '.
353 'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END '.
354 'WHERE '.$this->getTree()->getTreePk().' = %s',
355 $ilDB->quote($right,'integer'),
356 $ilDB->quote($right,'integer'),
357 $ilDB->quote($this->getTree()->getTreeId(),'integer'));
358 $res = $ilDB->manipulate($query);
359 break;
360
361 }
362
363 // get depth
364 $depth = $this->getTree()->getDepth($a_parent_id) + 1;
365
366 // insert node
367 $query = sprintf('INSERT INTO '.$this->getTree()->getTreeTable().' ('.$this->getTree()->getTreePk().',child,parent,lft,rgt,depth) '.
368 'VALUES (%s,%s,%s,%s,%s,%s)',
369 $ilDB->quote($this->getTree()->getTreeId(),'integer'),
370 $ilDB->quote($a_node_id,'integer'),
371 $ilDB->quote($a_parent_id,'integer'),
372 $ilDB->quote($lft,'integer'),
373 $ilDB->quote($rgt,'integer'),
374 $ilDB->quote($depth,'integer'));
375 $res = $ilDB->manipulate($query);
376 };
377
378 if($this->getTree()->__isMainTree())
379 {
380 $ilAtomQuery = $ilDB->buildAtomQuery();
381 $ilAtomQuery->addTableLock('tree');
382 $ilAtomQuery->addQueryCallable($insert_node_callable);
383 $ilAtomQuery->run();
384 }else
385 {
386 $insert_node_callable($ilDB);
387 }
388 }
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
ilTree\POS_FIRST_NODE
const POS_FIRST_NODE
Definition: class.ilTree.php:27
$r
$r
Definition: example_031.php:79

References $ilDB, $query, $r, $res, ilLogLevel\ERROR, ilLoggerFactory\getLogger(), getTree(), IL_LAST_NODE, ilTree\POS_FIRST_NODE, and sprintf.

+ Here is the call graph for this function:

◆ moveToTrash()

ilNestedSetTree::moveToTrash (   $a_node_id)

Move to trash.

Parameters
int$a_node_id
Returns
bool
Todo:
lock table locktable already active due to calling method

Implements ilTreeImplementation.

Definition at line 472 of file class.ilNestedSetTree.php.

473 {
474 global $ilDB;
475
476 $move_to_trash_callable = function(ilDBInterface $ilDB) use($a_node_id)
477 {
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 {
492 $ilAtomQuery = $ilDB->buildAtomQuery();
493 $ilAtomQuery->addTableLock("tree");
494
495 $ilAtomQuery->addQueryCallable($move_to_trash_callable);
496
497 $ilAtomQuery->run();
498 }
499 else
500 {
501 $move_to_trash_callable($ilDB);
502 }
503
504 return true;
505 }

References $ilDB, $query, and getTree().

+ Here is the call graph for this function:

◆ moveTree()

ilNestedSetTree::moveTree (   $a_source_id,
  $a_target_id,
  $a_position 
)

Move source subtree to target.

Parameters
type$a_source_id
type$a_target_id
type$a_position
Exceptions
InvalidArgumentException

Implements ilTreeImplementation.

Definition at line 683 of file class.ilNestedSetTree.php.

684 {
685 global $ilDB;
686
687 $move_tree_callable = function(ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position)
688 {
689 // Receive node infos for source and target
690 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
691 'WHERE ( child = %s OR child = %s ) ' .
692 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
693 $res = $ilDB->queryF($query, array('integer', 'integer', 'integer'), array(
694 $a_source_id,
695 $a_target_id,
696 $this->getTree()->getTreeId()));
697
698 // Check in tree
699 if ($res->numRows() != 2)
700 {
701 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR,'Objects not found in tree');
702 throw new InvalidArgumentException('Error moving subtree');
703 }
704 while ($row = $ilDB->fetchObject($res))
705 {
706 if ($row->child == $a_source_id)
707 {
708 $source_lft = $row->lft;
709 $source_rgt = $row->rgt;
710 $source_depth = $row->depth;
711 $source_parent = $row->parent;
712 }
713 else
714 {
715 $target_lft = $row->lft;
716 $target_rgt = $row->rgt;
717 $target_depth = $row->depth;
718 }
719 }
720
721 // Check target not child of source
722 if ($target_lft >= $source_lft and $target_rgt <= $source_rgt)
723 {
724 ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR,'Target is child of source');
725 throw new InvalidArgumentException('Error moving subtree: target is child of source');
726 }
727
728 // Now spread the tree at the target location. After this update the table should be still in a consistent state.
729 // implementation for IL_LAST_NODE
730 $spread_diff = $source_rgt - $source_lft + 1;
731 #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
732
733 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
734 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
735 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
736 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
737 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
738 $target_rgt,
739 $spread_diff,
740 $target_rgt,
741 $spread_diff,
742 $this->getTree()->getTreeId()));
743
744 // Maybe the source node has been updated, too.
745 // Check this:
746 if ($source_lft > $target_rgt)
747 {
748 $where_offset = $spread_diff;
749 $move_diff = $target_rgt - $source_lft - $spread_diff;
750 }
751 else
752 {
753 $where_offset = 0;
754 $move_diff = $target_rgt - $source_lft;
755 }
756 $depth_diff = $target_depth - $source_depth + 1;
757
758
759 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
760 'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
761 'rgt = rgt + %s, ' .
762 'lft = lft + %s, ' .
763 'depth = depth + %s ' .
764 'WHERE lft >= %s ' .
765 'AND rgt <= %s ' .
766 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
767 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), array(
768 $source_parent,
769 $a_target_id,
770 $move_diff,
771 $move_diff,
772 $depth_diff,
773 $source_lft + $where_offset,
774 $source_rgt + $where_offset,
775 $this->getTree()->getTreeId()));
776
777 // done: close old gap
778 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
779 'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
780 'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' .
781 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
782
783 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
784 $source_lft + $where_offset,
785 $spread_diff,
786 $source_rgt + $where_offset,
787 $spread_diff,
788 $this->getTree()->getTreeId()));
789 };
790
791
792 if ($this->getTree()->__isMainTree())
793 {
794
795 $ilAtomQuery = $ilDB->buildAtomQuery();
796 $ilAtomQuery->addTableLock('tree');
797 $ilAtomQuery->addQueryCallable($move_tree_callable);
798 $ilAtomQuery->run();
799 }
800 else
801 {
802 $move_tree_callable($ilDB);
803 }
804 }

References $ilDB, $query, $res, $row, ilLogLevel\ERROR, ilLoggerFactory\getLogger(), and getTree().

+ Here is the call graph for this function:

◆ validateParentRelations()

ilNestedSetTree::validateParentRelations ( )

Validate the parent relations of the tree implementation For nested set, validate the lft, rgt against child <-> parent For materialized path validate path against child <-> parent.

Returns
int[] array of failure nodes

Implements ilTreeImplementation.

Definition at line 845 of file class.ilNestedSetTree.php.

846 {
847 global $ilDB;
848
849 $query = 'select child from '.$this->getTree()->getTreeTable().' child where not exists '.
850 '( '.
851 'select child from '.$this->getTree()->getTreeTable().' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) '.
852 ')'.
853 'and '.$this->getTree()->getTreePk().' = '.$this->getTree()->getTreeId().' and child <> 1';
854 $res = $ilDB->query($query);
855
856 ilLoggerFactory::getLogger('tree')->debug($query);
857
858 $failures = array();
859 while($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC))
860 {
861 $failures[] = $row[$this->getTree()->getTreePk()];
862 }
863 return $failures;
864 }

References $ilDB, $query, $res, $row, ilDBConstants\FETCHMODE_ASSOC, ilLoggerFactory\getLogger(), and getTree().

+ Here is the call graph for this function:

Field Documentation

◆ $tree

ilNestedSetTree::$tree = NULL
private

Definition at line 18 of file class.ilNestedSetTree.php.

Referenced by getTree().

The documentation for this class was generated from the following file: