20970999518

Committed 13 Jan 2026 08:10PM UTC coverage: 99.383% (-0.001%) from 99.384%

Build # 20970999518

Build Type

Pull #2

github

Committed by

dakujem

Commit Message

Tree::link optimization possibility

Enable option to omit duplicity checking when linking wide trees

Pull Request Pull Request #2: Optimize `Tree::link` method

Run Details

7 of 7 new or added lines in 1 file covered. (100.0%)

1 existing line in 1 file now uncovered.

483 of 486 relevant lines covered (99.38%)

5.84 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.15

/src/Tree.php

<?php

declare(strict_types=1);

namespace Dakujem\Oliva;

use Dakujem\Oliva\Exceptions\NodeNotMovable;

/**
 * A helper class for high-level tree operations.
 *
 * This contrasts with the low-level interface of movable nodes:
 * @see MovableNodeContract
 *
 * @author Andrej Rypak <xrypak@gmail.com>
 */
final class Tree
{
    /**
     * Attaches a node to a parent,
     * establishing both the child-to-parent link and adding the child to the parent's children list.
     *
     * If a key is given, the node will be added under that key.
     * If already added, it will be re-added under the new key.
     *
     * If the node already has a parent at the moment of the call,
     * that link will be broken and the original parent will be returned.
     *
     * Null is returned in all other cases.
     */
    public static function link(
        MovableNodeContract $node,
        MovableNodeContract $parent,
        string|int|null $key = null,
        bool $preventDuplicateLinking = true,
    ): ?MovableNodeContract {
        $currentParent = $node->parent();

        // If the node already has a parent, but it is different from the target one, detach the node first.
        if (null !== $currentParent && $currentParent !== $parent) {
            $originalParent = self::unlink($node);
            $currentParent = null;
        }

        // Set the parent reference (child-to-parent link).
        if (null === $currentParent) {
            $node->setParent($parent);
        }

        // Create the parent-to-child link.
        self::adoptChild($parent, $node, $key, $preventDuplicateLinking);

        // If a parent was unlinked during the process, return it.
        return $originalParent ?? null;
    }

    /**
     * Detaches a node from its parent,
     * both resetting the child-to-parent link and removing the node from among its parent's children list.
     *
     * Returns the original parent, if any.
     */
    public static function unlink(
        MovableNodeContract $node,
    ): ?MovableNodeContract {
        $parent = $node->parent();
        if (null === $parent) {
            // The parent is already null, terminate.
            return null;
        }
        if (!$parent instanceof MovableNodeContract) {
            throw new NodeNotMovable($parent);
        }
        $node->setParent(null);
        $parent->removeChild($node);
        return $parent;
    }

    /**
     * Attaches a bunch of nodes to a parent,
     * establishing both the child-to-parent link and adding the child to the parent's children list.
     *
     * Does NOT remove the original children of the parent node ($parent).
     *
     * The callable $onParentUnlinked may be used to process cases where the original node's parent is unlinked.
     *
     * The call does not use the keys in the given list of children.
     * However, those may be used via the $key callable, in fact, any valid keys may be returned.
     */
    public static function linkChildren(
        MovableNodeContract $parent,
        iterable $children,
        ?callable $key = null,
        ?callable $onParentUnlinked = null,
    ): MovableNodeContract {
        foreach ($children as $index => $child) {
            if (!$child instanceof MovableNodeContract) {
                throw new NodeNotMovable($child);
            }
            $originalParent = self::link(
                node: $child,
                parent: $parent,
                key: null !== $key ? $key($child, $index) : null,
            );
            if (null !== $originalParent && null !== $onParentUnlinked) {
                $onParentUnlinked($originalParent, $child);
            }
        }
        return $parent;
    }

    /**
     * Unlinks all children of a node,
     * both resetting the child-to-parent links and removing the nodes the children list.
     */
    public static function unlinkChildren(
        MovableNodeContract $parent,
    ): void {
        foreach ($parent->children() as $key => $child) {
            if (!$child instanceof MovableNodeContract) {
                throw new NodeNotMovable($child);
            }
            $child->setParent(null);
        }
        $parent->removeChildren();
    }

