24612504022

Committed 18 Apr 2026 07:47PM UTC coverage: 97.634% (+0.02%) from 97.61%

Build # 24612504022

Build Type

push

github

Committed by

chdemko

Commit Message

🚨 Fix methods complexity

Coverage Stats

57 of 60 new or added lines in 1 file covered. (95.0%)

784 of 803 relevant lines covered (97.63%)

120.68 hits per line

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

96.31

/src/SortedCollection/TreeNode.php

<?php

/**
 * chdemko\SortedCollection\TreeNode class
 *
 * @author    Christophe Demko <chdemko@gmail.com>
 * @copyright Copyright (C) 2012-2024 Christophe Demko. All rights reserved.
 *
 * @license BSD 3-Clause License
 *
 * This file is part of the php-sorted-collections package https://github.com/chdemko/php-sorted-collections
 */

// Declare chdemko\SortedCollection namespace
namespace chdemko\SortedCollection;

/**
 * TreeNode
 *
 * @package SortedCollection
 *
 * @since 1.0.0
 *
 * @property-read TreeNode       $first        The first node of the tree
 * @property-read TreeNode       $last         The last node of the tree
 * @property-read TreeNode|null  $predecessor  The predecessor node
 * @property-read TreeNode|null  $successor    The successor node
 * @property-read mixed          $key          The key
 * @property-read integer        $count        The number of elements in the tree
 */
class TreeNode implements \Countable
{
    /**
     * @var integer  Information associated to that node.
     *                   Bits of order 0 and 1 are reserved for the existence of left and right tree.
     *                   Other bits are for the balance
     *
     * @since 1.0.0
     */
    private $information = 0;

    /**
     * @var TreeNode|null  Left|Predecessor node
     *
     * @since 1.0.0
     */
    private $left;

    /**
     * @var TreeNode|null  Right|Successor node
     *
     * @since 1.0.0
     */
    private $right;

    /**
     * @var mixed  Node key
     *
     * @since 1.0.0
     */
    private $keyInternal;

    /**
     * @var mixed  Node value
     *
     * @since 1.0.0
     */
    public $value;

    /**
     * Create a node
     *
     * @param mixed $key   The node key
     * @param mixed $value The node value
     *
     * @return TreeNode A new node
     *
     * @since 1.0.0
     */
    public static function create($key, $value)
    {
        return new static($key, $value);
    }

    /**
     * Constructor
     *
     * @param mixed    $key         The node key
     * @param mixed    $value       The node value
     * @param TreeNode $predecessor The left node
     * @param TreeNode $successor   The right node
     *
     * @since 1.0.0
     */
    protected function __construct($key, $value, $predecessor = null, $successor = null)
    {
        $this->keyInternal = $key;
        $this->value = $value;
        $this->left = $predecessor;
        $this->right = $successor;
    }

    /**
     * Magic get method
     *
     * @param string $property The node property
     *
     * @return mixed The value associated to the property
     *
     * @throws RuntimeException If the property is undefined
     *
     * @since 1.0.0
     */
    public function __get($property)
    {
        switch ($property) {
            case 'first':
                return $this->first();
            case 'last':
                return $this->last();
            case 'predecessor':
                return $this->predecessor();
            case 'successor':
                return $this->successor();
            case 'key':
                return $this->keyInternal;
            case 'count':
                return $this->count();
            default:
                throw new \RuntimeException('Undefined property');
        }
    }

    /**
     * Get the first node
     *
     * @return TreeNode the first node
     *
     * @since 1.0.0
     */
    public function first()
    {
        $node = $this;

        while ($node->information & 2) {
            $node = $node->left;
        }

        return $node;
    }

    /**
     * Get the last node
     *
     * @return TreeNode the last node
     *
     * @since 1.0.0
     */
    public function last()
    {
        $node = $this;

        while ($node->information & 1) {
            $node = $node->right;
        }

        return $node;
    }

    /**
     * Get the predecessor
     *
     * @return TreeNode|null the predecessor node
     *
     * @since 1.0.0
     */
    public function predecessor()
    {
        if ($this->information & 2) {
            $node = $this->left;

            while ($node->information & 1) {
                $node = $node->right;
            }

            return $node;
        } else {
            return $this->left;
        }
    }

