Issues in TreeNode.php - Fixed Issues - Inspection of "Publishing version 1.0.1" - chdemko/php-sorted-collections - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 602dbe...ab6845 )

by Christophe

created 2016-10-18 11:09 UTC

src/SortedCollection/TreeNode.php (8 issues)

Labels

Severity

Upgrade to new PHP Analysis Engine

These results are based on our legacy PHP analysis, consider migrating to our new PHP analysis engine instead. Learn more

<?php

/**
 * chdemko\SortedCollection\TreeNode class
 *
 * @author     Christophe Demko <[email protected]>
 * @copyright  Copyright (C) 2012-2015 Christophe Demko. All rights reserved.
 *
 * @license    http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html The CeCILL B 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  $predecessor  The predecessor node
 * @property-read  TreeNode  $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  Left|Predecessor node
	 *
	 * @since   1.0.0
	 */
	private $left;

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

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

	/**
	 * @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  A new node
	 *
	 * @since   1.0.0
	 */
	static public 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->key = $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();
		break;
switch ($x) {
    case 1:
        return 'foo';
        break; // This break is not necessary and can be left off.
}
		case 'last':
			return $this->last();
		break;
switch ($x) {
    case 1:
        return 'foo';
        break; // This break is not necessary and can be left off.
}
		case 'predecessor':
			return $this->predecessor();
		break;
switch ($x) {
    case 1:
        return 'foo';
        break; // This break is not necessary and can be left off.
}
		case 'successor':
			return $this->successor();
		break;
switch ($x) {
    case 1:
        return 'foo';
        break; // This break is not necessary and can be left off.
}
		case 'key':
			return $this->key;
		break;
switch ($x) {
    case 1:
        return 'foo';
        break; // This break is not necessary and can be left off.
}
		case 'count':
			return $this->count();
		break;
switch ($x) {
    case 1:
        return 'foo';
        break; // This break is not necessary and can be left off.
}
		default:
			throw new \RuntimeException('Undefined property');
		break;
function fx() {
    try {
        doSomething();
        return true;
    }
    catch (\Exception $e) {
        return false;
    }

    return false;
}
		}
	}

	/**
	 * Get the first node
	 *
	 * @return  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  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  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  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()
	{
		$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;

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

			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)
		{
			if ($this->right->information < 0)
			{
				$this->right = $this->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->key);

		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->key = $this->key;
			$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->key);

		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 <[email protected]>
7		* @copyright Copyright (C) 2012-2015 Christophe Demko. All rights reserved.
8		*
9		* @license http://www.cecill.info/licences/Licence_CeCILL-B_V1-en.html The CeCILL B 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 $predecessor The predecessor node
27		* @property-read TreeNode $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 Left\|Predecessor node
44		*
45		* @since 1.0.0
46		*/
47		private $left;
48
49		/**
50		* @var TreeNode 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 $key;
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 A new node
77		*
78		* @since 1.0.0
79		*/
80		static public function create($key, $value)
		0 ignored issues – show Coding Style introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this As per PSR2, the `static` declaration should come after the visibility declaration. Loading history...
