24612783811

Committed 18 Apr 2026 08:02PM UTC coverage: 97.64% (+0.006%) from 97.634%

Build # 24612783811

Build Type

push

github

Committed by

chdemko

Commit Message

🚨 Reduce complexity

Coverage Stats

98 of 100 new or added lines in 2 files covered. (98.0%)

1 existing line in 1 file now uncovered.

786 of 805 relevant lines covered (97.64%)

121.01 hits per line

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

96.43

/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
{
    /**
     * Property to accessor method map for magic get
     *
     * @var array
     *
     * @since 1.0.0
     */
    private const PROPERTY_METHOD_MAP = array(
        'first' => 'first',
        'last' => 'last',
        'predecessor' => 'predecessor',
        'successor' => 'successor',
        'count' => 'count',
    );

    /**
     * @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)
    {
        if ($property === 'key') {
            return $this->keyInternal;
        }

        return $this->getMappedProperty($property);
    }

    /**
     * Resolve mapped magic property
     *
     * @param string $property The node property
     *
     * @throws RuntimeException If the property is undefined
     *
     * @return mixed The value associated to the property
     *
     * @since 1.0.0
     */
    private function getMappedProperty($property)
    {
        if (!isset(self::PROPERTY_METHOD_MAP[$property])) {
            throw new \RuntimeException('Undefined property');
        }

        $method = self::PROPERTY_METHOD_MAP[$property];

        return $this->$method();
    }

    /**
     * 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) {
            return $this->resolveFindResultForNegativeCmp($node, $type);
        }

        if ($cmp > 0) {
            return $this->resolveFindResultForPositiveCmp($node, $type);
        }

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

    /**
     * Resolve find result when comparison is negative
     *
     * @param TreeNode $node The closest node
     * @param integer  $type The operation type
     *
     * @return mixed The resolved node or null
     *
     * @since 1.0.0
     */
    private function resolveFindResultForNegativeCmp($node, $type)
    {
        if ($type < 0) {
            return $node->left;
        }

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

        return null;
    }

    /**
     * Resolve find result when comparison is positive
     *
     * @param TreeNode $node The closest node
     * @param integer  $type The operation type
     *
     * @return mixed The resolved node or null
     *
     * @since 1.0.0
     */
    private function resolveFindResultForPositiveCmp($node, $type)
    {
        if ($type < 0) {
            return $node;
        }

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

        return null;
    }

    /**
     * Resolve find result when comparison is zero
     *
     * @param TreeNode $node The closest node
     * @param integer  $type The operation type
     *
     * @return mixed The resolved node
     *
     * @since 1.0.0
     */
    private function resolveFindResultForZeroCmp($node, $type)
    {

        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)
    {
        $cmp = call_user_func($comparator, $key, $this->keyInternal);

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

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

        return $this->insertHere($value);
    }

    /**
     * Insert into the left subtree
     *
     * @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
     */
    private function insertLeft($key, $value, $comparator)
    {
        if ($this->information & 2) {
            $left = $this->left;

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

            $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
            ) {
                return $this->decBalance();
            }

            return $this;
        }

        $this->left = new static($key, $value, $this->left, $this);
        $this->information |= 2;

        return $this->decBalance();
    }

    /**
     * Insert into the right subtree
     *
     * @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
     */
    private function insertRight($key, $value, $comparator)
    {
        if ($this->information & 1) {
            $right = $this->right;

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

            $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
            ) {
                return $this->incBalance();
            }

            return $this;
        }

        $this->right = new static($key, $value, $this, $this->right);
        $this->information |= 1;

        return $this->incBalance();
    }

    /**
     * Update current node value when key already exists
     *
     * @param mixed $value The value
     *
     * @return TreeNode The current node
     *
     * @since 1.0.0
     */
    private function insertHere($value)
    {
        $this->value = $value;

        return $this;
    }

    /**
     * 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) {
            return $this->pullUpLeftMostFromLeftSubtree();
        }

        return $this->pullUpLeftMostAtCurrentNode();
    }

    /**
     * Pull up left-most node via left subtree recursion
     *
     * @return TreeNode The new root
     *
     * @since 1.0.0
     */
    private function pullUpLeftMostFromLeftSubtree()
    {
        $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();
        }

        return $this;
    }

    /**
     * Pull up left-most node when current node has no left subtree
     *
     * @return TreeNode The new root
     *
     * @since 1.0.0
     */
    private function pullUpLeftMostAtCurrentNode()
    {
        $left = $this->left;
        $right = $this->right;

        $left->keyInternal = $this->keyInternal;
        $left->value = $this->value;

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

            return $right;
        }

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

            return $right;
        }

        $right->information &= ~ 2;

        return $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) {
            return $this->removeCurrentWithRightChild();
        }

        return $this->removeCurrentWithoutRightChild();
    }

    /**
     * Remove current node when a right child exists
     *
     * @return TreeNode|null The new root
     *
     * @since 1.0.0
     */
    private function removeCurrentWithRightChild()
    {
        $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;
    }

    /**
     * Remove current node when no right child exists
     *
     * @return TreeNode|null The new root
     *
     * @since 1.0.0
     */
    private function removeCurrentWithoutRightChild()
    {

        $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	* Property to accessor method map for magic get
35	*
36	* @var array
37	*
38	* @since 1.0.0
39	*/
40	private const PROPERTY_METHOD_MAP = array(
41	'first' => 'first',
42	'last' => 'last',
43	'predecessor' => 'predecessor',
44	'successor' => 'successor',
45	'count' => 'count',
46	);
47
48	/**
49	* @var integer Information associated to that node.
50	* Bits of order 0 and 1 are reserved for the existence of left and right tree.
51	* Other bits are for the balance
52	*
53	* @since 1.0.0
54	*/
55	private $information = 0;
56
57	/**
58	* @var TreeNode\|null Left\|Predecessor node
59	*
60	* @since 1.0.0
61	*/
62	private $left;
63
64	/**
65	* @var TreeNode\|null Right\|Successor node
66	*
67	* @since 1.0.0
68	*/
69	private $right;
70
71	/**
72	* @var mixed Node key
73	*
74	* @since 1.0.0
75	*/
76	private $keyInternal;
77
78	/**
79	* @var mixed Node value
80	*
81	* @since 1.0.0
82	*/
83	public $value;
84
85	/**
86	* Create a node
87	*
88	* @param mixed $key The node key
89	* @param mixed $value The node value
90	*
91	* @return TreeNode A new node
92	*
93	* @since 1.0.0
94	*/
95	public static function create($key, $value)
96	{
97	return new static($key, $value);	772✔
98	}
99
100	/**
101	* Constructor
102	*
103	* @param mixed $key The node key
104	* @param mixed $value The node value
105	* @param TreeNode $predecessor The left node
106	* @param TreeNode $successor The right node
107	*
108	* @since 1.0.0
109	*/
110	protected function __construct($key, $value, $predecessor = null, $successor = null)
111	{
112	$this->keyInternal = $key;	772✔
113	$this->value = $value;	772✔
114	$this->left = $predecessor;	772✔
115	$this->right = $successor;	772✔
116	}
117
118	/**
119	* Magic get method
120	*
121	* @param string $property The node property
122	*
123	* @return mixed The value associated to the property
124	*
125	* @throws RuntimeException If the property is undefined
126	*
127	* @since 1.0.0
128	*/
129	public function __get($property)
130	{
131	if ($property === 'key') {	614✔
132	return $this->keyInternal;	587✔
133	}
134
135	return $this->getMappedProperty($property);	515✔
136	}
137
138	/**
139	* Resolve mapped magic property
140	*
141	* @param string $property The node property
142	*
143	* @throws RuntimeException If the property is undefined
144	*
145	* @return mixed The value associated to the property
146	*
147	* @since 1.0.0
148	*/
149	private function getMappedProperty($property)
150	{
151	if (!isset(self::PROPERTY_METHOD_MAP[$property])) {	515✔
152	throw new \RuntimeException('Undefined property');	1✔
153	}
154
155	$method = self::PROPERTY_METHOD_MAP[$property];	514✔
156
157	return $this->$method();	514✔
158	}
159
160	/**
161	* Get the first node
162	*
163	* @return TreeNode the first node
164	*
165	* @since 1.0.0
166	*/
167	public function first()
168	{
169	$node = $this;	397✔
170
171	while ($node->information & 2) {	397✔
172	$node = $node->left;	392✔
173	}
174
175	return $node;	397✔
176	}
177
178	/**
179	* Get the last node
180	*
181	* @return TreeNode the last node
182	*
183	* @since 1.0.0
184	*/
185	public function last()
186	{
187	$node = $this;	368✔
188
189	while ($node->information & 1) {	368✔
190	$node = $node->right;	363✔
191	}
192
193	return $node;	368✔
194	}
195
196	/**
197	* Get the predecessor
198	*
199	* @return TreeNode\|null the predecessor node
200	*
201	* @since 1.0.0
202	*/
203	public function predecessor()
204	{
205	if ($this->information & 2) {	404✔
206	$node = $this->left;	374✔
207
208	while ($node->information & 1) {	374✔
209	$node = $node->right;	314✔
210	}
211
212	return $node;	374✔
213	} else {
214	return $this->left;	387✔
215	}
216	}
217
218	/**
219	* Get the successor
220	*
221	* @return TreeNode\|null the successor node
222	*
223	* @since 1.0.0
224	*/
225	public function successor()
226	{
227	if ($this->information & 1) {	445✔
228	$node = $this->right;	409✔
229
230	while ($node->information & 2) {	409✔
231	$node = $node->left;	340✔
232	}
233
234	return $node;	409✔
235	} else {
236	return $this->right;	433✔
237	}
238	}
239
240	/**
241	* Count the number of key/value pair
242	*
243	* @return integer
244	*
245	* @since 1.0.0
246	*/
247	public function count(): int
248	{
249	$count = 1;	7✔
250
251	if ($this->information & 2) {	7✔
252	$count += $this->left->count;	7✔
253	}
254
255	if ($this->information & 1) {	7✔
256	$count += $this->right->count;	7✔
257	}
258
259	return $count;	7✔
260	}
261
262	/**
263	* Get the node for a key
264	*
265	* @param mixed $key The key
266	* @param callable $comparator The comparator function
267	* @param integer $type The operation type
268	* -2 for the
269	* greatest key
270	* lesser than the
271	* given key -1 for
272	* the greatest key
273	* lesser than or
274	* equal to the given
275	* key 0 for the
276	* given key +1 for
277	* the lowest key
278	* greater than or
279	* equal to the given
280	* key +2 for the
281	* lowest key greater
282	* than the given key
283	*
284	* @return mixed The node or null if not found
285	*
286	* @since 1.0.0
287	*/
288	public function find($key, $comparator, $type = 0)
289	{
290	list($node, $cmp) = $this->traverseForFind($key, $comparator);	257✔
291
292	return $this->resolveFindResult($node, $cmp, $type);	257✔
293	}
294
295	/**
296	* Traverse tree for find operation
297	*
298	* @param mixed $key The searched key
299	* @param callable $comparator The comparator function
300	*
301	* @return array{0: TreeNode, 1: integer} The closest node and comparison result
302	*
303	* @since 1.0.0
304	*/
305	private function traverseForFind($key, $comparator)
306	{
307	$node = $this;	257✔
308	$cmp = 0;	257✔
309
310	while (true) {	257✔
311	$cmp = call_user_func($comparator, $key, $node->keyInternal);	257✔
312
313	if ($cmp < 0 && $node->information & 2) {	257✔
314	$node = $node->left;	118✔
315	} elseif ($cmp > 0 && $node->information & 1) {	257✔
316	$node = $node->right;	154✔
317	} else {
318	break;	257✔
319	}
320	}
321
322	return array($node, $cmp);	257✔
323	}
324
325	/**
326	* Resolve find result from traversal state
327	*
328	* @param TreeNode $node The closest node
329	* @param integer $cmp The key comparison result
330	* @param integer $type The operation type
331	*
332	* @return mixed The resolved node or null
333	*
334	* @since 1.0.0
335	*/
336	private function resolveFindResult($node, $cmp, $type)
337	{
338	if ($cmp < 0) {	257✔
339	return $this->resolveFindResultForNegativeCmp($node, $type);	29✔
340	}
341
342	if ($cmp > 0) {	228✔
343	return $this->resolveFindResultForPositiveCmp($node, $type);	39✔
344	}
345
346	return $this->resolveFindResultForZeroCmp($node, $type);	193✔
347	}
348
349	/**
350	* Resolve find result when comparison is negative
351	*
352	* @param TreeNode $node The closest node
353	* @param integer $type The operation type
354	*
355	* @return mixed The resolved node or null
356	*
357	* @since 1.0.0
358	*/
359	private function resolveFindResultForNegativeCmp($node, $type)
360	{
361	if ($type < 0) {	29✔
362	return $node->left;	12✔
363	}
364
365	if ($type > 0) {	17✔
366	return $node;	12✔
367	}
368
369	return null;	5✔
370	}
371
372	/**
373	* Resolve find result when comparison is positive
374	*
375	* @param TreeNode $node The closest node
376	* @param integer $type The operation type
377	*
378	* @return mixed The resolved node or null
379	*
380	* @since 1.0.0
381	*/
382	private function resolveFindResultForPositiveCmp($node, $type)
383	{
384	if ($type < 0) {	39✔
385	return $node;	12✔
386	}
387
388	if ($type > 0) {	27✔
389	return $node->right;	14✔
390	}
391
392	return null;	13✔
393	}
394
395	/**
396	* Resolve find result when comparison is zero
397	*
398	* @param TreeNode $node The closest node
399	* @param integer $type The operation type
400	*
401	* @return mixed The resolved node
402	*
403	* @since 1.0.0
404	*/
405	private function resolveFindResultForZeroCmp($node, $type)
406	{
407
408	if ($type < -1) {	193✔
409	return $node->predecessor;	41✔
410	}
411
412	if ($type > 1) {	159✔
413	return $node->successor;	46✔
414	}
415
416	return $node;	120✔
417	}
418
419	/**
420	* Rotate the node to the left
421	*
422	* @return TreeNode The rotated node
423	*
424	* @since 1.0.0
425	*/
426	private function rotateLeft()
427	{
428	$right = $this->right;	632✔
429
430	if ($right->information & 2) {	632✔
431	$this->right = $right->left;	471✔
432	$right->left = $this;	471✔
433	} else {
434	$right->information \|= 2;	632✔
435	$this->information &= ~ 1;	632✔
436	}
437
438	$this->information -= 4;	632✔
439
440	if ($right->information >= 4) {	632✔
441	$this->information -= $right->information & ~3;	630✔
442	}
443
444	$right->information -= 4;	632✔
445
446	if ($this->information < 0) {	632✔
447	$right->information += $this->information & ~3;	8✔
448	}
449
450	return $right;	632✔
451	}
452
453	/**
454	* Rotate the node to the right
455	*
456	* @return TreeNode The rotated node
457	*
458	* @since 1.0.0
459	*/
460	private function rotateRight()
461	{
462	$left = $this->left;	194✔
463
464	if ($left->information & 1) {	194✔
465	$this->left = $left->right;	60✔
466	$left->right = $this;	60✔
467	} else {
468	$this->information &= ~ 2;	185✔
469	$left->information \|= 1;	185✔
470	}
471
472	$this->information += 4;	194✔
473
474	if ($left->information < 0) {	194✔
475	$this->information -= $left->information & ~3;	154✔
476	}
477
478	$left->information += 4;	194✔
479
480	if ($this->information >= 4) {	194✔
481	$left->information += $this->information & ~3;	8✔
482	}
483
484	return $left;	194✔
485	}
486
487	/**
488	* Increment the balance of the node
489	*
490	* @return TreeNode $this or a rotated version of $this
491	*
492	* @since 1.0.0
493	*/
494	private function incBalance()
495	{
496	$this->information += 4;	702✔
497
498	if ($this->information >= 8) {	702✔
499	$right = $this->right;	630✔
500
501	if (!$right instanceof self) {	630✔
502	return $this;	×
503	}
504
505	if ($right->information < 0) {	630✔
506	$this->right = $right->rotateRight();	55✔
507	}
508
509	return $this->rotateLeft();	630✔
510	}
511
512	return $this;	702✔
513	}
514
515	/**
516	* Decrement the balance of the node
517	*
518	* @return TreeNode $this or a rotated version of $this
519	*
520	* @since 1.0.0
521	*/
522	private function decBalance()
523	{
524	$this->information -= 4;	393✔
525
526	if ($this->information < - 4) {	393✔
527	$left = $this->left;	166✔
528
529	if (!$left instanceof self) {	166✔
530	return $this;	×
531	}
532
533	if ($left->information >= 4) {	166✔
534	$this->left = $left->rotateLeft();	55✔
535	}
536
537	return $this->rotateRight();	166✔
538	}
539
540	return $this;	393✔
541	}
542
543	/**
544	* Insert a key/value pair
545	*
546	* @param mixed $key The key
547	* @param mixed $value The value
548	* @param callable $comparator The comparator function
549	*
550	* @return TreeNode The new root
551	*
552	* @since 1.0.0
553	*/
554	public function insert($key, $value, $comparator)
555	{
556	$cmp = call_user_func($comparator, $key, $this->keyInternal);	753✔
557
558	if ($cmp < 0) {	753✔
559	return $this->insertLeft($key, $value, $comparator);	387✔
560	}
561
562	if ($cmp > 0) {	703✔
563	return $this->insertRight($key, $value, $comparator);	700✔
564	}
565
566	return $this->insertHere($value);	4✔
567	}
568
569	/**
570	* Insert into the left subtree
571	*
572	* @param mixed $key The key
573	* @param mixed $value The value
574	* @param callable $comparator The comparator function
575	*
576	* @return TreeNode The new root
577	*
578	* @since 1.0.0
579	*/
580	private function insertLeft($key, $value, $comparator)
581	{
582	if ($this->information & 2) {	387✔
583	$left = $this->left;	317✔
584
585	if (!$left instanceof self) {	317✔
586	return $this;	×
587	}
588
589	$leftBalance = $left->information & ~3;	317✔
590	$this->left = $left->insert($key, $value, $comparator);	317✔
591
592	if (
593	$this->left instanceof self	317✔
594	&& ($this->left->information & ~3)	317✔
595	&& ($this->left->information & ~3) != $leftBalance	317✔
596	) {
597	return $this->decBalance();	316✔
598	}
599
600	return $this;	157✔
601	}
602
603	$this->left = new static($key, $value, $this->left, $this);	338✔
604	$this->information \|= 2;	338✔
605
606	return $this->decBalance();	338✔
607	}
608
609	/**
610	* Insert into the right subtree
611	*
612	* @param mixed $key The key
613	* @param mixed $value The value
614	* @param callable $comparator The comparator function
615	*
616	* @return TreeNode The new root
617	*
618	* @since 1.0.0
619	*/
620	private function insertRight($key, $value, $comparator)
621	{
622	if ($this->information & 1) {	700✔
623	$right = $this->right;	630✔
624
625	if (!$right instanceof self) {	630✔
NEW 626	return $this;	×
627	}
628
629	$rightBalance = $right->information & ~3;	630✔
630	$this->right = $right->insert($key, $value, $comparator);	630✔
631
632	if (
633	$this->right instanceof self	630✔
634	&& ($this->right->information & ~3)	630✔
635	&& ($this->right->information & ~3) != $rightBalance	630✔
636	) {
637	return $this->incBalance();	630✔
638	}
639
640	return $this;	509✔
641	}
642
643	$this->right = new static($key, $value, $this, $this->right);	700✔
644	$this->information \|= 1;	700✔
645
646	return $this->incBalance();	700✔
647	}
648
649	/**
650	* Update current node value when key already exists
651	*
652	* @param mixed $value The value
653	*
654	* @return TreeNode The current node
655	*
656	* @since 1.0.0
657	*/
658	private function insertHere($value)
659	{
660	$this->value = $value;	4✔
661
662	return $this;	4✔
663	}
664
665	/**
666	* Pull up the left most node of a node
667	*
668	* @return TreeNode The new root
669	*
670	* @since 1.0.0
671	*/
672	private function pullUpLeftMost()
673	{
674	if ($this->information & 2) {	177✔
675	return $this->pullUpLeftMostFromLeftSubtree();	143✔
676	}
677
678	return $this->pullUpLeftMostAtCurrentNode();	177✔
679	}
680
681	/**
682	* Pull up left-most node via left subtree recursion
683	*
684	* @return TreeNode The new root
685	*
686	* @since 1.0.0
687	*/
688	private function pullUpLeftMostFromLeftSubtree()
689	{
690	$left = $this->left;	143✔
691
692	if (!$left instanceof self) {	143✔
NEW 693	return $this;	×
694	}
695
696	$leftBalance = $left->information & ~3;	143✔
697	$this->left = $left->pullUpLeftMost();	143✔
698
699	if (
700	!($this->information & 2)	143✔
701	\|\| $leftBalance != 0 && ($this->left instanceof self) && ($this->left->information & ~3) == 0	143✔
702	) {
703	return $this->incBalance();	143✔
704	}
705
706	return $this;	7✔
707	}
708
709	/**
710	* Pull up left-most node when current node has no left subtree
711	*
712	* @return TreeNode The new root
713	*
714	* @since 1.0.0
715	*/
716	private function pullUpLeftMostAtCurrentNode()
717	{
718	$left = $this->left;	177✔
719	$right = $this->right;	177✔
720
721	$left->keyInternal = $this->keyInternal;	177✔
722	$left->value = $this->value;	177✔
723
724	if ($this->information & 1) {	177✔
725	$right->left = $left;	57✔
726
727	return $right;	57✔
728	}
729
730	if ($left->right == $this) {	177✔
731	$left->information &= ~ 1;	169✔
732
733	return $right;	169✔
734	}
735
736	$right->information &= ~ 2;	132✔
737
738	return $left;	132✔
739	}
740
741	/**
742	* Remove a key
743	*
744	* @param mixed $key The key
745	* @param callable $comparator The comparator function
746	*
747	* @return TreeNode The new root
748	*
749	* @since 1.0.0
750	*/
751	public function remove($key, $comparator)
752	{
753	$cmp = call_user_func($comparator, $key, $this->keyInternal);	180✔
754
755	if ($cmp < 0) {	180✔
756	return $this->removeFromLeft($key, $comparator);	177✔
757	}
758
759	if ($cmp > 0) {	180✔
760	return $this->removeFromRight($key, $comparator);	176✔
761	}
762
763	return $this->removeCurrent();	180✔
764	}
765
766	/**
767	* Remove from left subtree
768	*
769	* @param mixed $key The key
770	* @param callable $comparator The comparator function
771	*
772	* @return TreeNode\|null The new root
773	*
774	* @since 1.0.0
775	*/
776	private function removeFromLeft($key, $comparator)
777	{
778	if ($this->information & 2) {	177✔
779	$left = $this->left;	177✔
780
781	if (!$left instanceof self) {	177✔
782	return $this;	×
783	}
784
785	$leftBalance = $left->information & ~3;	177✔
786	$this->left = $left->remove($key, $comparator);	177✔
787
788	if (
789	!($this->information & 2)	177✔
790	\|\| $leftBalance != 0 && ($this->left instanceof self) && ($this->left->information & ~3) == 0	177✔
791	) {
792	return $this->incBalance();	175✔
793	}
794	}
795
796	return $this;	82✔
797	}
798
799	/**
800	* Remove from right subtree
801	*
802	* @param mixed $key The key
803	* @param callable $comparator The comparator function
804	*
805	* @return TreeNode\|null The new root
806	*
807	* @since 1.0.0
808	*/
809	private function removeFromRight($key, $comparator)
810	{
811	if ($this->information & 1) {	176✔
812	$right = $this->right;	176✔
813
814	if (!$right instanceof self) {	176✔
815	return $this;	×
816	}
817
818	$rightBalance = $right->information & ~3;	176✔
819	$this->right = $right->remove($key, $comparator);	176✔
820
821	if (
822	!($this->information & 1)	176✔
823	\|\| $rightBalance != 0 && ($this->right instanceof self) && ($this->right->information & ~3) == 0	176✔
824	) {
825	return $this->decBalance();	174✔
826	}
827	}
828
829	return $this;	82✔
830	}
831
832	/**
833	* Remove current node key
834	*
835	* @return TreeNode\|null The new root
836	*
837	* @since 1.0.0
838	*/
839	private function removeCurrent()
840	{
841	if ($this->information & 1) {	180✔
842	return $this->removeCurrentWithRightChild();	177✔
843	}
844
845	return $this->removeCurrentWithoutRightChild();	177✔
846	}
847
848	/**
849	* Remove current node when a right child exists
850	*
851	* @return TreeNode\|null The new root
852	*
853	* @since 1.0.0
854	*/
855	private function removeCurrentWithRightChild()
856	{
857	$right = $this->right;	177✔
858
859	if (!$right instanceof self) {	177✔
UNCOV 860	return $this;	×
861	}
862
863	$rightBalance = $right->information & ~3;	177✔
864	$this->right = $right->pullUpLeftMost();	177✔
865
866	if (
867	!($this->information & 1)	177✔
868	\|\| $rightBalance != 0 && ($this->right instanceof self) && ($this->right->information & ~3) == 0	177✔
869	) {
870	return $this->decBalance();	176✔
871	}
872
873	return $this;	81✔
874	}
875
876	/**
877	* Remove current node when no right child exists
878	*
879	* @return TreeNode\|null The new root
880	*
881	* @since 1.0.0
882	*/
883	private function removeCurrentWithoutRightChild()
884	{
885
886	$left = $this->left;	177✔
887	$right = $this->right;	177✔
888
889	if ($this->information & 2) {	177✔
890	$left->right = $right;	79✔
891
892	return $left;	79✔
893	}
894
895	if ($left && $left->right == $this) {	177✔
896	$left->information &= ~ 1;	167✔
897
898	return $right;	167✔
899	}
900
901	if ($right && $right->left == $this) {	170✔
902	$right->information &= ~ 2;	168✔
903
904	return $left;	168✔
905	}
906
907	return null;	2✔
908	}
909	}

chdemko / php-sorted-collections / 24612783811

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