    /**
     * Sorts children and recalculates their child keys of all tree nodes recursively.
     *
     * Both operations are optional:
     * - If the key-calculating function is not passed in, the child keys will not be altered.
     * - If the sorting function is not passed in, the order of the nodes will not change.
     *
     * Example usage of <=> (spaceship) operator to sort children based on path props:
     * `fn(Node $a, Node $b) => '!'.$a->data()->path <=> '!'.$b->data()->path`
     * (Note the `!` prefix above is to prevent issues with "000" <=> "000000" being 0, incorrect, while "!000" <=> "!000000" being -1, correct.)
     */
    public static function reindexTree(
        MovableNodeContract $node,
        ?callable $key,
        ?callable $sort,
    ): void {
        $children = Seed::array($node->children());
        $node->removeChildren();
        if (null !== $sort) {
            uasort($children, $sort);
        }
        $seq = 0;
        foreach ($children as $childKey => $child) {
            if (!$child instanceof MovableNodeContract) {
                throw new NodeNotMovable($child);
            }
            $newKey = null !== $key ? $key($child, $childKey, $seq) : $childKey;
            $node->addChild($child, $newKey);
            self::reindexTree($child, $key, $sort);
            $seq += 1;
        }
    }

    /**
     * @internal
     */
    private static function adoptChild(
        MovableNodeContract $parent,
        MovableNodeContract $child,
        string|int|null $key,
        bool $preventDuplicateLinking,
    ): void {
        // Note:
        // The duplicate adding prevention is very slow for nodes with many siblings due to the child node lookup
        // (done by the `childKey` method), if not optimized internally.
        $existing = $preventDuplicateLinking ? $parent->childKey($child) : null;
        if (
            null !== $existing &&
            $parent->child($existing) === $child &&
            (null === $key || $existing === $key)
        ) {
            // Already linked (with the same key or key not important).
            return;
        }
        $parent->addChild($child, $key);
        if (null !== $existing) {
            // The child has already been linked to the same parent but under a different key. Remove that link.
            // Note:
            //   Important to keep this _after_ adding the node
            //   to prevent inconsistent state if adding failed due to a conflicting key.
            $parent->removeChild($existing);
        }
    }
}

