alex-kalanis / nested-tree

NestedSet::listNodesBuildTreeWithChildren() A
last analyzed 2026-01-06 03:57 UTC

↳ Parent: NestedSet

Complexity

Conditions	6
Paths	6

Size

Total Lines	25
Code Lines	14

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	14
CRAP Score	6

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	14
c	1
b	0
f	0
dl	0
loc	25
ccs	14
cts	14
cp	1
rs	9.2222
cc	6
nc	6
nop	2
crap	6

<?php

namespace kalanis\nested_tree;

use kalanis\nested_tree\Sources\SourceInterface;

/**
 * Nested Set class for build left, right, level data.
 *
 * @see http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ Query references.
 */
class NestedSet
{
    public function __construct(
        protected readonly SourceInterface $source,
        protected readonly Support\Node $nodeBase = new Support\Node(),
        protected readonly Support\TableSettings $tableSettings = new Support\TableSettings(),
    ) {
    }

    /**
     * Add new record to structure
     * The position is set to end
     *
     * Note: Properties of tree will be skipped and filled later. For their change use different methods.
     *
     * @param Support\Node $node
     * @param Support\Options $options
     * @return Support\Node
     */
    public function add(Support\Node $node, Support\Options $options = new Support\Options()) : Support\Node
    {
        $node->position = $this->getNewPosition($node->parentId, $options->where);

        return $this->source->add($node, $options->where);
    }

    /**
     * Update current record in structure
     *
     * Note: Properties with Null value will be skipped and stay same in the storage.
     * Note: Properties of tree will be skipped too. For their change use different methods.
     *
     * @param Support\Node $node
     * @param Support\Options $options
     * @return bool
     */
    public function update(Support\Node $node, Support\Options $options = new Support\Options()) : bool
    {
        return $this->source->updateData($node, $options->where);
    }

    /**
     * Change parent node to different one; put the content on the last position
     * Parent id can be either some number for existing one or 0/null for root
     *
     * Return true for pass, false otherwise
     *
     * @param int<1, max> $nodeId
     * @param int<0, max>|null $newParentId
     * @param Support\Options $options
     * @return bool
     */
    public function changeParent(int $nodeId, ?int $newParentId, Support\Options $options = new Support\Options()) : bool
    {
        $currentNode = $this->getNodeById($nodeId);
        if (empty($currentNode)) {
            return false;
        }

        if (!empty($newParentId)) {
            $parentNode = $this->getNodeById($newParentId);
            if (empty($parentNode)) {
                return false;
            }
        } elseif (is_null($newParentId)) {

            $parentNode = null;
        } else {
            $parentNode = new Support\Node();
        }

        if (!$this->isNewParentOutsideCurrentNodeTree($nodeId, $newParentId, $options)) {
            return false;
        }
        $newPosition = $this->getNewPosition($parentNode, $options->where);

        return $this->source->updateNodeParent($currentNode, $parentNode, $newPosition, $options->where);
    }

    /**
     * Move node to new position
     *
     * @param int<1, max> $nodeId
     * @param int<0, max> $newPosition
     * @param Support\Options $options
     * @return bool
     */
    public function move(int $nodeId, int $newPosition, Support\Options $options = new Support\Options()) : bool
    {
        $currentNode = $this->getNodeById($nodeId, $options);
        if (empty($currentNode)) {
            return false;
        }

        $parentNode = $this->source->selectParent($currentNode, $options);

        // move it
        if ($this->source->makeHole($parentNode, $newPosition, $newPosition > $currentNode->position, $options->where)) {
            return $this->source->updateNodeParent($currentNode, $parentNode, $newPosition, $options->where);
        }

        return false;
    }

    /**
     * Delete the selected taxonomy ID and pull children's parent ID to the same as selected one.<br>
     * Example: selected taxonomy ID is 4, its parent ID is 2. This method will be pull all children that has parent ID = 4 to 2 and delete the taxonomy ID 4.<br>
     * Always run <code>$NestedSet->rebuild()</code> after insert, update, delete to rebuild the correctly level, left, right data.
     *
     * @param int<1, max> $nodeId The selected taxonomy ID.
     * @param Support\Options $options Where array structure will be like this.
     * @return bool Return true on success, false for otherwise.
     */
    public function deletePullUpChildren(int $nodeId, Support\Options $options = new Support\Options()) : bool
    {
        // get this taxonomy parent id
        $node = $this->getNodeById($nodeId);
        if (empty($node)) {
            return false;
        }
        $parentNode = $this->source->selectParent($node, $options);
        // update this children first level.
        $this->source->updateChildrenParent($node, $parentNode, $options->where);

        return $this->source->deleteSolo($node, $options->where);
    }