    /**
     * Get the successor
     *
     * @return TreeNode|null the successor node
     *
     * @since 1.0.0
     */
    public function successor()
    {
        if ($this->information & 1) {
            $node = $this->right;

            while ($node->information & 2) {
                $node = $node->left;
            }

            return $node;
        } else {
            return $this->right;
        }
    }

    /**
     * Count the number of key/value pair
     *
     * @return integer
     *
     * @since 1.0.0
     */
    public function count(): int
    {
        $count = 1;

        if ($this->information & 2) {
            $count += $this->left->count;
        }

        if ($this->information & 1) {
            $count += $this->right->count;
        }

        return $count;
    }

    /**
     * Get the node for a key
     *
     * @param mixed    $key        The key
     * @param callable $comparator The comparator function
     * @param integer  $type       The operation type
     *                             -2 for the
     *                             greatest key
     *                             lesser than the
     *                             given key -1 for
     *                             the greatest key
     *                             lesser than or
     *                             equal to the given
     *                             key 0 for the
     *                             given key +1 for
     *                             the lowest key
     *                             greater than or
     *                             equal to the given
     *                             key +2 for the
     *                             lowest key greater
     *                             than the given key
     *
     * @return mixed The node or null if not found
     *
     * @since 1.0.0
     */
    public function find($key, $comparator, $type = 0)
    {
        list($node, $cmp) = $this->traverseForFind($key, $comparator);

        return $this->resolveFindResult($node, $cmp, $type);
    }

    /**
     * Traverse tree for find operation
     *
     * @param mixed    $key        The searched key
     * @param callable $comparator The comparator function
     *
     * @return array{0: TreeNode, 1: integer} The closest node and comparison result
     *
     * @since 1.0.0
     */
    private function traverseForFind($key, $comparator)
    {
        $node = $this;
        $cmp = 0;

        while (true) {
            $cmp = call_user_func($comparator, $key, $node->keyInternal);

            if ($cmp < 0 && $node->information & 2) {
                $node = $node->left;
            } elseif ($cmp > 0 && $node->information & 1) {
                $node = $node->right;
            } else {
                break;
            }
        }

        return array($node, $cmp);
    }

    /**
     * Resolve find result from traversal state
     *
     * @param TreeNode $node The closest node
     * @param integer  $cmp  The key comparison result
     * @param integer  $type The operation type
     *
     * @return mixed The resolved node or null
     *
     * @since 1.0.0
     */
    private function resolveFindResult($node, $cmp, $type)
    {
        if ($cmp < 0) {
            if ($type < 0) {
                return $node->left;
            }

            if ($type > 0) {
                return $node;
            }

            return null;
        }

        if ($cmp > 0) {
            if ($type < 0) {
                return $node;
            }

            if ($type > 0) {
                return $node->right;
            }

            return null;
        }

        if ($type < -1) {
            return $node->predecessor;
        }

        if ($type > 1) {
            return $node->successor;
        }

        return $node;
    }

    /**
     * Rotate the node to the left
     *
     * @return TreeNode The rotated node
     *
     * @since 1.0.0
     */
    private function rotateLeft()
    {
        $right = $this->right;

        if ($right->information & 2) {
            $this->right = $right->left;
            $right->left = $this;
        } else {
            $right->information |= 2;
            $this->information &= ~ 1;
        }

        $this->information -= 4;

        if ($right->information >= 4) {
            $this->information -= $right->information & ~3;
        }

        $right->information -= 4;

        if ($this->information < 0) {
            $right->information += $this->information & ~3;
        }

        return $right;
    }

    /**
     * Rotate the node to the right
     *
     * @return TreeNode The rotated node
     *
     * @since 1.0.0
     */
    private function rotateRight()
    {
        $left = $this->left;

        if ($left->information & 1) {
            $this->left = $left->right;
            $left->right = $this;
        } else {
            $this->information &= ~ 2;
            $left->information |= 1;
        }

        $this->information += 4;

        if ($left->information < 0) {
            $this->information -= $left->information & ~3;
        }

        $left->information += 4;

        if ($this->information >= 4) {
            $left->information += $this->information & ~3;
        }

        return $left;
    }

    /**
     * Increment the balance of the node
     *
     * @return TreeNode $this or a rotated version of $this
     *
     * @since 1.0.0
     */
    private function incBalance()
    {
        $this->information += 4;

        if ($this->information >= 8) {
            $right = $this->right;

            if (!$right instanceof self) {
                return $this;
            }

            if ($right->information < 0) {
                $this->right = $right->rotateRight();
            }

            return $this->rotateLeft();
        }

        return $this;
    }

    /**
     * Decrement the balance of the node
     *
     * @return TreeNode $this or a rotated version of $this
     *
     * @since 1.0.0
     */
    private function decBalance()
    {
        $this->information -= 4;

        if ($this->information < - 4) {
            $left = $this->left;

            if (!$left instanceof self) {
                return $this;
            }

            if ($left->information >= 4) {
                $this->left = $left->rotateLeft();
            }

            return $this->rotateRight();
        }

        return $this;
    }

    /**
     * Insert a key/value pair
     *
     * @param mixed    $key        The key
     * @param mixed    $value      The value
     * @param callable $comparator The comparator function
     *
     * @return TreeNode The new root
     *
     * @since 1.0.0
     */
    public function insert($key, $value, $comparator)
    {
        $node = $this;
        $cmp = call_user_func($comparator, $key, $this->keyInternal);

        if ($cmp < 0) {
            if ($this->information & 2) {
                $left = $this->left;

                if (!$left instanceof self) {
                    return $node;
                }

                $leftBalance = $left->information & ~3;
                $this->left = $left->insert($key, $value, $comparator);

                if (
                    $this->left instanceof self
                    && ($this->left->information & ~3)
                    && ($this->left->information & ~3) != $leftBalance
                ) {
                    $node = $this->decBalance();
                }
            } else {
                $this->left = new static($key, $value, $this->left, $this);
                $this->information |= 2;
                $node = $this->decBalance();
            }
        } elseif ($cmp > 0) {
            if ($this->information & 1) {
                $right = $this->right;

                if (!$right instanceof self) {
                    return $node;
                }

                $rightBalance = $right->information & ~3;
                $this->right = $right->insert($key, $value, $comparator);

                if (
                    $this->right instanceof self
                    && ($this->right->information & ~3)
                    && ($this->right->information & ~3) != $rightBalance
                ) {
                    $node = $this->incBalance();
                }
            } else {
                $this->right = new static($key, $value, $this, $this->right);
                $this->information |= 1;
                $node = $this->incBalance();
            }
        } else {
            $this->value = $value;
        }

        return $node;
    }

    /**
     * Pull up the left most node of a node
     *
     * @return TreeNode The new root
     *
     * @since 1.0.0
     */
    private function pullUpLeftMost()
    {
        if ($this->information & 2) {
            $left = $this->left;

            if (!$left instanceof self) {
                return $this;
            }

            $leftBalance = $left->information & ~3;
            $this->left = $left->pullUpLeftMost();

            if (
                !($this->information & 2)
                || $leftBalance != 0 && ($this->left instanceof self) && ($this->left->information & ~3) == 0
            ) {
                return $this->incBalance();
            } else {
                return $this;
            }
        } else {
            $this->left->keyInternal = $this->keyInternal;
            $this->left->value = $this->value;

            if ($this->information & 1) {
                $this->right->left = $this->left;

                return $this->right;
            } else {
                if ($this->left->right == $this) {
                    $this->left->information &= ~ 1;

                    return $this->right;
                } else {
                    $this->right->information &= ~ 2;

                    return $this->left;
                }
            }
        }
    }

    /**
     * Remove a key
     *
     * @param mixed    $key        The key
     * @param callable $comparator The comparator function
     *
     * @return TreeNode The new root
     *
     * @since 1.0.0
     */
    public function remove($key, $comparator)
    {
        $cmp = call_user_func($comparator, $key, $this->keyInternal);

        if ($cmp < 0) {
            return $this->removeFromLeft($key, $comparator);
        }

        if ($cmp > 0) {
            return $this->removeFromRight($key, $comparator);
        }

        return $this->removeCurrent();
    }

    /**
     * Remove from left subtree
     *
     * @param mixed    $key        The key
     * @param callable $comparator The comparator function
     *
     * @return TreeNode|null The new root
     *
     * @since 1.0.0
     */
    private function removeFromLeft($key, $comparator)
    {
        if ($this->information & 2) {
            $left = $this->left;

            if (!$left instanceof self) {
                return $this;
            }

            $leftBalance = $left->information & ~3;
            $this->left = $left->remove($key, $comparator);

            if (
                !($this->information & 2)
                || $leftBalance != 0 && ($this->left instanceof self) && ($this->left->information & ~3) == 0
            ) {
                return $this->incBalance();
            }
        }

        return $this;
    }

    /**
     * Remove from right subtree
     *
     * @param mixed    $key        The key
     * @param callable $comparator The comparator function
     *
     * @return TreeNode|null The new root
     *
     * @since 1.0.0
     */
    private function removeFromRight($key, $comparator)
    {
        if ($this->information & 1) {
            $right = $this->right;

            if (!$right instanceof self) {
                return $this;
            }

            $rightBalance = $right->information & ~3;
            $this->right = $right->remove($key, $comparator);

            if (
                !($this->information & 1)
                || $rightBalance != 0 && ($this->right instanceof self) && ($this->right->information & ~3) == 0
            ) {
                return $this->decBalance();
            }
        }

        return $this;
    }

    /**
     * Remove current node key
     *
     * @return TreeNode|null The new root
     *
     * @since 1.0.0
     */
    private function removeCurrent()
    {
        if ($this->information & 1) {
            $right = $this->right;

            if (!$right instanceof self) {
                return $this;
            }

            $rightBalance = $right->information & ~3;
            $this->right = $right->pullUpLeftMost();

            if (
                !($this->information & 1)
                || $rightBalance != 0 && ($this->right instanceof self) && ($this->right->information & ~3) == 0
            ) {
                return $this->decBalance();
            }

            return $this;
        }

        $left = $this->left;
        $right = $this->right;

        if ($this->information & 2) {
            $left->right = $right;

            return $left;
        }

        if ($left && $left->right == $this) {
            $left->information &= ~ 1;

            return $right;
        }

        if ($right && $right->left == $this) {
            $right->information &= ~ 2;

            return $left;
        }

        return null;
    }
}

