AVLTree::recomputeHeight() - Code Metrics - Inspection of "remove method and helper methods. Also tests for i..." - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 6cf12e...43b9d1 )

by Siro Díaz

created 2017-06-29 10:37 UTC

AVLTree::recomputeHeight() A

↳ Parent: AVLTree

Complexity

Conditions	2
Paths	2

Size

Total Lines	6
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Importance

Changes

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

<?php
/**
 * DataStructures for PHP
 *
 * @link      https://github.com/SiroDiaz/DataStructures
 * @copyright Copyright (c) 2017 Siro Díaz Palazón
 * @license   https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
 */
namespace DataStructures\Trees;

use DataStructures\Trees\BinaryTreeAbstract;
use DataStructures\Trees\Nodes\AVLNode;

/**
 * AVLTree
 *
 * This class is an implementation of a AVL tree. It has as main feature that access,
 * insertion and deletion is O(log n). This is like a BST but it has a slightly difference
 * in nodes: contains a height attribute, used to detect when is needed to rebalance the
 * tree to keep the O(log n).
 *
 * @author Siro Diaz Palazon <[email protected]>
 */
class AVLTree extends BinaryTreeAbstract {
    
    /**
     * Creates a AVLNode.
     *
     * @param int|string $key the key used to store.
     * @param mixed $data the data.
     * @param DataStructures\Trees\Nodes\AVLNode|null $parent the parent node.
     * @param DataStructures\Trees\Nodes\AVLNode|null $left the left child node.
     * @param DataStructures\Trees\Nodes\AVLNode|null $right the right child node.
     *
     * @return DataStructures\Trees\Nodes\AVLNode the new node created.
     */
    public function createNode($key, $data, $parent = null, $left = null, $right = null) {
        return new AVLNode($key, $data, $parent, $left, $right);
    }

    /**
     * Does a right rotation.
     * 
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function rightRotation(AVLNode &$node) {

        $temp = &$node->left;
        $temp->parent = &$node->parent;

        $node->left = &$temp->right;
        if ($node->left !== null) {
            $node->left->parent = &$snode;

        }

        $temp->right = &$node;
        $node->parent = &$temp;

        // temp took over node's place so now its parent should point to temp
        if ($temp->parent !== null) {
            if ($node === $temp->parent->left) {
                $temp->parent->left = &$temp;
            } else {
                $temp->parent->right = &$temp;
            }
        } else {
            $this->root = &$temp;
        }
        
        return $temp;
    }

    /**
     * Does a right rotation.
     *
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function leftRotation(AVLNode &$node) {


        $temp = &$node->right;
        $temp->parent = &$node->parent;

        $node->right = &$temp->left;

        if ($node->right !== null) {
            $node->right->parent = &$node;
        }

        $temp->left = &$node;
        $node->parent = &$temp;

        // temp took over node's place so now its parent should point to temp
        if ($temp->parent !== null) {
            if ($node == $temp->parent->left) {
                $temp->parent->left = &$temp;
            } else {
                $temp->parent->right = &$temp;
            }
        } else {
            $this->root = &$temp;
        }
        
        return $temp;
    }

    /**
     * Double right rotation does first a left rotation of right child node
     * that detects the imbalance and finally does a right rotation
     * in the subtree root that detects the imbalance.
     * Case Right-Left.
     *
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function doubleRightRotation(AVLNode &$node) {
        $this->leftRotation($node->left);
        return $this->rightRotation($node);
    }

    /**
     * Double left rotation does first a right rotation of left child node
     * that detects the imbalance and finally does a left rotation
     * in the subtree root that detects the imbalance.
     * Case Left-Right.
     *
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function doubleLeftRotation(AVLNode &$node) {
        $this->rightRotation($node->right);
        return $this->leftRotation($node);
    }

    /**
     * {@inheritDoc}
     */
    public function put($key, $data, $update = false) {
        $nodeInserted = parent::put($key, $data, $update);
        $this->rebalance($nodeInserted);

        return $nodeInserted;
    }

