ILIAS  release_5-1 Revision 5.0.0-5477-g43f3e3fab5f
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$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
type$a_node_id

Implements ilTreeImplementation.

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

403 {
404 global $ilDB;
405
406 // LOCKED ###########################################################
407 // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
408 if($this->getTree()->__isMainTree())
409 {
410 $ilDB->lockTables(
411 array(
412 0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
413 }
414
415 // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
416 // (object_reference, object_data)
417 $query = 'SELECT * FROM '.$this->getTree()->getTreeTable().' '.
418 'WHERE child = '.$ilDB->quote($a_node_id,'integer').' '.
419 'AND '.$this->getTree()->getTreePk().' = '.$ilDB->quote($this->getTree()->getTreeId(),'integer');
420 $res = $ilDB->query($query);
421 $a_node = $res->fetchRow(DB_FETCHMODE_ASSOC);
422
423 // delete subtree
424 $query = sprintf('DELETE FROM '.$this->getTree()->getTreeTable().' '.
425 'WHERE lft BETWEEN %s AND %s '.
426 'AND rgt BETWEEN %s AND %s '.
427 'AND '.$this->getTree()->getTreePk().' = %s',
428 $ilDB->quote($a_node['lft'],'integer'),
429 $ilDB->quote($a_node['rgt'],'integer'),
430 $ilDB->quote($a_node['lft'],'integer'),
431 $ilDB->quote($a_node['rgt'],'integer'),
432 $ilDB->quote($a_node[$this->getTree()->getTreePk()],'integer'));
433 $res = $ilDB->manipulate($query);
434
435 // Performance improvement: We only close the gap, if the node
436 // is not in a trash tree, and if the resulting gap will be
437 // larger than twice the gap value
438
439 $diff = $a_node["rgt"] - $a_node["lft"] + 1;
440 if(
441 $a_node[$this->getTree()->getTreePk()] >= 0 &&
442 $a_node['rgt'] - $a_node['lft'] >= $this->getTree()->getGap() * 2
443 )
444 {
445 // close gaps
446 $query = sprintf('UPDATE '.$this->getTree()->getTreeTable().' SET '.
447 'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, '.
448 'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END '.
449 'WHERE '.$this->getTree()->getTreePk().' = %s ',
450 $ilDB->quote($a_node['lft'],'integer'),
451 $ilDB->quote($diff,'integer'),
452 $ilDB->quote($a_node['lft'],'integer'),
453 $ilDB->quote($diff,'integer'),
454 $ilDB->quote($a_node[$this->getTree()->getTreePk()],'integer'));
455
456 $res = $ilDB->manipulate($query);
457 }
458
459 if($this->getTree()->__isMainTree())
460 {
461 $ilDB->unlockTables();
462 }
463 // LOCKED ###########################################################
464 return true;
465 }
DB_FETCHMODE_ASSOC
const DB_FETCHMODE_ASSOC
Definition: class.ilDB.php:10
ilDB\LOCK_WRITE
const LOCK_WRITE
Definition: class.ilDB.php:30
ilNestedSetTree\getTree
getTree()
Get tree object.
Definition: class.ilNestedSetTree.php:33
$ilDB
global $ilDB
Definition: storeScorm2004.php:19

References $ilDB, $query, $res, DB_FETCHMODE_ASSOC, getTree(), and ilDB\LOCK_WRITE.

+ 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

Implements ilTreeImplementation.

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

157 {
158 return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
159 }
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:497

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 497 of file class.ilNestedSetTree.php.

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

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 620 of file class.ilNestedSetTree.php.

621 {
622 global $ilDB;
623
624 // The nested sets algorithm is very easy to implement.
625 // Unfortunately it always does a full table space scan to retrieve the path
626 // regardless whether indices on lft and rgt are set or not.
627 // (At least, this is what happens on MySQL 4.1).
628 // This algorithms performs well for small trees which are deeply nested.
629
630 $fields = array('integer','integer','integer');
631 $data = array($a_endnode_id,$this->getTree()->getTreeId(),$this->getTree()->getTreeId());
632
633 $query = "SELECT T2.child ".
634 "FROM ".$this->getTree()->getTreeTable()." T1, ".$this->getTree()->getTreeTable()." T2 ".
635 "WHERE T1.child = %s ".
636 "AND T1.lft BETWEEN T2.lft AND T2.rgt ".
637 "AND T1.".$this->getTree()->getTreePk()." = %s ".
638 "AND T2.".$this->getTree()->getTreePk()." = %s ".
639 "ORDER BY T2.depth";
640
641 $res = $ilDB->queryF($query,$fields,$data);
642
643 $takeId = $a_startnode_id == 0;
644 while($row = $ilDB->fetchAssoc($res))
645 {
646 if ($takeId || $row['child'] == $a_startnode_id)
647 {
648 $takeId = true;
649 $pathIds[] = $row['child'];
650 }
651 }
652 return $pathIds ? $pathIds : array();
653 }

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

Implements ilTreeImplementation.

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

124 {
125 if($a_node_a['child'] == $a_node_b['child'])
126 {
127 $GLOBALS['ilLog']->write(__METHOD__.': EQUALS');
128 return ilTree::RELATION_EQUALS;
129 }
130 if($a_node_a['lft'] < $a_node_b['lft'] and $a_node_a['rgt'] > $a_node_b['rgt'])
131 {
132 $GLOBALS['ilLog']->write(__METHOD__.': 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 {
137 $GLOBALS['ilLog']->write(__METHOD__.': CHILD');
138 return ilTree::RELATION_CHILD;
139 }
140
141 // if node is also parent of node b => sibling
142 if($a_node_a['parent'] == $a_node_b['parent'])
143 {
144 $GLOBALS['ilLog']->write(__METHOD__.': SIBLING');
145 return ilTree::RELATION_SIBLING;
146 }
147 $GLOBALS['ilLog']->write(__METHOD__.': NONE');
148 return ilTree::RELATION_NONE;
149 }
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
$GLOBALS
$GLOBALS['PHPCAS_CLIENT']
This global variable is used by the interface class phpCAS.
Definition: CAS.php:276

References $GLOBALS, ilTree\RELATION_CHILD, ilTree\RELATION_EQUALS, ilTree\RELATION_NONE, ilTree\RELATION_PARENT, and ilTree\RELATION_SIBLING.

◆ getSubTreeIds()

ilNestedSetTree::getSubTreeIds (   $a_node_id)

Get subtree ids.

Parameters
type$a_node_id

Implements ilTreeImplementation.

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

43 {
44 global $ilDB;
45
46 $query = 'SELECT s.child FROM '.
47 $this->getTree()->getTreeTable().' s, '.
48 $this->getTree()->getTreeTable().' t '.
49 'WHERE t.child = %s '.
50 'AND s.lft > t.lft '.
51 'AND s.rgt < t.rgt '.
52 'AND s.'.$this->getTree()->getTreePk().' = %s';
53
54 $res = $ilDB->queryF(
55 $query,
56 array('integer','integer'),
57 array($a_node_id,$this->getTree()->getTreeId())
58 );
59 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
60 {
61 $childs[] = $row->child;
62 }
63 return $childs ? $childs : array();
64 }
DB_FETCHMODE_OBJECT
const DB_FETCHMODE_OBJECT
Definition: class.ilDB.php:11

References $ilDB, $query, $res, $row, DB_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
type

Implements ilTreeImplementation.

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

796 {
797 global $ilDB;
798
799 $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type ".
800 "FROM ".$this->getTree()->getTreeTable()." t1 ".
801 "JOIN ".$this->getTree()->getTreeTable()." t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) ".
802 "JOIN ".$this->getTree()->getTableReference()." obr ON t2.child = obr.ref_id ".
803 "JOIN ".$this->getTree()->getObjectDataTable()." obd ON obr.obj_id = obd.obj_id ".
804 "WHERE t1.child = ".$ilDB->quote($a_endnode_id,'integer')." ".
805 "AND t1.".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer')." ".
806 "AND t2.".$this->getTree()->getTreePk()." = ".$ilDB->quote($this->getTree()->getTreeId(),'integer')." ".
807 "ORDER BY t2.lft";
808
809 $GLOBALS['ilLog']->write(__METHOD__.': '.$query);
810
811
812 $res = $ilDB->query($query);
813 $nodes = array();
814 while($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
815 {
816 $nodes[$row->child]['lft'] = $row->lft;
817 $nodes[$row->child]['rgt'] = $row->rgt;
818 $nodes[$row->child]['child']= $row->child;
819 $nodes[$row->child]['type'] = $row->type;
820
821 }
822 return (array) $nodes;
823 }

References $GLOBALS, $ilDB, $query, $res, $row, DB_FETCHMODE_OBJECT, 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
type$a_with_data
type$a_types

Implements ilTreeImplementation.

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

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

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

Implements ilTreeImplementation.

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

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

+ Here is the call graph for this function:

◆ moveToTrash()

ilNestedSetTree::moveToTrash (   $a_node_id)

Move to trash.

Parameters
type$a_node_id
Todo:
lock table

Implements ilTreeImplementation.

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

474 {
475 global $ilDB;
476
477 $node = $this->getTree()->getNodeTreeData($a_node_id);
478
479 $query = 'UPDATE '.$this->getTree()->getTreeTable().' '.
480 'SET tree = '.$ilDB->quote(-1 * $node['child'],'integer').' '.
481 'WHERE '.$this->getTree()->getTreePk().' = '.$ilDB->quote($this->getTree()->getTreeId(),'integer').' '.
482 'AND lft BETWEEN '.$ilDB->quote($node['lft'],'integer').' AND '.$ilDB->quote($node['rgt'],'integer').' ';
483
484 $ilDB->manipulate($query);
485 return true;
486 }

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

Implements ilTreeImplementation.

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

663 {
664 global $ilDB;
665
666 if ($this->getTree()->__isMainTree())
667 {
668 $ilDB->lockTables(
669 array(
670 0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
671 }
672 // Receive node infos for source and target
673 $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
674 'WHERE ( child = %s OR child = %s ) ' .
675 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
676 $res = $ilDB->queryF($query, array('integer', 'integer', 'integer'), array(
677 $a_source_id,
678 $a_target_id,
679 $this->getTree()->getTreeId()));
680
681 // Check in tree
682 if ($res->numRows() != 2)
683 {
684 if ($this->getTree()->__isMainTree())
685 {
686 $ilDB->unlockTables();
687 }
688 $GLOBALS['ilLog']->logStack();
689 $GLOBALS['ilLog']->write(__METHOD__.': Objects not found in tree');
690 throw new InvalidArgumentException('Error moving subtree');
691 }
692 while ($row = $ilDB->fetchObject($res))
693 {
694 if ($row->child == $a_source_id)
695 {
696 $source_lft = $row->lft;
697 $source_rgt = $row->rgt;
698 $source_depth = $row->depth;
699 $source_parent = $row->parent;
700 }
701 else
702 {
703 $target_lft = $row->lft;
704 $target_rgt = $row->rgt;
705 $target_depth = $row->depth;
706 }
707 }
708
709 // Check target not child of source
710 if ($target_lft >= $source_lft and $target_rgt <= $source_rgt)
711 {
712 if ($this->getTree()->__isMainTree())
713 {
714 $ilDB->unlockTables();
715 }
716 $GLOBALS['ilLog']->logStack();
717 $GLOBALS['ilLog']->write(__METHOD__.': Target is child of source');
718 throw new ilInvalidArgumentException('Error moving subtree: target is child of source');
719 }
720
721 // Now spread the tree at the target location. After this update the table should be still in a consistent state.
722 // implementation for IL_LAST_NODE
723 $spread_diff = $source_rgt - $source_lft + 1;
724 #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
725
726 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
727 'lft = CASE WHEN lft > %s THEN lft + %s ELSE lft END, ' .
728 'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
729 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
730 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
731 $target_rgt,
732 $spread_diff,
733 $target_rgt,
734 $spread_diff,
735 $this->getTree()->getTreeId()));
736
737 // Maybe the source node has been updated, too.
738 // Check this:
739 if ($source_lft > $target_rgt)
740 {
741 $where_offset = $spread_diff;
742 $move_diff = $target_rgt - $source_lft - $spread_diff;
743 }
744 else
745 {
746 $where_offset = 0;
747 $move_diff = $target_rgt - $source_lft;
748 }
749 $depth_diff = $target_depth - $source_depth + 1;
750
751
752 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
753 'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
754 'rgt = rgt + %s, ' .
755 'lft = lft + %s, ' .
756 'depth = depth + %s ' .
757 'WHERE lft >= %s ' .
758 'AND rgt <= %s ' .
759 'AND ' . $this->getTree()->getTreePk() . ' = %s ';
760 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), array(
761 $source_parent,
762 $a_target_id,
763 $move_diff,
764 $move_diff,
765 $depth_diff,
766 $source_lft + $where_offset,
767 $source_rgt + $where_offset,
768 $this->getTree()->getTreeId()));
769
770 // done: close old gap
771 $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
772 'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
773 'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' .
774 'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
775
776 $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
777 $source_lft + $where_offset,
778 $spread_diff,
779 $source_rgt + $where_offset,
780 $spread_diff,
781 $this->getTree()->getTreeId()));
782
783 if ($this->getTree()->__isMainTree())
784 {
785 $ilDB->unlockTables();
786 }
787 }

References $GLOBALS, $ilDB, $query, $res, $row, getTree(), and ilDB\LOCK_WRITE.

+ 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 828 of file class.ilNestedSetTree.php.

829 {
830 global $ilDB;
831
832 $query = 'select child from '.$this->getTree()->getTreeTable().' child where not exists '.
833 '( '.
834 'select child from '.$this->getTree()->getTreeTable().' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) '.
835 ')'.
836 'and '.$this->getTree()->getTreePk().' = '.$this->getTree()->getTreeId().' and child <> 1';
837 $res = $ilDB->query($query);
838
839 ilLoggerFactory::getLogger('tree')->debug($query);
840
841 $failures = array();
842 while($row = $res->fetchRow(DB_FETCHMODE_ASSOC))
843 {
844 $failures[] = $row[$this->getTree()->getTreePk()];
845 }
846 return $failures;
847 }
ilLoggerFactory\getLogger
static getLogger($a_component_id)
Get component logger.
Definition: class.ilLoggerFactory.php:82

References $ilDB, $query, $res, $row, DB_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: