TreeNode - Code Metrics - 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

TreeNode D

↳ Parent: Project

Complexity

Total Complexity

Size/Duplication

Total Lines	631
Duplicated Lines	29.79 %

Coupling/Cohesion

Components	1
Dependencies	0

Importance

Changes	2
Bugs	0	Features	0

Metric	Value
wmc	86
lcom	1
cbo	0
dl	188
loc	631
rs	4.7465
c	2
b	0
f	0

16 Methods

Rating	Name	Duplication	Size	Complexity
A	create()	0	4	1
A	__construct()	0	7	1
B	__get()	0	20	7
A	first()	0	11	2
A	last()	0	11	2
A	predecessor()	18	18	3
A	successor()	18	18	3
A	count()	0	16	3
C	find()	0	68	14
B	_rotateLeft()	31	31	4
B	_rotateRight()	31	31	4
A	_incBalance()	16	16	3
A	_decBalance()	16	16	3
C	insert()	35	50	9
C	_pullUpLeftMost()	0	44	7
C	remove()	23	77	20

How to fix Duplicated Code Complexity

Duplicated Code

Duplicate code is one of the most pungent code smells. A rule that is often used is to re-structure code once it is duplicated in three or more places.

Common duplication problems, and corresponding solutions are:

If you have the same expression in different places: Extract expression to a method
If you have the same method in different sub-classes: Extract method, and pull up field to the parent class
If you have the same code in unrelated classes: Consider extracting the code to a new class, and injecting that class

Complex Class

Tip: Before tackling complexity, make sure that you eliminate any duplication first. This often can reduce the size of classes significantly.

Complex classes like TreeNode often do a lot of different things. To break such a class down, we need to identify a cohesive component within that class. A common approach to find such a component is to look for fields/methods that share the same prefixes, or suffixes. You can also have a look at the cohesion graph to spot any un-connected, or weakly-connected components.

Once you have determined the fields that belong together, you can apply the Extract Class refactoring. If the component makes sense as a sub-class, Extract Subclass is also a candidate, and is often faster.

While breaking up the class, it is a good idea to analyze how other classes use TreeNode, and based on these observations, apply Extract Interface, too.

<?php

