BinaryTree::count() - Code Metrics - Inspection of "Automatic Push" - HOWZ1T/Ptypes - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — development ( f760e2...e8a84c )

by Dylan David

created 2018-04-03 00:18 UTC

BinaryTree::count() A

↳ Parent: BinaryTree

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	3
rs	10
c	0
b	0
f	0
cc	1
eloc	1
nc	1
nop	0

<?php

namespace Ptypes;

use Countable;
use Ptypes\TreeNode;
use Ptypes\Exceptions\UnexpectedType;
use Ptypes\Exceptions\InvalidArgument;

class BinaryTree implements Countable
{
	public const IN_ORDER = 0;
	public const PRE_ORDER = 1;
	public const POST_ORDER = 2;
	public const LEVEL_ORDER = 3;
	
	public $root;
	
	private $count = 0;
	
	public function __construct(&$root=null)
	{
		if($root != null)
		{
			$this->validate_parameter($root);
		}
		
		$this->root = $root;
		$this->count = ($root == null) ? 0 : 1;
	}
	
	public function insert($node) //$node is a treenode
	{
		$this->validate_parameter($node);
		
		$this->count++;
		
		if($this->root == null)
		{
			$this->root = $node;
			return $this;
		}
		
		$n = $this->root;
		while(1)
		{	
			if($node->value < $n->value)
			{
				if($n->left == null)
				{
					$n->left = $node;
					return $this;
				}
				
				$n = $n->left;
			}
			else if($node->value > $n->value)
			{
				if($n->right == null)
				{
					$n->right = $node;
					return $this;
				}
				
				$n = $n->right;
			}
			else if($node->value == $n->value) //node is already in the tree, we do not create duplicates!
			{
				return $this;
			}
		}
	}
	
	public function search($value)
	{
		if(gettype($value) != "integer" && gettype($value) != "int" && gettype($value) != "double")
		{
			throw new InvalidArgument("Expected a number, got: " . gettype($value) . " !\n");
		}
		
		return $this->recursive_search($value, $this->root);
	}
	
	private function recursive_search($value, $node)
	{
		if($node == null)
		{
			return null;
		}
		
		$eval = $value - $node->value;
		if($eval == 0)
		{
			return $node;
		}
		
		if($eval < 0)
		{
			return $this->recursive_search($value, $node->left);
		}
		else if($eval > 0)
		{
			return $this->recursive_search($value, $node->right);
		}
	}
	
	public function get_min($node)
	{
		while($node->left != null) //find left most leaf
		{
			$node = $node->left;
		}
		return $node;
	}
	
	public function compare($nodeA, $nodeB)
	{
		$this->validate_parameter($nodeA);
		$this->validate_parameter($nodeB);
		
		$eval = $nodeA->value - $nodeB->value;
		
		if($eval < 0)
		{
			return -1; //go left
		}
		
		if($eval > 0)
		{
			return 1; //go right
		}
		
		return 0; //equal
	}
	
	public function delete($value)
	{
		//check if value is in the tree
		$node = $this->search($value); //this function also handles type checking
		if($node != null)
		{
			$this->delete_recursive($this->root, $node->value);
		}
		
		$this->count--;
		return $this; //allows chaining
	}
	
	private function delete_recursive(&$parent, $value)
	{
		if($parent == null) 
		{
			return $parent;
		}
		
		if($value < $parent->value)
		{
			$parent->left = $this->delete_recursive($parent->left, $value);
		}
		else if($value > $parent->value)
		{
			$parent->right = $this->delete_recursive($parent->right, $value);
		}
		else
		{
			if($parent->left == null)
			{
				$temp = $parent->right;
				$parent = null;
				return $temp;
			}
			else if($parent->right == null)
			{
				$temp = $parent->left;
				$parent = null;
				return $temp;
			}
			
			$temp = $this->get_min($parent->right);
			$parent->value = $temp->value;
			$parent->right = $this->delete_recursive($parent->right, $temp->value);
		}
		
		return $parent;
	}
	
	public function size()
	{
		return $this->count + 1;
	}
	
	public function get_height()
	{
		return $this->get_height_recursive($this->root);
	}
	
	private function get_height_recursive($node)
	{
		if($node == null)
		{
			return 0;
		}
		
		$lHeight = $this->get_height_recursive($node->left);
		$rHeight = $this->get_height_recursive($node->right);
		
		if($lHeight > $rHeight)
		{
			return ($lHeight + 1);
		}
		else
		{
			return ($rHeight + 1);
		}
	}
	
	public function get_level($level)
	{
		if(gettype($level) != "integer" && gettype($level) != "int")
		{
			throw new InvalidArgument("Expected an int, got: " . gettype($level) . " !");
		}
		
		$h = $this->get_height();
		if($level > $h)
		{
			throw new InvalidArgument("Cannot get the level: " . $level . " as it is greater than the tree level of: " . $h . " !");
		}
		
		$results = array();
		$this->get_level_recursive($level, $this->root, $results);
		return $results;
	}
	
	private function get_level_recursive($level, $node=null, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if($node == null)
		{
			return null;
		}
		
		if($level == 1)
		{
			array_push($results, $node);
		}
		else if($level > 1)
		{
			$this->get_level_recursive($level-1, $node->left, $results);
			$this->get_level_recursive($level-1, $node->right, $results);
		}
	}
	
	public function traverse($order)
	{
		switch($order)
		{
			case self::IN_ORDER:
				$results = array();
				$this->in_order_traversal($this->root, $results);
				return $results;
				
			case self::PRE_ORDER:
				$results = array();
				$this->pre_order_traversal($this->root, $results);
				return $results;
				
			case self::POST_ORDER:
				$results = array();
				$this->post_order_traversal($this->root, $results);
				return $results;
				
			case self::LEVEL_ORDER:
				$results =array();
				$this->level_order_traversal($results);
				return $results;
				
			default:
				throw new InvalidArgument("Invalid order: " . $order . "! Valid orders: IN_ORDER (BinaryTree::IN_ORDER), PRE_ORDER (BinaryTree::PRE_ORDER), POST_ORDER (BinaryTree::POST_ORDER) and LEVEL_ORDER (BinaryTree::LEVEL_ORDER).\n");
		}
	}
	
	private function in_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if ($node == null)
		{
			return null;
		}
		
		$this->in_order_traversal($node->left, $results);
		
		array_push($results, $node->value);
		
		$this->in_order_traversal($node->right, $results);
	}
	
	private function pre_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if ($node == null)
		{
			return null;
		}
		
		array_push($results, $node->value);
		
		$this->pre_order_traversal($node->left, $results);
		$this->pre_order_traversal($node->right, $results);
	}
	
	private function post_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
	{
		if ($node == null)
		{
			return null;
		}
		
		$this->post_order_traversal($node->left, $results);
		$this->post_order_traversal($node->right, $results);
		
		array_push($results, $node->value);
	}
	
	private function level_order_traversal(&$results)
	{
		for($i = 1; $i <= $this->get_height(); $i++)
		{
			$results[$i] = $this->get_level($i);
		}
	}
	
	private function validate_parameter($node)
	{
		if(gettype($node) != "object")
		{
			throw new UnexpectedType("Expected a Ptypes\TreeNode, got: " . gettype($node));
		}
		
		if(get_class($node) != "Ptypes\TreeNode")
		{
			throw new UnexpectedType("Expected a Ptypes\TreeNode, got: " . get_class($node));
		}
	}
	
	//Overriding functions & magic methods below

	/**
	 * Count, same functionality as Size.
	 * Overrides the default count function call on this class.
	 *
	 * @return int
	 */
	public function count()
	{
		return $this->count + 1;
	}
}

1			<?php
2
3			namespace Ptypes;
4
5			use Countable;
6			use Ptypes\TreeNode;
7			use Ptypes\Exceptions\UnexpectedType;
8			use Ptypes\Exceptions\InvalidArgument;
9
10			class BinaryTree implements Countable
11			{
12			public const IN_ORDER = 0;
13			public const PRE_ORDER = 1;
14			public const POST_ORDER = 2;
15			public const LEVEL_ORDER = 3;
16
17			public $root;
18
19			private $count = 0;
20
21			public function __construct(&$root=null)
22			{
23			if($root != null)
24			{
25			$this->validate_parameter($root);
26			}
27
28			$this->root = $root;
29			$this->count = ($root == null) ? 0 : 1;
30			}
31
32			public function insert($node) //$node is a treenode
33			{
34			$this->validate_parameter($node);
35
36			$this->count++;
37
38			if($this->root == null)
39			{
40			$this->root = $node;
41			return $this;
42			}
43
44			$n = $this->root;
45			while(1)
46			{
47			if($node->value < $n->value)
48			{
49			if($n->left == null)
50			{
51			$n->left = $node;
52			return $this;
53			}
54
55			$n = $n->left;
56			}
57			else if($node->value > $n->value)
58			{
59			if($n->right == null)
60			{
61			$n->right = $node;
62			return $this;
63			}
64
65			$n = $n->right;
66			}
67			else if($node->value == $n->value) //node is already in the tree, we do not create duplicates!
68			{
69			return $this;
70			}
71			}
72			}
73
74			public function search($value)
75			{
76			if(gettype($value) != "integer" && gettype($value) != "int" && gettype($value) != "double")
77			{
78			throw new InvalidArgument("Expected a number, got: " . gettype($value) . " !\n");
79			}
80
81			return $this->recursive_search($value, $this->root);
82			}
83
84			private function recursive_search($value, $node)
85			{
86			if($node == null)
87			{
88			return null;
89			}
90
91			$eval = $value - $node->value;
92			if($eval == 0)
93			{
94			return $node;
95			}
96
97			if($eval < 0)
98			{
99			return $this->recursive_search($value, $node->left);
100			}
101			else if($eval > 0)
102			{
103			return $this->recursive_search($value, $node->right);
104			}
105			}
106
107			public function get_min($node)
108			{
109			while($node->left != null) //find left most leaf
110			{
111			$node = $node->left;
112			}
113			return $node;
114			}
115
116			public function compare($nodeA, $nodeB)
117			{
118			$this->validate_parameter($nodeA);
119			$this->validate_parameter($nodeB);
120
121			$eval = $nodeA->value - $nodeB->value;
122
123			if($eval < 0)
124			{
125			return -1; //go left
126			}
127
128			if($eval > 0)
129			{
130			return 1; //go right
131			}
132
133			return 0; //equal
134			}
135
136			public function delete($value)
137			{
138			//check if value is in the tree
139			$node = $this->search($value); //this function also handles type checking
140			if($node != null)
141			{
142			$this->delete_recursive($this->root, $node->value);
143			}
144
145			$this->count--;
146			return $this; //allows chaining
147			}
148
149			private function delete_recursive(&$parent, $value)
150			{
151			if($parent == null)
152			{
153			return $parent;
154			}
155
156			if($value < $parent->value)
157			{
158			$parent->left = $this->delete_recursive($parent->left, $value);
159			}
160			else if($value > $parent->value)
161			{
162			$parent->right = $this->delete_recursive($parent->right, $value);
163			}
164			else
165			{
166			if($parent->left == null)
167			{
168			$temp = $parent->right;
169			$parent = null;
170			return $temp;
171			}
172			else if($parent->right == null)
173			{
174			$temp = $parent->left;
175			$parent = null;
176			return $temp;
177			}
178
179			$temp = $this->get_min($parent->right);
180			$parent->value = $temp->value;
181			$parent->right = $this->delete_recursive($parent->right, $temp->value);
182			}
183
184			return $parent;
185			}
186
187			public function size()
188			{
189			return $this->count + 1;
190			}
191
192			public function get_height()
193			{
194			return $this->get_height_recursive($this->root);
195			}
196
197			private function get_height_recursive($node)
198			{
199			if($node == null)
200			{
201			return 0;
202			}
203
204			$lHeight = $this->get_height_recursive($node->left);
205			$rHeight = $this->get_height_recursive($node->right);
206
207			if($lHeight > $rHeight)
208			{
209			return ($lHeight + 1);
210			}
211			else
212			{
213			return ($rHeight + 1);
214			}
215			}
216
217			public function get_level($level)
218			{
219			if(gettype($level) != "integer" && gettype($level) != "int")
220			{
221			throw new InvalidArgument("Expected an int, got: " . gettype($level) . " !");
222			}
223
224			$h = $this->get_height();
225			if($level > $h)
226			{
227			throw new InvalidArgument("Cannot get the level: " . $level . " as it is greater than the tree level of: " . $h . " !");
228			}
229
230			$results = array();
231			$this->get_level_recursive($level, $this->root, $results);
232			return $results;
233			}
234
235			private function get_level_recursive($level, $node=null, &$results) //it is important that reference to results stays a reference (php pointer) !
236			{
237			if($node == null)
238			{
239			return null;
240			}
241
242			if($level == 1)
243			{
244			array_push($results, $node);
245			}
246			else if($level > 1)
247			{
248			$this->get_level_recursive($level-1, $node->left, $results);
249			$this->get_level_recursive($level-1, $node->right, $results);
250			}
251			}
252
253			public function traverse($order)
254			{
255			switch($order)
256			{
257			case self::IN_ORDER:
258			$results = array();
259			$this->in_order_traversal($this->root, $results);
260			return $results;
261
262			case self::PRE_ORDER:
263			$results = array();
264			$this->pre_order_traversal($this->root, $results);
265			return $results;
266
267			case self::POST_ORDER:
268			$results = array();
269			$this->post_order_traversal($this->root, $results);
270			return $results;
271
272			case self::LEVEL_ORDER:
273			$results =array();
274			$this->level_order_traversal($results);
275			return $results;
276
277			default:
278			throw new InvalidArgument("Invalid order: " . $order . "! Valid orders: IN_ORDER (BinaryTree::IN_ORDER), PRE_ORDER (BinaryTree::PRE_ORDER), POST_ORDER (BinaryTree::POST_ORDER) and LEVEL_ORDER (BinaryTree::LEVEL_ORDER).\n");
279			}
280			}
281
282			private function in_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
283			{
284			if ($node == null)
285			{
286			return null;
287			}
288
289			$this->in_order_traversal($node->left, $results);
290
291			array_push($results, $node->value);
292
293			$this->in_order_traversal($node->right, $results);
294			}
295
296			private function pre_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
297			{
298			if ($node == null)
299			{
300			return null;
301			}
302
303			array_push($results, $node->value);
304
305			$this->pre_order_traversal($node->left, $results);
306			$this->pre_order_traversal($node->right, $results);
307			}
308
309			private function post_order_traversal($node, &$results) //it is important that reference to results stays a reference (php pointer) !
310			{
311			if ($node == null)
312			{
313			return null;
314			}
315
316			$this->post_order_traversal($node->left, $results);
317			$this->post_order_traversal($node->right, $results);
318
319			array_push($results, $node->value);
320			}
321
322			private function level_order_traversal(&$results)
323			{
324			for($i = 1; $i <= $this->get_height(); $i++)
325			{
326			$results[$i] = $this->get_level($i);
327			}
328			}
329
330			private function validate_parameter($node)
331			{
332			if(gettype($node) != "object")
333			{
334			throw new UnexpectedType("Expected a Ptypes\TreeNode, got: " . gettype($node));
335			}
336
337			if(get_class($node) != "Ptypes\TreeNode")
338			{
339			throw new UnexpectedType("Expected a Ptypes\TreeNode, got: " . get_class($node));
340			}
341			}
342
343			//Overriding functions & magic methods below
344
345			/**
346			* Count, same functionality as Size.
347			* Overrides the default count function call on this class.
348			*
349			* @return int
350			*/
351			public function count()
352			{
353			return $this->count + 1;
354			}
355			}

HOWZ1T / Ptypes

Push — development ( f760e2...e8a84c )

BinaryTree::count() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like