24611992750

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

Build # 24611992750

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%)

777 of 788 relevant lines covered (98.6%)

114.3 hits per line

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

98.91

/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) {
            $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) {
                $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✔
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	$left = $this->left;	166✔
415
416	if (!$left instanceof self) {	166✔
NEW 417	return $this;	×
418	}
419
420	if ($left->information >= 4) {	166✔
421	$this->left = $left->rotateLeft();	55✔
422	}
423
424	return $this->rotateRight();	166✔
425	}
426
427	return $this;	393✔
428	}
429
430	/**
431	* Insert a key/value pair
432	*
433	* @param mixed $key The key
434	* @param mixed $value The value
435	* @param callable $comparator The comparator function
436	*
437	* @return TreeNode The new root
438	*
439	* @since 1.0.0
440	*/
441	public function insert($key, $value, $comparator)
442	{
443	$node = $this;	753✔
444	$cmp = call_user_func($comparator, $key, $this->keyInternal);	753✔
445
446	if ($cmp < 0) {	753✔
447	if ($this->information & 2) {	387✔
448	$leftBalance = $this->left->information & ~3;	317✔
449	$this->left = $this->left->insert($key, $value, $comparator);	317✔
450
451	if (($this->left->information & ~3) && ($this->left->information & ~3) != $leftBalance) {	317✔
452	$node = $this->decBalance();	316✔
453	}
454	} else {
455	$this->left = new static($key, $value, $this->left, $this);	338✔
456	$this->information \|= 2;	338✔
457	$node = $this->decBalance();	338✔
458	}
459	} elseif ($cmp > 0) {	703✔
460	if ($this->information & 1) {	700✔
461	$rightBalance = $this->right->information & ~3;	630✔
462	$this->right = $this->right->insert($key, $value, $comparator);	630✔
463
464	if (($this->right->information & ~3) && ($this->right->information & ~3) != $rightBalance) {	630✔
465	$node = $this->incBalance();	630✔
466	}
467	} else {
468	$this->right = new static($key, $value, $this, $this->right);	700✔
469	$this->information \|= 1;	700✔
470	$node = $this->incBalance();	700✔
471	}
472	} else {
473	$this->value = $value;	4✔
474	}
475
476	return $node;	753✔
477	}
478
479	/**
480	* Pull up the left most node of a node
481	*
482	* @return TreeNode The new root
483	*
484	* @since 1.0.0
485	*/
486	private function pullUpLeftMost()
487	{
488	if ($this->information & 2) {	177✔
489	$leftBalance = $this->left->information & ~3;	143✔
490	$this->left = $this->left->pullUpLeftMost();	143✔
491
492	if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0) {	143✔
493	return $this->incBalance();	143✔
494	} else {
495	return $this;	7✔
496	}
497	} else {
498	$this->left->keyInternal = $this->keyInternal;	177✔
499	$this->left->value = $this->value;	177✔
500
501	if ($this->information & 1) {	177✔
502	$this->right->left = $this->left;	57✔
503
504	return $this->right;	57✔
505	} else {
506	if ($this->left->right == $this) {	177✔
507	$this->left->information &= ~ 1;	169✔
508
509	return $this->right;	169✔
510	} else {
511	$this->right->information &= ~ 2;	132✔
512
513	return $this->left;	132✔
514	}
515	}
516	}
517	}
518
519	/**
520	* Remove a key
521	*
522	* @param mixed $key The key
523	* @param callable $comparator The comparator function
524	*
525	* @return TreeNode The new root
526	*
527	* @since 1.0.0
528	*/
529	public function remove($key, $comparator)
530	{
531	$cmp = call_user_func($comparator, $key, $this->keyInternal);	180✔
532
533	if ($cmp < 0) {	180✔
534	if ($this->information & 2) {	177✔
535	$leftBalance = $this->left->information & ~3;	177✔
536	$this->left = $this->left->remove($key, $comparator);	177✔
537
538	if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0) {	177✔
539	return $this->incBalance();	175✔
540	}
541	}
542	} elseif ($cmp > 0) {	180✔
543	if ($this->information & 1) {	176✔
544	$rightBalance = $this->right->information & ~3;	176✔
545	$this->right = $this->right->remove($key, $comparator);	176✔
546
547	if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0) {	176✔
548	return $this->decBalance();	174✔
549	}
550	}
551	} else {
552	if ($this->information & 1) {	180✔
553	$rightBalance = $this->right->information & ~3;	177✔
554	$this->right = $this->right->pullUpLeftMost();	177✔
555
556	if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0) {	177✔
557	return $this->decBalance();	176✔
558	}
559	} else {
560	$left = $this->left;	177✔
561	$right = $this->right;	177✔
562
563	if ($this->information & 2) {	177✔
564	$left->right = $right;	79✔
565
566	return $left;	79✔
567	} else {
568	if ($left && $left->right == $this) {	177✔
569	$left->information &= ~ 1;	167✔
570
571	return $right;	167✔
572	} elseif ($right && $right->left == $this) {	170✔
573	$right->information &= ~ 2;	168✔
574
575	return $left;	168✔
576	} else {
577	return null;	2✔
578	}
579	}
580	}
581	}
582
583	return $this;	111✔
584	}
585	}

chdemko / php-sorted-collections / 24611992750

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