ilNestedSetTree Class Reference

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.

    {
        $this->tree = $a_tree;
    }

Member Function Documentation

deleteTree()

ilNestedSetTree::deleteTree

(

$a_node_id

)

Delete a subtree.

Parameters

int

$a_node_id

Returns

bool

Implements ilTreeImplementation.

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

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
 
        $delete_tree_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
 
            // Fetch lft, rgt directly (without fetchNodeData) to avoid unnecessary table locks
            // (object_reference, object_data)
            $query = 'SELECT *  FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE child = ' . $ilDB->quote($a_node_id, 'integer') . ' ' .
                'AND ' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer');
            $res = $ilDB->query($query);
            $a_node = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC);
 
            // delete subtree
            $query = sprintf(
                'DELETE FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE lft BETWEEN %s AND %s ' .
                'AND rgt BETWEEN %s AND %s ' .
                'AND ' . $this->getTree()->getTreePk() . ' = %s',
                $ilDB->quote($a_node['lft'], 'integer'),
                $ilDB->quote($a_node['rgt'], 'integer'),
                $ilDB->quote($a_node['lft'], 'integer'),
                $ilDB->quote($a_node['rgt'], 'integer'),
                $ilDB->quote($a_node[$this->getTree()->getTreePk()], 'integer')
            );
            $res = $ilDB->manipulate($query);
 
            // Performance improvement: We only close the gap, if the node
            // is not in a trash tree, and if the resulting gap will be
            // larger than twice the gap value
 
            $diff = $a_node["rgt"] - $a_node["lft"] + 1;
            if (
                $a_node[$this->getTree()->getTreePk()] >= 0 &&
                $a_node['rgt'] - $a_node['lft'] >= $this->getTree()->getGap() * 2
            ) {
                // close gaps
                $query = sprintf(
                    'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                    'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
                    'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ' .
                    'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
                    $ilDB->quote($a_node['lft'], 'integer'),
                    $ilDB->quote($diff, 'integer'),
                    $ilDB->quote($a_node['lft'], 'integer'),
                    $ilDB->quote($diff, 'integer'),
                    $ilDB->quote($a_node[$this->getTree()->getTreePk()], 'integer')
                );
 
                $res = $ilDB->manipulate($query);
            }
        };
 
        // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock('tree');
            $ilAtomQuery->addQueryCallable($delete_tree_callable);
            $ilAtomQuery->run();
        } else {
            $delete_tree_callable($ilDB);
        }
 
        return true;
    }

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

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

    {
        return $this->getPathIdsUsingAdjacencyMap($a_endnode, $a_startnode);
    }

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

integer	node_id of endnode
integer	node_id of startnode (optional)

Returns

array all path ids from startnode to endnode

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

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
 
        // The adjacency map algorithm is harder to implement than the nested sets algorithm.
        // This algorithms performs an index search for each of the path element.
        // This algorithms performs well for large trees which are not deeply nested.
 
        // The $takeId variable is used, to determine if a given id shall be included in the path
        $takeId = $a_startnode_id == 0;
        
        $depth_cache = $this->getTree()->getDepthCache();
        $parent_cache = $this->getTree()->getParentCache();
        
        if (
            $this->getTree()->__isMainTree() &&
            isset($depth_cache[$a_endnode_id]) &&
            isset($parent_cache[$a_endnode_id])) {
            $nodeDepth = $depth_cache[$a_endnode_id];
            $parentId = $parent_cache[$a_endnode_id];
        } else {
            $nodeDepth = $this->getTree()->getDepth($a_endnode_id);
            $parentId = $this->getTree()->getParentId($a_endnode_id);
        }
 
        // Fetch the node ids. For shallow depths we can fill in the id's directly.
        $pathIds = array();
        
        // backward compatible check for nodes not in tree
        if (!$nodeDepth) {
            return array();
        } elseif ($nodeDepth == 1) {
            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $a_endnode_id;
            }
        } elseif ($nodeDepth == 2) {
            $takeId = $takeId || $parentId == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $parentId;
            }
            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $a_endnode_id;
            }
        } elseif ($nodeDepth == 3) {
            $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $this->getTree()->getRootId();
            }
            $takeId = $takeId || $parentId == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $parentId;
            }
            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $a_endnode_id;
            }
        } elseif ($nodeDepth < 32) {
            // Adjacency Map Tree performs better than
            // Nested Sets Tree even for very deep trees.
            // The following code construct nested self-joins
            // Since we already know the root-id of the tree and
            // we also know the id and parent id of the current node,
            // we only need to perform $nodeDepth - 3 self-joins.
            // We can further reduce the number of self-joins by 1
            // by taking into account, that each row in table tree
            // contains the id of itself and of its parent.
            $qSelect = 't1.child c0';
            $qJoin = '';
            for ($i = 1; $i < $nodeDepth - 2; $i++) {
                $qSelect .= ', t' . $i . '.parent c' . $i;
                $qJoin .= ' JOIN ' . $this->getTree()->getTreeTable() . ' t' . $i . ' ON ' .
                            't' . $i . '.child=t' . ($i - 1) . '.parent AND ' .
                            't' . $i . '.' . $this->getTree()->getTreePk() . ' = ' . (int) $this->getTree()->getTreeId();
            }
            
            $types = array('integer','integer');
            $data = array($this->getTree()->getTreeId(),$parentId);
            $query = 'SELECT ' . $qSelect . ' ' .
                'FROM ' . $this->getTree()->getTreeTable() . ' t0 ' . $qJoin . ' ' .
                'WHERE t0.' . $this->getTree()->getTreePk() . ' = %s ' .
                'AND t0.child = %s ';
                
            $ilDB->setLimit(1);
            $res = $ilDB->queryF($query, $types, $data);
 
            if ($res->numRows() == 0) {
                return array();
            }
            
            $row = $ilDB->fetchAssoc($res);
            
            $takeId = $takeId || $this->getTree()->getRootId() == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $this->getTree()->getRootId();
            }
            for ($i = $nodeDepth - 4; $i >= 0; $i--) {
                $takeId = $takeId || $row['c' . $i] == $a_startnode_id;
                if ($takeId) {
                    $pathIds[] = $row['c' . $i];
                }
            }
            $takeId = $takeId || $parentId == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $parentId;
            }
            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
            if ($takeId) {
                $pathIds[] = $a_endnode_id;
            }
        } else {
            // Fall back to nested sets tree for extremely deep tree structures
            return $this->getPathIdsUsingNestedSets($a_endnode_id, $a_startnode_id);
        }
        return $pathIds;
    }

References $data, $DIC, $i, $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

integer	node_id of endnode
integer	node_id of startnode (optional)

Returns

array all path ids from startnode to endnode

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

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
        
        // The nested sets algorithm is very easy to implement.
        // Unfortunately it always does a full table space scan to retrieve the path
        // regardless whether indices on lft and rgt are set or not.
        // (At least, this is what happens on MySQL 4.1).
        // This algorithms performs well for small trees which are deeply nested.
        
        $fields = array('integer','integer','integer');
        $data = array($a_endnode_id,$this->getTree()->getTreeId(),$this->getTree()->getTreeId());
        
        $query = "SELECT T2.child " .
            "FROM " . $this->getTree()->getTreeTable() . " T1, " . $this->getTree()->getTreeTable() . " T2 " .
            "WHERE T1.child = %s " .
            "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
            "AND T1." . $this->getTree()->getTreePk() . " = %s " .
            "AND T2." . $this->getTree()->getTreePk() . " = %s " .
            "ORDER BY T2.depth";
 
        $res = $ilDB->queryF($query, $fields, $data);
        
        $takeId = $a_startnode_id == 0;
        while ($row = $ilDB->fetchAssoc($res)) {
            if ($takeId || $row['child'] == $a_startnode_id) {
                $takeId = true;
                $pathIds[] = $row['child'];
            }
        }
        return $pathIds ? $pathIds : array();
    }

