BinaryTreeAbstract::getMaxNode() - Code Metrics - Inspection of "Big refactor of binary trees" - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( b592b0...7a2d4e )

by Siro Díaz

created 2017-06-09 19:44 UTC

BinaryTreeAbstract::getMaxNode() A

↳ Parent: BinaryTreeAbstract

Complexity

Conditions	3
Paths	3

Size

Total Lines	11
Code Lines	6

Duplication

Lines	11
Ratio	100 %

Importance

Changes

Metric	Value
c	0
b	0
f	0
dl	11
loc	11
rs	9.4285
cc	3
eloc	6
nc	3
nop	1

<?php

namespace DataStructures\Trees;

use DataStructures\Trees\Interfaces\TreeInterface;
use DataStructures\Trees\Interfaces\BinaryNodeInterface;

abstract class BinaryTreeAbstract implements TreeInterface {
    protected $root;
    protected $size;

    /**
     * Checks if the tree is empty.
     *
     * @return boolean true if is empty, else false.
     */
    public function empty() {
        return $this->root === null;
    }

    /**
     * Returns the tree size.
     *
     * @return int the length
     */
    public function size() {
        return $this->size;
    }

    public function put($key, $data){}
    public function putOrUpdate($key, $data){}

    /**
     * Retrieve the data stored in the tree.
     *
     * @param int|string $key the key to identify the data.
     * @return mixed
     */
    public function get($key){
        if($this->root === null) {
            return null;
        }

        $node = $this->root;
        while($node !== null) {
            if($key < $node->key) {
                $node = $node->left;
            } else if($key > $node->key) {
                $node = $node->right;
            } else {
                return $node->data;
            }
        }

        return null;
    }

    /**
     * Returns the root node.
     *
     * @return DataStructures\Trees\Nodes\BSTNode|null the root node.
     */
    public function getRoot(){
        return $this->root;
    }

