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