References $data, $DIC, $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 125 of file class.ilNestedSetTree.php.

    {
        if ($a_node_a['child'] == $a_node_b['child']) {
            ilLoggerFactory::getLogger('tree')->debug('EQUALS');
            return ilTree::RELATION_EQUALS;
        }
        if ($a_node_a['lft'] < $a_node_b['lft'] and $a_node_a['rgt'] > $a_node_b['rgt']) {
            ilLoggerFactory::getLogger('tree')->debug('PARENT');
            return ilTree::RELATION_PARENT;
        }
        if ($a_node_b['lft'] < $a_node_a['lft'] and $a_node_b['rgt'] > $a_node_a['rgt']) {
            ilLoggerFactory::getLogger('tree')->debug('CHILD');
            return ilTree::RELATION_CHILD;
        }
        
        // if node is also parent of node b => sibling
        if ($a_node_a['parent'] == $a_node_b['parent']) {
            ilLoggerFactory::getLogger('tree')->debug('SIBLING');
            return ilTree::RELATION_SIBLING;
        }
        ilLoggerFactory::getLogger('tree')->debug('NONE');
        return ilTree::RELATION_NONE;
    }

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.

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
        
        $query = 'SELECT s.child FROM ' .
            $this->getTree()->getTreeTable() . ' s, ' .
            $this->getTree()->getTreeTable() . ' t ' .
            'WHERE t.child = %s ' .
            'AND s.lft > t.lft ' .
            'AND s.rgt < t.rgt ' .
            'AND s.' . $this->getTree()->getTreePk() . ' = %s';
        
        $res = $ilDB->queryF(
            $query,
            array('integer','integer'),
            array($a_node_id,$this->getTree()->getTreeId())
        );
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
            $childs[] = $row->child;
        }
        return $childs ? $childs : array();
    }

References $DIC, $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 802 of file class.ilNestedSetTree.php.

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
        
        $query = "SELECT t2.lft lft, t2.rgt rgt, t2.child child, type " .
            "FROM " . $this->getTree()->getTreeTable() . " t1 " .
            "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) " .
            "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
            "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
            "WHERE t1.child = " . $ilDB->quote($a_endnode_id, 'integer') . " " .
            "AND t1." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
            "AND t2." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
            "ORDER BY t2.lft";
 
        ilLoggerFactory::getLogger('tree')->debug($query);
        
            
        $res = $ilDB->query($query);
        $nodes = array();
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
            $nodes[$row->child]['lft'] = $row->lft;
            $nodes[$row->child]['rgt'] = $row->rgt;
            $nodes[$row->child]['child'] = $row->child;
            $nodes[$row->child]['type'] = $row->type;
        }
        return (array) $nodes;
    }

References $DIC, $ilDB, $nodes, $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 77 of file class.ilNestedSetTree.php.

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
        
        $type_str = '';
        if (is_array($a_types)) {
            if ($a_types) {
                $type_str = "AND " . $ilDB->in($this->getTree()->getObjectDataTable() . ".type", $a_types, false, "text");
            }
        } elseif (strlen($a_types)) {
            $type_str = "AND " . $this->getTree()->getObjectDataTable() . ".type = " . $ilDB->quote($a_types, "text");
        }
        
        $join = '';
        if ($type_str or $a_force_join_reference) {
            $join = $this->getTree()->buildJoin();
        }
        
        $fields = '* ';
        if (count($a_fields)) {
            $fields = implode(',', $a_fields);
        }
 
        $query = 'SELECT ' .
            $fields . ' ' .
            "FROM " . $this->getTree()->getTreeTable() . " " .
            $join . ' ' .
            "WHERE " . $this->getTree()->getTreeTable() . '.lft ' .
            'BETWEEN ' . $ilDB->quote($a_node['lft'], 'integer') . ' ' .
            'AND ' . $ilDB->quote($a_node['rgt'], 'integer') . ' ' .
            "AND " . $this->getTree()->getTreeTable() . "." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
            $type_str . ' ' .
            "ORDER BY " . $this->getTree()->getTreeTable() . ".lft";
 
        #ilLoggerFactory::getLogger('tree')->debug('-----------------: '. $query);
        
        return $query;
    }

