ILIAS  Release_5_0_x_branch Revision 61816
 All Data Structures Namespaces Files Functions Variables Groups Pages
class.ilMaterializedPathTree.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 ilMaterializedPathTree implements ilTreeImplementation
17 {
18  private $maximum_possible_depth = 100;
19  private $tree = NULL;
20 
25  public function __construct(ilTree $a_tree)
26  {
27  $this->tree = $a_tree;
28  }
29 
30 
35  protected function getMaximumPossibleDepth()
36  {
37  return $this->maximum_possible_depth;
38  }
39 
44  public function getTree()
45  {
46  return $this->tree;
47  }
48 
53  public function getSubTreeIds($a_node_id)
54  {
55  global $ilDB;
56 
57  $node = $this->getTree()->getNodeTreeData($a_node_id);
58  $query = 'SELECT child FROM '.$this->getTree()->getTreeTable().' '.
59  'WHERE path BETWEEN '.
60  $ilDB->quote($node['path'], 'text').' AND '.
61  $ilDB->quote($node['path'].'.Z', 'text').' '.
62  'AND child != %s '.
63  'AND '.$this->getTree()->getTreePk().' = %s';
64 
65  $res = $ilDB->queryF(
66  $query,
67  array('integer', 'integer'),
68  array($a_node_id, $this->getTree()->getTreeId())
69  );
70  while($row = $ilDB->fetchAssoc($res))
71  {
72  $childs[] = $row['child'];
73  }
74  return $childs ? $childs : array();
75  }
76 
82  public function getRelation($a_node_a, $a_node_b)
83  {
84  if($a_node_a['child'] == $a_node_b['child'])
85  {
86  $GLOBALS['ilLog']->write(__METHOD__.': EQUALS');
87  return ilTree::RELATION_EQUALS;
88  }
89  if(stristr($a_node_a['path'], $a_node_b['path']))
90  {
91  $GLOBALS['ilLog']->write(__METHOD__.': CHILD');
92  return ilTree::RELATION_CHILD;
93  }
94  if(stristr($a_node_b['path'], $a_node_a['path']))
95  {
96  $GLOBALS['ilLog']->write(__METHOD__.': PARENT');
97  return ilTree::RELATION_PARENT;
98  }
99  $path_a = substr($a_node_a['path'],0,strrpos($a_node_a['path'],'.'));
100  $path_b = substr($a_node_b['path'],0,strrpos($a_node_b['path'],'.'));
101  $GLOBALS['ilLog']->write(__METHOD__.': Comparing '.$path_a .' '. 'with '.$path_b);
102 
103  if($a_node_a['path'] and (strcmp($path_a,$path_b) === 0))
104  {
105  $GLOBALS['ilLog']->write(__METHOD__.': SIBLING');
106  return ilTree::RELATION_SIBLING;
107  }
108 
109  $GLOBALS['ilLog']->write(__METHOD__.': NONE');
110  return ilTree::RELATION_NONE;
111  }
112 
119  public function getSubTreeQuery($a_node, $a_types = '', $a_force_join_reference = true, $a_fields = array())
120  {
121  global $ilDB;
122 
123  $type_str = '';
124  if(is_array($a_types))
125  {
126  if($a_types)
127  {
128  $type_str = "AND ".$ilDB->in($this->getTree()->getObjectDataTable().".type", $a_types, false, "text");
129  }
130  }
131  else if(strlen($a_types))
132  {
133  $type_str = "AND ".$this->getTree()->getObjectDataTable().".type = ".$ilDB->quote($a_types, "text");
134  }
135 
136  $join = '';
137  if($type_str or $a_force_join_reference)
138  {
139  $join = $this->getTree()->buildJoin();
140  }
141 
142  $fields = '* ';
143  if(count($a_fields))
144  {
145  $fields = implode(',',$a_fields);
146  }
147 
148  // @todo order by
149  $query = 'SELECT '.
150  $fields.' '.
151  'FROM '.$this->getTree()->getTreeTable().' '.
152  $join.' '.
153  'WHERE '.$this->getTree()->getTreeTable().'.path '.
154  'BETWEEN '.
155  $ilDB->quote($a_node['path'],'text').' AND '.
156  $ilDB->quote($a_node['path'].'.Z','text').' '.
157  'AND '.$this->getTree()->getTreeTable().'.'.$this->getTree()->getTreePk().' = '.$ilDB->quote($this->getTree()->getTreeId(),'integer').' '.
158  $type_str.' '.
159  'ORDER BY '.$this->getTree()->getTreeTable().'.path';
160 
161  return $query;
162  }
163 
169  public function getPathIds($a_endnode, $a_startnode = 0)
170  {
171  global $ilDB;
172 
173  $ilDB->setLimit(1);
174  $query = 'SELECT path FROM ' . $this->getTree()->getTreeTable() .' '.
175  'WHERE child = '. $ilDB->quote($a_endnode,'integer').' ';
176  $res = $ilDB->query($query);
177 
178  $path = null;
179  while ($row = $ilDB->fetchAssoc($res))
180  {
181  $path = $row['path'];
182  }
183 
184  $pathIds = explode('.', $path);
185 
186  if ($a_startnode != 0)
187  {
188  while (count($pathIds) > 0 && $pathIds[0] != $a_startnode)
189  {
190  array_shift($pathIds);
191  }
192  }
193  return $pathIds;
194  }
195 
202  public function insertNode($a_node_id, $a_parent_id, $a_pos)
203  {
204  global $ilDB;
205 
206  // LOCKED ###########################################################
207  if ($this->getTree()->__isMainTree())
208  {
209  $ilDB->lockTables(
210  array(
211  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
212  }
213 
214  // get path and depth of parent
215  $ilDB->setLimit(1);
216 
217  $res = $ilDB->queryF(
218  'SELECT parent, depth, path FROM ' . $this->getTree()->getTreeTable() . ' ' .
219  'WHERE child = %s '. ' '.
220  'AND ' . $this->getTree()->getTreePk() . ' = %s', array('integer', 'integer'),
221  array($a_parent_id, $this->getTree()->getTreeId()));
222 
223 
224  $r = $ilDB->fetchObject($res);
225 
226  if ($r->parent == NULL)
227  {
228  if ($this->getTree()->__isMainTree())
229  {
230  $ilDB->unlockTables();
231  }
232  $GLOBALS['ilLog']->logStack();
233  throw new ilInvalidTreeStructureException('Parent node not found in tree');
234  }
235 
236  if ($r->depth >= $this->getMaximumPossibleDepth())
237  {
238  // LOCKED ###########################################################
239  if ($this->getTree()->__isMainTree())
240  {
241  $ilDB->unlockTables();
242  }
243  $GLOBALS['ilLog']->logStack();
244  throw new ilInvalidTreeStructureException('Maximum tree depth exceeded');
245  }
246 
247  $parentPath = $r->path;
248  $depth = $r->depth + 1;
249  $lft = 0;
250  $rgt = 0;
251 
252 
253  $ilDB->insert($this->getTree()->getTreeTable(), array($this->getTree()->getTreePk() => array('integer', $this->getTree()->getTreeId()),
254  'child' => array('integer', $a_node_id),
255  'parent' => array('integer', $a_parent_id),
256  'lft' => array('integer', $lft),
257  'rgt' => array('integer', $rgt),
258  'depth' => array('integer', $depth),
259  'path' => array('text', $parentPath . "." . $a_node_id)));
260 
261 
262  if ($this->getTree()->__isMainTree())
263  {
264  $ilDB->unlockTables();
265  }
266  }
267 
268 
273  public function deleteTree($a_node_id)
274  {
275  global $ilDB;
276 
277  $a_node = $this->getTree()->getNodeData($a_node_id);
278 
279  $query = 'DELETE FROM '.$this->getTree()->getTreeTable().' '.
280  'WHERE path BETWEEN '.$ilDB->quote($a_node['path'],'text').' '.
281  'AND '.$ilDB->quote($a_node['path'].'.Z','text').' '.
282  'AND '.$this->getTree()->getTreePk().' = '.$ilDB->quote($a_node[$this->getTree()->getTreePk()]);
283  $ilDB->manipulate($query);
284  return true;
285  }
286 
291  public function moveToTrash($a_node_id)
292  {
293  global $ilDB;
294 
295  // LOCKED ###########################################################
296  if ($this->getTree()->__isMainTree())
297  {
298  $ilDB->lockTables(
299  array(
300  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
301  }
302  try
303  {
304  $node = $this->getTree()->getNodeTreeData($a_node_id);
305  }
306  catch(Exception $e)
307  {
308  if ($this->getTree()->__isMainTree())
309  {
310  $ilDB->unlockTables();
311  }
312  throw $e;
313  }
314 
315 
316  // Set the nodes deleted (negative tree id)
317  $ilDB->manipulateF('
318  UPDATE ' . $this->getTree()->getTreeTable().' '.
319  'SET tree = %s' .' '.
320  'WHERE ' . $this->getTree()->getTreePk() . ' = %s ' .
321  'AND path BETWEEN %s AND %s',
322  array('integer', 'integer', 'text', 'text'),
323  array(-$a_node_id, $this->getTree()->getTreeId(), $node['path'], $node['path'] . '.Z'));
324 
325 
326  // LOCKED ###########################################################
327  if ($this->getTree()->__isMainTree())
328  {
329  $ilDB->unlockTables();
330  }
331  return true;
332  }
333 
340  public function moveTree($a_source_id, $a_target_id, $a_position)
341  {
342  global $ilDB;
343 
344  if ($this->getTree()->__isMainTree())
345  {
346  $ilDB->lockTables(
347  array(
348  0 => array('name' => 'tree', 'type' => ilDB::LOCK_WRITE)));
349  }
350 
351  // Receive node infos for source and target
352  $ilDB->setLimit(2);
353  $res = $ilDB->query(
354  'SELECT depth, child, parent, path FROM ' . $this->getTree()->getTreeTable() . ' '.
355  'WHERE ' . $ilDB->in('child', array($a_source_id, $a_target_id), false, 'integer') . ' '.
356  'AND tree = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer')
357  );
358 
359  // Check in tree
360  if ($ilDB->numRows($res) != 2)
361  {
362  if ($this->getTree()->__isMainTree())
363  {
364  $ilDB->unlockTables();
365  }
366  $GLOBALS['ilLog']->logStack();
367  $GLOBALS['ilLog']->write(__METHOD__.': Objects not found in tree');
368  throw new InvalidArgumentException('Error moving subtree');
369  }
370 
371  while ($row = $ilDB->fetchObject($res))
372  {
373  if ($row->child == $a_source_id)
374  {
375  $source_path = $row->path;
376  $source_depth = $row->depth;
377  $source_parent = $row->parent;
378  }
379  else
380  {
381  $target_path = $row->path;
382  $target_depth = $row->depth;
383  }
384  }
385 
386  if ($target_depth >= $source_depth)
387  {
388  // We move nodes deeper into the tree. Therefore we need to
389  // check whether we might exceed the maximal path length.
390  // We use FOR UPDATE here, because we don't want anyone to
391  // insert new nodes while we move the subtree.
392 
393  $res = $ilDB->queryF(
394  'SELECT MAX(depth) max_depth '.
395  'FROM ' . $this->getTree()->getTreeTable() . ' '.
396  'WHERE path BETWEEN %s AND %s'.' '.
397  'AND tree = %s ',
398  array('text', 'text', 'integer'), array($source_path, $source_path . '.Z', $this->getTree()->getTreeId()));
399 
400  $row = $ilDB->fetchObject($res);
401 
402  if ($row->max_depth - $source_depth + $target_depth + 1 > $this->getMaximumPossibleDepth())
403  {
404  if ($this->getTree()->__isMainTree())
405  {
406  $ilDB->unlockTables();
407  }
408  $GLOBALS['ilLog']->logStack();
409  $GLOBALS['ilLog']->write(__METHOD__.': Objects not found in tree');
410  throw new ilInvalidTreeStructureException('Maximum tree depth exceeded');
411  }
412  }
413  // Check target not child of source
414  if (substr($target_path . '.', 0, strlen($source_path) . '.') == $source_path . '.')
415  {
416  if ($this->getTree()->__isMainTree())
417  {
418  $ilDB->unlockTables();
419  }
420  $GLOBALS['ilLog']->logStack();
421  $GLOBALS['ilLog']->write(__METHOD__.': Target is child of source');
422  throw new ilInvalidArgumentException('Error moving subtree: target is child of source');
423  }
424  $depth_diff = $target_depth - $source_depth + 1;
425 
426  // move subtree:
427  $query = '
428  UPDATE ' . $this->getTree()->getTreeTable() . '
429  SET parent = CASE WHEN parent = ' . $ilDB->quote($source_parent, 'integer') . '
430  THEN ' . $ilDB->quote($a_target_id, 'integer') . '
431  ELSE parent END,
432 
433  path = ' . $ilDB->concat(array(
434  array($ilDB->quote($target_path, 'text'), 'text'),
435  array($ilDB->substr('path', strrpos('.' . $source_path, '.')), 'text'))) . ' ,
436 
437  depth = depth + ' . $ilDB->quote($depth_diff, 'integer') . '
438 
439  WHERE path BETWEEN ' . $ilDB->quote($source_path, 'text') . '
440  AND ' . $ilDB->quote($source_path . '.Z', 'text') . '
441 
442  AND tree = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer');
443 
444  $GLOBALS['ilLog']->write(__METHOD__.': query is ' . $query);
445 
446 
447  $ilDB->manipulate($query);
448  if ($this->getTree()->__isMainTree())
449  {
450  $ilDB->unlockTables();
451  }
452  return true;
453  }
454 
455 
456  public static function createFromParentReleation()
457  {
458  global $ilDB;
459 
460  $r = $ilDB->queryF('SELECT DISTINCT * FROM tree WHERE parent = %s', array('integer'), array(0));
461 
462  while ($row = $ilDB->fetchAssoc($r))
463  {
464  $success = self::createMaterializedPath(0, '');
465 
466  if ($success !== true)
467  {
468  }
469  }
470  }
471 
472 
473  private static function createMaterializedPath($parent, $parentPath)
474  {
475  global $ilDB;
476  $q = ' UPDATE tree
477  SET path = CONCAT(COALESCE(' . $ilDB->quote($parentPath, 'text') . ', \'\'), COALESCE(child, \'\'))
478  WHERE parent = %s';
479  $r = $ilDB->manipulateF($q, array('integer'), array($parent));
480 
481  $r = $ilDB->queryF('SELECT child FROM tree WHERE parent = %s', array('integer'), array($parent));
482 
483  while ($row = $ilDB->fetchAssoc($r))
484  {
485  self::createMaterializedPath($row['child'], $parentPath . $row['child'] . '.');
486  }
487 
488  return true;
489  }
490 
491  public function getSubtreeInfo($a_endnode_id)
492  {
493  global $ilDB;
494 
495  // This is an optimization without the temporary tables become too big for our system.
496  // The idea is to use a subquery to join and filter the trees, and only the result
497  // is joined to obj_reference and obj_data.
498 
499  $query = "SELECT t2.child child, type, t2.path path " .
500  "FROM " . $this->getTree()->getTreeTable() . " t1 " .
501  "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.path BETWEEN t1.path AND CONCAT(t1.path, '.Z')) " .
502  "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
503  "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
504  "WHERE t1.child = " . $ilDB->quote($a_endnode_id, 'integer') . " " .
505  "AND t1." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
506  "AND t2." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
507  "ORDER BY t2.path";
508 
509 
510  $res = $ilDB->query($query);
511  $nodes = array();
512  while ($row = $res->fetchRow(DB_FETCHMODE_OBJECT))
513  {
514  #$nodes[$row->child]['lft'] = $row->lft;
515  #$nodes[$row->child]['rgt'] = $row->rgt;
516  $nodes[$row->child]['child'] = $row->child;
517  $nodes[$row->child]['type'] = $row->type;
518  $nodes[$row->child]['path'] = $row->path;
519  }
520 
521  $depth_first_compare = function($a, $b)
522  {
523  $a_exploded = explode('.', $a['path']);
524  #$GLOBALS['ilLog']->write(__METHOD__.': '.print_r($a_exploded,TRUE));
525  $b_exploded = explode('.', $b['path']);
526 
527  $a_padded = '';
528  foreach($a_exploded as $num)
529  {
530  $a_padded .= (str_pad((string) $num, 14,'0', STR_PAD_LEFT));
531  }
532  $b_padded = '';
533  foreach($b_exploded as $num)
534  {
535  $b_padded .= (str_pad((string) $num, 14, '0', STR_PAD_LEFT));
536  }
537  #$GLOBALS['ilLog']->write(__METHOD__.': '.$a_padded);
538  #$GLOBALS['ilLog']->write(__METHOD__.': '.$a_padded);
539  return strcasecmp($a_padded, $b_padded);
540  };
541 
542  #$GLOBALS['ilLog']->write(__METHOD__.': '.print_r($nodes,TRUE));
543 
544  uasort($nodes,$depth_first_compare);
545 
546  #$GLOBALS['ilLog']->write(__METHOD__.': '.print_r($nodes,TRUE));
547 
548  return (array) $nodes;
549  }
550 }
551 
552 ?>