ILIAS  release_5-0 Revision 5.0.0-1144-gc4397b1f87
ilMaterializedPathTree Class Reference

Base class for materialize path based trees Based on implementation of Werner Randelshofer. More...

+ Inheritance diagram for ilMaterializedPathTree:
+ Collaboration diagram for ilMaterializedPathTree:

Public Member Functions

 __construct (ilTree $a_tree)
 Constructor. More...
 
 getTree ()
 Get tree object. More...
 
 getSubTreeIds ($a_node_id)
 Get subtree ids. More...
 
 getRelation ($a_node_a, $a_node_b)
 Get relation of two nodes. More...
 
 getSubTreeQuery ($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
 Get subtree query. More...
 
 getPathIds ($a_endnode, $a_startnode=0)
 Get path ids. More...
 
 insertNode ($a_node_id, $a_parent_id, $a_pos)
 Insert new node under parent node. More...
 
 deleteTree ($a_node_id)
 Delete a subtree. More...
 
 moveToTrash ($a_node_id)
 Move subtree to trash. More...
 
 moveTree ($a_source_id, $a_target_id, $a_position)
 move source subtree to target node More...
 
 getSubtreeInfo ($a_endnode_id)
 Get subtree info lft, rgt, path, child, type. More...
 

Static Public Member Functions

static createFromParentReleation ()
 

Protected Member Functions

 getMaximumPossibleDepth ()
 Get maximum possible depth. More...
 

Static Private Member Functions

static createMaterializedPath ($parent, $parentPath)
 

Private Attributes

 $maximum_possible_depth = 100
 
 $tree = NULL
 

Detailed Description

Base class for materialize path based trees Based on implementation of Werner Randelshofer.

Author
Stefan Meyer meyer.nosp@m.@lei.nosp@m.fos.c.nosp@m.om
Version
$Id$

Definition at line 16 of file class.ilMaterializedPathTree.php.

Constructor & Destructor Documentation

◆ __construct()

ilMaterializedPathTree::__construct ( ilTree  $a_tree)

Constructor.

Parameters
ilTree$tree

Definition at line 25 of file class.ilMaterializedPathTree.php.

26  {
27  $this->tree = $a_tree;
28  }

Member Function Documentation

◆ createFromParentReleation()

static ilMaterializedPathTree::createFromParentReleation ( )
static

Definition at line 456 of file class.ilMaterializedPathTree.php.

References $ilDB, $r, $row, and $success.

Referenced by ilSetupGUI\switchTree().

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  }
$success
Definition: Utf8Test.php:87
global $ilDB
$r
+ Here is the caller graph for this function:

◆ createMaterializedPath()

static ilMaterializedPathTree::createMaterializedPath (   $parent,
  $parentPath 
)
staticprivate

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

References $ilDB, $r, and $row.

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  }
global $ilDB
$r

◆ deleteTree()

ilMaterializedPathTree::deleteTree (   $a_node_id)

Delete a subtree.

Parameters
int$a_node_id

Implements ilTreeImplementation.

Definition at line 273 of file class.ilMaterializedPathTree.php.

References $ilDB, $query, and getTree().

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  }
global $ilDB
+ Here is the call graph for this function:

◆ getMaximumPossibleDepth()

ilMaterializedPathTree::getMaximumPossibleDepth ( )
protected

Get maximum possible depth.

Returns
type

Definition at line 35 of file class.ilMaterializedPathTree.php.

References $maximum_possible_depth.

◆ getPathIds()

ilMaterializedPathTree::getPathIds (   $a_endnode,
  $a_startnode = 0 
)

Get path ids.

Parameters
int$a_endnode
int$a_startnode

Implements ilTreeImplementation.

Definition at line 169 of file class.ilMaterializedPathTree.php.

References $ilDB, $path, $query, $res, $row, and getTree().

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  }
$path
Definition: index.php:22
global $ilDB
+ Here is the call graph for this function:

◆ getRelation()

ilMaterializedPathTree::getRelation (   $a_node_a,
  $a_node_b 
)

Get relation of two nodes.

Parameters
type$a_node_a
type$a_node_b

Implements ilTreeImplementation.

Definition at line 82 of file class.ilMaterializedPathTree.php.

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