References $DIC, $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.

    {
        return $this->tree;
    }

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

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
 
        $insert_node_callable = function (ilDBInterface $ilDB) use ($a_node_id, $a_parent_id, $a_pos) {
            switch ($a_pos) {
                case ilTree::POS_FIRST_NODE:
 
                    // get left value of parent
                    $query = sprintf(
                        'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
                        'WHERE child = %s ' .
                        'AND ' . $this->getTree()->getTreePk() . ' = %s ',
                        $ilDB->quote($a_parent_id, 'integer'),
                        $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                    );
 
                    $res = $ilDB->query($query);
                    $r = $ilDB->fetchObject($res);
 
                    if ($r->parent === null) {
                        ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
                        throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
                    }
 
                    $left = $r->lft;
                    $lft = $left + 1;
                    $rgt = $left + 2;
 
                    // spread tree
                    $query = sprintf(
                        'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                        'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
                        'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
                        'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
                        $ilDB->quote($left, 'integer'),
                        $ilDB->quote($left, 'integer'),
                        $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                    );
                    $res = $ilDB->manipulate($query);
                    break;
 
                case IL_LAST_NODE:
                    // Special treatment for trees with gaps
                    if ($this->getTree()->getGap() > 0) {
                        // get lft and rgt value of parent
                        $query = sprintf(
                            'SELECT rgt,lft,parent FROM ' . $this->getTree()->getTreeTable() . ' ' .
                            'WHERE child = %s ' .
                            'AND ' . $this->getTree()->getTreePk() . ' =  %s',
                            $ilDB->quote($a_parent_id, 'integer'),
                            $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                        );
                        $res = $ilDB->query($query);
                        $r = $ilDB->fetchAssoc($res);
 
                        if ($r['parent'] === null) {
                            ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
                            throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
                        }
                        $parentRgt = $r['rgt'];
                        $parentLft = $r['lft'];
 
                        // Get the available space, without taking children into account yet
                        $availableSpace = $parentRgt - $parentLft;
                        if ($availableSpace < 2) {
                            // If there is not enough space between parent lft and rgt, we don't need
                            // to look any further, because we must spread the tree.
                            $lft = $parentRgt;
                        } else {
                            // If there is space between parent lft and rgt, we need to check
                            // whether there is space left between the rightmost child of the
                            // parent and parent rgt.
                            $query = sprintf(
                                'SELECT MAX(rgt) max_rgt FROM ' . $this->getTree()->getTreeTable() . ' ' .
                                'WHERE parent = %s ' .
                                'AND ' . $this->getTree()->getTreePk() . ' = %s',
                                $ilDB->quote($a_parent_id, 'integer'),
                                $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                            );
                            $res = $ilDB->query($query);
                            $r = $ilDB->fetchAssoc($res);
 
                            if (isset($r['max_rgt'])) {
                                // If the parent has children, we compute the available space
                                // between rgt of the rightmost child and parent rgt.
                                $availableSpace = $parentRgt - $r['max_rgt'];
                                $lft = $r['max_rgt'] + 1;
                            } else {
                                // If the parent has no children, we know now, that we can
                                // add the new node at parent lft + 1 without having to spread
                                // the tree.
                                $lft = $parentLft + 1;
                            }
                        }
                        $rgt = $lft + 1;
 
 
                        // spread tree if there is not enough space to insert the new node
                        if ($availableSpace < 2) {
                            //$this->log->write('ilTree.insertNode('.$a_node_id.','.$a_parent_id.') creating gap at '.$a_parent_id.' '.$parentLft.'..'.$parentRgt.'+'.(2 + $this->gap * 2));
                            $query = sprintf(
                                'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                                'lft = CASE WHEN lft  > %s THEN lft + %s ELSE lft END, ' .
                                'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
                                'WHERE ' . $this->getTree()->getTreePk() . ' = %s ',
                                $ilDB->quote($parentRgt, 'integer'),
                                $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
                                $ilDB->quote($parentRgt, 'integer'),
                                $ilDB->quote((2 + $this->getTree()->getGap() * 2), 'integer'),
                                $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                            );
                            $res = $ilDB->manipulate($query);
                        }
                    }
                    // Treatment for trees without gaps
                    else {
 
                        // get right value of parent
                        $query = sprintf(
                            'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
                            'WHERE child = %s ' .
                            'AND ' . $this->getTree()->getTreePk() . ' = %s ',
                            $ilDB->quote($a_parent_id, 'integer'),
                            $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                        );
                        $res = $ilDB->query($query);
                        $r = $ilDB->fetchObject($res);
 
                        if ($r->parent === null) {
                            ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
                            throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
                        }
 
                        $right = $r->rgt;
                        $lft = $right;
                        $rgt = $right + 1;
 
                        // spread tree
                        $query = sprintf(
                            'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                            'lft = CASE WHEN lft >  %s THEN lft + 2 ELSE lft END, ' .
                            'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ' .
                            'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
                            $ilDB->quote($right, 'integer'),
                            $ilDB->quote($right, 'integer'),
                            $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                        );
                        $res = $ilDB->manipulate($query);
                    }
 
                    break;
 
                default:
 
                    // get right value of preceeding child
                    $query = sprintf(
                        'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
                        'WHERE child = %s ' .
                        'AND ' . $this->getTree()->getTreePk() . ' = %s ',
                        $ilDB->quote($a_pos, 'integer'),
                        $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                    );
                    $res = $ilDB->query($query);
                    $r = $ilDB->fetchObject($res);
 
                    // crosscheck parents of sibling and new node (must be identical)
                    if ($r->parent != $a_parent_id) {
                        ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
                        throw new ilInvalidTreeStructureException('Parent with id ' . $a_parent_id . ' not found in tree');
                    }
 
                    $right = $r->rgt;
                    $lft = $right + 1;
                    $rgt = $right + 2;
 
                    // update lft/rgt values
                    $query = sprintf(
                        'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                        'lft = CASE WHEN lft >  %s THEN lft + 2 ELSE lft END, ' .
                        'rgt = CASE WHEN rgt >  %s THEN rgt + 2 ELSE rgt END ' .
                        'WHERE ' . $this->getTree()->getTreePk() . ' = %s',
                        $ilDB->quote($right, 'integer'),
                        $ilDB->quote($right, 'integer'),
                        $ilDB->quote($this->getTree()->getTreeId(), 'integer')
                    );
                    $res = $ilDB->manipulate($query);
                    break;
 
            }
 
            // get depth
            $depth = $this->getTree()->getDepth($a_parent_id) + 1;
 
            // insert node
            $query = sprintf(
                'INSERT INTO ' . $this->getTree()->getTreeTable() . ' (' . $this->getTree()->getTreePk() . ',child,parent,lft,rgt,depth) ' .
                'VALUES (%s,%s,%s,%s,%s,%s)',
                $ilDB->quote($this->getTree()->getTreeId(), 'integer'),
                $ilDB->quote($a_node_id, 'integer'),
                $ilDB->quote($a_parent_id, 'integer'),
                $ilDB->quote($lft, 'integer'),
                $ilDB->quote($rgt, 'integer'),
                $ilDB->quote($depth, 'integer')
            );
            $res = $ilDB->manipulate($query);
        };
 
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock('tree');
            $ilAtomQuery->addQueryCallable($insert_node_callable);
            $ilAtomQuery->run();
        } else {
            $insert_node_callable($ilDB);
        }
    }

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

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

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
 
        $move_to_trash_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
            $node = $this->getTree()->getNodeTreeData($a_node_id);
 
            $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' ' .
                'SET tree = ' . $ilDB->quote(-1 * $node['child'], 'integer') . ' ' .
                'WHERE ' . $this->getTree()->getTreePk() . ' =  ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
                'AND lft BETWEEN ' . $ilDB->quote($node['lft'], 'integer') . ' AND ' . $ilDB->quote($node['rgt'], 'integer') . ' ';
 
            $ilDB->manipulate($query);
        };
 
        // use ilAtomQuery to lock tables if tree is main tree
        // otherwise just call this closure without locking
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock("tree");
 
            $ilAtomQuery->addQueryCallable($move_to_trash_callable);
 
            $ilAtomQuery->run();
        } else {
            $move_to_trash_callable($ilDB);
        }
 
        return true;
    }