1	<?php
2
3	declare(strict_types=1);
4
5	namespace Dakujem\Oliva;
6
7	use Dakujem\Oliva\Exceptions\NodeNotMovable;
8
9	/**
10	* A helper class for high-level tree operations.
11	*
12	* This contrasts with the low-level interface of movable nodes:
13	* @see MovableNodeContract
14	*
15	* @author Andrej Rypak <xrypak@gmail.com>
16	*/
17	final class Tree
18	{
19	/**
20	* Attaches a node to a parent,
21	* establishing both the child-to-parent link and adding the child to the parent's children list.
22	*
23	* If a key is given, the node will be added under that key.
24	* If already added, it will be re-added under the new key.
25	*
26	* If the node already has a parent at the moment of the call,
27	* that link will be broken and the original parent will be returned.
28	*
29	* Null is returned in all other cases.
30	*/
31	public static function link(
32	MovableNodeContract $node,
33	MovableNodeContract $parent,
34	string\|int\|null $key = null,
35	bool $preventDuplicateLinking = true,
36	): ?MovableNodeContract {
37	$currentParent = $node->parent();	6✔
38
39	// If the node already has a parent, but it is different from the target one, detach the node first.
40	if (null !== $currentParent && $currentParent !== $parent) {	6✔
41	$originalParent = self::unlink($node);	6✔
42	$currentParent = null;	6✔
43	}
44
45	// Set the parent reference (child-to-parent link).
46	if (null === $currentParent) {	6✔
47	$node->setParent($parent);	6✔
48	}
49
50	// Create the parent-to-child link.
51	self::adoptChild($parent, $node, $key, $preventDuplicateLinking);	6✔
52
53	// If a parent was unlinked during the process, return it.
54	return $originalParent ?? null;	6✔
55	}
56
57	/**
58	* Detaches a node from its parent,
59	* both resetting the child-to-parent link and removing the node from among its parent's children list.
60	*
61	* Returns the original parent, if any.
62	*/
63	public static function unlink(
64	MovableNodeContract $node,
65	): ?MovableNodeContract {
66	$parent = $node->parent();	6✔
67	if (null === $parent) {	6✔
68	// The parent is already null, terminate.
69	return null;	6✔
70	}
71	if (!$parent instanceof MovableNodeContract) {	6✔
72	throw new NodeNotMovable($parent);	6✔
73	}
74	$node->setParent(null);	6✔
75	$parent->removeChild($node);	6✔
76	return $parent;	6✔
77	}
78
79	/**
80	* Attaches a bunch of nodes to a parent,
81	* establishing both the child-to-parent link and adding the child to the parent's children list.
82	*
83	* Does NOT remove the original children of the parent node ($parent).
84	*
85	* The callable $onParentUnlinked may be used to process cases where the original node's parent is unlinked.
86	*
87	* The call does not use the keys in the given list of children.
88	* However, those may be used via the $key callable, in fact, any valid keys may be returned.
89	*/
90	public static function linkChildren(
91	MovableNodeContract $parent,
92	iterable $children,
93	?callable $key = null,
94	?callable $onParentUnlinked = null,
95	): MovableNodeContract {
96	foreach ($children as $index => $child) {	6✔
97	if (!$child instanceof MovableNodeContract) {	6✔
UNCOV 98	throw new NodeNotMovable($child);	×
99	}
100	$originalParent = self::link(	6✔
101	node: $child,	6✔
102	parent: $parent,	6✔
103	key: null !== $key ? $key($child, $index) : null,	6✔
104	);
105	if (null !== $originalParent && null !== $onParentUnlinked) {	6✔
106	$onParentUnlinked($originalParent, $child);	6✔
107	}
108	}
109	return $parent;	6✔
110	}
111
112	/**
113	* Unlinks all children of a node,
114	* both resetting the child-to-parent links and removing the nodes the children list.
115	*/
116	public static function unlinkChildren(
117	MovableNodeContract $parent,
118	): void {
119	foreach ($parent->children() as $key => $child) {	6✔
120	if (!$child instanceof MovableNodeContract) {	6✔
121	throw new NodeNotMovable($child);	6✔
122	}
123	$child->setParent(null);	6✔
124	}
125	$parent->removeChildren();	6✔
126	}	6✔
127
128	/**
129	* Sorts children and recalculates their child keys of all tree nodes recursively.
130	*
131	* Both operations are optional:
132	* - If the key-calculating function is not passed in, the child keys will not be altered.
133	* - If the sorting function is not passed in, the order of the nodes will not change.
134	*
135	* Example usage of <=> (spaceship) operator to sort children based on path props:
136	* `fn(Node $a, Node $b) => '!'.$a->data()->path <=> '!'.$b->data()->path`
137	* (Note the `!` prefix above is to prevent issues with "000" <=> "000000" being 0, incorrect, while "!000" <=> "!000000" being -1, correct.)
138	*/
139	public static function reindexTree(
140	MovableNodeContract $node,
141	?callable $key,
142	?callable $sort,
143	): void {
144	$children = Seed::array($node->children());	6✔
145	$node->removeChildren();	6✔
146	if (null !== $sort) {	6✔
147	uasort($children, $sort);	6✔
148	}
149	$seq = 0;	6✔
150	foreach ($children as $childKey => $child) {	6✔
151	if (!$child instanceof MovableNodeContract) {	6✔
152	throw new NodeNotMovable($child);	6✔
153	}
154	$newKey = null !== $key ? $key($child, $childKey, $seq) : $childKey;	6✔
155	$node->addChild($child, $newKey);	6✔
156	self::reindexTree($child, $key, $sort);	6✔
157	$seq += 1;	6✔
158	}
159	}	6✔
160
161	/**
162	* @internal
163	*/
164	private static function adoptChild(
165	MovableNodeContract $parent,
166	MovableNodeContract $child,
167	string\|int\|null $key,
168	bool $preventDuplicateLinking,
169	): void {
170	// Note:
171	// The duplicate adding prevention is very slow for nodes with many siblings due to the child node lookup
172	// (done by the `childKey` method), if not optimized internally.
173	$existing = $preventDuplicateLinking ? $parent->childKey($child) : null;	6✔
174	if (
175	null !== $existing &&	6✔
176	$parent->child($existing) === $child &&	6✔
177	(null === $key \|\| $existing === $key)	6✔
178	) {
179	// Already linked (with the same key or key not important).
180	return;	6✔
181	}
182	$parent->addChild($child, $key);	6✔
183	if (null !== $existing) {	6✔
184	// The child has already been linked to the same parent but under a different key. Remove that link.
185	// Note:
186	// Important to keep this _after_ adding the node
187	// to prevent inconsistent state if adding failed due to a conflicting key.
188	$parent->removeChild($existing);	6✔
189	}
190	}	6✔
191	}

dakujem / oliva / 20970999518

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous