24611899944

Committed 18 Apr 2026 07:13PM UTC coverage: 98.726% (-0.1%) from 98.849%

Build # 24611899944

Build Type

push

github

Committed by

chdemko

Commit Message

🚨 Fix scrutinizer

Coverage Stats

4 of 5 new or added lines in 1 file covered. (80.0%)

775 of 785 relevant lines covered (98.73%)

114.32 hits per line

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

99.44

/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)
    {
        $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;
            }
        }

        if ($cmp < 0) {
            if ($type < 0) {
                return $node->left;
            } elseif ($type > 0) {
                return $node;
            } else {
                return null;
            }
        } elseif ($cmp > 0) {
            if ($type < 0) {
                return $node;
            } elseif ($type > 0) {
                return $node->right;
            } else {
                return null;
            }
        } else {
            if ($type < -1) {
                return $node->predecessor;
            } elseif ($type > 1) {
                return $node->successor;
            } else {
                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) {
            if ($this->left->information >= 4) {
                $this->left = $this->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) {
                $leftBalance = $this->left->information & ~3;
                $this->left = $this->left->insert($key, $value, $comparator);

                if (($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) {
                $rightBalance = $this->right->information & ~3;
                $this->right = $this->right->insert($key, $value, $comparator);

                if (($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) {
            $leftBalance = $this->left->information & ~3;
            $this->left = $this->left->pullUpLeftMost();

            if (!($this->information & 2) || $leftBalance != 0 && ($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) {
            if ($this->information & 2) {
                $leftBalance = $this->left->information & ~3;
                $this->left = $this->left->remove($key, $comparator);

                if (!($this->information & 2) || $leftBalance != 0 && ($this->left->information & ~3) == 0) {
                    return $this->incBalance();
                }
            }
        } elseif ($cmp > 0) {
            if ($this->information & 1) {
                $rightBalance = $this->right->information & ~3;
                $this->right = $this->right->remove($key, $comparator);

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

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

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

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

                        return $right;
                    } elseif ($right && $right->left == $this) {
                        $right->information &= ~ 2;

                        return $left;
                    } else {
                        return null;
                    }
                }
            }
        }

        return $this;
    }
}

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	$node = $this;	257✔
265	$cmp = 0;	257✔
266
267	while (true) {	257✔
268	$cmp = call_user_func($comparator, $key, $node->keyInternal);	257✔
269
270	if ($cmp < 0 && $node->information & 2) {	257✔
271	$node = $node->left;	118✔
272	} elseif ($cmp > 0 && $node->information & 1) {	257✔
273	$node = $node->right;	154✔
274	} else {
275	break;	257✔
276	}
277	}
278
279	if ($cmp < 0) {	257✔
280	if ($type < 0) {	29✔
281	return $node->left;	12✔
282	} elseif ($type > 0) {	17✔
283	return $node;	12✔
284	} else {
285	return null;	5✔
286	}
287	} elseif ($cmp > 0) {	228✔
288	if ($type < 0) {	39✔
289	return $node;	12✔
290	} elseif ($type > 0) {	27✔
291	return $node->right;	14✔
292	} else {
293	return null;	13✔
294	}
295	} else {
296	if ($type < -1) {	193✔
297	return $node->predecessor;	41✔
298	} elseif ($type > 1) {	159✔
299	return $node->successor;	46✔
300	} else {
301	return $node;	120✔
302	}
303	}
304	}
305
306	/**
307	* Rotate the node to the left
308	*
309	* @return TreeNode The rotated node
310	*
311	* @since 1.0.0
312	*/
313	private function rotateLeft()
314	{
315	$right = $this->right;	632✔
316
317	if ($right->information & 2) {	632✔
318	$this->right = $right->left;	471✔
319	$right->left = $this;	471✔
320	} else {
321	$right->information \|= 2;	632✔
322	$this->information &= ~ 1;	632✔
323	}
324
325	$this->information -= 4;	632✔
326
327	if ($right->information >= 4) {	632✔
328	$this->information -= $right->information & ~3;	630✔
329	}
330
331	$right->information -= 4;	632✔
332
333	if ($this->information < 0) {	632✔
334	$right->information += $this->information & ~3;	8✔
335	}
336
337	return $right;	632✔
338	}
339
340	/**
341	* Rotate the node to the right
342	*
343	* @return TreeNode The rotated node
344	*
345	* @since 1.0.0
346	*/
347	private function rotateRight()
348	{
349	$left = $this->left;	194✔
350
351	if ($left->information & 1) {	194✔
352	$this->left = $left->right;	60✔
353	$left->right = $this;	60✔
354	} else {
355	$this->information &= ~ 2;	185✔
356	$left->information \|= 1;	185✔
357	}
358
359	$this->information += 4;	194✔
360
361	if ($left->information < 0) {	194✔
362	$this->information -= $left->information & ~3;	154✔
363	}
364
365	$left->information += 4;	194✔
366
367	if ($this->information >= 4) {	194✔
368	$left->information += $this->information & ~3;	8✔
369	}
370
371	return $left;	194✔
372	}
373
374	/**
375	* Increment the balance of the node
376	*
377	* @return TreeNode $this or a rotated version of $this
378	*
379	* @since 1.0.0
380	*/
381	private function incBalance()
382	{
383	$this->information += 4;	702✔
384
385	if ($this->information >= 8) {	702✔
386	$right = $this->right;	630✔
387
388	if (!$right instanceof self) {	630✔
NEW 389	return $this;	×
390	}
391
392	if ($right->information < 0) {	630✔
393	$this->right = $right->rotateRight();	55✔
394	}
395
396	return $this->rotateLeft();	630✔
397	}
398
399	return $this;	702✔
400	}
401
402	/**
403	* Decrement the balance of the node
404	*
405	* @return TreeNode $this or a rotated version of $this
406	*
407	* @since 1.0.0
408	*/
409	private function decBalance()
410	{
411	$this->information -= 4;	393✔
412
413	if ($this->information < - 4) {	393✔
414	if ($this->left->information >= 4) {	166✔
415	$this->left = $this->left->rotateLeft();	55✔
416	}
417
418	return $this->rotateRight();	166✔
419	}
420
421	return $this;	393✔
422	}
423
424	/**
425	* Insert a key/value pair
426	*
427	* @param mixed $key The key
428	* @param mixed $value The value
429	* @param callable $comparator The comparator function
430	*
431	* @return TreeNode The new root
432	*
433	* @since 1.0.0
434	*/
435	public function insert($key, $value, $comparator)
436	{
437	$node = $this;	753✔
438	$cmp = call_user_func($comparator, $key, $this->keyInternal);	753✔
439
440	if ($cmp < 0) {	753✔
441	if ($this->information & 2) {	387✔
442	$leftBalance = $this->left->information & ~3;	317✔
443	$this->left = $this->left->insert($key, $value, $comparator);	317✔
444
445	if (($this->left->information & ~3) && ($this->left->information & ~3) != $leftBalance) {	317✔
446	$node = $this->decBalance();	316✔
447	}
448	} else {
449	$this->left = new static($key, $value, $this->left, $this);	338✔
450	$this->information \|= 2;	338✔
451	$node = $this->decBalance();	338✔
452	}
453	} elseif ($cmp > 0) {	703✔
454	if ($this->information & 1) {	700✔
455	$rightBalance = $this->right->information & ~3;	630✔
456	$this->right = $this->right->insert($key, $value, $comparator);	630✔
457
458	if (($this->right->information & ~3) && ($this->right->information & ~3) != $rightBalance) {	630✔
459	$node = $this->incBalance();	630✔
460	}
461	} else {
462	$this->right = new static($key, $value, $this, $this->right);	700✔
463	$this->information \|= 1;	700✔
464	$node = $this->incBalance();	700✔
465	}
466	} else {
467	$this->value = $value;	4✔
468	}
469
470	return $node;	753✔
471	}
472
473	/**
474	* Pull up the left most node of a node
475	*
476	* @return TreeNode The new root
477	*
478	* @since 1.0.0
479	*/
480	private function pullUpLeftMost()
481	{
482	if ($this->information & 2) {	177✔
483	$leftBalance = $this->left->information & ~3;	143✔
484	$this->left = $this->left->pullUpLeftMost();	143✔
485
486	if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0) {	143✔
487	return $this->incBalance();	143✔
488	} else {
489	return $this;	7✔
490	}
491	} else {
492	$this->left->keyInternal = $this->keyInternal;	177✔
493	$this->left->value = $this->value;	177✔
494
495	if ($this->information & 1) {	177✔
496	$this->right->left = $this->left;	57✔
497
498	return $this->right;	57✔
499	} else {
500	if ($this->left->right == $this) {	177✔
501	$this->left->information &= ~ 1;	169✔
502
503	return $this->right;	169✔
504	} else {
505	$this->right->information &= ~ 2;	132✔
506
507	return $this->left;	132✔
508	}
509	}
510	}
511	}
512
513	/**
514	* Remove a key
515	*
516	* @param mixed $key The key
517	* @param callable $comparator The comparator function
518	*
519	* @return TreeNode The new root
520	*
521	* @since 1.0.0
522	*/
523	public function remove($key, $comparator)
524	{
525	$cmp = call_user_func($comparator, $key, $this->keyInternal);	180✔
526
527	if ($cmp < 0) {	180✔
528	if ($this->information & 2) {	177✔
529	$leftBalance = $this->left->information & ~3;	177✔
530	$this->left = $this->left->remove($key, $comparator);	177✔
531
532	if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0) {	177✔
533	return $this->incBalance();	175✔
534	}
535	}
536	} elseif ($cmp > 0) {	180✔
537	if ($this->information & 1) {	176✔
538	$rightBalance = $this->right->information & ~3;	176✔
539	$this->right = $this->right->remove($key, $comparator);	176✔
540
541	if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0) {	176✔
542	return $this->decBalance();	174✔
543	}
544	}
545	} else {
546	if ($this->information & 1) {	180✔
547	$rightBalance = $this->right->information & ~3;	177✔
548	$this->right = $this->right->pullUpLeftMost();	177✔
549
550	if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0) {	177✔
551	return $this->decBalance();	176✔
552	}
553	} else {
554	$left = $this->left;	177✔
555	$right = $this->right;	177✔
556
557	if ($this->information & 2) {	177✔
558	$left->right = $right;	79✔
559
560	return $left;	79✔
561	} else {
562	if ($left && $left->right == $this) {	177✔
563	$left->information &= ~ 1;	167✔
564
565	return $right;	167✔
566	} elseif ($right && $right->left == $this) {	170✔
567	$right->information &= ~ 2;	168✔
568
569	return $left;	168✔
570	} else {
571	return null;	2✔
572	}
573	}
574	}
575	}
576
577	return $this;	111✔
578	}
579	}

chdemko / php-sorted-collections / 24611899944

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