4include_once 
'./Services/Tree/interfaces/interface.ilTreeImplementation.php';
 
   26        $this->tree = $a_tree;
 
   49        $query = 
'SELECT s.child FROM ' .
 
   50            $this->
getTree()->getTreeTable() . 
' s, ' .
 
   51            $this->
getTree()->getTreeTable() . 
' t ' .
 
   52            'WHERE t.child = %s ' .
 
   53            'AND s.lft > t.lft ' .
 
   54            'AND s.rgt < t.rgt ' .
 
   55            'AND s.' . $this->
getTree()->getTreePk() . 
' = %s';
 
   59            array(
'integer',
'integer'),
 
   60            array($a_node_id,$this->
getTree()->getTreeId())
 
   63            $childs[] = 
$row->child;
 
   65        return $childs ? $childs : array();
 
   77    public function getSubTreeQuery($a_node, $a_types = 
'', $a_force_join_reference = 
true, $a_fields = array())
 
   84        if (is_array($a_types)) {
 
   86                $type_str = 
"AND " . 
$ilDB->in($this->
getTree()->getObjectDataTable() . 
".type", $a_types, 
false, 
"text");
 
   88        } elseif (strlen($a_types)) {
 
   89            $type_str = 
"AND " . $this->
getTree()->getObjectDataTable() . 
".type = " . 
$ilDB->quote($a_types, 
"text");
 
   93        if ($type_str or $a_force_join_reference) {
 
   94            $join = $this->
getTree()->buildJoin();
 
   98        if (count($a_fields)) {
 
   99            $fields = implode(
',', $a_fields);
 
  104            "FROM " . $this->
getTree()->getTreeTable() . 
" " .
 
  106            "WHERE " . $this->
getTree()->getTreeTable() . 
'.lft ' .
 
  107            'BETWEEN ' . 
$ilDB->quote($a_node[
'lft'], 
'integer') . 
' ' .
 
  108            'AND ' . 
$ilDB->quote($a_node[
'rgt'], 
'integer') . 
' ' .
 
  109            "AND " . $this->
getTree()->getTreeTable() . 
"." . $this->
getTree()->getTreePk() . 
" = " . 
$ilDB->quote($this->
getTree()->getTreeId(), 
'integer') . 
' ' .
 
  111            "ORDER BY " . $this->
getTree()->getTreeTable() . 
".lft";
 
  113        #ilLoggerFactory::getLogger('tree')->debug('-----------------: '. $query); 
  127        if ($a_node_a[
'child'] == $a_node_b[
'child']) {
 
  131        if ($a_node_a[
'lft'] < $a_node_b[
'lft'] and $a_node_a[
'rgt'] > $a_node_b[
'rgt']) {
 
  135        if ($a_node_b[
'lft'] < $a_node_a[
'lft'] and $a_node_b[
'rgt'] > $a_node_a[
'rgt']) {
 
  141        if ($a_node_a[
'parent'] == $a_node_b[
'parent']) {
 
  174        $insert_node_callable = 
function (
ilDBInterface $ilDB) use ($a_node_id, $a_parent_id, $a_pos) {
 
  180                        'SELECT * FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  181                        'WHERE child = %s ' .
 
  182                        'AND ' . $this->
getTree()->getTreePk() . 
' = %s ',
 
  183                        $ilDB->quote($a_parent_id, 
'integer'),
 
  184                        $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  190                    if (
$r->parent === 
null) {
 
  201                        'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  202                        'lft = CASE WHEN lft > %s THEN lft + 2 ELSE lft END, ' .
 
  203                        'rgt = CASE WHEN rgt > %s THEN rgt + 2 ELSE rgt END ' .
 
  204                        'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s ',
 
  205                        $ilDB->quote($left, 
'integer'),
 
  206                        $ilDB->quote($left, 
'integer'),
 
  207                        $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  214                    if ($this->
getTree()->getGap() > 0) {
 
  217                            'SELECT rgt,lft,parent FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  218                            'WHERE child = %s ' .
 
  219                            'AND ' . $this->
getTree()->getTreePk() . 
' =  %s',
 
  220                            $ilDB->quote($a_parent_id, 
'integer'),
 
  221                            $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  226                        if (
$r[
'parent'] === 
null) {
 
  230                        $parentRgt = 
$r[
'rgt'];
 
  231                        $parentLft = 
$r[
'lft'];
 
  234                        $availableSpace = $parentRgt - $parentLft;
 
  235                        if ($availableSpace < 2) {
 
  244                                'SELECT MAX(rgt) max_rgt FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  245                                'WHERE parent = %s ' .
 
  246                                'AND ' . $this->
getTree()->getTreePk() . 
' = %s',
 
  247                                $ilDB->quote($a_parent_id, 
'integer'),
 
  248                                $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  253                            if (isset(
$r[
'max_rgt'])) {
 
  256                                $availableSpace = $parentRgt - 
$r[
'max_rgt'];
 
  257                                $lft = 
$r[
'max_rgt'] + 1;
 
  262                                $lft = $parentLft + 1;
 
  269                        if ($availableSpace < 2) {
 
  272                                'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  273                                'lft = CASE WHEN lft  > %s THEN lft + %s ELSE lft END, ' .
 
  274                                'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
 
  275                                'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s ',
 
  276                                $ilDB->quote($parentRgt, 
'integer'),
 
  277                                $ilDB->quote((2 + $this->getTree()->getGap() * 2), 
'integer'),
 
  278                                $ilDB->quote($parentRgt, 
'integer'),
 
  279                                $ilDB->quote((2 + $this->getTree()->getGap() * 2), 
'integer'),
 
  280                                $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  290                            'SELECT * FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  291                            'WHERE child = %s ' .
 
  292                            'AND ' . $this->
getTree()->getTreePk() . 
' = %s ',
 
  293                            $ilDB->quote($a_parent_id, 
'integer'),
 
  294                            $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  299                        if (
$r->parent === 
null) {
 
  310                            'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  311                            'lft = CASE WHEN lft >  %s THEN lft + 2 ELSE lft END, ' .
 
  312                            'rgt = CASE WHEN rgt >= %s THEN rgt + 2 ELSE rgt END ' .
 
  313                            'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s',
 
  314                            $ilDB->quote($right, 
'integer'),
 
  315                            $ilDB->quote($right, 
'integer'),
 
  316                            $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  327                        'SELECT * FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  328                        'WHERE child = %s ' .
 
  329                        'AND ' . $this->
getTree()->getTreePk() . 
' = %s ',
 
  330                        $ilDB->quote($a_pos, 
'integer'),
 
  331                        $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  337                    if (
$r->parent != $a_parent_id) {
 
  348                        'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  349                        'lft = CASE WHEN lft >  %s THEN lft + 2 ELSE lft END, ' .
 
  350                        'rgt = CASE WHEN rgt >  %s THEN rgt + 2 ELSE rgt END ' .
 
  351                        'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s',
 
  352                        $ilDB->quote($right, 
'integer'),
 
  353                        $ilDB->quote($right, 
'integer'),
 
  354                        $ilDB->quote($this->getTree()->getTreeId(), 
'integer')
 
  362            $depth = $this->
getTree()->getDepth($a_parent_id) + 1;
 
  366                'INSERT INTO ' . $this->
getTree()->getTreeTable() . 
' (' . $this->
getTree()->getTreePk() . 
',child,parent,lft,rgt,depth) ' .
 
  367                'VALUES (%s,%s,%s,%s,%s,%s)',
 
  368                $ilDB->quote($this->getTree()->getTreeId(), 
'integer'),
 
  369                $ilDB->quote($a_node_id, 
'integer'),
 
  370                $ilDB->quote($a_parent_id, 
'integer'),
 
  371                $ilDB->quote($lft, 
'integer'),
 
  372                $ilDB->quote($rgt, 
'integer'),
 
  373                $ilDB->quote($depth, 
'integer')
 
  378        if ($this->
getTree()->__isMainTree()) {
 
  379            $ilAtomQuery = 
$ilDB->buildAtomQuery();
 
  380            $ilAtomQuery->addTableLock(
'tree');
 
  381            $ilAtomQuery->addQueryCallable($insert_node_callable);
 
  384            $insert_node_callable(
$ilDB);
 
  404            $query = 
'SELECT *  FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  405                'WHERE child = ' . 
$ilDB->quote($a_node_id, 
'integer') . 
' ' .
 
  406                'AND ' . $this->
getTree()->getTreePk() . 
' = ' . 
$ilDB->quote($this->
getTree()->getTreeId(), 
'integer');
 
  412                'DELETE FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  413                'WHERE lft BETWEEN %s AND %s ' .
 
  414                'AND rgt BETWEEN %s AND %s ' .
 
  415                'AND ' . $this->
getTree()->getTreePk() . 
' = %s',
 
  416                $ilDB->quote($a_node[
'lft'], 
'integer'),
 
  417                $ilDB->quote($a_node[
'rgt'], 
'integer'),
 
  418                $ilDB->quote($a_node[
'lft'], 
'integer'),
 
  419                $ilDB->quote($a_node[
'rgt'], 
'integer'),
 
  420                $ilDB->quote($a_node[$this->getTree()->getTreePk()], 
'integer')
 
  428            $diff = $a_node[
"rgt"] - $a_node[
"lft"] + 1;
 
  430                $a_node[$this->
getTree()->getTreePk()] >= 0 &&
 
  431                $a_node[
'rgt'] - $a_node[
'lft'] >= $this->
getTree()->getGap() * 2
 
  435                    'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  436                    'lft = CASE WHEN lft > %s THEN lft - %s ELSE lft END, ' .
 
  437                    'rgt = CASE WHEN rgt > %s THEN rgt - %s ELSE rgt END ' .
 
  438                    'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s ',
 
  439                    $ilDB->quote($a_node[
'lft'], 
'integer'),
 
  440                    $ilDB->quote($diff, 
'integer'),
 
  441                    $ilDB->quote($a_node[
'lft'], 
'integer'),
 
  442                    $ilDB->quote($diff, 
'integer'),
 
  443                    $ilDB->quote($a_node[$this->getTree()->getTreePk()], 
'integer')
 
  451        if ($this->
getTree()->__isMainTree()) {
 
  452            $ilAtomQuery = 
$ilDB->buildAtomQuery();
 
  453            $ilAtomQuery->addTableLock(
'tree');
 
  454            $ilAtomQuery->addQueryCallable($delete_tree_callable);
 
  457            $delete_tree_callable(
$ilDB);
 
  478            $node = $this->
getTree()->getNodeTreeData($a_node_id);
 
  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') . 
' ';
 
  490        if ($this->
getTree()->__isMainTree()) {
 
  491            $ilAtomQuery = 
$ilDB->buildAtomQuery();
 
  492            $ilAtomQuery->addTableLock(
"tree");
 
  494            $ilAtomQuery->addQueryCallable($move_to_trash_callable);
 
  498            $move_to_trash_callable(
$ilDB);
 
  524        $takeId = $a_startnode_id == 0;
 
  526        $depth_cache = $this->
getTree()->getDepthCache();
 
  527        $parent_cache = $this->
getTree()->getParentCache();
 
  530            $this->
getTree()->__isMainTree() &&
 
  531            isset($depth_cache[$a_endnode_id]) &&
 
  532            isset($parent_cache[$a_endnode_id])) {
 
  533            $nodeDepth = $depth_cache[$a_endnode_id];
 
  534            $parentId = $parent_cache[$a_endnode_id];
 
  536            $nodeDepth = $this->
getTree()->getDepth($a_endnode_id);
 
  537            $parentId = $this->
getTree()->getParentId($a_endnode_id);
 
  546        } elseif ($nodeDepth == 1) {
 
  547            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
 
  549                $pathIds[] = $a_endnode_id;
 
  551        } elseif ($nodeDepth == 2) {
 
  552            $takeId = $takeId || $parentId == $a_startnode_id;
 
  554                $pathIds[] = $parentId;
 
  556            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
 
  558                $pathIds[] = $a_endnode_id;
 
  560        } elseif ($nodeDepth == 3) {
 
  561            $takeId = $takeId || $this->
getTree()->getRootId() == $a_startnode_id;
 
  563                $pathIds[] = $this->
getTree()->getRootId();
 
  565            $takeId = $takeId || $parentId == $a_startnode_id;
 
  567                $pathIds[] = $parentId;
 
  569            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
 
  571                $pathIds[] = $a_endnode_id;
 
  573        } elseif ($nodeDepth < 32) {
 
  583            $qSelect = 
't1.child c0';
 
  585            for (
$i = 1; 
$i < $nodeDepth - 2; 
$i++) {
 
  586                $qSelect .= 
', t' . 
$i . 
'.parent c' . 
$i;
 
  587                $qJoin .= 
' JOIN ' . $this->
getTree()->getTreeTable() . 
' t' . 
$i . 
' ON ' .
 
  588                            't' . 
$i . 
'.child=t' . (
$i - 1) . 
'.parent AND ' .
 
  589                            't' . 
$i . 
'.' . $this->
getTree()->getTreePk() . 
' = ' . (int) $this->
getTree()->getTreeId();
 
  592            $types = array(
'integer',
'integer');
 
  594            $query = 
'SELECT ' . $qSelect . 
' ' .
 
  595                'FROM ' . $this->
getTree()->getTreeTable() . 
' t0 ' . $qJoin . 
' ' .
 
  596                'WHERE t0.' . $this->
getTree()->getTreePk() . 
' = %s ' .
 
  597                'AND t0.child = %s ';
 
  602            if (
$res->numRows() == 0) {
 
  608            $takeId = $takeId || $this->
getTree()->getRootId() == $a_startnode_id;
 
  610                $pathIds[] = $this->
getTree()->getRootId();
 
  612            for (
$i = $nodeDepth - 4; 
$i >= 0; 
$i--) {
 
  613                $takeId = $takeId || 
$row[
'c' . 
$i] == $a_startnode_id;
 
  615                    $pathIds[] = 
$row[
'c' . 
$i];
 
  618            $takeId = $takeId || $parentId == $a_startnode_id;
 
  620                $pathIds[] = $parentId;
 
  622            $takeId = $takeId || $a_endnode_id == $a_startnode_id;
 
  624                $pathIds[] = $a_endnode_id;
 
  653        $fields = array(
'integer',
'integer',
'integer');
 
  656        $query = 
"SELECT T2.child " .
 
  657            "FROM " . $this->
getTree()->getTreeTable() . 
" T1, " . $this->
getTree()->getTreeTable() . 
" T2 " .
 
  658            "WHERE T1.child = %s " .
 
  659            "AND T1.lft BETWEEN T2.lft AND T2.rgt " .
 
  660            "AND T1." . $this->
getTree()->getTreePk() . 
" = %s " .
 
  661            "AND T2." . $this->
getTree()->getTreePk() . 
" = %s " .
 
  666        $takeId = $a_startnode_id == 0;
 
  668            if ($takeId || 
$row[
'child'] == $a_startnode_id) {
 
  670                $pathIds[] = 
$row[
'child'];
 
  673        return $pathIds ? $pathIds : array();
 
  685    public function moveTree($a_source_id, $a_target_id, $a_position)
 
  691        $move_tree_callable = 
function (
ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position) {
 
  693            $query = 
'SELECT * FROM ' . $this->
getTree()->getTreeTable() . 
' ' .
 
  694                'WHERE ( child = %s OR child = %s ) ' .
 
  695                'AND ' . $this->
getTree()->getTreePk() . 
' = %s ';
 
  696            $res = 
$ilDB->queryF(
$query, array(
'integer', 
'integer', 
'integer'), array(
 
  699                $this->
getTree()->getTreeId()));
 
  702            if (
$res->numRows() != 2) {
 
  704                throw new InvalidArgumentException(
'Error moving subtree');
 
  707                if (
$row->child == $a_source_id) {
 
  708                    $source_lft = 
$row->lft;
 
  709                    $source_rgt = 
$row->rgt;
 
  710                    $source_depth = 
$row->depth;
 
  711                    $source_parent = 
$row->parent;
 
  713                    $target_lft = 
$row->lft;
 
  714                    $target_rgt = 
$row->rgt;
 
  715                    $target_depth = 
$row->depth;
 
  720            if ($target_lft >= $source_lft and $target_rgt <= $source_rgt) {
 
  722                throw new InvalidArgumentException(
'Error moving subtree: target is child of source');
 
  727            $spread_diff = $source_rgt - $source_lft + 1;
 
  728            #var_dump("<pre>","SPREAD_DIFF: ",$spread_diff,"<pre>");
 
  730            $query = 
'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  731                'lft = CASE WHEN lft >  %s THEN lft + %s ELSE lft END, ' .
 
  732                'rgt = CASE WHEN rgt >= %s THEN rgt + %s ELSE rgt END ' .
 
  733                'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s ';
 
  734            $res = 
$ilDB->manipulateF(
$query, array(
'integer', 
'integer', 
'integer', 
'integer', 
'integer'), array(
 
  739                $this->
getTree()->getTreeId()));
 
  743            if ($source_lft > $target_rgt) {
 
  744                $where_offset = $spread_diff;
 
  745                $move_diff = $target_rgt - $source_lft - $spread_diff;
 
  748                $move_diff = $target_rgt - $source_lft;
 
  750            $depth_diff = $target_depth - $source_depth + 1;
 
  753            $query = 
'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  754                'parent = CASE WHEN parent = %s THEN %s ELSE parent END, ' .
 
  757                'depth = depth + %s ' .
 
  760                'AND ' . $this->
getTree()->getTreePk() . 
' = %s ';
 
  761            $res = 
$ilDB->manipulateF(
$query, array(
'integer', 
'integer', 
'integer', 
'integer', 
'integer', 
'integer', 
'integer', 
'integer'), array(
 
  767                $source_lft + $where_offset,
 
  768                $source_rgt + $where_offset,
 
  769                $this->
getTree()->getTreeId()));
 
  772            $query = 
'UPDATE ' . $this->
getTree()->getTreeTable() . 
' SET ' .
 
  773                'lft = CASE WHEN lft >= %s THEN lft - %s ELSE lft END, ' .
 
  774                'rgt = CASE WHEN rgt >= %s THEN rgt - %s ELSE rgt END ' .
 
  775                'WHERE ' . $this->
getTree()->getTreePk() . 
' = %s ';
 
  777            $res = 
$ilDB->manipulateF(
$query, array(
'integer', 
'integer', 
'integer', 
'integer', 
'integer'), array(
 
  778                $source_lft + $where_offset,
 
  780                $source_rgt + $where_offset,
 
  782                $this->
getTree()->getTreeId()));
 
  786        if ($this->
getTree()->__isMainTree()) {
 
  787            $ilAtomQuery = 
$ilDB->buildAtomQuery();
 
  788            $ilAtomQuery->addTableLock(
'tree');
 
  789            $ilAtomQuery->addQueryCallable($move_tree_callable);
 
  792            $move_tree_callable(
$ilDB);
 
  808        $query = 
"SELECT t2.lft lft, t2.rgt rgt, t2.child child, type " .
 
  809            "FROM " . $this->
getTree()->getTreeTable() . 
" t1 " .
 
  810            "JOIN " . $this->
getTree()->getTreeTable() . 
" t2 ON (t2.lft BETWEEN t1.lft AND t1.rgt) " .
 
  811            "JOIN " . $this->
getTree()->getTableReference() . 
" obr ON t2.child = obr.ref_id " .
 
  812            "JOIN " . $this->
getTree()->getObjectDataTable() . 
" obd ON obr.obj_id = obd.obj_id " .
 
  813            "WHERE t1.child = " . 
$ilDB->quote($a_endnode_id, 
'integer') . 
" " .
 
  814            "AND t1." . $this->
getTree()->getTreePk() . 
" = " . 
$ilDB->quote($this->
getTree()->getTreeId(), 
'integer') . 
" " .
 
  815            "AND t2." . $this->
getTree()->getTreePk() . 
" = " . 
$ilDB->quote($this->
getTree()->getTreeId(), 
'integer') . 
" " .
 
  841        $query = 
'select child from ' . $this->
getTree()->getTreeTable() . 
' child where not exists ' .
 
  843                'select child from ' . $this->
getTree()->getTreeTable() . 
' parent where child.parent = parent.child and (parent.lft < child.lft) and (parent.rgt > child.rgt) ' .
 
  845                'and ' . $this->
getTree()->getTreePk() . 
' = ' . $this->
getTree()->getTreeId() . 
' and child <> 1';
 
An exception for terminatinating execution or to throw for unit testing.
Thrown if invalid tree strucutes are found.
static getLogger($a_component_id)
Get component logger.
Base class for nested set path based trees.
moveToTrash($a_node_id)
Move to trash.
getRelation($a_node_a, $a_node_b)
Get relation.
insertNode($a_node_id, $a_parent_id, $a_pos)
Insert tree node.
getPathIds($a_endnode, $a_startnode=0)
Get path ids.
getTree()
Get tree object.
deleteTree($a_node_id)
Delete a subtree.
getSubTreeQuery($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
Get subtree.
moveTree($a_source_id, $a_target_id, $a_position)
Move source subtree to target.
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...
__construct(ilTree $a_tree)
Constructor.
getSubtreeInfo($a_endnode_id)
Get rbac subtree info @global type $ilDB.
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...
validateParentRelations()
Validate the parent relations of the tree implementation For nested set, validate the lft,...
getSubTreeIds($a_node_id)
Get subtree ids.
Tree class data representation in hierachical trees using the Nested Set Model with Gaps by Joe Celco...
Interface for tree implementations Currrently nested set or materialize path.
foreach($_POST as $key=> $value) $res