BinarySearchTree::_preorder() - Code Metrics - Inspection of "moved all traversal method to abstract class" - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 7af6a9...1c5b8d )

by Siro Díaz

created 2017-06-09 23:22 UTC

BinarySearchTree::_preorder() A

↳ Parent: Project

Complexity

Conditions	3
Paths	3

Size

Total Lines	10
Code Lines	7

Duplication

Lines	10
Ratio	100 %

Importance

Changes

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

<?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\Nodes\BSTNode;
use DataStructures\Trees\Interfaces\BinaryNodeInterface;
use DataStructures\Trees\BinaryTreeAbstract;

/**
 * BinarySearchTree
 * 
 * Represents a BST actions that can be realized. All the implementation
 * is in BinaryTreeAbstract class.
 * At the beginning root is null and it can grow up to a O(n) in search,
 * delete and insert (in worst case). In best cases it will be O(log n).
 *
 * @author Siro Diaz Palazon <[email protected]>
 */
class BinarySearchTree extends BinaryTreeAbstract {

    public function __construct() {
        $this->root = null;
        $this->size = 0;
    }

    /**
     * Inserts data in the correct position.
     *
     * @param integer|string $key the key used to store.
     * @param mixed $data the data to store.
     * @param bool $update if false the node isn't updated
     *  else if the key matches is updated.
     */
    public function put($key, $data, $update = false) {
        $newNode = new BSTNode($key, $data);
        
        if($this->root === null) {
            $this->root = &$newNode;
            $this->size++;
            return;
        }

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

        $newNode->parent = &$parentNode;
        if($key < $parentNode->key) {
            $parentNode->left = &$newNode;
        } else {
            $parentNode->right = &$newNode;
        }

        $this->size++;
    }
    
    /**
     * Creates a new node or updates it if already exists.
     *
     * @param int|string $key the key.
     * @param mixed $data the data to be stored. 
     */
    public function putOrUpdate($key, $data) {
        $this->put($key, $data, true);
    }

    /**
     * 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 delete($key) {
        $deleteNode = $this->search($key);
        if($deleteNode !== null) {
            $this->_delete($deleteNode);
            return $deleteNode;
        }

        return null;
    }

    /**
     * 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 function _delete(BinaryNodeInterface &$node) {
        if($node !== null) {
            $nodeToReturn = null;
            if($node->left === null) {
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                $nodeToReturn = $this->replace($node, $node->right);
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
            } else if($node->right === null) {
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                $nodeToReturn = $this->replace($node, $node->left);
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

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

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                if($successorNode->parent !== $node) {
                    $this->replace($successorNode, $successorNode->right);
                    $successorNode->right = &$node->right;
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                    $successorNode->right->parent = &$successorNode;
                }

                $this->replace($node, $successorNode);
                $successorNode->left = &$node->left;
                $successorNode->left->parent = &$successorNode;
                $nodeToReturn = &$successorNode;
            }

            $this->size--;
            return $nodeToReturn;
        }

        return null;
    }

    
}

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\Nodes\BSTNode;
12			use DataStructures\Trees\Interfaces\BinaryNodeInterface;
13			use DataStructures\Trees\BinaryTreeAbstract;
14
15			/**
16			* BinarySearchTree
17			*
18			* Represents a BST actions that can be realized. All the implementation
19			* is in BinaryTreeAbstract class.
20			* At the beginning root is null and it can grow up to a O(n) in search,
21			* delete and insert (in worst case). In best cases it will be O(log n).
22			*
23			* @author Siro Diaz Palazon <[email protected]>
24			*/
25			class BinarySearchTree extends BinaryTreeAbstract {
26
27			public function __construct() {
28			$this->root = null;
29			$this->size = 0;
30			}
31
32			/**
33			* Inserts data in the correct position.
34			*
35			* @param integer\|string $key the key used to store.
36			* @param mixed $data the data to store.
37			* @param bool $update if false the node isn't updated
38			* else if the key matches is updated.
39			*/
40			public function put($key, $data, $update = false) {
41			$newNode = new BSTNode($key, $data);
42
43			if($this->root === null) {
44			$this->root = &$newNode;
45			$this->size++;
46			return;
47			}
48
49			$parentNode = null;
50			$current = &$this->root;
51			while($current !== null) {
52			$parentNode = &$current;
53			if($key < $current->key) {
54			$current = &$current->left;
55			} else if($key > $current->key) {
56			$current = &$current->right;
57			} else {
58			if($update) {
59			$current->data = $data;
60			}
61			return;
62			}
63			}
64
65			$newNode->parent = &$parentNode;
66			if($key < $parentNode->key) {
67			$parentNode->left = &$newNode;
68			} else {
69			$parentNode->right = &$newNode;
70			}
71
72			$this->size++;
73			}
74
75			/**
76			* Creates a new node or updates it if already exists.
77			*
78			* @param int\|string $key the key.
79			* @param mixed $data the data to be stored.
80			*/
81			public function putOrUpdate($key, $data) {
82			$this->put($key, $data, true);
83			}
84
85			/**
86			* Deletes the node with the maximum key and returns it. The most right and more bottom.
87			*
88			* @param DataStructures\Trees\Nodes\BSTNode\|null if null takes the root.
89			* @return DataStructures\Trees\Nodes\BSTNode\|null the maximum node or
90			* null if the tree is empty.
91			*/
92			public function delete($key) {
93			$deleteNode = $this->search($key);
94			if($deleteNode !== null) {
95			$this->_delete($deleteNode);
96			return $deleteNode;
97			}
98
99			return null;
100			}
101
102			/**
103			* Deletes the selected node if is not null and returns the node
104			* that replaces the deleted node. Also decrease the size of tree.
105			*
106			* @param DataStructures\Trees\Nodes\BSTNode\|null The node to be deleted.
107			* @return the node that replaces the deleted.
108			*/
109			protected function _delete(BinaryNodeInterface &$node) {
110			if($node !== null) {
111			$nodeToReturn = null;
112			if($node->left === null) {
			0 ignored issues – show Bug introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report Accessing `left` 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...
113			$nodeToReturn = $this->replace($node, $node->right);
			0 ignored issues – show Bug introduced 2017-06-09 19:46 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... Documentation introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report `$node` is of type `object<DataStructures\Tr...es\BinaryNodeInterface>`, but the function expects a `object<DataStructures\Tr...es\Trees\Nodes\BSTNode>`. It seems like the type of the argument is not accepted by the function/method which you are calling. In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug. We suggest to add an explicit type cast like in the following example: function acceptsInteger($int) { } $x = '123'; // string "123" // Instead of acceptsInteger($x); // we recommend to use acceptsInteger((integer) $x); Loading history... Bug Compatibility introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The expression `$this->replace($node, $node->right);` of type `DataStructures\Trees\Dat...rees\Nodes\BSTNode\|null` adds the type `DataStructures\Trees\Dat...res\Trees\Nodes\BSTNode` to the return on line 131 which is incompatible with the return type declared by the abstract method `DataStructures\Trees\BinaryTreeAbstract::_delete` of type `DataStructures\Trees\the`. Loading history...
114			} else if($node->right === null) {
			0 ignored issues – show Bug introduced 2017-06-09 19:46 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...
115			$nodeToReturn = $this->replace($node, $node->left);
			0 ignored issues – show Bug introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report Accessing `left` 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... Documentation introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report `$node` is of type `object<DataStructures\Tr...es\BinaryNodeInterface>`, but the function expects a `object<DataStructures\Tr...es\Trees\Nodes\BSTNode>`. It seems like the type of the argument is not accepted by the function/method which you are calling. In some cases, in particular if PHP’s automatic type-juggling kicks in this might be fine. In other cases, however this might be a bug. We suggest to add an explicit type cast like in the following example: function acceptsInteger($int) { } $x = '123'; // string "123" // Instead of acceptsInteger($x); // we recommend to use acceptsInteger((integer) $x); Loading history... Bug Compatibility introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The expression `$this->replace($node, $node->left);` of type `DataStructures\Trees\Dat...rees\Nodes\BSTNode\|null` adds the type `DataStructures\Trees\Dat...res\Trees\Nodes\BSTNode` to the return on line 131 which is incompatible with the return type declared by the abstract method `DataStructures\Trees\BinaryTreeAbstract::_delete` of type `DataStructures\Trees\the`. Loading history...
116			} else {
117			$successorNode = $this->getMinNode($node->right);
			0 ignored issues – show Bug introduced 2017-06-09 19:46 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-09 19:46 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... Bug Compatibility introduced 2017-06-09 19:46 UTC by Report Bug Copy Issue Report The expression `$this->getMinNode($node->right);` of type `DataStructures\Trees\Dat...rees\Nodes\BSTNode\|null` adds the type `DataStructures\Trees\Dat...res\Trees\Nodes\BSTNode` to the return on line 131 which is incompatible with the return type declared by the abstract method `DataStructures\Trees\BinaryTreeAbstract::_delete` of type `DataStructures\Trees\the`. Loading history...
118			if($successorNode->parent !== $node) {
119			$this->replace($successorNode, $successorNode->right);
120			$successorNode->right = &$node->right;
			0 ignored issues – show Bug introduced 2017-06-09 19:46 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...
121			$successorNode->right->parent = &$successorNode;
122			}
123
124			$this->replace($node, $successorNode);
125			$successorNode->left = &$node->left;
126			$successorNode->left->parent = &$successorNode;
127			$nodeToReturn = &$successorNode;
128			}
129
130			$this->size--;
131			return $nodeToReturn;
132			}
133
134			return null;
135			}
136
137
138			}

SiroDiaz / DataStructures

Push — master ( 7af6a9...1c5b8d )

BinarySearchTree::_preorder() A

Complexity

Size

Duplication

Importance

Available Fixes

Available Fixes

Available Fixes

Available Fixes

Available Fixes

Available Fixes

Duplication Side-by-Side

Filter issues like