81		{
82		return new static($key, $value);
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->key = $key;
98		$this->value = $value;
99		$this->left = $predecessor;
100		$this->right = $successor;
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		{
118		case 'first':
119		return $this->first();
120		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break` is not strictly necessary here and could be removed. The `break` statement is not necessary if it is preceded for example by a `return` statement: switch ($x) { case 1: return 'foo'; break; // This break is not necessary and can be left off. } If you would like to keep this construct to be consistent with other `case` statements, you can safely mark this issue as a false-positive. Loading history...
121		case 'last':
122		return $this->last();
123		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break` is not strictly necessary here and could be removed. The `break` statement is not necessary if it is preceded for example by a `return` statement: switch ($x) { case 1: return 'foo'; break; // This break is not necessary and can be left off. } If you would like to keep this construct to be consistent with other `case` statements, you can safely mark this issue as a false-positive. Loading history...
124		case 'predecessor':
125		return $this->predecessor();
126		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break` is not strictly necessary here and could be removed. The `break` statement is not necessary if it is preceded for example by a `return` statement: switch ($x) { case 1: return 'foo'; break; // This break is not necessary and can be left off. } If you would like to keep this construct to be consistent with other `case` statements, you can safely mark this issue as a false-positive. Loading history...
127		case 'successor':
128		return $this->successor();
129		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break` is not strictly necessary here and could be removed. The `break` statement is not necessary if it is preceded for example by a `return` statement: switch ($x) { case 1: return 'foo'; break; // This break is not necessary and can be left off. } If you would like to keep this construct to be consistent with other `case` statements, you can safely mark this issue as a false-positive. Loading history...
130		case 'key':
131		return $this->key;
132		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break` is not strictly necessary here and could be removed. The `break` statement is not necessary if it is preceded for example by a `return` statement: switch ($x) { case 1: return 'foo'; break; // This break is not necessary and can be left off. } If you would like to keep this construct to be consistent with other `case` statements, you can safely mark this issue as a false-positive. Loading history...
133		case 'count':
134		return $this->count();
135		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break` is not strictly necessary here and could be removed. The `break` statement is not necessary if it is preceded for example by a `return` statement: switch ($x) { case 1: return 'foo'; break; // This break is not necessary and can be left off. } If you would like to keep this construct to be consistent with other `case` statements, you can safely mark this issue as a false-positive. Loading history...
136		default:
137		throw new \RuntimeException('Undefined property');
138		break;
		0 ignored issues – show Unused Code introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report Show Similar Issues like this `break;` does not seem to be reachable. This check looks for unreachable code. It uses sophisticated control flow analysis techniques to find statements which will never be executed. Unreachable code is most often the result of `return`, `die` or `exit` statements that have been added for debug purposes. function fx() { try { doSomething(); return true; } catch (\Exception $e) { return false; } return false; } In the above example, the last `return false` will never be executed, because a return statement has already been met in every possible execution path. Loading history...
139		}
140		}
141
142		/**
143		* Get the first node
144		*
145		* @return the first node
146		*
147		* @since 1.0.0
148		*/
149		public function first()
150		{
151		$node = $this;
152
153		while ($node->information & 2)
154		{
155		$node = $node->left;
156		}
157
158		return $node;
159		}
160
161		/**
162		* Get the last node
163		*
164		* @return the last node
165		*
166		* @since 1.0.0
167		*/
168		public function last()
169		{
170		$node = $this;
171
172		while ($node->information & 1)
173		{
174		$node = $node->right;
175		}
176
177		return $node;
178		}
179
180		/**
181		* Get the predecessor
182		*
183		* @return the predecessor node
184		*
185		* @since 1.0.0
186		*/
187	View Code Duplication	public function predecessor()
188		{
189		if ($this->information & 2)
190		{
191		$node = $this->left;
192
193		while ($node->information & 1)
194		{
195		$node = $node->right;
196		}
197
198		return $node;
199		}
200		else
201		{
202		return $this->left;
203		}
204		}
205
206		/**
207		* Get the successor
208		*
209		* @return the successor node
210		*
211		* @since 1.0.0
212		*/
213	View Code Duplication	public function successor()
214		{
215		if ($this->information & 1)
216		{
217		$node = $this->right;
218
219		while ($node->information & 2)
220		{
221		$node = $node->left;
222		}
223
224		return $node;
225		}
226		else
227		{
228		return $this->right;
229		}
230		}
231
232		/**
233		* Count the number of key/value pair
234		*
235		* @return integer
236		*
237		* @since 1.0.0
238		*/
239		public function count()
240		{
241		$count = 1;
242
243		if ($this->information & 2)
244		{
245		$count += $this->left->count;
246		}
247
248		if ($this->information & 1)
249		{
250		$count += $this->right->count;
251		}
252
253		return $count;
254		}
255
256		/**
257		* Get the node for a key
258		*
259		* @param mixed $key The key
260		* @param Callable $comparator The comparator function
261		* @param integer $type The operation type
262		* -2 for the greatest key lesser than the given key
263		* -1 for the greatest key lesser than or equal to the given key
264		* 0 for the given key
265		* +1 for the lowest key greater than or equal to the given key
266		* +2 for the lowest key greater than the given key
267		*
268		* @return mixed The node or null if not found
269		*
270		* @since 1.0.0
271		*/
272		public function find($key, $comparator, $type = 0)
273		{
274		$node = $this;
275
276		while (true)
277		{
278		$cmp = call_user_func($comparator, $key, $node->key);
279
280		if ($cmp < 0 && $node->information & 2)
281		{
282		$node = $node->left;
283		}
284		elseif ($cmp > 0 && $node->information & 1)
285		{
286		$node = $node->right;
287		}
288		else
289		{
290		break;
291		}
292		}
293
294		if ($cmp < 0)
295		{
296		if ($type < 0)
297		{
298		return $node->left;
299		}
300		elseif ($type > 0)
301		{
302		return $node;
303		}
304		else
305		{
306		return null;
307		}
308		}
309		elseif ($cmp > 0)
310		{
311		if ($type < 0)
312		{
313		return $node;
314		}
315		elseif ($type > 0)
316		{
317		return $node->right;
318		}
319		else
320		{
321		return null;
322		}
323		}
324		else
325		{
326		if ($type < -1)
327		{
328		return $node->predecessor;
329		}
330		elseif ($type > 1)
331		{
332		return $node->successor;
333		}
334		else
335		{
336		return $node;
337		}
338		}
339		}
340
341		/**
342		* Rotate the node to the left
343		*
344		* @return TreeNode The rotated node
345		*
346		* @since 1.0.0
347		*/
348	View Code Duplication	private function _rotateLeft()
349		{
350		$right = $this->right;
351
352		if ($right->information & 2)
353		{
354		$this->right = $right->left;
355		$right->left = $this;
356		}
357		else
358		{
359		$right->information \|= 2;
360		$this->information &= ~ 1;
361		}
362
363		$this->information -= 4;
364
365		if ($right->information >= 4)
366		{
367		$this->information -= $right->information & ~3;
368		}
369
370		$right->information -= 4;
371
372		if ($this->information < 0)
373		{
374		$right->information += $this->information & ~3;
375		}
376
377		return $right;
378		}
379
380		/**
381		* Rotate the node to the right
382		*
383		* @return TreeNode The rotated node
384		*
385		* @since 1.0.0
386		*/
387	View Code Duplication	private function _rotateRight()
388		{
389		$left = $this->left;
390
391		if ($left->information & 1)
392		{
393		$this->left = $left->right;
394		$left->right = $this;
395		}
396		else
397		{
398		$this->information &= ~ 2;
399		$left->information \|= 1;
400		}
401
402		$this->information += 4;
403
404		if ($left->information < 0)
405		{
406		$this->information -= $left->information & ~3;
407		}
408
409		$left->information += 4;
410
411		if ($this->information >= 4)
412		{
413		$left->information += $this->information & ~3;
414		}
415
416		return $left;
417		}
418
419		/**
420		* Increment the balance of the node
421		*
422		* @return TreeNode $this or a rotated version of $this
423		*
424		* @since 1.0.0
425		*/
426	View Code Duplication	private function _incBalance()
427		{
428		$this->information += 4;
429
430		if ($this->information >= 8)
431		{
432		if ($this->right->information < 0)
433		{
434		$this->right = $this->right->_rotateRight();
435		}
436
437		return $this->_rotateLeft();
438		}
439
440		return $this;
441		}
442
443		/**
444		* Decrement the balance of the node
445		*
446		* @return TreeNode $this or a rotated version of $this
447		*
448		* @since 1.0.0
449		*/
450	View Code Duplication	private function _decBalance()
451		{
452		$this->information -= 4;
453
454		if ($this->information < - 4)
455		{
456		if ($this->left->information >= 4)
457		{
458		$this->left = $this->left->_rotateLeft();
459		}
460
461		return $this->_rotateRight();
462		}
463
464		return $this;
465		}
466
467		/**
468		* Insert a key/value pair
469		*
470		* @param mixed $key The key
471		* @param mixed $value The value
472		* @param Callable $comparator The comparator function
473		*
474		* @return TreeNode The new root
475		*
476		* @since 1.0.0
477		*/
478		public function insert($key, $value, $comparator)
479		{
480		$node = $this;
481		$cmp = call_user_func($comparator, $key, $this->key);
482
483		if ($cmp < 0)
484		{
485	View Code Duplication	if ($this->information & 2)
486		{
487		$leftBalance = $this->left->information & ~3;
488		$this->left = $this->left->insert($key, $value, $comparator);
489
490		if (($this->left->information & ~3) && ($this->left->information & ~3) != $leftBalance)
491		{
492		$node = $this->_decBalance();
493		}
494		}
495		else
496		{
497		$this->left = new static($key, $value, $this->left, $this);
498		$this->information\|= 2;
499		$node = $this->_decBalance();
500		}
501		}
502	View Code Duplication	elseif ($cmp > 0)
503		{
504		if ($this->information & 1)
505		{
506		$rightBalance = $this->right->information & ~3;
507		$this->right = $this->right->insert($key, $value, $comparator);
508
509		if (($this->right->information & ~3) && ($this->right->information & ~3) != $rightBalance)
510		{
511		$node = $this->_incBalance();
512		}
513		}
514		else
515		{
516		$this->right = new static($key, $value, $this, $this->right);
517		$this->information\|= 1;
518		$node = $this->_incBalance();
519		}
520		}
521		else
522		{
523		$this->value = $value;
524		}
525
526		return $node;
527		}
528
529		/**
530		* Pull up the left most node of a node
531		*
532		* @return TreeNode The new root
533		*
534		* @since 1.0.0
535		*/
536		private function _pullUpLeftMost()
537		{
538		if ($this->information & 2)
539		{
540		$leftBalance = $this->left->information & ~3;
541		$this->left = $this->left->_pullUpLeftMost();
542
543		if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0)
544		{
545		return $this->_incBalance();
546		}
547		else
548		{
549		return $this;
550		}
551		}
552		else
553		{
554		$this->left->key = $this->key;
555		$this->left->value = $this->value;
556
557		if ($this->information & 1)
558		{
559		$this->right->left = $this->left;
560
561		return $this->right;
562		}
563		else
564		{
565		if ($this->left->right == $this)
566		{
567		$this->left->information &= ~ 1;
568
569		return $this->right;
570		}
571		else
572		{
573		$this->right->information &= ~ 2;
574
575		return $this->left;
576		}
577		}
578		}
579		}
580
581		/**
582		* Remove a key
583		*
584		* @param mixed $key The key
585		* @param Callable $comparator The comparator function
586		*
587		* @return TreeNode The new root
588		*
589		* @since 1.0.0
590		*/
591		public function remove($key, $comparator)
592		{
593		$cmp = call_user_func($comparator, $key, $this->key);
594
595		if ($cmp < 0)
596		{
597	View Code Duplication	if ($this->information & 2)
598		{
599		$leftBalance = $this->left->information & ~3;
600		$this->left = $this->left->remove($key, $comparator);
601
602		if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0)
603		{
604		return $this->_incBalance();
605		}
606		}
607		}
608	View Code Duplication	elseif ($cmp > 0)
609		{
610		if ($this->information & 1)
611		{
612		$rightBalance = $this->right->information & ~3;
613		$this->right = $this->right->remove($key, $comparator);
614
615		if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0)
616		{
617		return $this->_decBalance();
618		}
619		}
620		}
621		else
622		{
623		if ($this->information & 1)
624		{
625		$rightBalance = $this->right->information & ~3;
626		$this->right = $this->right->_pullUpLeftMost();
627
628		if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0)
629		{
630		return $this->_decBalance();
631		}
632		}
633		else
634		{
635		$left = $this->left;
636		$right = $this->right;
637
638		if ($this->information & 2)
639		{
640		$left->right = $right;
641
642		return $left;
643		}
644		else
645		{
646		if ($left && $left->right == $this)
647		{
648		$left->information &= ~ 1;
649
650		return $right;
651		}
652		elseif ($right && $right->left == $this)
653		{
654		$right->information &= ~ 2;
655
656		return $left;
657		}
658		else
659		{
660		return null;
661		}
662		}
663		}
664		}
665
666		return $this;
667		}
668		}
669

chdemko / php-sorted-collections

Push — master ( 602dbe...ab6845 )

src/SortedCollection/TreeNode.php (8 issues)

Labels

Severity

Introduced By

Upgrade to new PHP Analysis Engine

Duplication Side-by-Side

Filter issues like