83  {
84  if($a_node_a['child'] == $a_node_b['child'])
85  {
86  $GLOBALS['ilLog']->write(__METHOD__.': EQUALS');
88  }
89  if(stripos($a_node_a['path'], $a_node_b['path']. '.') === 0)
90  {
91  $GLOBALS['ilLog']->write(__METHOD__.': CHILD');
93  }
94  if(stripos($a_node_b['path'], $a_node_a['path'] . '.') === 0)
95  {
96  $GLOBALS['ilLog']->write(__METHOD__.': 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');
107  }
108 
109  $GLOBALS['ilLog']->write(__METHOD__.': NONE');
110  return ilTree::RELATION_NONE;
111  }
const RELATION_PARENT
$GLOBALS['ct_recipient']
const RELATION_EQUALS
const RELATION_CHILD
const RELATION_NONE
const RELATION_SIBLING

◆ getSubTreeIds()

ilMaterializedPathTree::getSubTreeIds (   $a_node_id)

Get subtree ids.

Parameters
type$a_node_id

Implements ilTreeImplementation.

Definition at line 53 of file class.ilMaterializedPathTree.php.

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

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  }
global $ilDB
+ Here is the call graph for this function:

◆ getSubtreeInfo()

ilMaterializedPathTree::getSubtreeInfo (   $a_endnode_id)

Get subtree info lft, rgt, path, child, type.

Returns
array

Implements ilTreeImplementation.

Definition at line 491 of file class.ilMaterializedPathTree.php.

References $ilDB, $query, $res, $row, DB_FETCHMODE_OBJECT, and getTree().

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  }
const DB_FETCHMODE_OBJECT
Definition: class.ilDB.php:11
global $ilDB
+ Here is the call graph for this function:

◆ getSubTreeQuery()

ilMaterializedPathTree::getSubTreeQuery (   $a_node,
  $a_types = '',
  $a_force_join_reference = true,
  $a_fields = array() 
)

Get subtree query.

Parameters
type$a_node
type$a_types

Implements ilTreeImplementation.

Definition at line 119 of file class.ilMaterializedPathTree.php.

References $ilDB, $query, and getTree().

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  }
global $ilDB
+ Here is the call graph for this function:

◆ getTree()

ilMaterializedPathTree::getTree ( )

Get tree object.

Returns
ilTree $tree

Definition at line 44 of file class.ilMaterializedPathTree.php.

References $tree.

Referenced by deleteTree(), getPathIds(), getSubTreeIds(), getSubtreeInfo(), getSubTreeQuery(), insertNode(), moveToTrash(), and moveTree().

+ Here is the caller graph for this function:

◆ insertNode()

ilMaterializedPathTree::insertNode (   $a_node_id,
  $a_parent_id,
  $a_pos 
)

Insert new node under parent node.

Parameters
type$a_node_id
type$a_parent_id
type$a_pos

Implements ilTreeImplementation.

Definition at line 202 of file class.ilMaterializedPathTree.php.

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

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  }
Thrown if invalid tree strucutes are found.
$GLOBALS['ct_recipient']
const LOCK_WRITE
Definition: class.ilDB.php:30
global $ilDB
$r
+ Here is the call graph for this function:

◆ moveToTrash()

ilMaterializedPathTree::moveToTrash (   $a_node_id)

Move subtree to trash.

Parameters
type$a_node_id

Implements ilTreeImplementation.

Definition at line 291 of file class.ilMaterializedPathTree.php.

References $ilDB, getTree(), and ilDB\LOCK_WRITE.

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  }
const LOCK_WRITE
Definition: class.ilDB.php:30
global $ilDB
+ Here is the call graph for this function:

◆ moveTree()

ilMaterializedPathTree::moveTree (   $a_source_id,
  $a_target_id,
  $a_position 
)

move source subtree to target node

Parameters
type$a_source_id
type$a_target_id
type$a_position

Implements ilTreeImplementation.

Definition at line 340 of file class.ilMaterializedPathTree.php.

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

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  }
Thrown if invalid tree strucutes are found.
$GLOBALS['ct_recipient']
const LOCK_WRITE
Definition: class.ilDB.php:30
global $ilDB
+ Here is the call graph for this function:

Field Documentation

◆ $maximum_possible_depth

ilMaterializedPathTree::$maximum_possible_depth = 100
private

Definition at line 18 of file class.ilMaterializedPathTree.php.

Referenced by getMaximumPossibleDepth().

◆ $tree

ilMaterializedPathTree::$tree = NULL
private

Definition at line 19 of file class.ilMaterializedPathTree.php.

Referenced by getTree().


The documentation for this class was generated from the following file: