BinaryTree::compare() - Code Metrics - Inspection of "More work on binary tree" - HOWZ1T/Ptypes - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — development ( 49dbbd...6c43d4 )

by Dylan David

created 2018-04-02 09:08 UTC

BinaryTree::compare() A

↳ Parent: BinaryTree

Complexity

Conditions	3
Paths	3

Size

Total Lines	18
Code Lines	8

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	18
rs	9.4285
c	0
b	0
f	0
cc	3
eloc	8
nc	3
nop	2

<?php

namespace Ptypes;

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

class BinaryTree
{
	public const IN_ORDER = 0;
	public const PRE_ORDER = 1;
	public const POST_ORDER = 2;
	public const LEVEL_ORDER = 3;
	
	public $root;
	
	public function __construct(&$root=null)
	{
		$this->root = $root;
	}
	
	public function insert($node) //$node is a treenode
	{
		$this->validate_parameter($node);
		
		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);
		}
		
		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 is_complete()
	{
		//TODO
	}
	
	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));
		}
	}
}

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

HOWZ1T / Ptypes

Push — development ( 49dbbd...6c43d4 )

BinaryTree::compare() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like