ILIAS  release_5-1 Revision 5.0.0-5477-g43f3e3fab5f
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
4include_once './Services/Tree/interfaces/interface.ilTreeImplementation.php';
5
16class 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(stripos($a_node_a['path'], $a_node_b['path']. '.') === 0)
90 {
91 $GLOBALS['ilLog']->write(__METHOD__.': CHILD');
92 return ilTree::RELATION_CHILD;
93 }
94 if(stripos($a_node_b['path'], $a_node_a['path'] . '.') === 0)
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
555 public function validateParentRelations()
556 {
557 global $ilDB;
558
559 $query = 'select child from '.$this->getTree()->getTreeTable().' child where not exists '.
560 '( '.
561 'select child from '.$this->getTree()->getTreeTable().' parent where child.parent = parent.child and '.
562 '(child.path BETWEEN parent.path AND CONCAT(parent.path,'.$ilDB->quote('Z','text').') )'. ')'.
563 'and '.$this->getTree()->getTreePk().' = '.$this->getTree()->getTreeId().' and child <> 1';
564 $res = $ilDB->query($query);
565
566 ilLoggerFactory::getLogger('tree')->debug($query);
567
568 $failures = array();
569 while($row = $res->fetchRow(DB_FETCHMODE_ASSOC))
570 {
571 $failures[] = $row[$this->getTree()->getTreePk()];
572 }
573 return $failures;
574 }
575}
576
577?>
$success
$success
Definition: Utf8Test.php:87
DB_FETCHMODE_ASSOC
const DB_FETCHMODE_ASSOC
Definition: class.ilDB.php:10
DB_FETCHMODE_OBJECT
const DB_FETCHMODE_OBJECT
Definition: class.ilDB.php:11
ilDB\LOCK_WRITE
const LOCK_WRITE
Definition: class.ilDB.php:30
ilInvalidTreeStructureException
Thrown if invalid tree strucutes are found.
Definition: class.ilInvalidTreeStructureException.php:17
ilLoggerFactory\getLogger
static getLogger($a_component_id)
Get component logger.
Definition: class.ilLoggerFactory.php:82
ilMaterializedPathTree
Base class for materialize path based trees Based on implementation of Werner Randelshofer.
Definition: class.ilMaterializedPathTree.php:17
ilMaterializedPathTree\moveTree
moveTree($a_source_id, $a_target_id, $a_position)
move source subtree to target node
Definition: class.ilMaterializedPathTree.php:340
ilMaterializedPathTree\getPathIds
getPathIds($a_endnode, $a_startnode=0)
Get path ids.
Definition: class.ilMaterializedPathTree.php:169
ilMaterializedPathTree\validateParentRelations
validateParentRelations()
Validaate parent relations.
Definition: class.ilMaterializedPathTree.php:555
ilMaterializedPathTree\getSubTreeIds
getSubTreeIds($a_node_id)
Get subtree ids.
Definition: class.ilMaterializedPathTree.php:53
ilMaterializedPathTree\deleteTree
deleteTree($a_node_id)
Delete a subtree.
Definition: class.ilMaterializedPathTree.php:273
ilMaterializedPathTree\getSubtreeInfo
getSubtreeInfo($a_endnode_id)
Get subtree info lft, rgt, path, child, type.
Definition: class.ilMaterializedPathTree.php:491
ilMaterializedPathTree\getSubTreeQuery
getSubTreeQuery($a_node, $a_types='', $a_force_join_reference=true, $a_fields=array())
Get subtree query.
Definition: class.ilMaterializedPathTree.php:119
ilMaterializedPathTree\__construct
__construct(ilTree $a_tree)
Constructor.
Definition: class.ilMaterializedPathTree.php:25
ilMaterializedPathTree\getMaximumPossibleDepth
getMaximumPossibleDepth()
Get maximum possible depth.
Definition: class.ilMaterializedPathTree.php:35
ilMaterializedPathTree\moveToTrash
moveToTrash($a_node_id)
Move subtree to trash.
Definition: class.ilMaterializedPathTree.php:291
ilMaterializedPathTree\getRelation
getRelation($a_node_a, $a_node_b)
Get relation of two nodes.
Definition: class.ilMaterializedPathTree.php:82
ilMaterializedPathTree\insertNode
insertNode($a_node_id, $a_parent_id, $a_pos)
Insert new node under parent node.
Definition: class.ilMaterializedPathTree.php:202
ilMaterializedPathTree\createMaterializedPath
static createMaterializedPath($parent, $parentPath)
Definition: class.ilMaterializedPathTree.php:473
ilTree
Tree class data representation in hierachical trees using the Nested Set Model with Gaps by Joe Celco...
Definition: class.ilTree.php:25
ilTree\RELATION_EQUALS
const RELATION_EQUALS
Definition: class.ilTree.php:33
ilTree\RELATION_PARENT
const RELATION_PARENT
Definition: class.ilTree.php:31
ilTree\RELATION_NONE
const RELATION_NONE
Definition: class.ilTree.php:34
ilTree\RELATION_SIBLING
const RELATION_SIBLING
Definition: class.ilTree.php:32
ilTree\RELATION_CHILD
const RELATION_CHILD
Definition: class.ilTree.php:30
$r
$r
Definition: example_031.php:79
$GLOBALS
$GLOBALS['PHPCAS_CLIENT']
This global variable is used by the interface class phpCAS.
Definition: CAS.php:276
ilTreeImplementation
Interface for tree implementations Currrently nested set or materialize path.
Definition: interface.ilTreeImplementation.php:15
$path
$path
Definition: index.php:22
$ilDB
global $ilDB
Definition: storeScorm2004.php:19