class.ilMaterializedPathTree.php

Go to the documentation of this file.

<?php
/* Copyright (c) 1998-2009 ILIAS open source, Extended GPL, see docs/LICENSE */

include_once './Services/Tree/interfaces/interface.ilTreeImplementation.php';

class ilMaterializedPathTree implements ilTreeImplementation
{
    private $maximum_possible_depth = 100;
    private $tree = null;
    
    public function __construct(ilTree $a_tree)
    {
        $this->tree = $a_tree;
    }
    
    
    protected function getMaximumPossibleDepth()
    {
        return $this->maximum_possible_depth;
    }

    public function getTree()
    {
        return $this->tree;
    }
    
    public function getSubTreeIds($a_node_id)
    {
        global $ilDB;
        
        $node = $this->getTree()->getNodeTreeData($a_node_id);
        $query = 'SELECT child FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE path BETWEEN ' .
                $ilDB->quote($node['path'], 'text') . ' AND ' .
                $ilDB->quote($node['path'] . '.Z', 'text') . ' ' .
                'AND child != %s ' .
                'AND ' . $this->getTree()->getTreePk() . ' = %s';
        
        $res = $ilDB->queryF(
            $query,
            array('integer', 'integer'),
            array($a_node_id, $this->getTree()->getTreeId())
        );
        while ($row = $ilDB->fetchAssoc($res)) {
            $childs[] = $row['child'];
        }
        return $childs ? $childs : array();
    }

    public function getRelation($a_node_a, $a_node_b)
    {
        if ($a_node_a['child'] == $a_node_b['child']) {
            ilLoggerFactory::getLogger('tree')->debug('EQUALS');
            return ilTree::RELATION_EQUALS;
        }
        if (stripos($a_node_a['path'], $a_node_b['path'] . '.') === 0) {
            ilLoggerFactory::getLogger('tree')->debug('CHILD');
            return ilTree::RELATION_CHILD;
        }
        if (stripos($a_node_b['path'], $a_node_a['path'] . '.') === 0) {
            ilLoggerFactory::getLogger('tree')->debug('PARENT');
            return ilTree::RELATION_PARENT;
        }
        $path_a = substr($a_node_a['path'], 0, strrpos($a_node_a['path'], '.'));
        $path_b = substr($a_node_b['path'], 0, strrpos($a_node_b['path'], '.'));

        ilLoggerFactory::getLogger('tree')->debug('Comparing ' . $path_a . ' ' . 'with ' . $path_b);

        if ($a_node_a['path'] and (strcmp($path_a, $path_b) === 0)) {
            ilLoggerFactory::getLogger('tree')->debug('SIBLING');
            return ilTree::RELATION_SIBLING;
        }

        ilLoggerFactory::getLogger('tree')->debug('NONE');
        return ilTree::RELATION_NONE;
    }

    public function getSubTreeQuery($a_node, $a_types = '', $a_force_join_reference = true, $a_fields = array())
    {
        global $ilDB;
        
        $type_str = '';
        if (is_array($a_types)) {
            if ($a_types) {
                $type_str = "AND " . $ilDB->in($this->getTree()->getObjectDataTable() . ".type", $a_types, false, "text");
            }
        } elseif (strlen($a_types)) {
            $type_str = "AND " . $this->getTree()->getObjectDataTable() . ".type = " . $ilDB->quote($a_types, "text");
        }

        $join = '';
        if ($type_str or $a_force_join_reference) {
            $join = $this->getTree()->buildJoin();
        }
        
        $fields = '* ';
        if (count($a_fields)) {
            $fields = implode(',', $a_fields);
        }

        // @todo order by
        $query = 'SELECT ' .
                $fields . ' ' .
                'FROM ' . $this->getTree()->getTreeTable() . ' ' .
                $join . ' ' .
                'WHERE ' . $this->getTree()->getTreeTable() . '.path ' .
                'BETWEEN ' .
                $ilDB->quote($a_node['path'], 'text') . ' AND ' .
                $ilDB->quote($a_node['path'] . '.Z', 'text') . ' ' .
                'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . ' ' .
                $type_str . ' ' .
                'ORDER BY ' . $this->getTree()->getTreeTable() . '.path';
        
        return $query;
    }
    
    public function getPathIds($a_endnode, $a_startnode = 0)
    {
        global $ilDB;
        
        $ilDB->setLimit(1);
        $query = 'SELECT path FROM ' . $this->getTree()->getTreeTable() . ' ' .
            'WHERE child = ' . $ilDB->quote($a_endnode, 'integer') . ' ';
        $res = $ilDB->query($query);

        $path = null;
        while ($row = $ilDB->fetchAssoc($res)) {
            $path = $row['path'];
        }

        $pathIds = explode('.', $path);

        if ($a_startnode != 0) {
            while (count($pathIds) > 0 && $pathIds[0] != $a_startnode) {
                array_shift($pathIds);
            }
        }
        return $pathIds;
    }
    
    public function insertNode($a_node_id, $a_parent_id, $a_pos)
    {
        global $ilDB;

        $insert_node_callable = function (ilDBInterface $ilDB) use ($a_node_id, $a_parent_id, $a_pos) {
            // get path and depth of parent
            $ilDB->setLimit(1);

            $res = $ilDB->queryF(
                'SELECT parent, depth, path FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE child = %s ' . ' ' .
                'AND ' . $this->getTree()->getTreePk() . ' = %s',
                array('integer', 'integer'),
                array($a_parent_id, $this->getTree()->getTreeId())
            );


            $r = $ilDB->fetchObject($res);

            if ($r->parent === null) {
                ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
                throw new ilInvalidTreeStructureException('Parent node not found in tree');
            }

            if ($r->depth >= $this->getMaximumPossibleDepth()) {
                ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR);
                throw new ilInvalidTreeStructureException('Maximum tree depth exceeded');
            }

            $parentPath = $r->path;
            $depth = $r->depth + 1;
            $lft = 0;
            $rgt = 0;


            $ilDB->insert($this->getTree()->getTreeTable(), array($this->getTree()->getTreePk() => array('integer', $this->getTree()->getTreeId()),
                'child' => array('integer', $a_node_id),
                'parent' => array('integer', $a_parent_id),
                'lft' => array('integer', $lft),
                'rgt' => array('integer', $rgt),
                'depth' => array('integer', $depth),
                'path' => array('text', $parentPath . "." . $a_node_id)));
        };
         
