class.ilTree.php

Go to the documentation of this file.

<?php

declare(strict_types=1);
class ilTree
{
    public const TREE_TYPE_MATERIALIZED_PATH = 'mp';
    public const TREE_TYPE_NESTED_SET = 'ns';

    public const POS_LAST_NODE = -2;
    public const POS_FIRST_NODE = -1;

    public const RELATION_CHILD = 1;
    public const RELATION_PARENT = 2;
    public const RELATION_SIBLING = 3;
    public const RELATION_EQUALS = 4;
    public const RELATION_NONE = 5;

    protected const DEFAULT_LANGUAGE = 'en';
    protected const DEFAULT_GAP = 50;

    protected ilLogger $logger;
    protected ilDBInterface $db;
    protected ?ilAppEventHandler $eventHandler;

    private string $lang_code;

    protected int $root_id;

    protected int $tree_id;

    protected string $table_tree;

    protected string $table_obj_data;

    protected string $table_obj_reference;

    protected string $ref_pk;

    protected string $obj_pk;

    protected string $tree_pk;

    private int $gap;

    protected bool $use_cache;
    protected array $oc_preloaded = [];
    protected array $depth_cache = [];
    protected array $parent_cache = [];
    protected array $in_tree_cache = [];
    protected array $translation_cache = [];
    protected array $parent_type_cache = [];
    protected array $is_saved_cache = [];

    private ?ilTreeImplementation $tree_impl = null;

    private array $path_id_cache = [];

    public function __construct(
        int $a_tree_id,
        int $a_root_id = 0,
        ilDBInterface $db = null
    ) {
        global $DIC;

        $this->db = $db ?? $DIC->database();
        $this->logger = ilLoggerFactory::getLogger('tree');
        //$this->logger = $DIC->logger()->tree();
        if (isset($DIC['ilAppEventHandler'])) {
            $this->eventHandler = $DIC['ilAppEventHandler'];
        }

        $this->lang_code = self::DEFAULT_LANGUAGE;

        if (func_num_args() > 3) {
            $this->logger->error("Wrong parameter count!");
            $this->logger->logStack(ilLogLevel::ERROR);
            throw new InvalidArgumentException("Wrong parameter count!");
        }

        if ($a_root_id > 0) {
            $this->root_id = $a_root_id;
        } else {
            $this->root_id = ROOT_FOLDER_ID;
        }

        $this->tree_id = $a_tree_id;
        $this->table_tree = 'tree';
        $this->table_obj_data = 'object_data';
        $this->table_obj_reference = 'object_reference';
        $this->ref_pk = 'ref_id';
        $this->obj_pk = 'obj_id';
        $this->tree_pk = 'tree';

        $this->use_cache = true;

        // By default, we create gaps in the tree sequence numbering for 50 nodes
        $this->gap = self::DEFAULT_GAP;

        // init tree implementation
        $this->initTreeImplementation();
    }

    public static function lookupTreesForNode(int $node_id): array
    {
        global $DIC;

        $db = $DIC->database();

        $query = 'select tree from tree ' .
            'where child = ' . $db->quote($node_id, \ilDBConstants::T_INTEGER);
        $res = $db->query($query);

        $trees = [];
        while ($row = $res->fetchRow(\ilDBConstants::FETCHMODE_OBJECT)) {
            $trees[] = (int) $row->tree;
        }
        return $trees;
    }

    public function initTreeImplementation(): void
    {
        global $DIC;

        if (!$DIC->isDependencyAvailable('settings') || $DIC->settings()->getModule() != 'common') {
            $setting = new ilSetting('common');
        } else {
            $setting = $DIC->settings();
        }

        if ($this->__isMainTree()) {
            if ($setting->get('main_tree_impl', 'ns') == 'ns') {
                $this->tree_impl = new ilNestedSetTree($this);
            } else {
                $this->tree_impl = new ilMaterializedPathTree($this);
            }
        } else {
            $this->tree_impl = new ilNestedSetTree($this);
        }
    }

    public function getTreeImplementation(): ilTreeImplementation
    {
        return $this->tree_impl;
    }

    public function useCache(bool $a_use = true): void
    {
        $this->use_cache = $a_use;
    }

    public function isCacheUsed(): bool
    {
        return $this->__isMainTree() && $this->use_cache;
    }

    public function getDepthCache(): array
    {
        return $this->depth_cache;
    }

    public function getParentCache(): array
    {
        return $this->parent_cache;
    }

    protected function getLangCode(): string
    {
        return $this->lang_code;
    }

    public function initLangCode(): void
    {
        global $DIC;

        if ($DIC->offsetExists('ilUser')) {
            $this->lang_code = $DIC->user()->getCurrentLanguage() ?
                $DIC->user()->getCurrentLanguage() : self::DEFAULT_LANGUAGE;
        } else {
            $this->lang_code = self::DEFAULT_LANGUAGE;
        }
    }

    public function getTreeTable(): string
    {
        return $this->table_tree;
    }

    public function getObjectDataTable(): string
    {
        return $this->table_obj_data;
    }

    public function getTreePk(): string
    {
        return $this->tree_pk;
    }

    public function getTableReference(): string
    {
        return $this->table_obj_reference;
    }

    public function getGap(): int
    {
        return $this->gap;
    }

    public function resetInTreeCache(): void
    {
        $this->in_tree_cache = array();
    }

    public function setTableNames(
        string $a_table_tree,
        string $a_table_obj_data,
        string $a_table_obj_reference = ""
    ): void {
        $this->table_tree = $a_table_tree;
        $this->table_obj_data = $a_table_obj_data;
        $this->table_obj_reference = $a_table_obj_reference;

        // reconfigure tree implementation
        $this->initTreeImplementation();
    }

    public function setReferenceTablePK(string $a_column_name): void
    {
        $this->ref_pk = $a_column_name;
    }

    public function setObjectTablePK(string $a_column_name): void
    {
        $this->obj_pk = $a_column_name;
    }

    public function setTreeTablePK(string $a_column_name): void
    {
        $this->tree_pk = $a_column_name;
    }

    public function buildJoin(): string
    {
        if ($this->table_obj_reference) {
            // Use inner join instead of left join to improve performance
            return "JOIN " . $this->table_obj_reference . " ON " . $this->table_tree . ".child=" . $this->table_obj_reference . "." . $this->ref_pk . " " .
                "JOIN " . $this->table_obj_data . " ON " . $this->table_obj_reference . "." . $this->obj_pk . "=" . $this->table_obj_data . "." . $this->obj_pk . " ";
        } else {
            // Use inner join instead of left join to improve performance
            return "JOIN " . $this->table_obj_data . " ON " . $this->table_tree . ".child=" . $this->table_obj_data . "." . $this->obj_pk . " ";
        }
    }

    public function getRelation(int $a_node_a, int $a_node_b): int
    {
        return $this->getRelationOfNodes(
            $this->getNodeTreeData($a_node_a),
            $this->getNodeTreeData($a_node_b)
        );
    }

    public function getRelationOfNodes(array $a_node_a_arr, array $a_node_b_arr): int
    {
        return $this->getTreeImplementation()->getRelation($a_node_a_arr, $a_node_b_arr);
    }

    public function getChildIds(int $a_node): array
    {
        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE parent = ' . $this->db->quote($a_node, 'integer') . ' ' .
            'AND tree = ' . $this->db->quote($this->tree_id, 'integer' . ' ' .
                'ORDER BY lft');
        $res = $this->db->query($query);

        $childs = array();
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
            $childs[] = (int) $row->child;
        }
        return $childs;
    }

    public function getChilds(int $a_node_id, string $a_order = "", string $a_direction = "ASC"): array
    {
        global $DIC;

        $ilObjDataCache = $DIC['ilObjDataCache'];
        $ilUser = $DIC['ilUser'];

        // init childs
        $childs = [];

        // number of childs
        $count = 0;

        // init order_clause
        $order_clause = "";

        // set order_clause if sort order parameter is given
        if (!empty($a_order)) {
            $order_clause = "ORDER BY " . $a_order . " " . $a_direction;
        } else {
            $order_clause = "ORDER BY " . $this->table_tree . ".lft";
        }

        $query = sprintf(
            'SELECT * FROM ' . $this->table_tree . ' ' .
            $this->buildJoin() .
            "WHERE parent = %s " .
            "AND " . $this->table_tree . "." . $this->tree_pk . " = %s " .
            $order_clause,
            $this->db->quote($a_node_id, 'integer'),
            $this->db->quote($this->tree_id, 'integer')
        );

        $res = $this->db->query($query);

        if (!$count = $res->numRows()) {
            return [];
        }

        // get rows and object ids
        $rows = [];
        $obj_ids = [];
        while ($r = $this->db->fetchAssoc($res)) {
            $rows[] = $r;
            $obj_ids[] = (int) $r["obj_id"];
        }

        // preload object translation information
        if ($this->__isMainTree() && $this->isCacheUsed() && is_object($ilObjDataCache) &&
            is_object($ilUser) && $this->lang_code == $ilUser->getLanguage() && !isset($this->oc_preloaded[$a_node_id])) {
            //                  $ilObjDataCache->preloadTranslations($obj_ids, $this->lang_code);
            $ilObjDataCache->preloadObjectCache($obj_ids, $this->lang_code);
            $this->fetchTranslationFromObjectDataCache($obj_ids);
            $this->oc_preloaded[$a_node_id] = true;
        }

        foreach ($rows as $row) {
            $childs[] = $this->fetchNodeData($row);

            // Update cache of main tree
            if ($this->__isMainTree()) {
                #$GLOBALS['DIC']['ilLog']->write(__METHOD__.': Storing in tree cache '.$row['child'].' = true');
                $this->in_tree_cache[$row['child']] = $row['tree'] == 1;
            }
        }
        $childs[$count - 1]["last"] = true;
        return $childs;
    }

    public function getFilteredChilds(
        array $a_filter,
        int $a_node,
        string $a_order = "",
        string $a_direction = "ASC"
    ): array {
        $childs = $this->getChilds($a_node, $a_order, $a_direction);

        $filtered = [];
        foreach ($childs as $child) {
            if (!in_array($child["type"], $a_filter)) {
                $filtered[] = $child;
            }
        }
        return $filtered;
    }

    public function getChildsByType(int $a_node_id, string $a_type): array
    {
        if ($a_type == 'rolf' && $this->table_obj_reference) {
            // Performance optimization: A node can only have exactly one
            // role folder as its child. Therefore we don't need to sort the
            // results, and we can let the database know about the expected limit.
            $this->db->setLimit(1, 0);
            $query = sprintf(
                "SELECT * FROM " . $this->table_tree . " " .
                $this->buildJoin() .
                "WHERE parent = %s " .
                "AND " . $this->table_tree . "." . $this->tree_pk . " = %s " .
                "AND " . $this->table_obj_data . ".type = %s ",
                $this->db->quote($a_node_id, 'integer'),
                $this->db->quote($this->tree_id, 'integer'),
                $this->db->quote($a_type, 'text')
            );
        } else {
            $query = sprintf(
                "SELECT * FROM " . $this->table_tree . " " .
                $this->buildJoin() .
                "WHERE parent = %s " .
                "AND " . $this->table_tree . "." . $this->tree_pk . " = %s " .
                "AND " . $this->table_obj_data . ".type = %s " .
                "ORDER BY " . $this->table_tree . ".lft",
                $this->db->quote($a_node_id, 'integer'),
                $this->db->quote($this->tree_id, 'integer'),
                $this->db->quote($a_type, 'text')
            );
        }
        $res = $this->db->query($query);

        // init childs
        $childs = [];
        while ($row = $this->db->fetchAssoc($res)) {
            $childs[] = $this->fetchNodeData($row);
        }
        return $childs;
    }

    public function getChildsByTypeFilter(
        int $a_node_id,
        array $a_types,
        string $a_order = "",
        string $a_direction = "ASC"
    ): array {
        $filter = ' ';
        if ($a_types) {
            $filter = 'AND ' . $this->table_obj_data . '.type IN(' . implode(',', ilArrayUtil::quoteArray($a_types)) . ') ';
        }

        // set order_clause if sort order parameter is given
        if (!empty($a_order)) {
            $order_clause = "ORDER BY " . $a_order . " " . $a_direction;
        } else {
            $order_clause = "ORDER BY " . $this->table_tree . ".lft";
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            $this->buildJoin() .
            'WHERE parent = ' . $this->db->quote($a_node_id, 'integer') . ' ' .
            'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = ' . $this->db->quote(
                $this->tree_id,
                'integer'
            ) . ' ' .
            $filter .
            $order_clause;

        $res = $this->db->query($query);

        $childs = [];
        while ($row = $this->db->fetchAssoc($res)) {
            $childs[] = $this->fetchNodeData($row);
        }

        return $childs;
    }

    public function insertNodeFromTrash(
        int $a_source_id,
        int $a_target_id,
        int $a_tree_id,
        int $a_pos = self::POS_LAST_NODE,
        bool $a_reset_deleted_date = false
    ): void {
        if ($this->__isMainTree()) {
            if ($a_source_id <= 1 || $a_target_id <= 0) {
                $this->logger->logStack(ilLogLevel::WARNING);
                throw new InvalidArgumentException('Invalid parameter given for ilTree::insertNodeFromTrash');
            }
        }
        if ($this->isInTree($a_source_id)) {
            ilLoggerFactory::getLogger('tree')->error('Node already in tree');
            ilLoggerFactory::getLogger('tree')->logStack(ilLogLevel::WARNING);
            throw new InvalidArgumentException('Node already in tree.');
        }

        $query = 'DELETE from tree ' .
            'WHERE tree = ' . $this->db->quote($a_tree_id, 'integer') . ' ' .
            'AND child = ' . $this->db->quote($a_source_id, 'integer');
        $this->db->manipulate($query);

        $this->insertNode($a_source_id, $a_target_id, self::POS_LAST_NODE, $a_reset_deleted_date);
    }

    public function insertNode(
        int $a_node_id,
        int $a_parent_id,
        int $a_pos = self::POS_LAST_NODE,
        bool $a_reset_deletion_date = false
    ): void {
        // CHECK node_id and parent_id > 0 if in main tree
        if ($this->__isMainTree()) {
            if ($a_node_id <= 1 || $a_parent_id <= 0) {
                $message = sprintf(
                    'Invalid parameters! $a_node_id: %s $a_parent_id: %s',
                    $a_node_id,
                    $a_parent_id
                );
                $this->logger->logStack(ilLogLevel::ERROR, $message);
                throw new InvalidArgumentException($message);
            }
        }
        if ($this->isInTree($a_node_id)) {
            throw new InvalidArgumentException("Node " . $a_node_id . " already in tree " .
                $this->table_tree . "!");
        }

        $this->getTreeImplementation()->insertNode($a_node_id, $a_parent_id, $a_pos);

        $this->in_tree_cache[$a_node_id] = true;

        // reset deletion date
        if ($a_reset_deletion_date) {
            ilObject::_resetDeletedDate($a_node_id);
        }
        if (isset($this->eventHandler) && ($this->eventHandler instanceof ilAppEventHandler) && $this->__isMainTree()) {
            $this->eventHandler->raise(
                'Services/Tree',
                'insertNode',
                [
                    'tree' => $this->table_tree,
                    'node_id' => $a_node_id,
                    'parent_id' => $a_parent_id
                ]
            );
        }
    }

    public function getFilteredSubTree(int $a_node_id, array $a_filter = []): array
    {
        $node = $this->getNodeData($a_node_id);

        $first = true;
        $depth = 0;
        $filtered = [];
        foreach ($this->getSubTree($node) as $subnode) {
            if ($depth && $subnode['depth'] > $depth) {
                continue;
            }
            if (!$first && in_array($subnode['type'], $a_filter)) {
                $depth = $subnode['depth'];
                $first = false;
                continue;
            }
            $depth = 0;
            $first = false;
            $filtered[] = $subnode;
        }
        return $filtered;
    }

    public function getSubTreeIds(int $a_ref_id): array
    {
        return $this->getTreeImplementation()->getSubTreeIds($a_ref_id);
    }

    public function getSubTree(array $a_node, bool $a_with_data = true, array $a_type = []): array
    {
        $query = $this->getTreeImplementation()->getSubTreeQuery($a_node, $a_type);

        $res = $this->db->query($query);
        $subtree = [];
        while ($row = $this->db->fetchAssoc($res)) {
            if ($a_with_data) {
                $subtree[] = $this->fetchNodeData($row);
            } else {
                $subtree[] = (int) $row['child'];
            }
            // the lm_data "hack" should be removed in the trunk during an alpha
            if ($this->__isMainTree() || $this->table_tree == "lm_tree") {
                $this->in_tree_cache[$row['child']] = true;
            }
        }
        return $subtree;
    }

    public function deleteTree(array $a_node): void
    {
        if ($this->__isMainTree()) {
            // moved to trash and then deleted.
            if (!$this->__checkDelete($a_node)) {
                $this->logger->logStack(ilLogLevel::ERROR);
                throw new ilInvalidTreeStructureException('Deletion canceled due to invalid tree structure.' . print_r(
                    $a_node,
                    true
                ));
            }
        }
        $this->getTreeImplementation()->deleteTree((int) $a_node['child']);
        $this->resetInTreeCache();
    }

    public function validateParentRelations(): array
    {
        return $this->getTreeImplementation()->validateParentRelations();
    }

    public function getPathFull(int $a_endnode_id, int $a_startnode_id = 0): array
    {
        $pathIds = $this->getPathId($a_endnode_id, $a_startnode_id);

        // We retrieve the full path in a single query to improve performance
        // Abort if no path ids were found
        if (count($pathIds) == 0) {
            return [];
        }

        $inClause = 'child IN (';
        for ($i = 0; $i < count($pathIds); $i++) {
            if ($i > 0) {
                $inClause .= ',';
            }
            $inClause .= $this->db->quote($pathIds[$i], 'integer');
        }
        $inClause .= ')';

        $q = 'SELECT * ' .
            'FROM ' . $this->table_tree . ' ' .
            $this->buildJoin() . ' ' .
            'WHERE ' . $inClause . ' ' .
            'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = ' . $this->db->quote(
                $this->tree_id,
                'integer'
            ) . ' ' .
            'ORDER BY depth';
        $r = $this->db->query($q);

        $pathFull = [];
        while ($row = $r->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
            $pathFull[] = $this->fetchNodeData($row);

            // Update cache
            if ($this->__isMainTree()) {
                $this->in_tree_cache[$row['child']] = $row['tree'] == 1;
            }
        }
        return $pathFull;
    }

    public function preloadDepthParent(array $a_node_ids): void
    {
        global $DIC;

        if (!$this->__isMainTree() || !$this->isCacheUsed()) {
            return;
        }

        $res = $this->db->query('SELECT t.depth, t.parent, t.child ' .
            'FROM ' . $this->table_tree . ' t ' .
            'WHERE ' . $this->db->in("child", $a_node_ids, false, "integer") .
            'AND ' . $this->tree_pk . ' = ' . $this->db->quote($this->tree_id, "integer"));
        while ($row = $this->db->fetchAssoc($res)) {
            $this->depth_cache[$row["child"]] = (int) $row["depth"];
            $this->parent_cache[$row["child"]] = (int) $row["parent"];
        }
    }

    public function getPathId(int $a_endnode_id, int $a_startnode_id = 0): array
    {
        if (!$a_endnode_id) {
            $this->logger->logStack(ilLogLevel::ERROR);
            throw new InvalidArgumentException(__METHOD__ . ': No endnode given!');
        }

        // path id cache
        if ($this->isCacheUsed() && isset($this->path_id_cache[$a_endnode_id][$a_startnode_id])) {
            return $this->path_id_cache[$a_endnode_id][$a_startnode_id];
        }

        $pathIds = $this->getTreeImplementation()->getPathIds($a_endnode_id, $a_startnode_id);

        if ($this->__isMainTree()) {
            $this->path_id_cache[$a_endnode_id][$a_startnode_id] = $pathIds;
        }
        return $pathIds;
    }

    public function getNodePath(int $a_endnode_id, int $a_startnode_id = 0): array
    {
        $pathIds = $this->getPathId($a_endnode_id, $a_startnode_id);

        // Abort if no path ids were found
        if (count($pathIds) == 0) {
            return [];
        }

        $types = [];
        $data = [];
        for ($i = 0; $i < count($pathIds); $i++) {
            $types[] = 'integer';
            $data[] = $pathIds[$i];
        }

        $query = 'SELECT t.depth,t.parent,t.child,d.obj_id,d.type,d.title ' .
            'FROM ' . $this->table_tree . ' t ' .
            'JOIN ' . $this->table_obj_reference . ' r ON r.ref_id = t.child ' .
            'JOIN ' . $this->table_obj_data . ' d ON d.obj_id = r.obj_id ' .
            'WHERE ' . $this->db->in('t.child', $data, false, 'integer') . ' ' .
            'ORDER BY t.depth ';

        $res = $this->db->queryF($query, $types, $data);

        $titlePath = [];
        while ($row = $this->db->fetchAssoc($res)) {
            $titlePath[] = $row;
        }
        return $titlePath;
    }

    public function checkTree(): bool
    {
        $types = array('integer');
        $query = 'SELECT lft,rgt FROM ' . $this->table_tree . ' ' .
            'WHERE ' . $this->tree_pk . ' = %s ';

        $res = $this->db->queryF($query, $types, array($this->tree_id));
        $lft = $rgt = [];
        while ($row = $this->db->fetchObject($res)) {
            $lft[] = $row->lft;
            $rgt[] = $row->rgt;
        }

        $all = array_merge($lft, $rgt);
        $uni = array_unique($all);

        if (count($all) != count($uni)) {
            $message = 'Tree is corrupted!';
            $this->logger->error($message);
            throw new ilInvalidTreeStructureException($message);
        }
        return true;
    }

    public function checkTreeChilds(bool $a_no_zero_child = true): bool
    {
        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE ' . $this->tree_pk . ' = %s ' .
            'ORDER BY lft';
        $r1 = $this->db->queryF($query, array('integer'), array($this->tree_id));

        while ($row = $this->db->fetchAssoc($r1)) {
            //echo "tree:".$row[$this->tree_pk].":lft:".$row["lft"].":rgt:".$row["rgt"].":child:".$row["child"].":<br>";
            if (($row["child"] == 0) && $a_no_zero_child) {
                $message = "Tree contains child with ID 0!";
                $this->logger->error($message);
                throw new ilInvalidTreeStructureException($message);
            }

            if ($this->table_obj_reference) {
                // get object reference data
                $query = 'SELECT * FROM ' . $this->table_obj_reference . ' WHERE ' . $this->ref_pk . ' = %s ';
                $r2 = $this->db->queryF($query, array('integer'), array($row['child']));

                //echo "num_childs:".$r2->numRows().":<br>";
                if ($r2->numRows() == 0) {
                    $message = "No Object-to-Reference entry found for ID " . $row["child"] . "!";
                    $this->logger->error($message);
                    throw new ilInvalidTreeStructureException($message);
                }
                if ($r2->numRows() > 1) {
                    $message = "More Object-to-Reference entries found for ID " . $row["child"] . "!";
                    $this->logger->error($message);
                    throw new ilInvalidTreeStructureException($message);
                }

                // get object data
                $obj_ref = $this->db->fetchAssoc($r2);

                $query = 'SELECT * FROM ' . $this->table_obj_data . ' WHERE ' . $this->obj_pk . ' = %s';
                $r3 = $this->db->queryF($query, array('integer'), array($obj_ref[$this->obj_pk]));
                if ($r3->numRows() == 0) {
                    $message = " No child found for ID " . $obj_ref[$this->obj_pk] . "!";
                    $this->logger->error($message);
                    throw new ilInvalidTreeStructureException($message);
                }
                if ($r3->numRows() > 1) {
                    $message = "More childs found for ID " . $obj_ref[$this->obj_pk] . "!";
                    $this->logger->error($message);
                    throw new ilInvalidTreeStructureException($message);
                }
            } else {
                // get only object data
                $query = 'SELECT * FROM ' . $this->table_obj_data . ' WHERE ' . $this->obj_pk . ' = %s';
                $r2 = $this->db->queryF($query, array('integer'), array($row['child']));
                //echo "num_childs:".$r2->numRows().":<br>";
                if ($r2->numRows() == 0) {
                    $message = "No child found for ID " . $row["child"] . "!";
                    $this->logger->error($message);
                    throw new ilInvalidTreeStructureException($message);
                }
                if ($r2->numRows() > 1) {
                    $message = "More childs found for ID " . $row["child"] . "!";
                    $this->logger->error($message);
                    throw new ilInvalidTreeStructureException($message);
                }
            }
        }
        return true;
    }

    public function getMaximumDepth(): int
    {
        global $DIC;

        $query = 'SELECT MAX(depth) depth FROM ' . $this->table_tree;
        $res = $this->db->query($query);

        $row = $this->db->fetchAssoc($res);
        return (int) $row['depth'];
    }

    public function getDepth(int $a_node_id): int
    {
        global $DIC;

        if ($a_node_id) {
            if ($this->__isMainTree()) {
                $query = 'SELECT depth FROM ' . $this->table_tree . ' ' .
                    'WHERE child = %s ';
                $res = $this->db->queryF($query, array('integer'), array($a_node_id));
                $row = $this->db->fetchObject($res);
            } else {
                $query = 'SELECT depth FROM ' . $this->table_tree . ' ' .
                    'WHERE child = %s ' .
                    'AND ' . $this->tree_pk . ' = %s ';
                $res = $this->db->queryF($query, array('integer', 'integer'), array($a_node_id, $this->tree_id));
                $row = $this->db->fetchObject($res);
            }
            return (int) ($row->depth ?? 0);
        }
        return 1;
    }

    public function getNodeTreeData(int $a_node_id): array
    {
        global $DIC;

        if (!$a_node_id) {
            $this->logger->logStack(ilLogLevel::ERROR);
            throw new InvalidArgumentException('Missing or empty parameter $a_node_id: ' . $a_node_id);
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE child = ' . $this->db->quote($a_node_id, 'integer');
        $res = $this->db->query($query);
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
            return $row;
        }
        return [];
    }

    public function getNodeData(int $a_node_id, ?int $a_tree_pk = null): array
    {
        if ($this->__isMainTree()) {
            if ($a_node_id < 1) {
                $message = 'No valid parameter given! $a_node_id: %s' . $a_node_id;
                $this->logger->error($message);
                throw new InvalidArgumentException($message);
            }
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            $this->buildJoin() .
            'WHERE ' . $this->table_tree . '.child = %s ' .
            'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            $a_node_id,
            $a_tree_pk === null ? $this->tree_id : $a_tree_pk
        ));
        $row = $this->db->fetchAssoc($res);
        $row[$this->tree_pk] = $this->tree_id;

        return $this->fetchNodeData($row);
    }

    public function fetchNodeData(array $a_row): array
    {
        global $DIC;

        $objDefinition = $DIC['objDefinition'];
        $lng = $DIC['lng'];

        $data = $a_row;
        $data["desc"] = (string) ($a_row["description"] ?? '');  // for compability

        // multilingual support systemobjects (sys) & categories (db)
        $translation_type = '';
        if (is_object($objDefinition)) {
            $translation_type = $objDefinition->getTranslationType($data["type"] ?? '');
        }

        if ($translation_type == "sys") {
            if ($data["type"] == "rolf" && $data["obj_id"] != ROLE_FOLDER_ID) {
                $data["description"] = (string) $lng->txt("obj_" . $data["type"] . "_local_desc") . $data["title"] . $data["desc"];
                $data["desc"] = $lng->txt("obj_" . $data["type"] . "_local_desc") . $data["title"] . $data["desc"];
                $data["title"] = $lng->txt("obj_" . $data["type"] . "_local");
            } else {
                $data["title"] = $lng->txt("obj_" . $data["type"]);
                $data["description"] = $lng->txt("obj_" . $data["type"] . "_desc");
                $data["desc"] = $lng->txt("obj_" . $data["type"] . "_desc");
            }
        } elseif ($translation_type == "db") {

            // Try to retrieve object translation from cache
            $lang_code = ''; // This did never work, because it was undefined before
            if ($this->isCacheUsed() &&
                array_key_exists($data["obj_id"] . '.' . $lang_code, $this->translation_cache)) {
                $key = $data["obj_id"] . '.' . $lang_code;
                $data["title"] = $this->translation_cache[$key]['title'];
                $data["description"] = $this->translation_cache[$key]['description'];
                $data["desc"] = $this->translation_cache[$key]['desc'];
            } else {
                // Object translation is not in cache, read it from database
                $query = 'SELECT title,description FROM object_translation ' .
                    'WHERE obj_id = %s ' .
                    'AND lang_code = %s ';

                $res = $this->db->queryF($query, array('integer', 'text'), array(
                    $data['obj_id'],
                    $this->lang_code
                ));
                $row = $this->db->fetchObject($res);

                if ($row) {
                    $data["title"] = (string) $row->title;
                    $data["description"] = ilStr::shortenTextExtended((string) $row->description, ilObject::DESC_LENGTH, true);
                    $data["desc"] = (string) $row->description;
                }

                // Store up to 1000 object translations in cache
                if ($this->isCacheUsed() && count($this->translation_cache) < 1000) {
                    $key = $data["obj_id"] . '.' . $lang_code;
                    $this->translation_cache[$key] = [];
                    $this->translation_cache[$key]['title'] = $data["title"];
                    $this->translation_cache[$key]['description'] = $data["description"];
                    $this->translation_cache[$key]['desc'] = $data["desc"];
                }
            }
        }

        // TODO: Handle this switch by module.xml definitions
        if (isset($data['type']) && ($data['type'] == 'crsr' || $data['type'] == 'catr' || $data['type'] == 'grpr' || $data['type'] === 'prgr')) {
            $data['title'] = ilContainerReference::_lookupTitle((int) $data['obj_id']);
        }
        return $data;
    }

    protected function fetchTranslationFromObjectDataCache(array $a_obj_ids): void
    {
        global $DIC;

        $ilObjDataCache = $DIC['ilObjDataCache'];

        if ($this->isCacheUsed() && is_array($a_obj_ids) && is_object($ilObjDataCache)) {
            foreach ($a_obj_ids as $id) {
                $this->translation_cache[$id . '.']['title'] = $ilObjDataCache->lookupTitle((int) $id);
                $this->translation_cache[$id . '.']['description'] = $ilObjDataCache->lookupDescription((int) $id);
                $this->translation_cache[$id . '.']['desc'] =
                    $this->translation_cache[$id . '.']['description'];
            }
        }
    }

    public function isInTree(?int $a_node_id): bool
    {
        if (is_null($a_node_id) || !$a_node_id) {
            return false;
        }
        // is in tree cache
        if ($this->isCacheUsed() && isset($this->in_tree_cache[$a_node_id])) {
            return $this->in_tree_cache[$a_node_id];
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE ' . $this->table_tree . '.child = %s ' .
            'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s';

        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            $a_node_id,
            $this->tree_id
        ));

        if ($res->numRows() > 0) {
            if ($this->__isMainTree()) {
                $this->in_tree_cache[$a_node_id] = true;
            }
            return true;
        } else {
            if ($this->__isMainTree()) {
                $this->in_tree_cache[$a_node_id] = false;
            }
            return false;
        }
    }

    public function getParentNodeData(int $a_node_id): array
    {
        global $DIC;

        $ilLog = $DIC['ilLog'];

        if ($this->table_obj_reference) {
            // Use inner join instead of left join to improve performance
            $innerjoin = "JOIN " . $this->table_obj_reference . " ON v.child=" . $this->table_obj_reference . "." . $this->ref_pk . " " .
                "JOIN " . $this->table_obj_data . " ON " . $this->table_obj_reference . "." . $this->obj_pk . "=" . $this->table_obj_data . "." . $this->obj_pk . " ";
        } else {
            // Use inner join instead of left join to improve performance
            $innerjoin = "JOIN " . $this->table_obj_data . " ON v.child=" . $this->table_obj_data . "." . $this->obj_pk . " ";
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' s, ' . $this->table_tree . ' v ' .
            $innerjoin .
            'WHERE s.child = %s ' .
            'AND s.parent = v.child ' .
            'AND s.' . $this->tree_pk . ' = %s ' .
            'AND v.' . $this->tree_pk . ' = %s';
        $res = $this->db->queryF($query, array('integer', 'integer', 'integer'), array(
            $a_node_id,
            $this->tree_id,
            $this->tree_id
        ));
        $row = $this->db->fetchAssoc($res);
        if (is_array($row)) {
            return $this->fetchNodeData($row);
        }
        return [];
    }

    public function isGrandChild(int $a_startnode_id, int $a_querynode_id): bool
    {
        return $this->getRelation($a_startnode_id, $a_querynode_id) == self::RELATION_PARENT;
    }

    public function addTree(int $a_tree_id, int $a_node_id = -1): bool
    {
        global $DIC;

        // FOR SECURITY addTree() IS NOT ALLOWED ON MAIN TREE
        if ($this->__isMainTree()) {
            $message = sprintf(
                'Operation not allowed on main tree! $a_tree_if: %s $a_node_id: %s',
                $a_tree_id,
                $a_node_id
            );
            $this->logger->error($message);
            throw new InvalidArgumentException($message);
        }

        if ($a_node_id <= 0) {
            $a_node_id = $a_tree_id;
        }

        $query = 'INSERT INTO ' . $this->table_tree . ' (' .
            $this->tree_pk . ', child,parent,lft,rgt,depth) ' .
            'VALUES ' .
            '(%s,%s,%s,%s,%s,%s)';
        $res = $this->db->manipulateF(
            $query,
            array('integer', 'integer', 'integer', 'integer', 'integer', 'integer'),
            array(
                $a_tree_id,
                $a_node_id,
                0,
                1,
                2,
                1
            )
        );

        return true;
    }

    public function removeTree(int $a_tree_id): bool
    {
        if ($this->__isMainTree()) {
            $this->logger->logStack(ilLogLevel::ERROR);
            throw new InvalidArgumentException('Operation not allowed on main tree');
        }
        if (!$a_tree_id) {
            $this->logger->logStack(ilLogLevel::ERROR);
            throw new InvalidArgumentException('Missing parameter tree id');
        }

        $query = 'DELETE FROM ' . $this->table_tree .
            ' WHERE ' . $this->tree_pk . ' = %s ';
        $this->db->manipulateF($query, array('integer'), array($a_tree_id));
        return true;
    }

    public function moveToTrash(int $a_node_id, bool $a_set_deleted = false, int $a_deleted_by = 0): bool
    {
        global $DIC;

        $user = $DIC->user();
        if (!$a_deleted_by) {
            $a_deleted_by = $user->getId();
        }

        if (!$a_node_id) {
            $this->logger->logStack(ilLogLevel::ERROR);
            throw new InvalidArgumentException('No valid parameter given! $a_node_id: ' . $a_node_id);
        }

        $query = $this->getTreeImplementation()->getSubTreeQuery($this->getNodeTreeData($a_node_id), [], false);
        $res = $this->db->query($query);

        $subnodes = [];
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_ASSOC)) {
            $subnodes[] = (int) $row['child'];
        }

        if (!count($subnodes)) {
            // Possibly already deleted
            return false;
        }

        if ($a_set_deleted) {
            ilObject::setDeletedDates($subnodes, $a_deleted_by);
        }
        // netsted set <=> mp
        $this->getTreeImplementation()->moveToTrash($a_node_id);
        return true;
    }

    public function isDeleted(int $a_node_id): bool
    {
        return $this->isSaved($a_node_id);
    }

    public function isSaved(int $a_node_id): bool
    {
        if ($this->isCacheUsed() && isset($this->is_saved_cache[$a_node_id])) {
            return $this->is_saved_cache[$a_node_id];
        }

        $query = 'SELECT ' . $this->tree_pk . ' FROM ' . $this->table_tree . ' ' .
            'WHERE child = %s ';
        $res = $this->db->queryF($query, array('integer'), array($a_node_id));
        $row = $this->db->fetchAssoc($res);

        $tree_id = $row[$this->tree_pk] ?? 0;
        if ($tree_id < 0) {
            if ($this->__isMainTree()) {
                $this->is_saved_cache[$a_node_id] = true;
            }
            return true;
        } else {
            if ($this->__isMainTree()) {
                $this->is_saved_cache[$a_node_id] = false;
            }
            return false;
        }
    }

    public function preloadDeleted(array $a_node_ids): void
    {
        if (!is_array($a_node_ids) || !$this->isCacheUsed()) {
            return;
        }

        $query = 'SELECT ' . $this->tree_pk . ', child FROM ' . $this->table_tree . ' ' .
            'WHERE ' . $this->db->in("child", $a_node_ids, false, "integer");

        $res = $this->db->query($query);
        while ($row = $this->db->fetchAssoc($res)) {
            if ($row[$this->tree_pk] < 0) {
                if ($this->__isMainTree()) {
                    $this->is_saved_cache[$row["child"]] = true;
                }
            } else {
                if ($this->__isMainTree()) {
                    $this->is_saved_cache[$row["child"]] = false;
                }
            }
        }
    }

    public function getSavedNodeData(int $a_parent_id): array
    {
        global $DIC;

        if (!isset($a_parent_id)) {
            $message = "No node_id given!";
            $this->logger->error($message);
            throw new InvalidArgumentException($message);
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            $this->buildJoin() .
            'WHERE ' . $this->table_tree . '.' . $this->tree_pk . ' < %s ' .
            'AND ' . $this->table_tree . '.parent = %s';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            0,
            $a_parent_id
        ));

        $saved = [];
        while ($row = $this->db->fetchAssoc($res)) {
            $saved[] = $this->fetchNodeData($row);
        }

        return $saved;
    }

    public function getSavedNodeObjIds(array $a_obj_ids): array
    {
        global $DIC;

        $query = 'SELECT ' . $this->table_obj_data . '.obj_id FROM ' . $this->table_tree . ' ' .
            $this->buildJoin() .
            'WHERE ' . $this->table_tree . '.' . $this->tree_pk . ' < ' . $this->db->quote(0, 'integer') . ' ' .
            'AND ' . $this->db->in($this->table_obj_data . '.obj_id', $a_obj_ids, false, 'integer');
        $res = $this->db->query($query);
        $saved = [];
        while ($row = $this->db->fetchAssoc($res)) {
            $saved[] = (int) $row['obj_id'];
        }

        return $saved;
    }

    public function getParentId(int $a_node_id): ?int
    {
        global $DIC;
        if ($this->__isMainTree()) {
            $query = 'SELECT parent FROM ' . $this->table_tree . ' ' .
                'WHERE child = %s ';
            $res = $this->db->queryF(
                $query,
                ['integer'],
                [$a_node_id]
            );
        } else {
            $query = 'SELECT parent FROM ' . $this->table_tree . ' ' .
                'WHERE child = %s ' .
                'AND ' . $this->tree_pk . ' = %s ';
            $res = $this->db->queryF($query, array('integer', 'integer'), array(
                $a_node_id,
                $this->tree_id
            ));
        }

        if ($row = $this->db->fetchObject($res)) {
            return (int) $row->parent;
        }
        return null;
    }

    public function getLeftValue(int $a_node_id): int
    {
        global $DIC;

        if (!isset($a_node_id)) {
            $message = "No node_id given!";
            $this->logger->error($message);
            throw new InvalidArgumentException($message);
        }

        $query = 'SELECT lft FROM ' . $this->table_tree . ' ' .
            'WHERE child = %s ' .
            'AND ' . $this->tree_pk . ' = %s ';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            $a_node_id,
            $this->tree_id
        ));
        $row = $this->db->fetchObject($res);
        return (int) $row->lft;
    }

    public function getChildSequenceNumber(array $a_node, string $type = ""): int
    {
        if (!isset($a_node)) {
            $message = "No node_id given!";
            $this->logger->error($message);
            throw new InvalidArgumentException($message);
        }

        if ($type) {
            $query = 'SELECT count(*) cnt FROM ' . $this->table_tree . ' ' .
                $this->buildJoin() .
                'WHERE lft <= %s ' .
                'AND type = %s ' .
                'AND parent = %s ' .
                'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ';

            $res = $this->db->queryF($query, array('integer', 'text', 'integer', 'integer'), array(
                $a_node['lft'],
                $type,
                $a_node['parent'],
                $this->tree_id
            ));
        } else {
            $query = 'SELECT count(*) cnt FROM ' . $this->table_tree . ' ' .
                $this->buildJoin() .
                'WHERE lft <= %s ' .
                'AND parent = %s ' .
                'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ';

            $res = $this->db->queryF($query, array('integer', 'integer', 'integer'), array(
                $a_node['lft'],
                $a_node['parent'],
                $this->tree_id
            ));
        }
        $row = $this->db->fetchAssoc($res);
        return (int) $row["cnt"];
    }

    public function readRootId(): int
    {
        $query = 'SELECT child FROM ' . $this->table_tree . ' ' .
            'WHERE parent = %s ' .
            'AND ' . $this->tree_pk . ' = %s ';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            0,
            $this->tree_id
        ));
        $this->root_id = 0;
        if ($row = $this->db->fetchObject($res)) {
            $this->root_id = (int) $row->child;
        }
        return $this->root_id;
    }

    public function getRootId(): int
    {
        return $this->root_id;
    }

    public function setRootId(int $a_root_id): void
    {
        $this->root_id = $a_root_id;
    }

    public function getTreeId(): int
    {
        return $this->tree_id;
    }

    public function setTreeId(int $a_tree_id): void
    {
        $this->tree_id = $a_tree_id;
    }

    public function fetchSuccessorNode(int $a_node_id, string $a_type = ""): ?array
    {
        // get lft value for current node
        $query = 'SELECT lft FROM ' . $this->table_tree . ' ' .
            'WHERE ' . $this->table_tree . '.child = %s ' .
            'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            $a_node_id,
            $this->tree_id
        ));
        $curr_node = $this->db->fetchAssoc($res);

        if ($a_type) {
            $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
                $this->buildJoin() .
                'WHERE lft > %s ' .
                'AND ' . $this->table_obj_data . '.type = %s ' .
                'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ' .
                'ORDER BY lft ';
            $this->db->setLimit(1, 0);
            $res = $this->db->queryF($query, array('integer', 'text', 'integer'), array(
                $curr_node['lft'],
                $a_type,
                $this->tree_id
            ));
        } else {
            $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
                $this->buildJoin() .
                'WHERE lft > %s ' .
                'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ' .
                'ORDER BY lft ';
            $this->db->setLimit(1, 0);
            $res = $this->db->queryF($query, array('integer', 'integer'), array(
                $curr_node['lft'],
                $this->tree_id
            ));
        }

        if ($res->numRows() < 1) {
            return null;
        } else {
            $row = $this->db->fetchAssoc($res);
            return $this->fetchNodeData($row);
        }
    }

    public function fetchPredecessorNode(int $a_node_id, string $a_type = ""): ?array
    {
        if (!isset($a_node_id)) {
            $message = "No node_id given!";
            $this->logger->error($message);
            throw new InvalidArgumentException($message);
        }

        // get lft value for current node
        $query = 'SELECT lft FROM ' . $this->table_tree . ' ' .
            'WHERE ' . $this->table_tree . '.child = %s ' .
            'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            $a_node_id,
            $this->tree_id
        ));

        $curr_node = $this->db->fetchAssoc($res);

        if ($a_type) {
            $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
                $this->buildJoin() .
                'WHERE lft < %s ' .
                'AND ' . $this->table_obj_data . '.type = %s ' .
                'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ' .
                'ORDER BY lft DESC';
            $this->db->setLimit(1, 0);
            $res = $this->db->queryF($query, array('integer', 'text', 'integer'), array(
                $curr_node['lft'],
                $a_type,
                $this->tree_id
            ));
        } else {
            $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
                $this->buildJoin() .
                'WHERE lft < %s ' .
                'AND ' . $this->table_tree . '.' . $this->tree_pk . ' = %s ' .
                'ORDER BY lft DESC';
            $this->db->setLimit(1, 0);
            $res = $this->db->queryF($query, array('integer', 'integer'), array(
                $curr_node['lft'],
                $this->tree_id
            ));
        }

        if ($res->numRows() < 1) {
            return null;
        } else {
            $row = $this->db->fetchAssoc($res);
            return $this->fetchNodeData($row);
        }
    }

    public function renumber(int $node_id = 1, int $i = 1): int
    {
        $renumber_callable = function (ilDBInterface $db) use ($node_id, $i, &$return) {
            $return = $this->__renumber($node_id, $i);
        };

        // LOCKED ###################################
        if ($this->__isMainTree()) {
            $ilAtomQuery = $this->db->buildAtomQuery();
            $ilAtomQuery->addTableLock($this->table_tree);

            $ilAtomQuery->addQueryCallable($renumber_callable);
            $ilAtomQuery->run();
        } else {
            $renumber_callable($this->db);
        }
        return $return;
    }

    private function __renumber(int $node_id = 1, int $i = 1): int
    {
        if ($this->isRepositoryTree()) {
            $query = 'UPDATE ' . $this->table_tree . ' SET lft = %s WHERE child = %s';
            $this->db->manipulateF(
                $query,
                array('integer', 'integer'),
                array(
                    $i,
                    $node_id
                )
            );
        } else {
            $query = 'UPDATE ' . $this->table_tree . ' SET lft = %s WHERE child = %s AND tree = %s';
            $this->db->manipulateF(
                $query,
                array('integer', 'integer', 'integer'),
                array(
                    $i,
                    $node_id,
                    $this->tree_id
                )
            );
        }

        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE parent = ' . $this->db->quote($node_id, 'integer') . ' ' .
            'ORDER BY lft';
        $res = $this->db->query($query);

        $childs = [];
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
            $childs[] = (int) $row->child;
        }

        foreach ($childs as $child) {
            $i = $this->__renumber($child, $i + 1);
        }
        $i++;

        // Insert a gap at the end of node, if the node has children
        if (count($childs) > 0) {
            $i += $this->gap * 2;
        }

        if ($this->isRepositoryTree()) {
            $query = 'UPDATE ' . $this->table_tree . ' SET rgt = %s WHERE child = %s';
            $res = $this->db->manipulateF(
                $query,
                array('integer', 'integer'),
                array(
                    $i,
                    $node_id
                )
            );
        } else {
            $query = 'UPDATE ' . $this->table_tree . ' SET rgt = %s WHERE child = %s AND tree = %s';
            $res = $this->db->manipulateF($query, array('integer', 'integer', 'integer'), array(
                $i,
                $node_id,
                $this->tree_id
            ));
        }
        return $i;
    }

    public function checkForParentType(int $a_ref_id, string $a_type, bool $a_exclude_source_check = false): int
    {
        // #12577
        $cache_key = $a_ref_id . '.' . $a_type . '.' . ((int) $a_exclude_source_check);

        // Try to return a cached result
        if ($this->isCacheUsed() &&
            array_key_exists($cache_key, $this->parent_type_cache)) {
            return (int) $this->parent_type_cache[$cache_key];
        }

        // Store up to 1000 results in cache
        $do_cache = ($this->__isMainTree() && count($this->parent_type_cache) < 1000);

        // ref_id is not in tree
        if (!$this->isInTree($a_ref_id)) {
            if ($do_cache) {
                $this->parent_type_cache[$cache_key] = false;
            }
            return 0;
        }

        $path = array_reverse($this->getPathFull($a_ref_id));

        // remove first path entry as it is requested node
        if ($a_exclude_source_check) {
            array_shift($path);
        }

        foreach ($path as $node) {
            // found matching parent
            if ($node["type"] == $a_type) {
                if ($do_cache) {
                    $this->parent_type_cache[$cache_key] = (int) $node["child"];
                }
                return (int) $node["child"];
            }
        }

        if ($do_cache) {
            $this->parent_type_cache[$cache_key] = false;
        }
        return 0;
    }

    public static function _removeEntry(int $a_tree, int $a_child, string $a_db_table = "tree"): void
    {
        global $DIC;

        $db = $DIC->database();

        if ($a_db_table === 'tree') {
            if ($a_tree == 1 && $a_child == ROOT_FOLDER_ID) {
                $message = sprintf(
                    'Tried to delete root node! $a_tree: %s $a_child: %s',
                    $a_tree,
                    $a_child
                );
                ilLoggerFactory::getLogger('tree')->error($message);
                throw new InvalidArgumentException($message);
            }
        }

        $query = 'DELETE FROM ' . $a_db_table . ' ' .
            'WHERE tree = %s ' .
            'AND child = %s ';
        $res = $db->manipulateF($query, array('integer', 'integer'), array(
            $a_tree,
            $a_child
        ));
    }

    public function __isMainTree(): bool
    {
        return $this->table_tree === 'tree';
    }

    public function __checkDelete(array $a_node): bool
    {
        $query = $this->getTreeImplementation()->getSubTreeQuery($a_node, [], false);
        $this->logger->debug($query);
        $res = $this->db->query($query);

        $counter = (int) $lft_childs = [];
        while ($row = $this->db->fetchObject($res)) {
            $lft_childs[$row->child] = (int) $row->parent;
            ++$counter;
        }

        // CHECK FOR DUPLICATE CHILD IDS
        if ($counter != count($lft_childs)) {
            $message = 'Duplicate entries for "child" in maintree! $a_node_id: ' . $a_node['child'];

            $this->logger->error($message);
            throw new ilInvalidTreeStructureException($message);
        }

        // GET SUBTREE BY PARENT RELATION
        $parent_childs = [];
        $this->__getSubTreeByParentRelation((int)$a_node['child'], $parent_childs);
        $this->__validateSubtrees($lft_childs, $parent_childs);

        return true;
    }

    public function __getSubTreeByParentRelation(int $a_node_id, array &$parent_childs): bool
    {
        // GET PARENT ID
        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE child = %s ' .
            'AND tree = %s ';
        $res = $this->db->queryF($query, array('integer', 'integer'), array(
            $a_node_id,
            $this->tree_id
        ));

        $counter = 0;
        while ($row = $this->db->fetchObject($res)) {
            $parent_childs[$a_node_id] = (int) $row->parent;
            ++$counter;
        }
        // MULTIPLE ENTRIES
        if ($counter > 1) {
            $message = 'Multiple entries in maintree! $a_node_id: ' . $a_node_id;

            $this->logger->error($message);
            throw new ilInvalidTreeStructureException($message);
        }

        // GET ALL CHILDS
        $query = 'SELECT * FROM ' . $this->table_tree . ' ' .
            'WHERE parent = %s ';
        $res = $this->db->queryF($query, array('integer'), array($a_node_id));

        while ($row = $this->db->fetchObject($res)) {
            // RECURSION
            $this->__getSubTreeByParentRelation((int) $row->child, $parent_childs);
        }
        return true;
    }

    public function __validateSubtrees(array &$lft_childs, array $parent_childs): bool
    {
        // SORT BY KEY
        ksort($lft_childs);
        ksort($parent_childs);

        $this->logger->debug('left childs ' . print_r($lft_childs, true));
        $this->logger->debug('parent childs ' . print_r($parent_childs, true));

        if (count($lft_childs) != count($parent_childs)) {
            $message = '(COUNT) Tree is corrupted! Left/Right subtree does not comply with parent relation';
            $this->logger->error($message);
            throw new ilInvalidTreeStructureException($message);
        }

        foreach ($lft_childs as $key => $value) {
            if ($parent_childs[$key] != $value) {
                $message = '(COMPARE) Tree is corrupted! Left/Right subtree does not comply with parent relation';
                $this->logger->error($message);
                throw new ilInvalidTreeStructureException($message);
            }
            if ($key == ROOT_FOLDER_ID) {
                $message = '(ROOT_FOLDER) Tree is corrupted! Tried to delete root folder';
                $this->logger->error($message);
                throw new ilInvalidTreeStructureException($message);
            }
        }
        return true;
    }

    public function moveTree(int $a_source_id, int $a_target_id, int $a_location = self::POS_LAST_NODE): void
    {
        $old_parent_id = $this->getParentId($a_source_id);
        $this->getTreeImplementation()->moveTree($a_source_id, $a_target_id, $a_location);
        if (isset($GLOBALS['DIC']["ilAppEventHandler"]) && $this->__isMainTree()) {
            $GLOBALS['DIC']['ilAppEventHandler']->raise(
                "Services/Tree",
                "moveTree",
                array(
                    'tree' => $this->table_tree,
                    'source_id' => $a_source_id,
                    'target_id' => $a_target_id,
                    'old_parent_id' => $old_parent_id
                )
            );
        }
    }

    public function getRbacSubtreeInfo(int $a_endnode_id): array
    {
        return $this->getTreeImplementation()->getSubtreeInfo($a_endnode_id);
    }

    public function getSubTreeQuery(
        int $a_node_id,
        array $a_fields = [],
        array $a_types = [],
        bool $a_force_join_reference = false
    ): string {
        return $this->getTreeImplementation()->getSubTreeQuery(
            $this->getNodeTreeData($a_node_id),
            $a_types,
            $a_force_join_reference,
            $a_fields
        );
    }

    public function getTrashSubTreeQuery(
        int $a_node_id,
        array $a_fields = [],
        array $a_types = [],
        bool $a_force_join_reference = false
    ): string {
        return $this->getTreeImplementation()->getTrashSubTreeQuery(
            $this->getNodeTreeData($a_node_id),
            $a_types,
            $a_force_join_reference,
            $a_fields
        );
    }

    public function getSubTreeFilteredByObjIds(int $a_node_id, array $a_obj_ids, array $a_fields = []): array
    {
        $node = $this->getNodeData($a_node_id);
        if (!count($node)) {
            return [];
        }

        $res = [];

        $query = $this->getTreeImplementation()->getSubTreeQuery($node, [], true, array($this->ref_pk));

        $fields = '*';
        if (count($a_fields)) {
            $fields = implode(',', $a_fields);
        }

        $query = "SELECT " . $fields .
            " FROM " . $this->getTreeTable() .
            " " . $this->buildJoin() .
            " WHERE " . $this->getTableReference() . "." . $this->ref_pk . " IN (" . $query . ")" .
            " AND " . $this->db->in($this->getObjectDataTable() . "." . $this->obj_pk, $a_obj_ids, false, "integer");
        $set = $this->db->query($query);
        while ($row = $this->db->fetchAssoc($set)) {
            $res[] = $row;
        }

        return $res;
    }

    public function deleteNode(int $a_tree_id, int $a_node_id): void
    {
        $query = 'DELETE FROM tree where ' .
            'child = ' . $this->db->quote($a_node_id, 'integer') . ' ' .
            'AND tree = ' . $this->db->quote($a_tree_id, 'integer');
        $this->db->manipulate($query);

        $this->eventHandler->raise(
            "Services/Tree",
            "deleteNode",
            [
                'tree' => $this->table_tree,
                'node_id' => $a_node_id,
                'tree_id' => $a_tree_id
            ]
        );
    }

    public function lookupTrashedObjectTypes(): array
    {
        $query = 'SELECT DISTINCT(o.type) ' . $this->db->quoteIdentifier('type') .
            ' FROM tree t JOIN object_reference r ON child = r.ref_id ' .
            'JOIN object_data o on r.obj_id = o.obj_id ' .
            'WHERE tree < ' . $this->db->quote(0, 'integer') . ' ' .
            'AND child = -tree ' .
            'GROUP BY o.type';
        $res = $this->db->query($query);

        $types_deleted = [];
        while ($row = $res->fetchRow(ilDBConstants::FETCHMODE_OBJECT)) {
            $types_deleted[] = (string) $row->type;
        }
        return $types_deleted;
    }

    public function isRepositoryTree(): bool
    {
        return $this->table_tree == 'tree';
    }
} // END class.tree