/**
 * chdemko\SortedCollection\TreeNode class
 *
 * @author     Christophe Demko <[email protected]>
 * @copyright  Copyright (C) 2012-2016 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
	 */
	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->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();
		case 'last':
			return $this->last();
		case 'predecessor':
			return $this->predecessor();
		case 'successor':
			return $this->successor();
		case 'key':
			return $this->key;
		case 'count':
			return $this->count();
		default:
			throw new \RuntimeException('Undefined property');
		}
	}

	/**
	 * 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)
function myFunction($a) {
    switch ($a) {
        case 'foo':
            $x = 1;
            break;

        case 'bar':
            $x = 2;
            break;
    }

    // $x is potentially undefined here.
    echo $x;
}
		{
			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-2016 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		public static function create($key, $value)
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		case 'last':
121		return $this->last();
122		case 'predecessor':
123		return $this->predecessor();
124		case 'successor':
125		return $this->successor();
126		case 'key':
127		return $this->key;
128		case 'count':
129		return $this->count();
130		default:
131		throw new \RuntimeException('Undefined property');
132		}
133		}
134
135		/**
136		* Get the first node
137		*
138		* @return the first node
139		*
140		* @since 1.0.0
141		*/
142		public function first()
143		{
144		$node = $this;
145
146		while ($node->information & 2)
147		{
148		$node = $node->left;
149		}
150
151		return $node;
152		}
153
154		/**
155		* Get the last node
156		*
157		* @return the last node
158		*
159		* @since 1.0.0
160		*/
161		public function last()
162		{
163		$node = $this;
164
165		while ($node->information & 1)
166		{
167		$node = $node->right;
168		}
169
170		return $node;
171		}
172
173		/**
174		* Get the predecessor
175		*
176		* @return the predecessor node
177		*
178		* @since 1.0.0
179		*/
180	View Code Duplication	public function predecessor()
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
181		{
182		if ($this->information & 2)
183		{
184		$node = $this->left;
185
186		while ($node->information & 1)
187		{
188		$node = $node->right;
189		}
190
191		return $node;
192		}
193		else
194		{
195		return $this->left;
196		}
197		}
198
199		/**
200		* Get the successor
201		*
202		* @return the successor node
203		*
204		* @since 1.0.0
205		*/
206	View Code Duplication	public function successor()
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
207		{
208		if ($this->information & 1)
209		{
210		$node = $this->right;
211
212		while ($node->information & 2)
213		{
214		$node = $node->left;
215		}
216
217		return $node;
218		}
219		else
220		{
221		return $this->right;
222		}
223		}
224
225		/**
226		* Count the number of key/value pair
227		*
228		* @return integer
229		*
230		* @since 1.0.0
231		*/
232		public function count()
233		{
234		$count = 1;
235
236		if ($this->information & 2)
237		{
238		$count += $this->left->count;
239		}
240
241		if ($this->information & 1)
242		{
243		$count += $this->right->count;
244		}
245
246		return $count;
247		}
248
249		/**
250		* Get the node for a key
251		*
252		* @param mixed $key The key
253		* @param Callable $comparator The comparator function
254		* @param integer $type The operation type
255		* -2 for the greatest key lesser than the given key
256		* -1 for the greatest key lesser than or equal to the given key
257		* 0 for the given key
258		* +1 for the lowest key greater than or equal to the given key
259		* +2 for the lowest key greater than the given key
260		*
261		* @return mixed The node or null if not found
262		*
263		* @since 1.0.0
264		*/
265		public function find($key, $comparator, $type = 0)
266		{
267		$node = $this;
268
269		while (true)
270		{
271		$cmp = call_user_func($comparator, $key, $node->key);
272
273		if ($cmp < 0 && $node->information & 2)
274		{
275		$node = $node->left;
276		}
277		elseif ($cmp > 0 && $node->information & 1)
278		{
279		$node = $node->right;
280		}
281		else
282		{
283		break;
284		}
285		}
286
287		if ($cmp < 0)
288		{
289		if ($type < 0)
290		{
291		return $node->left;
292		}
293		elseif ($type > 0)
294		{
295		return $node;
296		}
297		else
298		{
299		return null;
300		}
301		}
302		elseif ($cmp > 0)
		1 ignored issue – show Bug introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report The variable `$cmp` does not seem to be defined for all execution paths leading up to this point. If you define a variable conditionally, it can happen that it is not defined for all execution paths. Let’s take a look at an example: function myFunction($a) { switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; } // $x is potentially undefined here. echo $x; } In the above example, the variable `$x` is defined if you pass “foo” or “bar” as argument for `$a`. However, since the `switch` statement has no default case statement, if you pass any other value, the variable `$x` would be undefined. Available Fixes Check for existence of the variable explicitly: function myFunction($a) { switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; } if (isset($x)) { // Make sure it's always set. echo $x; } } Define a default value for the variable: function myFunction($a) { $x = ''; // Set a default which gets overridden for certain paths. switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; } echo $x; } Add a value for the missing path: function myFunction($a) { switch ($a) { case 'foo': $x = 1; break; case 'bar': $x = 2; break; // We add support for the missing case. default: $x = ''; break; } echo $x; } Loading history...
303		{
304		if ($type < 0)
305		{
306		return $node;
307		}
308		elseif ($type > 0)
309		{
310		return $node->right;
311		}
312		else
313		{
314		return null;
315		}
316		}
317		else
318		{
319		if ($type < -1)
320		{
321		return $node->predecessor;
322		}
323		elseif ($type > 1)
324		{
325		return $node->successor;
326		}
327		else
328		{
329		return $node;
330		}
331		}
332		}
333
334		/**
335		* Rotate the node to the left
336		*
337		* @return TreeNode The rotated node
338		*
339		* @since 1.0.0
340		*/
341	View Code Duplication	private function _rotateLeft()
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
342		{
343		$right = $this->right;
344
345		if ($right->information & 2)
346		{
347		$this->right = $right->left;
348		$right->left = $this;
349		}
350		else
351		{
352		$right->information \|= 2;
353		$this->information &= ~ 1;
354		}
355
356		$this->information -= 4;
357
358		if ($right->information >= 4)
359		{
360		$this->information -= $right->information & ~3;
361		}
362
363		$right->information -= 4;
364
365		if ($this->information < 0)
366		{
367		$right->information += $this->information & ~3;
368		}
369
370		return $right;
371		}
372
373		/**
374		* Rotate the node to the right
375		*
376		* @return TreeNode The rotated node
377		*
378		* @since 1.0.0
379		*/
380	View Code Duplication	private function _rotateRight()
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
381		{
382		$left = $this->left;
383
384		if ($left->information & 1)
385		{
386		$this->left = $left->right;
387		$left->right = $this;
388		}
389		else
390		{
391		$this->information &= ~ 2;
392		$left->information \|= 1;
393		}
394
395		$this->information += 4;
396
397		if ($left->information < 0)
398		{
399		$this->information -= $left->information & ~3;
400		}
401
402		$left->information += 4;
403
404		if ($this->information >= 4)
405		{
406		$left->information += $this->information & ~3;
407		}
408
409		return $left;
410		}
411
412		/**
413		* Increment the balance of the node
414		*
415		* @return TreeNode $this or a rotated version of $this
416		*
417		* @since 1.0.0
418		*/
419	View Code Duplication	private function _incBalance()
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
420		{
421		$this->information += 4;
422
423		if ($this->information >= 8)
424		{
425		if ($this->right->information < 0)
426		{
427		$this->right = $this->right->_rotateRight();
428		}
429
430		return $this->_rotateLeft();
431		}
432
433		return $this;
434		}
435
436		/**
437		* Decrement the balance of the node
438		*
439		* @return TreeNode $this or a rotated version of $this
440		*
441		* @since 1.0.0
442		*/
443	View Code Duplication	private function _decBalance()
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
444		{
445		$this->information -= 4;
446
447		if ($this->information < - 4)
448		{
449		if ($this->left->information >= 4)
450		{
451		$this->left = $this->left->_rotateLeft();
452		}
453
454		return $this->_rotateRight();
455		}
456
457		return $this;
458		}
459
460		/**
461		* Insert a key/value pair
462		*
463		* @param mixed $key The key
464		* @param mixed $value The value
465		* @param Callable $comparator The comparator function
466		*
467		* @return TreeNode The new root
468		*
469		* @since 1.0.0
470		*/
471		public function insert($key, $value, $comparator)
472		{
473		$node = $this;
474		$cmp = call_user_func($comparator, $key, $this->key);
475
476		if ($cmp < 0)
477		{
478	View Code Duplication	if ($this->information & 2)
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
479		{
480		$leftBalance = $this->left->information & ~3;
481		$this->left = $this->left->insert($key, $value, $comparator);
482
483		if (($this->left->information & ~3) && ($this->left->information & ~3) != $leftBalance)
484		{
485		$node = $this->_decBalance();
486		}
487		}
488		else
489		{
490		$this->left = new static($key, $value, $this->left, $this);
491		$this->information\|= 2;
492		$node = $this->_decBalance();
493		}
494		}
495	View Code Duplication	elseif ($cmp > 0)
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
496		{
497		if ($this->information & 1)
498		{
499		$rightBalance = $this->right->information & ~3;
500		$this->right = $this->right->insert($key, $value, $comparator);
501
502		if (($this->right->information & ~3) && ($this->right->information & ~3) != $rightBalance)
503		{
504		$node = $this->_incBalance();
505		}
506		}
507		else
508		{
509		$this->right = new static($key, $value, $this, $this->right);
510		$this->information\|= 1;
511		$node = $this->_incBalance();
512		}
513		}
514		else
515		{
516		$this->value = $value;
517		}
518
519		return $node;
520		}
521
522		/**
523		* Pull up the left most node of a node
524		*
525		* @return TreeNode The new root
526		*
527		* @since 1.0.0
528		*/
529		private function _pullUpLeftMost()
530		{
531		if ($this->information & 2)
532		{
533		$leftBalance = $this->left->information & ~3;
534		$this->left = $this->left->_pullUpLeftMost();
535
536		if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0)
537		{
538		return $this->_incBalance();
539		}
540		else
541		{
542		return $this;
543		}
544		}
545		else
546		{
547		$this->left->key = $this->key;
548		$this->left->value = $this->value;
549
550		if ($this->information & 1)
551		{
552		$this->right->left = $this->left;
553
554		return $this->right;
555		}
556		else
557		{
558		if ($this->left->right == $this)
559		{
560		$this->left->information &= ~ 1;
561
562		return $this->right;
563		}
564		else
565		{
566		$this->right->information &= ~ 2;
567
568		return $this->left;
569		}
570		}
571		}
572		}
573
574		/**
575		* Remove a key
576		*
577		* @param mixed $key The key
578		* @param Callable $comparator The comparator function
579		*
580		* @return TreeNode The new root
581		*
582		* @since 1.0.0
583		*/
584		public function remove($key, $comparator)
585		{
586		$cmp = call_user_func($comparator, $key, $this->key);
587
588		if ($cmp < 0)
589		{
590	View Code Duplication	if ($this->information & 2)
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
591		{
592		$leftBalance = $this->left->information & ~3;
593		$this->left = $this->left->remove($key, $comparator);
594
595		if (!($this->information & 2) \|\| $leftBalance != 0 && ($this->left->information & ~3) == 0)
596		{
597		return $this->_incBalance();
598		}
599		}
600		}
601	View Code Duplication	elseif ($cmp > 0)
		1 ignored issue – show Duplication introduced 2016-10-18 10:02 UTC by Report Bug Copy Issue Report This code seems to be duplicated across your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
602		{
603		if ($this->information & 1)
604		{
605		$rightBalance = $this->right->information & ~3;
606		$this->right = $this->right->remove($key, $comparator);
607
608		if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0)
609		{
610		return $this->_decBalance();
611		}
612		}
613		}
614		else
615		{
616		if ($this->information & 1)
617		{
618		$rightBalance = $this->right->information & ~3;
619		$this->right = $this->right->_pullUpLeftMost();
620
621		if (!($this->information & 1) \|\| $rightBalance != 0 && ($this->right->information & ~3) == 0)
622		{
623		return $this->_decBalance();
624		}
625		}
626		else
627		{
628		$left = $this->left;
629		$right = $this->right;
630
631		if ($this->information & 2)
632		{
633		$left->right = $right;
634
635		return $left;
636		}
637		else
638		{
639		if ($left && $left->right == $this)
640		{
641		$left->information &= ~ 1;
642
643		return $right;
644		}
645		elseif ($right && $right->left == $this)
646		{
647		$right->information &= ~ 2;
648
649		return $left;
650		}
651		else
652		{
653		return null;
654		}
655		}
656		}
657		}
658
659		return $this;
660		}
661		}
662

chdemko / php-sorted-collections