        // use ilAtomQuery to lock tables if tree is main tree
        // otherwise just call this closure without locking
        if ($this-> getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock("tree");

            $ilAtomQuery->addQueryCallable($insert_node_callable);

            $ilAtomQuery->run();
        } else {
            $insert_node_callable($ilDB);
        }
    }
    

    public function deleteTree($a_node_id)
    {
        global $ilDB;
        $delete_tree_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
            $query = 'SELECT * FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE ' . $this->getTree()->getTreeTable() . '.child = %s ' .
                'AND ' . $this->getTree()->getTreeTable() . '.' . $this->getTree()->getTreePk() . ' = %s ';
            $res = $ilDB->queryF($query, array('integer','integer'), array(
                $a_node_id,
                $this->getTree()->getTreeId()));
            $row = $ilDB->fetchAssoc($res);

            $query = 'DELETE FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE path BETWEEN ' . $ilDB->quote($row['path'], 'text') . ' ' .
                'AND ' . $ilDB->quote($row['path'] . '.Z', 'text') . ' ' .
                'AND ' . $this->getTree()->getTreePk() . ' = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer');
            $ilDB->manipulate($query);
        };

        // get lft and rgt values. Don't trust parameter lft/rgt values of $a_node
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock('tree');
            $ilAtomQuery->addQueryCallable($delete_tree_callable);
            $ilAtomQuery->run();
        } else {
            $delete_tree_callable($ilDB);
        }

        return true;
    }
    
    public function moveToTrash($a_node_id)
    {
        global $ilDB;

        $move_to_trash_callable = function (ilDBInterface $ilDB) use ($a_node_id) {
            $node = $this->getTree()->getNodeTreeData($a_node_id);

            // Set the nodes deleted (negative tree id)
            $ilDB->manipulateF(
                '
                                UPDATE ' . $this->getTree()->getTreeTable() . ' ' .
                'SET tree = %s' . ' ' .
                'WHERE ' . $this->getTree()->getTreePk() . ' = %s ' .
                'AND path BETWEEN %s AND %s',
                array('integer', 'integer', 'text', 'text'),
                array(-$a_node_id, $this->getTree()->getTreeId(), $node['path'], $node['path'] . '.Z')
            );
        };

        // use ilAtomQuery to lock tables if tree is main tree
        // otherwise just call this closure without locking
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock("tree");

            $ilAtomQuery->addQueryCallable($move_to_trash_callable);

            $ilAtomQuery->run();
        } else {
            $move_to_trash_callable($ilDB);
        }

        return true;
    }
    
    public function moveTree($a_source_id, $a_target_id, $a_position)
    {
        global $ilDB;

        $move_tree_callable = function (ilDBInterface $ilDB) use ($a_source_id, $a_target_id, $a_position) {
            // Receive node infos for source and target
            $ilDB->setLimit(2);

            $res = $ilDB->query(
                'SELECT depth, child, parent, path FROM ' . $this->getTree()->getTreeTable() . ' ' .
                'WHERE ' . $ilDB->in('child', array($a_source_id, $a_target_id), false, 'integer') . ' ' .
                'AND tree = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer')
            );

            // Check in tree
            if ($ilDB->numRows($res) != 2) {
                ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
                throw new InvalidArgumentException('Error moving subtree');
            }

            while ($row = $ilDB->fetchObject($res)) {
                if ($row->child == $a_source_id) {
                    $source_path = $row->path;
                    $source_depth = $row->depth;
                    $source_parent = $row->parent;
                } else {
                    $target_path = $row->path;
                    $target_depth = $row->depth;
                }
            }

            if ($target_depth >= $source_depth) {
                // We move nodes deeper into the tree. Therefore we need to
                // check whether we might exceed the maximal path length.
                // We use FOR UPDATE here, because we don't want anyone to
                // insert new nodes while we move the subtree.

                $res = $ilDB->queryF(
                    'SELECT  MAX(depth) max_depth ' .
                    'FROM    ' . $this->getTree()->getTreeTable() . ' ' .
                    'WHERE   path BETWEEN %s AND %s' . ' ' .
                    'AND     tree = %s ',
                    array('text', 'text', 'integer'),
                    array($source_path, $source_path . '.Z', $this->getTree()->getTreeId())
                );

                $row = $ilDB->fetchObject($res);

                if ($row->max_depth - $source_depth + $target_depth + 1 > $this->getMaximumPossibleDepth()) {
                    ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Objects not found in tree');
                    throw new ilInvalidTreeStructureException('Maximum tree depth exceeded');
                }
            }
            // Check target not child of source
            if (substr($target_path . '.', 0, strlen($source_path) . '.') == $source_path . '.') {
                ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::ERROR, 'Target is child of source');
                throw new InvalidArgumentException('Error moving subtree: target is child of source');
            }
            $depth_diff = $target_depth - $source_depth + 1;

            // move subtree:
            $query = '
                UPDATE ' . $this->getTree()->getTreeTable() . '
                SET parent = CASE WHEN parent = ' . $ilDB->quote($source_parent, 'integer') . '
                             THEN ' . $ilDB->quote($a_target_id, 'integer') . '
                             ELSE parent END,

                    path = ' . $ilDB->concat(array(
                    array($ilDB->quote($target_path, 'text'), 'text'),
                    array($ilDB->substr('path', strrpos('.' . $source_path, '.')), 'text'))) . ' ,

                    depth = depth + ' . $ilDB->quote($depth_diff, 'integer') . '

                WHERE path  BETWEEN ' . $ilDB->quote($source_path, 'text') . '
                            AND ' . $ilDB->quote($source_path . '.Z', 'text') . '

                AND tree = ' . $ilDB->quote($this->getTree()->getTreeId(), 'integer');

            ilLoggerFactory::getLogger('tree')->debug('Query is ' . $query);

            $ilDB->manipulate($query);
        };

        
        if ($this->getTree()->__isMainTree()) {
            $ilAtomQuery = $ilDB->buildAtomQuery();
            $ilAtomQuery->addTableLock("tree");
            $ilAtomQuery->addQueryCallable($move_tree_callable);
            $ilAtomQuery->run();
        } else {
            $move_tree_callable($ilDB);
        }

        return true;
    }
    
    
    public static function createFromParentReleation()
    {
        global $ilDB;

        $r = $ilDB->queryF('SELECT DISTINCT * FROM tree WHERE parent = %s', array('integer'), array(0));

        while ($row = $ilDB->fetchAssoc($r)) {
            $success = self::createMaterializedPath(0, '');

            if ($success !== true) {
            }
        }
    }

    private static function createMaterializedPath($parent, $parentPath)
    {
        global $ilDB;
        $q = ' UPDATE tree
                        SET path = CONCAT(COALESCE(' . $ilDB->quote($parentPath, 'text') . ', \'\'), COALESCE( ' . $ilDB->cast("child", "text") . ' , \'\'))
                        WHERE parent = %s';
        $r = $ilDB->manipulateF($q, array('integer'), array($parent));

        $r = $ilDB->queryF('SELECT child FROM tree WHERE parent = %s', array('integer'), array($parent));

        while ($row = $ilDB->fetchAssoc($r)) {
            self::createMaterializedPath($row['child'], $parentPath . $row['child'] . '.');
        }

        return true;
    }

    public function getSubtreeInfo($a_endnode_id)
    {
        global $ilDB;
        
        // This is an optimization without the temporary tables become too big for our system.
        // The idea is to use a subquery to join and filter the trees, and only the result
        // is joined to obj_reference and obj_data.
        
        $query = "SELECT t2.child child, type, t2.path path " .
                "FROM " . $this->getTree()->getTreeTable() . " t1 " .
                "JOIN " . $this->getTree()->getTreeTable() . " t2 ON (t2.path BETWEEN t1.path AND CONCAT(t1.path, '.Z')) " .
                "JOIN " . $this->getTree()->getTableReference() . " obr ON t2.child = obr.ref_id " .
                "JOIN " . $this->getTree()->getObjectDataTable() . " obd ON obr.obj_id = obd.obj_id " .
                "WHERE t1.child = " . $ilDB->quote($a_endnode_id, 'integer') . " " .
                "AND t1." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
                "AND t2." . $this->getTree()->getTreePk() . " = " . $ilDB->quote($this->getTree()->getTreeId(), 'integer') . " " .
                "ORDER BY t2.path";

        
        $res = $ilDB->query($query);
        $nodes = array();
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
            #$nodes[$row->child]['lft'] = $row->lft;
            #$nodes[$row->child]['rgt'] = $row->rgt;
            $nodes[$row->child]['child'] = $row->child;
            $nodes[$row->child]['type'] = $row->type;
            $nodes[$row->child]['path'] = $row->path;
        }
        
        $depth_first_compare = function ($a, $b) {
            $a_exploded = explode('.', $a['path']);
            #ilLoggerFactory::getLogger('tree')->debug(print_r($a_exploded,TRUE));
            $b_exploded = explode('.', $b['path']);
            
            $a_padded = '';
            foreach ($a_exploded as $num) {
                $a_padded .= (str_pad((string) $num, 14, '0', STR_PAD_LEFT));
            }
            $b_padded = '';
            foreach ($b_exploded as $num) {
                $b_padded .= (str_pad((string) $num, 14, '0', STR_PAD_LEFT));
            }

            #ilLoggerFactory::getLogger('tree')->debug($a_padded);
            return strcasecmp($a_padded, $b_padded);
        };

        #ilLoggerFactory::getLogger('tree')->debug(print_r($nodes,TRUE));
        
        uasort($nodes, $depth_first_compare);

        #ilLoggerFactory::getLogger('tree')->debug(print_r($nodes,TRUE));

        return (array) $nodes;
    }

    public function validateParentRelations()
    {
        global $ilDB;
        
        $query = 'select child from ' . $this->getTree()->getTreeTable() . ' child where not exists ' .
                '( ' .
                    'select child from ' . $this->getTree()->getTreeTable() . ' parent where child.parent = parent.child and ' .
                    '(child.path BETWEEN parent.path AND CONCAT(parent.path,' . $ilDB->quote('Z', 'text') . ') )' . ')' .
                'and ' . $this->getTree()->getTreePk() . ' = ' . $this->getTree()->getTreeId() . ' and child <> 1';
        $res = $ilDB->query($query);
        
        ilLoggerFactory::getLogger('tree')->debug($query);
        
        $failures = array();
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
            $failures[] = $row[$this->getTree()->getTreePk()];
        }
        return $failures;
    }
}