    /**
     * {@inheritDoc}
     */
    public function delete($key) {
        $nodeDelete = $this->search($key);
        if($nodeDelete !== null) {
            $successorNode = parent::delete($key);
            if($successorNode !== null) {
                $minimumNode = ($successorNode->right !== null) ?
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                    $this->getMinNode($successorNode->right) : $successorNode;
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                
                $this->recomputeHeight($minimumNode);
                $this->rebalance($minimumNode);
            } else {
                $this->recomputeHeight($nodeDelete->parent);
                $this->rebalance($nodeDelete->parent);
            }

            return $successorNode;
        }
        
        return null;
    }

    /**
     *
     */
    private function rebalance(&$node) {
        while($node !== null) {
            $parent = &$node->parent;

            $leftHeight = ($node->left === null) ? 0 : $node->left->height;
            $rightHeight = ($node->right === null) ? 0 : $node->right->height;
            $nodeBalance = $rightHeight - $leftHeight;

            if($nodeBalance >= 2) {
                if($node->right->right !== null) {
                    $this->leftRotation($node);
                    return;
                } else {
                    $this->doubleLeftRotation($node);
                    return;
                }
            } else if($nodeBalance <= -2) {
                if($node->left->left !== null) {
                    $this->rightRotation($node);
                    return;
                } else {
                    $this->doubleRightRotation($node);
                    return;
                }
            } else {
                $this->adjustHeight($node);
            }

            $node = &$parent;
        }
    }

    private function recomputeHeight($node) {
        while($node !== null) {
            $node->height = $this->maxHeight($node->left, $node->right) + 1;
            $node = &$node->parent;
        }
    }

    private function maxHeight($node1, $node2) {
        if($node1 !== null && $node2 !== null) {
            return $node1->height > $node2->height ? $node1->height : $node2->height;
        } else if($node1 === null) {
            return $node2 !== null ? $node2->height : 0;
        } else if($node2 === null) {
            return $node1 !== null ? $node1->height : 0;
        }

        return 0;
    }

    /**
     *
     */
    private function adjustHeight(&$node) {
        $leftHeight = ($node->left === null) ? 0 : $node->left->height;
        $rightHeight = ($node->right === null) ? 0 : $node->right->height;
        
        $node->height = 1 + max($leftHeight, $rightHeight);
    }
}

Push — master ( 6cf12e...43b9d1 )

AVLTree::recomputeHeight() A

Complexity

Size

Duplication

Importance

Available Fixes

Available Fixes

1		<?php
2		/**
3		* DataStructures for PHP
4		*
5		* @link https://github.com/SiroDiaz/DataStructures
6		* @copyright Copyright (c) 2017 Siro Díaz Palazón
7		* @license https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
8		*/
9		namespace DataStructures\Trees;
10
11		use DataStructures\Trees\BinaryTreeAbstract;
12		use DataStructures\Trees\Nodes\AVLNode;
13
14		/**
15		* AVLTree
16		*
17		* This class is an implementation of a AVL tree. It has as main feature that access,
18		* insertion and deletion is O(log n). This is like a BST but it has a slightly difference
19		* in nodes: contains a height attribute, used to detect when is needed to rebalance the
20		* tree to keep the O(log n).
21		*
22		* @author Siro Diaz Palazon <[email protected]>
23		*/
24		class AVLTree extends BinaryTreeAbstract {
25
26		/**
27		* Creates a AVLNode.
28		*
29		* @param int\|string $key the key used to store.
30		* @param mixed $data the data.
31		* @param DataStructures\Trees\Nodes\AVLNode\|null $parent the parent node.
32		* @param DataStructures\Trees\Nodes\AVLNode\|null $left the left child node.
33		* @param DataStructures\Trees\Nodes\AVLNode\|null $right the right child node.
34		*
35		* @return DataStructures\Trees\Nodes\AVLNode the new node created.
36		*/
37		public function createNode($key, $data, $parent = null, $left = null, $right = null) {
38		return new AVLNode($key, $data, $parent, $left, $right);
39		}
40
41		/**
42		* Does a right rotation.
43		*
44		* @param DataStructures\Trees\Nodes\AVLNode $node The node to be
45		* rotated.
46		* @return DataStructures\Trees\Nodes\AVLNode
47		*/
48	View Code Duplication	private function rightRotation(AVLNode &$node) {
		0 ignored issues – show Duplication introduced 2017-06-11 05:48 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...
49		$temp = &$node->left;
50		$temp->parent = &$node->parent;
51
52		$node->left = &$temp->right;
53		if ($node->left !== null) {
54		$node->left->parent = &$snode;
		0 ignored issues – show Bug introduced 2017-06-27 23:28 UTC by Report Bug Copy Issue Report The variable `$snode` does not exist. Did you forget to declare it? This check marks access to variables or properties that have not been declared yet. While PHP has no explicit notion of declaring a variable, accessing it before a value is assigned to it is most likely a bug. Loading history...
55		}
56
57		$temp->right = &$node;
58		$node->parent = &$temp;
59
60		// temp took over node's place so now its parent should point to temp
61		if ($temp->parent !== null) {
62		if ($node === $temp->parent->left) {
63		$temp->parent->left = &$temp;
64		} else {
65		$temp->parent->right = &$temp;
66		}
67		} else {
68		$this->root = &$temp;
69		}
70
71		return $temp;
72		}
73
74		/**
75		* Does a right rotation.
76		*
77		* @param DataStructures\Trees\Nodes\AVLNode $node The node to be
78		* rotated.
79		* @return DataStructures\Trees\Nodes\AVLNode
80		*/
81	View Code Duplication	private function leftRotation(AVLNode &$node) {
		0 ignored issues – show Duplication introduced 2017-06-11 05:48 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...
82
83		$temp = &$node->right;
84		$temp->parent = &$node->parent;
85
86		$node->right = &$temp->left;
87
88		if ($node->right !== null) {
89		$node->right->parent = &$node;
90		}
91
92		$temp->left = &$node;
93		$node->parent = &$temp;
94
95		// temp took over node's place so now its parent should point to temp
96		if ($temp->parent !== null) {
97		if ($node == $temp->parent->left) {
98		$temp->parent->left = &$temp;
99		} else {
100		$temp->parent->right = &$temp;
101		}
102		} else {
103		$this->root = &$temp;
104		}
105
106		return $temp;
107		}
108
109		/**
110		* Double right rotation does first a left rotation of right child node
111		* that detects the imbalance and finally does a right rotation
112		* in the subtree root that detects the imbalance.
113		* Case Right-Left.
114		*
115		* @param DataStructures\Trees\Nodes\AVLNode $node The node to be
116		* rotated.
117		* @return DataStructures\Trees\Nodes\AVLNode
118		*/
119		private function doubleRightRotation(AVLNode &$node) {
120		$this->leftRotation($node->left);
121		return $this->rightRotation($node);
122		}
123
124		/**
125		* Double left rotation does first a right rotation of left child node
126		* that detects the imbalance and finally does a left rotation
127		* in the subtree root that detects the imbalance.
128		* Case Left-Right.
129		*
130		* @param DataStructures\Trees\Nodes\AVLNode $node The node to be
131		* rotated.
132		* @return DataStructures\Trees\Nodes\AVLNode
133		*/
134		private function doubleLeftRotation(AVLNode &$node) {
135		$this->rightRotation($node->right);
136		return $this->leftRotation($node);
137		}
138
139		/**
140		* {@inheritDoc}
141		*/
142		public function put($key, $data, $update = false) {
143		$nodeInserted = parent::put($key, $data, $update);
144		$this->rebalance($nodeInserted);
145
146		return $nodeInserted;
147		}
148
149		/**
150		* {@inheritDoc}
151		*/
152		public function delete($key) {
153		$nodeDelete = $this->search($key);
154		if($nodeDelete !== null) {
155		$successorNode = parent::delete($key);
156		if($successorNode !== null) {
157		$minimumNode = ($successorNode->right !== null) ?
		0 ignored issues – show Bug introduced 2017-06-29 10:39 UTC by Report Bug Copy Issue Report Accessing `right` on the interface `DataStructures\Trees\Int...ces\BinaryNodeInterface` suggest that you code against a concrete implementation. How about adding an `instanceof` check? If you access a property on an interface, you most likely code against a concrete implementation of the interface. Available Fixes Adding an additional type check: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeInterface $object) { if ($object instanceof SomeClass) { $a = $object->a; } } Changing the type hint: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeClass $object) { $a = $object->a; } Loading history...
158		$this->getMinNode($successorNode->right) : $successorNode;
		0 ignored issues – show Bug introduced 2017-06-29 10:39 UTC by Report Bug Copy Issue Report The method `getMinNode()` cannot be called from this context as it is declared private in class `DataStructures\Trees\BinaryTreeAbstract`. This check looks for access to methods that are not accessible from the current context. If you need to make a method accessible to another context you can raise its visibility level in the defining class. Loading history... Bug introduced 2017-06-29 10:39 UTC by Report Bug Copy Issue Report Accessing `right` on the interface `DataStructures\Trees\Int...ces\BinaryNodeInterface` suggest that you code against a concrete implementation. How about adding an `instanceof` check? If you access a property on an interface, you most likely code against a concrete implementation of the interface. Available Fixes Adding an additional type check: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeInterface $object) { if ($object instanceof SomeClass) { $a = $object->a; } } Changing the type hint: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeClass $object) { $a = $object->a; } Loading history...
159
160		$this->recomputeHeight($minimumNode);
161		$this->rebalance($minimumNode);
162		} else {
163		$this->recomputeHeight($nodeDelete->parent);
164		$this->rebalance($nodeDelete->parent);
165		}
166
167		return $successorNode;
168		}
169
170		return null;
171		}
172
173		/**
174		*
175		*/
176		private function rebalance(&$node) {
177		while($node !== null) {
178		$parent = &$node->parent;
179
180		$leftHeight = ($node->left === null) ? 0 : $node->left->height;
181		$rightHeight = ($node->right === null) ? 0 : $node->right->height;
182		$nodeBalance = $rightHeight - $leftHeight;
183
184		if($nodeBalance >= 2) {
185		if($node->right->right !== null) {
186		$this->leftRotation($node);
187		return;
188		} else {
189		$this->doubleLeftRotation($node);
190		return;
191		}
192		} else if($nodeBalance <= -2) {
193		if($node->left->left !== null) {
194		$this->rightRotation($node);
195		return;
196		} else {
197		$this->doubleRightRotation($node);
198		return;
199		}
200		} else {
201		$this->adjustHeight($node);
202		}
203
204		$node = &$parent;
205		}
206		}
207
208		private function recomputeHeight($node) {
209		while($node !== null) {
210		$node->height = $this->maxHeight($node->left, $node->right) + 1;
211		$node = &$node->parent;
212		}
213		}
214
215		private function maxHeight($node1, $node2) {
216		if($node1 !== null && $node2 !== null) {
217		return $node1->height > $node2->height ? $node1->height : $node2->height;
218		} else if($node1 === null) {
219		return $node2 !== null ? $node2->height : 0;
220		} else if($node2 === null) {
221		return $node1 !== null ? $node1->height : 0;
222		}
223
224		return 0;
225		}
226
227		/**
228		*
229		*/
230		private function adjustHeight(&$node) {
231		$leftHeight = ($node->left === null) ? 0 : $node->left->height;
232		$rightHeight = ($node->right === null) ? 0 : $node->right->height;
233
234		$node->height = 1 + max($leftHeight, $rightHeight);
235		}
236		}

SiroDiaz / DataStructures

Push — master ( 6cf12e...43b9d1 )

AVLTree::recomputeHeight() A

Complexity

Size

Duplication

Importance

Available Fixes

Available Fixes

Duplication Side-by-Side

Filter issues like