1	<?php
2
3	/**
4	* chdemko\SortedCollection\TreeNode class
5	*
6	* @author Christophe Demko <chdemko@gmail.com>
7	* @copyright Copyright (C) 2012-2024 Christophe Demko. All rights reserved.
8	*
9	* @license BSD 3-Clause License
10	*
11	* This file is part of the php-sorted-collections package https://github.com/chdemko/php-sorted-collections
12	*/
13
14	// Declare chdemko\SortedCollection namespace
15	namespace chdemko\SortedCollection;
16
17	/**
18	* TreeNode
19	*
20	* @package SortedCollection
21	*
22	* @since 1.0.0
23	*
24	* @property-read TreeNode $first The first node of the tree
25	* @property-read TreeNode $last The last node of the tree
26	* @property-read TreeNode\|null $predecessor The predecessor node
27	* @property-read TreeNode\|null $successor The successor node
28	* @property-read mixed $key The key
29	* @property-read integer $count The number of elements in the tree
30	*/
31	class TreeNode implements \Countable
32	{
33	/**
34	* @var integer Information associated to that node.
35	* Bits of order 0 and 1 are reserved for the existence of left and right tree.
36	* Other bits are for the balance
37	*
38	* @since 1.0.0
39	*/
40	private $information = 0;
41
42	/**
43	* @var TreeNode\|null Left\|Predecessor node
44	*
45	* @since 1.0.0
46	*/
47	private $left;
48
49	/**
50	* @var TreeNode\|null Right\|Successor node
51	*
52	* @since 1.0.0
53	*/
54	private $right;
55
56	/**
57	* @var mixed Node key
58	*
59	* @since 1.0.0
60	*/
61	private $keyInternal;
62
63	/**
64	* @var mixed Node value
65	*
66	* @since 1.0.0
67	*/
68	public $value;
69
70	/**
71	* Create a node
72	*
73	* @param mixed $key The node key
74	* @param mixed $value The node value
75	*
76	* @return TreeNode A new node
77	*
78	* @since 1.0.0
79	*/
80	public static function create($key, $value)
81	{
82	return new static($key, $value);	772✔
83	}
84
85	/**
86	* Constructor
87	*
88	* @param mixed $key The node key
89	* @param mixed $value The node value
90	* @param TreeNode $predecessor The left node
91	* @param TreeNode $successor The right node
92	*
93	* @since 1.0.0
94	*/
95	protected function __construct($key, $value, $predecessor = null, $successor = null)
96	{
97	$this->keyInternal = $key;	772✔
98	$this->value = $value;	772✔
99	$this->left = $predecessor;	772✔
100	$this->right = $successor;	772✔
101	}
102
103	/**
104	* Magic get method
105	*
106	* @param string $property The node property
107	*
108	* @return mixed The value associated to the property
109	*
110	* @throws RuntimeException If the property is undefined
111	*
112	* @since 1.0.0
113	*/
114	public function __get($property)
115	{
116	switch ($property) {
117	case 'first':	614✔
118	return $this->first();	397✔
119	case 'last':	614✔
120	return $this->last();	368✔
121	case 'predecessor':	614✔
122	return $this->predecessor();	404✔
123	case 'successor':	604✔
124	return $this->successor();	445✔
125	case 'key':	593✔
126	return $this->keyInternal;	587✔
127	case 'count':	8✔
128	return $this->count();	7✔
129	default:
130	throw new \RuntimeException('Undefined property');	1✔
131	}
132	}
133
134	/**
135	* Get the first node
136	*
137	* @return TreeNode the first node
138	*
139	* @since 1.0.0
140	*/
141	public function first()
142	{
143	$node = $this;	397✔
144
145	while ($node->information & 2) {	397✔
146	$node = $node->left;	392✔
147	}
148
149	return $node;	397✔
150	}
151
152	/**
153	* Get the last node
154	*
155	* @return TreeNode the last node
156	*
157	* @since 1.0.0
158	*/
159	public function last()
160	{
161	$node = $this;	368✔
162
163	while ($node->information & 1) {	368✔
164	$node = $node->right;	363✔
165	}
166
167	return $node;	368✔
168	}
169
170	/**
171	* Get the predecessor
172	*
173	* @return TreeNode\|null the predecessor node
174	*
175	* @since 1.0.0
176	*/
177	public function predecessor()
178	{
179	if ($this->information & 2) {	404✔
180	$node = $this->left;	374✔
181
182	while ($node->information & 1) {	374✔
183	$node = $node->right;	314✔
184	}
185
186	return $node;	374✔
187	} else {
188	return $this->left;	387✔
189	}
190	}
191
192	/**
193	* Get the successor
194	*
195	* @return TreeNode\|null the successor node
196	*
197	* @since 1.0.0
198	*/
199	public function successor()
200	{
201	if ($this->information & 1) {	445✔
202	$node = $this->right;	409✔
203
204	while ($node->information & 2) {	409✔
205	$node = $node->left;	340✔
206	}
207
208	return $node;	409✔
209	} else {
210	return $this->right;	433✔
211	}
212	}
213
214	/**
215	* Count the number of key/value pair
216	*
217	* @return integer
218	*
219	* @since 1.0.0
220	*/
221	public function count(): int
222	{
223	$count = 1;	7✔
224
225	if ($this->information & 2) {	7✔
226	$count += $this->left->count;	7✔
227	}
228
229	if ($this->information & 1) {	7✔
230	$count += $this->right->count;	7✔
231	}
232
233	return $count;	7✔
234	}
235
236	/**
237	* Get the node for a key
238	*
239	* @param mixed $key The key
240	* @param callable $comparator The comparator function
241	* @param integer $type The operation type
242	* -2 for the
243	* greatest key
244	* lesser than the
245	* given key -1 for
246	* the greatest key
247	* lesser than or
248	* equal to the given
249	* key 0 for the
250	* given key +1 for
251	* the lowest key
252	* greater than or
253	* equal to the given
254	* key +2 for the
255	* lowest key greater
256	* than the given key
257	*
258	* @return mixed The node or null if not found
259	*
260	* @since 1.0.0
261	*/
262	public function find($key, $comparator, $type = 0)
263	{
264	list($node, $cmp) = $this->traverseForFind($key, $comparator);	257✔
265
266	return $this->resolveFindResult($node, $cmp, $type);	257✔
267	}
268
269	/**
270	* Traverse tree for find operation
271	*
272	* @param mixed $key The searched key
273	* @param callable $comparator The comparator function
274	*
275	* @return array{0: TreeNode, 1: integer} The closest node and comparison result
276	*
277	* @since 1.0.0
278	*/
279	private function traverseForFind($key, $comparator)
280	{
281	$node = $this;	257✔
282	$cmp = 0;	257✔
283
284	while (true) {	257✔
285	$cmp = call_user_func($comparator, $key, $node->keyInternal);	257✔
286
287	if ($cmp < 0 && $node->information & 2) {	257✔
288	$node = $node->left;	118✔
289	} elseif ($cmp > 0 && $node->information & 1) {	257✔
290	$node = $node->right;	154✔
291	} else {
292	break;	257✔
293	}
294	}
295
296	return array($node, $cmp);	257✔
297	}
298
299	/**
300	* Resolve find result from traversal state
301	*
302	* @param TreeNode $node The closest node
303	* @param integer $cmp The key comparison result
304	* @param integer $type The operation type
305	*
306	* @return mixed The resolved node or null
307	*
308	* @since 1.0.0
309	*/
310	private function resolveFindResult($node, $cmp, $type)
311	{
312	if ($cmp < 0) {	257✔
313	if ($type < 0) {	29✔
314	return $node->left;	12✔
315	}
316
317	if ($type > 0) {	17✔
318	return $node;	12✔
319	}
320
321	return null;	5✔
322	}
323
324	if ($cmp > 0) {	228✔
325	if ($type < 0) {	39✔
326	return $node;	12✔
327	}
328
329	if ($type > 0) {	27✔
330	return $node->right;	14✔
331	}
332
333	return null;	13✔
334	}
335
336	if ($type < -1) {	193✔
337	return $node->predecessor;	41✔
338	}
339
340	if ($type > 1) {	159✔
341	return $node->successor;	46✔
342	}
343
344	return $node;	120✔
345	}
346
347	/**
348	* Rotate the node to the left
349	*
350	* @return TreeNode The rotated node
351	*
352	* @since 1.0.0
353	*/
354	private function rotateLeft()
355	{
356	$right = $this->right;	632✔
357
358	if ($right->information & 2) {	632✔
359	$this->right = $right->left;	471✔
360	$right->left = $this;	471✔
361	} else {
362	$right->information \|= 2;	632✔
363	$this->information &= ~ 1;	632✔
364	}
365
366	$this->information -= 4;	632✔
367
368	if ($right->information >= 4) {	632✔
369	$this->information -= $right->information & ~3;	630✔
370	}
371
372	$right->information -= 4;	632✔
373
374	if ($this->information < 0) {	632✔
375	$right->information += $this->information & ~3;	8✔
376	}
377
378	return $right;	632✔
379	}
380
381	/**
382	* Rotate the node to the right
383	*
384	* @return TreeNode The rotated node
385	*
386	* @since 1.0.0
387	*/
388	private function rotateRight()
389	{
390	$left = $this->left;	194✔
391
392	if ($left->information & 1) {	194✔
393	$this->left = $left->right;	60✔
394	$left->right = $this;	60✔
395	} else {
396	$this->information &= ~ 2;	185✔
397	$left->information \|= 1;	185✔
398	}
399
400	$this->information += 4;	194✔
401
402	if ($left->information < 0) {	194✔
403	$this->information -= $left->information & ~3;	154✔
404	}
405
406	$left->information += 4;	194✔
407
408	if ($this->information >= 4) {	194✔
409	$left->information += $this->information & ~3;	8✔
410	}
411
412	return $left;	194✔
413	}
414
415	/**
416	* Increment the balance of the node
417	*
418	* @return TreeNode $this or a rotated version of $this
419	*
420	* @since 1.0.0
421	*/
422	private function incBalance()
423	{
424	$this->information += 4;	702✔
425
426	if ($this->information >= 8) {	702✔
427	$right = $this->right;	630✔
428
429	if (!$right instanceof self) {	630✔
430	return $this;	×
431	}
432
433	if ($right->information < 0) {	630✔
434	$this->right = $right->rotateRight();	55✔
435	}
436
437	return $this->rotateLeft();	630✔
438	}
439
440	return $this;	702✔
441	}
442
443	/**
444	* Decrement the balance of the node
445	*
446	* @return TreeNode $this or a rotated version of $this
447	*
448	* @since 1.0.0
449	*/
450	private function decBalance()
451	{
452	$this->information -= 4;	393✔
453
454	if ($this->information < - 4) {	393✔
455	$left = $this->left;	166✔
456
457	if (!$left instanceof self) {	166✔
458	return $this;	×
459	}
460
461	if ($left->information >= 4) {	166✔
462	$this->left = $left->rotateLeft();	55✔
463	}
464
465	return $this->rotateRight();	166✔
466	}
467
468	return $this;	393✔
469	}
470
471	/**
472	* Insert a key/value pair
473	*
474	* @param mixed $key The key
475	* @param mixed $value The value
476	* @param callable $comparator The comparator function
477	*
478	* @return TreeNode The new root
479	*
480	* @since 1.0.0
481	*/
482	public function insert($key, $value, $comparator)
483	{
484	$node = $this;	753✔
485	$cmp = call_user_func($comparator, $key, $this->keyInternal);	753✔
486
487	if ($cmp < 0) {	753✔
488	if ($this->information & 2) {	387✔
489	$left = $this->left;	317✔
490
491	if (!$left instanceof self) {	317✔
492	return $node;	×
493	}
494
495	$leftBalance = $left->information & ~3;	317✔
496	$this->left = $left->insert($key, $value, $comparator);	317✔
497
498	if (
499	$this->left instanceof self	317✔
500	&& ($this->left->information & ~3)	317✔
501	&& ($this->left->information & ~3) != $leftBalance	317✔
502	) {
503	$node = $this->decBalance();	316✔
504	}
505	} else {
506	$this->left = new static($key, $value, $this->left, $this);	338✔
507	$this->information \|= 2;	338✔
508	$node = $this->decBalance();	338✔
509	}
510	} elseif ($cmp > 0) {	703✔
511	if ($this->information & 1) {	700✔
512	$right = $this->right;	630✔
513
514	if (!$right instanceof self) {	630✔
515	return $node;	×
516	}
517
518	$rightBalance = $right->information & ~3;	630✔
519	$this->right = $right->insert($key, $value, $comparator);	630✔
520
521	if (
522	$this->right instanceof self	630✔
523	&& ($this->right->information & ~3)	630✔
524	&& ($this->right->information & ~3) != $rightBalance	630✔
525	) {
526	$node = $this->incBalance();	630✔
527	}
528	} else {
529	$this->right = new static($key, $value, $this, $this->right);	700✔
530	$this->information \|= 1;	700✔
531	$node = $this->incBalance();	700✔
532	}
533	} else {
534	$this->value = $value;	4✔
535	}
536
537	return $node;	753✔
538	}
539
540	/**
541	* Pull up the left most node of a node
542	*
543	* @return TreeNode The new root
544	*
545	* @since 1.0.0
546	*/
547	private function pullUpLeftMost()
548	{
549	if ($this->information & 2) {	177✔
550	$left = $this->left;	143✔
551
552	if (!$left instanceof self) {	143✔
553	return $this;	×
554	}
555
556	$leftBalance = $left->information & ~3;	143✔
557	$this->left = $left->pullUpLeftMost();	143✔
558
559	if (
560	!($this->information & 2)	143✔
561	\|\| $leftBalance != 0 && ($this->left instanceof self) && ($this->left->information & ~3) == 0	143✔
562	) {
563	return $this->incBalance();	143✔
564	} else {
565	return $this;	7✔
566	}
567	} else {
568	$this->left->keyInternal = $this->keyInternal;	177✔
569	$this->left->value = $this->value;	177✔
570
571	if ($this->information & 1) {	177✔
572	$this->right->left = $this->left;	57✔
573
574	return $this->right;	57✔
575	} else {
576	if ($this->left->right == $this) {	177✔
577	$this->left->information &= ~ 1;	169✔
578
579	return $this->right;	169✔
580	} else {
581	$this->right->information &= ~ 2;	132✔
582
583	return $this->left;	132✔
584	}
585	}
586	}
587	}
588
589	/**
590	* Remove a key
591	*
592	* @param mixed $key The key
593	* @param callable $comparator The comparator function
594	*
595	* @return TreeNode The new root
596	*
597	* @since 1.0.0
598	*/
599	public function remove($key, $comparator)
600	{
601	$cmp = call_user_func($comparator, $key, $this->keyInternal);	180✔
602
603	if ($cmp < 0) {	180✔
604	return $this->removeFromLeft($key, $comparator);	177✔
605	}
606
607	if ($cmp > 0) {	180✔
608	return $this->removeFromRight($key, $comparator);	176✔
609	}
610
611	return $this->removeCurrent();	180✔
612	}
613
614	/**
615	* Remove from left subtree
616	*
617	* @param mixed $key The key
618	* @param callable $comparator The comparator function
619	*
620	* @return TreeNode\|null The new root
621	*
622	* @since 1.0.0
623	*/
624	private function removeFromLeft($key, $comparator)
625	{
626	if ($this->information & 2) {	177✔
627	$left = $this->left;	177✔
628
629	if (!$left instanceof self) {	177✔
NEW 630	return $this;	×
631	}
632
633	$leftBalance = $left->information & ~3;	177✔
634	$this->left = $left->remove($key, $comparator);	177✔
635
636	if (
637	!($this->information & 2)	177✔
638	\|\| $leftBalance != 0 && ($this->left instanceof self) && ($this->left->information & ~3) == 0	177✔
639	) {
640	return $this->incBalance();	175✔
641	}
642	}
643
644	return $this;	82✔
645	}
646
647	/**
648	* Remove from right subtree
649	*
650	* @param mixed $key The key
651	* @param callable $comparator The comparator function
652	*
653	* @return TreeNode\|null The new root
654	*
655	* @since 1.0.0
656	*/
657	private function removeFromRight($key, $comparator)
658	{
659	if ($this->information & 1) {	176✔
660	$right = $this->right;	176✔
661
662	if (!$right instanceof self) {	176✔
NEW 663	return $this;	×
664	}
665
666	$rightBalance = $right->information & ~3;	176✔
667	$this->right = $right->remove($key, $comparator);	176✔
668
669	if (
670	!($this->information & 1)	176✔
671	\|\| $rightBalance != 0 && ($this->right instanceof self) && ($this->right->information & ~3) == 0	176✔
672	) {
673	return $this->decBalance();	174✔
674	}
675	}
676
677	return $this;	82✔
678	}
679
680	/**
681	* Remove current node key
682	*
683	* @return TreeNode\|null The new root
684	*
685	* @since 1.0.0
686	*/
687	private function removeCurrent()
688	{
689	if ($this->information & 1) {	180✔
690	$right = $this->right;	177✔
691
692	if (!$right instanceof self) {	177✔
NEW 693	return $this;	×
694	}
695
696	$rightBalance = $right->information & ~3;	177✔
697	$this->right = $right->pullUpLeftMost();	177✔
698
699	if (
700	!($this->information & 1)	177✔
701	\|\| $rightBalance != 0 && ($this->right instanceof self) && ($this->right->information & ~3) == 0	177✔
702	) {
703	return $this->decBalance();	176✔
704	}
705
706	return $this;	81✔
707	}
708
709	$left = $this->left;	177✔
710	$right = $this->right;	177✔
711
712	if ($this->information & 2) {	177✔
713	$left->right = $right;	79✔
714
715	return $left;	79✔
716	}
717
718	if ($left && $left->right == $this) {	177✔
719	$left->information &= ~ 1;	167✔
720
721	return $right;	167✔
722	}
723
724	if ($right && $right->left == $this) {	170✔
725	$right->information &= ~ 2;	168✔
726
727	return $left;	168✔
728	}
729
730	return null;	2✔
731	}
732	}

chdemko / php-sorted-collections / 24612504022

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