    /**
     * Looks for the node with the given key.
     *
     * @param int|string $key the key used to look for.
     * @return bool true if was found.
     */
    public function exists($key){
        // $this->_exists($this->root, $key); for recursive search

        if($this->root === null) {
            return false;
        }

        if($this->root->key === $key) {
            return true;
        } else {
            $node = $this->root;
            while($node !== null) {
                if($key < $node->key) {
                    $node = $node->left;
                } else if($key > $node->key) {
                    $node = $node->right;
                } else {
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * Method that retrieves true if found a node with the specified key.
     * It's the recursive version of exists method and it's used internally
     * for traverse through a root node.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null $node the root node.
     * @param int|string $key the key used to look for.
     * @return bool true if exists a node with that key.
     */
    private function _exists($node, $key) : bool {

        if($node === null) {
            return false;
        }

        if($node->key === $key) {
            return true;
        } else if($key < $node->key) {
            return $this->_exists($node->left, $key);
        } else if($key > $node->key) {
            return $this->_exists($node->right, $key);
        }
    }

    public function floor($key){}
    public function ceil($key){}

    /**
     * Gets the node with the minimum key. The most left and more bottom.
     * 
     * @return DataStructures\Trees\Nodes\BSTNode|null the minum node or
     *  null if the tree is empty.
     */
    public function min() {
        if($this->root === null) {
            return null;
        }

        if($this->root->left === null) {
            return $this->root;
class Author {
    private $name;

    public function __construct($name) {
        $this->name = $name;
    }

    public function getName() {
        return $this->name;
    }
}

abstract class Post {
    public function getAuthor() {
        return 'Johannes';
    }
}

class BlogPost extends Post {
    public function getAuthor() {
        return new Author('Johannes');
    }
}

class ForumPost extends Post { /* ... */ }

function my_function(Post $post) {
    echo strtoupper($post->getAuthor());
}
        }

        $current = $this->root;
        while($current->left !== null) {
            $current = $current->left;
        }

        return $current;
    }

    /**
     * Gets the node with the maximum key. The most right and more bottom.
     * 
     * @return DataStructures\Trees\Nodes\BSTNode|null the maximum node or
     *  null if the tree is empty.
     */
    public function max() {
        if($this->root === null) {
            return null;
        }

        if($this->root->right === null) {
            return $this->root;
class Author {
    private $name;

    public function __construct($name) {
        $this->name = $name;
    }

    public function getName() {
        return $this->name;
    }
}

abstract class Post {
    public function getAuthor() {
        return 'Johannes';
    }
}

class BlogPost extends Post {
    public function getAuthor() {
        return new Author('Johannes');
    }
}

class ForumPost extends Post { /* ... */ }

function my_function(Post $post) {
    echo strtoupper($post->getAuthor());
}
        }

        $node = $this->root;
        while($node->right !== null) {
            $node = $node->right;
        }

        return $node;
    }

    /**
     * Returns the minimum node from a given node in position X.
     *
     * @param DataStructures\Trees\Nodes\BSTNode $node the start point.
     * @return DataStructures\Trees\Nodes\BSTNode|null the minimum node.
     */
    private function getMinNode(BinaryNodeInterface $node = null) {

        if($node === null) {
            return null;
        }

        while($node->left !== null) {
            $node = $node->left;
        }

        return $node;
    }

    /**
     * Returns the maximum node from a given node in position X.
     *
     * @param DataStructures\Trees\Nodes\BSTNode $node the start point.
     * @return DataStructures\Trees\Nodes\BSTNode|null the maximum node.
     */
    private function getMaxNode(BinaryNodeInterface $node = null) {

        if($node === null) {
            return null;
        }
        
        while($node->right !== null) {
            $node = $node->right;
        }

        return $node;
    }
    
    /**
     * Deletes the node with the minimum key and returns it. The most left and more bottom.
     * 
     * @param DataStructures\Trees\Nodes\BSTNode|null if null takes the root.
     * @return DataStructures\Trees\Nodes\BSTNode|null the minimum node or
     *  null if the tree is empty.
     */
    public function deleteMin(BinaryNodeInterface $node = null) {

        $node = $this->getMinNode($node ?? $this->root);
        if($node !== null) {
            $this->_delete($node);
        }
        
        return $node;
    }
    
    /**
     * Deletes the node with the maximum key and returns it. The most right and more bottom.
     * 
     * @param DataStructures\Trees\Nodes\BSTNode|null if null takes the root.
     * @return DataStructures\Trees\Nodes\BSTNode|null the maximum node or
     *  null if the tree is empty.
     */
    public function deleteMax(BinaryNodeInterface $node = null) {

        $node = $this->getMaxNode($node ?? $this->root);
        if($node !== null) {
            $this->_delete($node);
        }

        return $node;
    }

    /**
     * Deletes the selected node if is not null and returns the node
     * that replaces the deleted node. Also decrease the size of tree.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null The node to be deleted.
     * @return the node that replaces the deleted.
     */
    protected abstract function _delete(BinaryNodeInterface &$node);


    /**
     * Replaces the node n to remove a new one k and links k with the parent
     * of n.
     *
     * @param DataStructures\Trees\Nodes\BSTNode $nodeToReplace the node to remove.
     * @param DataStructures\Trees\Nodes\BSTNode|null $newNode the newNode
     *  to link with the $nodeToReplace parent.
     * @return DataStructures\Trees\Nodes\BSTNode the new linked node.
     */
    protected function replace(&$nodeToReplace, &$newNode) {
        if($nodeToReplace->parent === null) {
            $this->root = &$newNode;
        } else if($nodeToReplace === $nodeToReplace->parent->left) {
            $nodeToReplace->parent->left = &$newNode;
        } else if($nodeToReplace === $nodeToReplace->parent->right) {
            $nodeToReplace->parent->right = &$newNode;
        }

        if($newNode !== null) {
            $newNode->parent = &$nodeToReplace->parent;
        }

        return $newNode;
    }

    public function delete($key){}

    /**
     * Retrieves the node with the specified key.
     *
     * @param int|string $key the key used to store.
     * @return DataStructures\Trees\Nodes\BSTNode|null the node or null.
     */
    public function search($key) {
        if($this->root === null) {
            return null;
        }

        if($this->root->key === $key) {
            return $this->root;

        } else {
            $node = $this->root;
            while($node !== null) {
                if($key < $node->key) {
                    $node = $node->left;
                } else if($key > $node->key) {
                    $node = $node->right;
                } else {
                    return $node;
                }
            }
        }

        return null;
    }
    
    /**
     * Returns true if is leaf the node.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null $node default to null.
     * @return true if is leaf the node, is not null and their subtrees has no
     *  pointers to successors.
     */
    public function isLeaf($node) { // BinaryTreeNode
        return ($node !== null && $node->left === null && $node->right === null);
    }

    /**
     * Checks if a node is root. New nodes that does not point to any other node
     * also are called a root node.
     *
     * @param DataStructures\Trees\Nodes\BSTNode|null $node default to null.
     * @return true if is root the node, is not null and their subtrees has no
     *  pointers to successors.
     */
    public function isRoot($node) {
        return $node !== null && $node->parent === null;
    }

    /**
     * Binds to count() method. This is equal to make $this->tree->size().
     *
     * @return integer the tree size. 0 if it is empty.
     */
    public function count() {
        return $this->size;
    }
}

1		<?php
2
3		namespace DataStructures\Trees;
4
5		use DataStructures\Trees\Interfaces\TreeInterface;
6		use DataStructures\Trees\Interfaces\BinaryNodeInterface;
7
8		abstract class BinaryTreeAbstract implements TreeInterface {
9		protected $root;
10		protected $size;
11
12		/**
13		* Checks if the tree is empty.
14		*
15		* @return boolean true if is empty, else false.
16		*/
17		public function empty() {
18		return $this->root === null;
19		}
20
21		/**
22		* Returns the tree size.
23		*
24		* @return int the length
25		*/
26		public function size() {
27		return $this->size;
28		}
29
30		public function put($key, $data){}
31		public function putOrUpdate($key, $data){}
32
33		/**
34		* Retrieve the data stored in the tree.
35		*
36		* @param int\|string $key the key to identify the data.
37		* @return mixed
38		*/
39		public function get($key){
40		if($this->root === null) {
41		return null;
42		}
43
44		$node = $this->root;
45		while($node !== null) {
46		if($key < $node->key) {
47		$node = $node->left;
48		} else if($key > $node->key) {
49		$node = $node->right;
50		} else {
51		return $node->data;
52		}
53		}
54
55		return null;
56		}
57
58		/**
59		* Returns the root node.
60		*
61		* @return DataStructures\Trees\Nodes\BSTNode\|null the root node.
62		*/
63		public function getRoot(){
64		return $this->root;
65		}
66
67		/**
68		* Looks for the node with the given key.
69		*
70		* @param int\|string $key the key used to look for.
71		* @return bool true if was found.
72		*/
73		public function exists($key){
74		// $this->_exists($this->root, $key); for recursive search
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report `53%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
75		if($this->root === null) {
76		return false;
77		}
78
79		if($this->root->key === $key) {
80		return true;
81		} else {
82		$node = $this->root;
83		while($node !== null) {
84		if($key < $node->key) {
85		$node = $node->left;
86		} else if($key > $node->key) {
87		$node = $node->right;
88		} else {
89		return true;
90		}
91		}
92		}
93
94		return false;
95		}
96
97		/**
98		* Method that retrieves true if found a node with the specified key.
99		* It's the recursive version of exists method and it's used internally
100		* for traverse through a root node.
101		*
102		* @param DataStructures\Trees\Nodes\BSTNode\|null $node the root node.
103		* @param int\|string $key the key used to look for.
104		* @return bool true if exists a node with that key.
105		*/
106		private function _exists($node, $key) : bool {
		0 ignored issues – show Unused Code introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report This method is not used, and could be removed. Loading history...
107		if($node === null) {
108		return false;
109		}
110
111		if($node->key === $key) {
112		return true;
113		} else if($key < $node->key) {
114		return $this->_exists($node->left, $key);
115		} else if($key > $node->key) {
116		return $this->_exists($node->right, $key);
117		}
118		}
119
120		public function floor($key){}
121		public function ceil($key){}
122
123		/**
124		* Gets the node with the minimum key. The most left and more bottom.
125		*
126		* @return DataStructures\Trees\Nodes\BSTNode\|null the minum node or
127		* null if the tree is empty.
128		*/
129		public function min() {
130		if($this->root === null) {
131		return null;
132		}
133
134		if($this->root->left === null) {
135		return $this->root;
		0 ignored issues – show Bug Best Practice introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The return type of `return $this->root;` (`DataStructures\Trees\Nodes\BSTNode`) is incompatible with the return type documented by `DataStructures\Trees\BinaryTreeAbstract::min` of type `DataStructures\Trees\Dat...rees\Nodes\BSTNode\|null`. If you return a value from a function or method, it should be a sub-type of the type that is given by the parent type f.e. an interface, or abstract method. This is more formally defined by the Lizkov substitution principle, and guarantees that classes that depend on the parent type can use any instance of a child type interchangably. This principle also belongs to the SOLID principles for object oriented design. Let’s take a look at an example: class Author { private $name; public function __construct($name) { $this->name = $name; } public function getName() { return $this->name; } } abstract class Post { public function getAuthor() { return 'Johannes'; } } class BlogPost extends Post { public function getAuthor() { return new Author('Johannes'); } } class ForumPost extends Post { /* ... */ } function my_function(Post $post) { echo strtoupper($post->getAuthor()); } Our function `my_function` expects a `Post` object, and outputs the author of the post. The base class `Post` returns a simple string and outputting a simple string will work just fine. However, the child class `BlogPost` which is a sub-type of `Post` instead decided to return an `object`, and is therefore violating the SOLID principles. If a `BlogPost` were passed to `my_function`, PHP would not complain, but ultimately fail when executing the `strtoupper` call in its body. Loading history...
136		}
137
138		$current = $this->root;
139		while($current->left !== null) {
140		$current = $current->left;
141		}
142
143		return $current;
144		}
145
146		/**
147		* Gets the node with the maximum key. The most right and more bottom.
148		*
149		* @return DataStructures\Trees\Nodes\BSTNode\|null the maximum node or
150		* null if the tree is empty.
151		*/
152		public function max() {
153		if($this->root === null) {
154		return null;
155		}
156
157		if($this->root->right === null) {
158		return $this->root;
		0 ignored issues – show Bug Best Practice introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The return type of `return $this->root;` (`DataStructures\Trees\Nodes\BSTNode`) is incompatible with the return type documented by `DataStructures\Trees\BinaryTreeAbstract::max` of type `DataStructures\Trees\Dat...rees\Nodes\BSTNode\|null`. If you return a value from a function or method, it should be a sub-type of the type that is given by the parent type f.e. an interface, or abstract method. This is more formally defined by the Lizkov substitution principle, and guarantees that classes that depend on the parent type can use any instance of a child type interchangably. This principle also belongs to the SOLID principles for object oriented design. Let’s take a look at an example: class Author { private $name; public function __construct($name) { $this->name = $name; } public function getName() { return $this->name; } } abstract class Post { public function getAuthor() { return 'Johannes'; } } class BlogPost extends Post { public function getAuthor() { return new Author('Johannes'); } } class ForumPost extends Post { /* ... */ } function my_function(Post $post) { echo strtoupper($post->getAuthor()); } Our function `my_function` expects a `Post` object, and outputs the author of the post. The base class `Post` returns a simple string and outputting a simple string will work just fine. However, the child class `BlogPost` which is a sub-type of `Post` instead decided to return an `object`, and is therefore violating the SOLID principles. If a `BlogPost` were passed to `my_function`, PHP would not complain, but ultimately fail when executing the `strtoupper` call in its body. Loading history...
159		}
160
161		$node = $this->root;
162		while($node->right !== null) {
163		$node = $node->right;
164		}
165
166		return $node;
167		}
168
169		/**
170		* Returns the minimum node from a given node in position X.
171		*
172		* @param DataStructures\Trees\Nodes\BSTNode $node the start point.
173		* @return DataStructures\Trees\Nodes\BSTNode\|null the minimum node.
174		*/
175	View Code Duplication	private function getMinNode(BinaryNodeInterface $node = null) {
		0 ignored issues – show Duplication introduced 2017-06-09 19:46 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...
176		if($node === null) {
177		return null;
178		}
179
180		while($node->left !== null) {
181		$node = $node->left;
182		}
183
184		return $node;
185		}
186
187		/**
188		* Returns the maximum node from a given node in position X.
189		*
190		* @param DataStructures\Trees\Nodes\BSTNode $node the start point.
191		* @return DataStructures\Trees\Nodes\BSTNode\|null the maximum node.
192		*/
193	View Code Duplication	private function getMaxNode(BinaryNodeInterface $node = null) {
		0 ignored issues – show Duplication introduced 2017-06-09 19:46 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...
194		if($node === null) {
195		return null;
196		}
197
198		while($node->right !== null) {
199		$node = $node->right;
200		}
201
202		return $node;
203		}
204
205		/**
206		* Deletes the node with the minimum key and returns it. The most left and more bottom.
207		*
208		* @param DataStructures\Trees\Nodes\BSTNode\|null if null takes the root.
209		* @return DataStructures\Trees\Nodes\BSTNode\|null the minimum node or
210		* null if the tree is empty.
211		*/
212	View Code Duplication	public function deleteMin(BinaryNodeInterface $node = null) {
		0 ignored issues – show Duplication introduced 2017-06-09 19:46 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...
213		$node = $this->getMinNode($node ?? $this->root);
214		if($node !== null) {
215		$this->_delete($node);
216		}
217
218		return $node;
219		}
220
221		/**
222		* Deletes the node with the maximum key and returns it. The most right and more bottom.
223		*
224		* @param DataStructures\Trees\Nodes\BSTNode\|null if null takes the root.
225		* @return DataStructures\Trees\Nodes\BSTNode\|null the maximum node or
226		* null if the tree is empty.
227		*/
228	View Code Duplication	public function deleteMax(BinaryNodeInterface $node = null) {
		0 ignored issues – show Duplication introduced 2017-06-09 19:46 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...
229		$node = $this->getMaxNode($node ?? $this->root);
230		if($node !== null) {
231		$this->_delete($node);
232		}
233
234		return $node;
235		}
236
237		/**
238		* Deletes the selected node if is not null and returns the node
239		* that replaces the deleted node. Also decrease the size of tree.
240		*
241		* @param DataStructures\Trees\Nodes\BSTNode\|null The node to be deleted.
242		* @return the node that replaces the deleted.
243		*/
244		protected abstract function _delete(BinaryNodeInterface &$node);
		0 ignored issues – show Coding Style introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The abstract declaration must precede the visibility declaration Loading history...
245
246		/**
247		* Replaces the node n to remove a new one k and links k with the parent
248		* of n.
249		*
250		* @param DataStructures\Trees\Nodes\BSTNode $nodeToReplace the node to remove.
251		* @param DataStructures\Trees\Nodes\BSTNode\|null $newNode the newNode
252		* to link with the $nodeToReplace parent.
253		* @return DataStructures\Trees\Nodes\BSTNode the new linked node.
254		*/
255		protected function replace(&$nodeToReplace, &$newNode) {
256		if($nodeToReplace->parent === null) {
257		$this->root = &$newNode;
258		} else if($nodeToReplace === $nodeToReplace->parent->left) {
259		$nodeToReplace->parent->left = &$newNode;
260		} else if($nodeToReplace === $nodeToReplace->parent->right) {
261		$nodeToReplace->parent->right = &$newNode;
262		}
263
264		if($newNode !== null) {
265		$newNode->parent = &$nodeToReplace->parent;
266		}
267
268		return $newNode;
269		}
270
271		public function delete($key){}
272
273		/**
274		* Retrieves the node with the specified key.
275		*
276		* @param int\|string $key the key used to store.
277		* @return DataStructures\Trees\Nodes\BSTNode\|null the node or null.
278		*/
279		public function search($key) {
280		if($this->root === null) {
281		return null;
282		}
283
284		if($this->root->key === $key) {
285		return $this->root;
		0 ignored issues – show Bug Compatibility introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The expression `$this->root;` of type `DataStructures\Trees\Nod...res\Trees\Nodes\BSTNode` adds the type `DataStructures\Trees\Nodes\BSTNode` to the return on line 285 which is incompatible with the return type documented by `DataStructures\Trees\BinaryTreeAbstract::search` of type `DataStructures\Trees\Dat...rees\Nodes\BSTNode\|null`. Loading history...
286		} else {
287		$node = $this->root;
288		while($node !== null) {
289		if($key < $node->key) {
290		$node = $node->left;
291		} else if($key > $node->key) {
292		$node = $node->right;
293		} else {
294		return $node;
295		}
296		}
297		}
298
299		return null;
300		}
301
302		/**
303		* Returns true if is leaf the node.
304		*
305		* @param DataStructures\Trees\Nodes\BSTNode\|null $node default to null.
306		* @return true if is leaf the node, is not null and their subtrees has no
307		* pointers to successors.
308		*/
309		public function isLeaf($node) { // BinaryTreeNode
310		return ($node !== null && $node->left === null && $node->right === null);
311		}
312
313		/**
314		* Checks if a node is root. New nodes that does not point to any other node
315		* also are called a root node.
316		*
317		* @param DataStructures\Trees\Nodes\BSTNode\|null $node default to null.
318		* @return true if is root the node, is not null and their subtrees has no
319		* pointers to successors.
320		*/
321		public function isRoot($node) {
322		return $node !== null && $node->parent === null;
323		}
324
325		/**
326		* Binds to count() method. This is equal to make $this->tree->size().
327		*
328		* @return integer the tree size. 0 if it is empty.
329		*/
330		public function count() {
331		return $this->size;
332		}
333		}

SiroDiaz / DataStructures

Push — master ( b592b0...7a2d4e )

BinaryTreeAbstract::getMaxNode() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like