References $DIC, $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 685 of file class.ilNestedSetTree.php.

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
 
        $move_tree_callable = function (ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position) {
            // Receive node infos for source and target
            $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE ( child = %s OR child = %s ) ' .
                'AND ' . $this->getTree()->getTreePk() . ' = %s ';
            $res = $ilDB->queryF($query, array('integer', 'integer', 'integer'), array(
                $a_source_id,
                $a_target_id,
                $this->getTree()->getTreeId()));
 
            // Check in tree
            if ($res->numRows() != 2) {
                ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
                throw new InvalidArgumentException('Error moving subtree');
            }
            while ($row = $ilDB->fetchObject($res)) {
                if ($row->child == $a_source_id) {
                    $source_lft = $row->lft;
                    $source_rgt = $row->rgt;
                    $source_depth = $row->depth;
                    $source_parent = $row->parent;
                } else {
                    $target_lft = $row->lft;
                    $target_rgt = $row->rgt;
                    $target_depth = $row->depth;
                }
            }
 
            // Check target not child of source
            if ($target_lft >= $source_lft and $target_rgt <= $source_rgt) {
                ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Target is child of source');
                throw new InvalidArgumentException('Error moving subtree: target is child of source');
            }
 
            // Now spread the tree at the target location. After this update the table should be still in a consistent state.
            // implementation for IL_LAST_NODE
            $spread_diff = $source_rgt - $source_lft + 1;
            #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
 
            $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                'lft = CASE WHEN lft >  %s THEN lft + %s ELSE lft END, ' .
                'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
                'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
            $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
                $target_rgt,
                $spread_diff,
                $target_rgt,
                $spread_diff,
                $this->getTree()->getTreeId()));
 
            // Maybe the source node has been updated, too.
            // Check this:
            if ($source_lft > $target_rgt) {
                $where_offset = $spread_diff;
                $move_diff = $target_rgt - $source_lft - $spread_diff;
            } else {
                $where_offset = 0;
                $move_diff = $target_rgt - $source_lft;
            }
            $depth_diff = $target_depth - $source_depth + 1;
 
 
            $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
                'rgt = rgt + %s, ' .
                'lft = lft + %s, ' .
                'depth = depth + %s ' .
                'WHERE lft >= %s ' .
                'AND rgt <= %s ' .
                'AND ' . $this->getTree()->getTreePk() . ' = %s ';
            $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer', 'integer'), array(
                $source_parent,
                $a_target_id,
                $move_diff,
                $move_diff,
                $depth_diff,
                $source_lft + $where_offset,
                $source_rgt + $where_offset,
                $this->getTree()->getTreeId()));
 
            // done: close old gap
            $query = 'UPDATE ' . $this->getTree()->getTreeTable() . ' SET ' .
                'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
                'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' .
                'WHERE ' . $this->getTree()->getTreePk() . ' = %s ';
 
            $res = $ilDB->manipulateF($query, array('integer', 'integer', 'integer', 'integer', 'integer'), array(
                $source_lft + $where_offset,
                $spread_diff,
                $source_rgt + $where_offset,
                $spread_diff,
                $this->getTree()->getTreeId()));
        };
 
 
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock('tree');
            $ilAtomQuery->addQueryCallable($move_tree_callable);
            $ilAtomQuery->run();
        } else {
            $move_tree_callable($ilDB);
        }
    }

References $DIC, $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 835 of file class.ilNestedSetTree.php.

    {
        global $DIC;
 
        $ilDB = $DIC['ilDB'];
        
        $query = 'select child from ' . $this->getTree()->getTreeTable() . ' child where not exists ' .
                '( ' .
                'select child from ' . $this->getTree()->getTreeTable() . ' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) ' .
                ')' .
                'and ' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId() . ' and child <> 1';
        $res = $ilDB->query($query);
        
        ilLoggerFactory::getLogger('tree')->debug($query);
        
        $failures = array();
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
            $failures[] = $row[$this->getTree()->getTreePk()];
        }
        return $failures;
    }

References $DIC, $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:

• Services/Tree/classes/class.ilNestedSetTree.php