    /**
     * Delete the selected taxonomy ID with its ALL children.<br>
     * Always run <code>$NestedSet->rebuild()</code> after insert, update, delete to rebuild the correctly level, left, right data.
     *
     * The columns `left`, `right` must have been built before using this method, otherwise the result will be incorrect.
     *
     * @param int<1, max> $nodeId The taxonomy ID to delete.
     * @param Support\Options $options Where array structure will be like this.
     * @return int|null Return number on success, return null for otherwise.
     */
    public function deleteWithChildren(int $nodeId, Support\Options $options = new Support\Options()) : ?int
    {
        $options->currentId = $nodeId;
        $options->unlimited = true;
        $result = $this->getNodesWithChildren($options);
        $i_count = 0;

        if (!empty($result->items)) {
            foreach ($result->items as $row) {
                if ($this->source->deleteSolo($row, $options->where)) {
                    $i_count++;
                }
            }
        }

        if (0 >= $i_count) {
            return null;
        }

        return $i_count;
    }

    /**
     * Get new position for taxonomy in the selected parent.
     *
     * @param int<0, max>|Support\Node|null $parent The parent ID. If root, set this to 0 or null.
     * @param Support\Conditions|null $where Where array structure will be like this.
     * @return int<1, max> Return the new position in the same parent.<br>
     *              WARNING! If there are no results or the results according to the conditions cannot be found. It always returns 1.
     */
    public function getNewPosition(int|Support\Node|null $parent, ?Support\Conditions $where = null) : int
    {
        $parentNode = is_object($parent)
            ? $parent
            : (
                is_null($parent)
                    ? null
                    : (
                        0 === $parent
                            ? new Support\Node()
                            : $this->getNodeById($parent)
                    )
            );
        $lastPosition = $this->source->selectLastPosition($parentNode, $where);

        return null === $lastPosition ? 1 : $lastPosition + 1;
    }

    /**
     * Get taxonomy from selected item and fetch its ALL children.<br>
     * Example: There are taxonomy tree like this. Root 1 > 1.1 > 1.1.1, Root 2, Root 3 > 3.1, Root 3 > 3.2 > 3.2.1, Root 3 > 3.2 > 3.2.2, Root 3 > 3.3<br>
     * Assume that selected item is Root 3. So, the result will be Root 3 > 3.1, 3.2 > 3.2.1, 3.2.2, 3.3<br>
     *
     * Warning! Even this method has options for search, custom where conditions,
     * but it is recommended that you should set the option to select only specific item.<br>
     * This method is intended to show results from a single target.
     *
     * The columns `left`, `right` must have been built before using this method, otherwise the result will be incorrect.
     *
     * @param Support\Options $options Available options
     *
     * @return Support\Result Return object of taxonomy data
     */
    public function getNodesWithChildren(Support\Options $options = new Support\Options()) : Support\Result
    {
        // set unwanted options that is available in `listTaxonomy()` method to defaults
        $options->parentId = null;
        $options->filterIdBy = [];
        $options->noSortOrder = false;
        // set required option.
        $options->listFlattened = true;

        return $this->listNodes($options);
    }

    /**
     * Get simple taxonomy from all known; set things to make the query more limited
     *
     * @param Support\Options $options
     * @return Support\Node|null
     */
    public function getNode(Support\Options $options = new Support\Options()) : ?Support\Node
    {
        $options = clone $options;
        $options->unlimited = false;
        $options->offset = 0;
        $options->limit = 1;
        $options->noSortOrder = false;
        $nodes = $this->source->selectLimited($options);
        if (empty($nodes)) {
            return null;
        }

        return reset($nodes);
    }

    /**
     * Get simple taxonomy by its ID; set things to make the query more limited
     *
     * @param int $nodeId
     * @param Support\Options $options
     * @return Support\Node|null
     */
    public function getNodeById(int $nodeId, Support\Options $options = new Support\Options()) : ?Support\Node
    {
        $customOptions = clone $options;
        $customOptions->currentId = $nodeId;

        $nodes = $this->source->selectSimple($customOptions);
        if (empty($nodes)) {
            return null;
        }

        return reset($nodes);
    }

    /**
     * Get taxonomy from selected item and fetch its parent in a line until root item.<br>
     * Example: There are taxonomy tree like this. Root1 > 1.1 > 1.1.1 > 1.1.1.1<br>
     * Assume that you selected at 1.1.1. So, the result will be Root1 > 1.1 > 1.1.1<br>
     * But if you set 'skipCurrent' to true the result will be Root1 > 1.1
     *
     * Warning! Even this method has options for search, custom where conditions,
     * but it is recommended that you should set the option to select only specific item.<br>
     * This method is intended to show results from a single target.
     *
     * The columns `left`, `right` must have been built before using this method, otherwise the result will be incorrect.
     *
     * @see http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/ Original source.
     * @param Support\Options $options Available options
     * @return Support\Result Return array object of taxonomy data
     */
    public function getNodesWithParents(Support\Options $options = new Support\Options()) : Support\Result
    {
        $result = new Support\Result();
        $result->items = $this->source->selectWithParents($options);
        $result->count = count($result->items);

        return $result;
    }

    /**
     * Rebuild children into array.
     *
     * @internal This method was called from `getTreeWithChildren()`.
     * @param array<int<-1, max>, Support\Node> $array The array data that was get while running `getTreeWithChildren()`. This data contains 'children' object property but empty, it will be added here.

     * @return array<int<-1, max>, Support\Node> Return added correct id of the children to data.

     */
    protected function getTreeRebuildChildren(array $array) : array
    {
        foreach ($array as $id => $row) {
            if (
                !is_null($row->parentId)
                && !empty($array[$row->parentId])
                && ($row->parentId !== $row->id)
            ) {
                $array[$row->parentId]->childrenIds[$id] = $id;
                $array[$row->parentId]->childrenNodes[$id] = $row;
            } elseif (
                is_null($row->parentId)
                && $this->tableSettings->rootIsNull
                && !empty($row->id)
                && ($this->tableSettings->virtualRootId !== $row->id)
            ) {
                $array[$this->tableSettings->virtualRootId]->childrenIds[$id] = $id;
                $array[$this->tableSettings->virtualRootId]->childrenNodes[$id] = $row;
            }
        }

        return $array;
    }

    /**
     * Get the data nest tree with children.<br>
     * Its result will be look like this...<pre>
     * Array(
     *     [0] => Support\Node Object
     *         (
     *             [id] => 0
     *             [children] => Array
     *                 (
     *                     [1] => 1
     *                     [2] => 2
     *                     [3] => 3
     *                 )
     *         )
     *     [1] => Support\Node Object
     *         (
     *             [id] => 1
     *             [parent_id] => 0
     *             [level] => 1
     *             [children] => Array
     *                 (
     *                 )
     *         )
     *     [2] => Support\Node Object
     *         (
     *             [id] => 2
     *             [parent_id] => 0
     *             [level] => 1
     *             [children] => Array
     *                 (
     *                     [4] => 4
     *                     [5] => 5
     *                 )
     *         )
     *     [3] => Support\Node Object
     *         (
     *             [id] => 3
     *             [parent_id] => 0
     *             [level] => 1
     *             [children] => Array
     *                 (
     *                 )
     *         )
     *     [4] => Support\Node Object
     *         (
     *             [id] => 4
     *             [parent_id] => 2
     *             [level] => 2
     *             [children] => Array
     *                 (
     *                 )
     *         )
     *     [5] => Support\Node Object
     *         (
     *             [id] => 5
     *             [parent_id] => 2
     *             [level] => 2
     *             [children] => Array
     *                 (
     *                 )
     *         )
     * )</pre>
     *
     * Usually, this method is for get taxonomy tree data in the array format that suit for loop/nest loop verify level.
     *
     * @since 1.0
     * @internal This method was called from `rebuild()`.
     * @param Support\Options $options Where array structure will be like this.
     * @return array<int<-1, max>, Support\Node> Return formatted array structure as seen in example of docblock.

     */
    protected function getTreeWithChildren(Support\Options $options = new Support\Options()) : array
    {
        // create a root node to hold child data about first level items
        $result = $this->source->selectSimple($options);
        // map ids to keys
        $result = array_combine(array_map(fn (Support\Node $node) : int => $node->id, $result), $result);
        // fill root one
        if (empty($result[$this->tableSettings->virtualRootId])) {
            // !!! beware that this creates a virtual node!
            $virtualRoot = clone $this->nodeBase; // hack for root node
            $virtualRoot->id = $this->tableSettings->virtualRootId; // must be outside the db values
            $virtualRoot->left = -1; // must be outside the db values
            $virtualRoot->level = $this->tableSettings->rootLevel - 1; // must be lower than the actual root level
            $result[$this->tableSettings->virtualRootId] = $virtualRoot;
        }

        // now process the array and build the child data
        return $this->getTreeRebuildChildren($result);
    }

    /**
     * Detect that is this taxonomy's parent setting to be under this taxonomy's children or not.<br>
     * For example: Root 1 > 1.1 > 1.1.1 > 1.1.1.1 > 1.1.1.1.1<br>
     * Assume that you are editing 1.1.1 and its parent is 1.1. Now you change its parent to 1.1.1.1.1 which is under its children.<br>
     * The parent of 1.1.1 must be root, Root 1, 1.1 and never go under that.
     *
     * @param int<1, max> $currentNodeId The taxonomy ID that is changing the parent.
     * @param int<0, max>|null $newParentId The selected parent ID to check.
     * @param Support\Options $options Where array structure will be like this.
     * @return bool Return `false` if its parent is under its children (INCORRECT changes).<br>
     *              Return `false` if search result was not found (INCORRECT changes).<br>
     *              Return `true` if its parent is not under its children (CORRECT changes).
     */
    public function isNewParentOutsideCurrentNodeTree(int $currentNodeId, ?int $newParentId, Support\Options $options = new Support\Options()) : bool
    {
        if (empty($newParentId)) {
            // if parent is root, always return true because that is always correct!
            return true;
        }

        // check for selected parent that must not under this taxonomy.
        $options->currentId = $newParentId;
        $nodesWithParents = $this->getNodesWithParents($options);

        if (!empty($nodesWithParents->items)) {
            foreach ($nodesWithParents->items as $row) {
                if ($row->parentId === $currentNodeId) {
                    return false;
                }
            }

            return true;
        }

        return false;
    }

    /**
     * List taxonomy.
     *
     * The columns `left`, `right` must have been built before using this method, otherwise the result will be incorrect.
     *
     * @param Support\Options $options Available options
     */
    public function listNodes(Support\Options $options = new Support\Options()) : Support\Result
    {
        $output = new Support\Result();
        $output->count = $this->source->selectCount($options);
        $output->items = $this->source->selectLimited($options);

        if (!$options->listFlattened) {
            $output = $this->listNodesBuildTreeWithChildren($output, $options);
        }

        return $output;
    }

    /**
     * Build tree data with children.
     *
     * @internal This method was called from `listTaxonomy()`.
     * @param Support\Result $result The array item get from fetchAll() method using the PDO.
     * @param Support\Options $options Available options
     * @return Support\Result Return array data of formatted values.
     */
    protected function listNodesBuildTreeWithChildren(Support\Result $result, Support\Options $options) : Support\Result
    {
        $items = [];
        foreach ($result->items as &$item) {
            $items[$item->parentId][] = $item;
        }

        if (empty($options->filterIdBy)) {
            // without taxonomy_id_in option exists, this result can format to be hierarchical.
            foreach ($result->items as $row) {
                if (isset($items[$row->id])) {
                    $row->childrenNodes = $items[$row->id];
                    $row->childrenIds = array_map(fn (Support\Node $node) => $node->id, $row->childrenNodes);
                }
            }

            $partItems = ($items[0] ?? array_shift($items)); // this is important ([0]) for prevent duplicate items
            if (empty($partItems)) {
                return new Support\Result();
            } else {
                $result->items = $partItems;
            }
        }

        return $result;
    }

    /**
     * List taxonomy as flatten not tree.<br>
     * All parameters or arguments are same as `listTaxonomy()` method.
     *
     * @param Support\Options $options Available options
     */
    public function listNodesFlatten(Support\Options $options = new Support\Options()) : Support\Result
    {
        $options->listFlattened = true;

        return $this->listNodes($options);
    }

    /**
     * Rebuilds the tree data and save it to the database.<br>
     * This will rebuild the level, left, right values.
     *
     * The columns `left`, `right` must have been built before using this method, otherwise the result will be incorrect.
     *
     * @param Support\Options $options Where array structure will be like this.
     */
    public function rebuild(Support\Options $options = new Support\Options()) : void
    {
        // get taxonomy tree data in the array format that suit for loop/nest loop verify level.
        $data = $this->getTreeWithChildren($options);

        // because it's possible that data reference themselves I need to remove them from the circle
        $this->clearChildrenForSelfReferences($data);

        $n = $data[$this->tableSettings->virtualRootId]->left + 1; // need a variable to hold the running n tally
        $p = 0; // need a variable to hold the running position tally

        // rebuild positions
        $this->rebuildGeneratePositionData($data, $this->tableSettings->virtualRootId, $p);

        // verify the level data. this method will alter the $data value because it will be called as reference.
        // so, it doesn't need to use `$data = $this->rebuildGenerateTreeData()`;
        $this->rebuildGenerateTreeData($data, $this->tableSettings->virtualRootId, $this->tableSettings->rootLevel, $n);

        foreach ($data as $row) {
            if ($this->tableSettings->rootIsNull && $this->tableSettings->virtualRootId === $row->id) {
                // this shall skip the virtual root
                // normal one will need to be updated too
                continue;
            }

            $this->source->updateLeftRightPos($row, $options->where);
        }
    }

    /**
     * Rebuild taxonomy level, left, right for tree data.<br>
     * This method will alter the $array value. It will be set level, left, right value.
     *
     * This method modify variables via argument reference without return anything.
     *
     * @internal This method was called from `rebuild()`.
     * @param array<int<-1, max>, Support\Node> $array The data array, will be call as reference and modify its value.

     * @param int<-1, max> $id The ID of taxonomy.
     * @param int<-1, max> $level The level of taxonomy.
     * @param int<0, max> $n The tally or count number, will be call as reference and modify its value.
     */
    protected function rebuildGenerateTreeData(array &$array, int $id, int $level, int &$n) : void
    {
        $array[$id]->level = $level;
        $array[$id]->left = $n++;

        // loop over the node's children and process their data
        // before assigning the right value
        foreach ($array[$id]->childrenIds as $childNodeId) {
            $this->rebuildGenerateTreeData($array, $childNodeId, $level + 1, $n);
        }

        $array[$id]->right = $n++;
    }

    /**
     * Rebuild taxonomy positions for tree data.<br>
     * This method will alter the $array value. It will set position value.
     *
     * This method modify variables via argument reference without return anything.
     *
     * @internal This method was called from `rebuild()`.
     * @param array<int<-1, max>, Support\Node> $array The data array, will be call as reference and modify its value.

     * @param int<-1, max> $id The ID of taxonomy.
     * @param int<0, max> $n The position number, will be call as reference and modify its value.
     */
    protected function rebuildGeneratePositionData(array &$array, int $id, int &$n) : void
    {
        $array[$id]->position = ++$n;

        // loop over the node's children and process their data
        // before assigning the right value
        $p = 0;
        foreach ($array[$id]->childrenIds as $childNodeId) {
            $this->rebuildGeneratePositionData($array, $childNodeId, $p);
        }

        usort($array[$id]->childrenIds, function (int $a, int $b) use ($array) {
            return $array[$a]->position <=> $array[$b]->position;
        });
    }

    /**
     * Clear data of references to Self.<br>
     * This method will alter the $array value. It will remove the ids of entries which references the entry itself
     *
     * This method modify variables via argument reference without return anything.
     *
     * @internal This method was called from `rebuild()`.
     * @param array<int<-1, max>, Support\Node> $array The data array, will be call as reference and modify its value.

     */
    protected function clearChildrenForSelfReferences(array &$array) : void
    {
        // loop over the node's children and process their data
        foreach ($array as &$node) {
            $node->childrenIds = array_filter(
                $node->childrenIds,
                fn (int $id) : bool => $node->id !== $id
            );
            $node->childrenNodes = array_filter(
                $node->childrenNodes,
                fn (Support\Node $child) : bool => in_array($child->id, $node->childrenIds)
            );
        }
    }
}
