KDTree::delete() - Code Metrics - Inspection of "some refactoring" - f1r3starter/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 8ddf73...92c967 )

by Andrii

created 2019-12-21 05:12 UTC

KDTree::delete() A

↳ Parent: KDTree

Complexity

Conditions	1
Paths	1

Size

Total Lines	6
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

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

<?php

declare(strict_types=1);

namespace KDTree;

use KDTree\Exceptions\{InvalidDimensionsCount, PointAlreadyExists, PointNotFound};
use KDTree\Structure\{Node, PointsList};
use KDTree\Interfaces\{KDTreeInterface, NodeInterface, PointInterface, PointsListInterface};

class KDTree implements KDTreeInterface
{
    /**
     * @var PointsListInterface
     */
    private $points;

    /**
     * @var NodeInterface|null
     */
    private $root;

    /**
     * @var int
     */
    private $dimensions;

    /**
     * @param int $dimensions
     *
     * @throws InvalidDimensionsCount
     */
    public function __construct(int $dimensions)
    {
        if ($dimensions < 1) {
            throw new InvalidDimensionsCount();
        }
        $this->dimensions = $dimensions;
        $this->points = new PointsList($dimensions);
    }

    /**
     * @inheritDoc
     */
    public function isEmpty(): bool
    {
        return null === $this->root;
    }

    /**
     * @inheritDoc
     */
    public function size(): int
    {
        return $this->points->count();
    }

    /**
     * @param PointInterface $point
     *
     * @return KDTreeInterface
     * @throws Exceptions\InvalidPointProvided|PointAlreadyExists
     */
    public function put(PointInterface $point): KDTreeInterface
    {
        if ($this->points->pointExists($point)) {
            throw new PointAlreadyExists();
        }

        $this->root = $this->insertNode($this->root, $point, 0);
        $this->points->addPoint($point);

        return $this;
    }

    /**
     * @inheritDoc
     */
    public function contains(PointInterface $point): bool
    {
        return $this->points->pointExists($point);
    }

    /**
     * @inheritDoc
     */
    public function points(): PointsListInterface
    {
        return $this->points;
    }

    /**
     * @param PointInterface $point
     *
     * @return KDTreeInterface
     * @throws PointNotFound
     */
    public function delete(PointInterface $point): KDTreeInterface
    {
        $this->deletePoint($point, $this->root, 0);
        $this->points->removePoint($point);

        return $this;
    }

    /**
     * @inheritDoc
     */
    public function getDimensions(): int
    {
        return $this->dimensions;
    }

    /**
     * @return NodeInterface|null
     */
    public function getRoot(): ?NodeInterface
    {
        return $this->root;
    }

    /**
     * @param NodeInterface|null $node
     * @param PointInterface $point
     * @param int $cuttingDimension
     *
     * @return NodeInterface|null
     * @throws PointAlreadyExists
     */
    private function insertNode(?NodeInterface $node, PointInterface $point, int $cuttingDimension): ?NodeInterface
    {
        if (null === $node) {
            return new Node($point);
        }

        if ($node->getPoint()->equals($point)) {
            throw new PointAlreadyExists();
        }

        $nextDimension = ($cuttingDimension + 1) % $this->dimensions;

        if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
            $node->setLeft($this->insertNode($node->getLeft(), $point, $nextDimension));
        } else {
            $node->setRight($this->insertNode($node->getRight(), $point, $nextDimension));
        }

        return $node;
    }

    /**
     * @param NodeInterface|null $node
     * @param int $dimension
     * @param int $cuttingDimension
     *
     * @return PointInterface|null
     */
    public function findMin(?NodeInterface $node, int $dimension, int $cuttingDimension): ?PointInterface
    {
        if (null === $node) {
            return null;
        }

        $nextDimension = ($cuttingDimension + 1) % $this->dimensions;
        if ($cuttingDimension === $dimension) {
            if (null === $node->getLeft()) {
                return $node->getPoint();
            }

            return $this->findMin(
                $node->getLeft(),
                $dimension,
                $nextDimension
            );
        }

        $leftMin = $this->findMin($node->getLeft(), $dimension, $nextDimension);
        $rightMin = $this->findMin($node->getRight(), $dimension, $nextDimension);
        $current = $node->getPoint()->getDAxis($dimension);
        $minimums = [
            $this->getPointAxis($leftMin, $dimension)  => $leftMin,
            $this->getPointAxis($rightMin, $dimension) => $rightMin,
            $current                                   => $node->getPoint(),
        ];
        $minKey = min(
            array_keys(
                array_filter($minimums)
            )
        );

        return $minimums[$minKey];
    }

    /**
     * @param PointInterface|null $point
     * @param int $dimension
     *
     * @return float|null
     */
    private function getPointAxis(?PointInterface $point, int $dimension): ?float
    {
        return null === $point ? null : $point->getDAxis($dimension);
    }

    /**
     * @param PointInterface $point
     * @param NodeInterface|null $node
     * @param int $cuttingDimension
     *
     * @return NodeInterface|null
     * @throws PointNotFound
     */
    private function deletePoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): ?NodeInterface
    {
        if (null === $node) {
            throw new PointNotFound();
        }

        $nextDimension = ($cuttingDimension + 1) % $this->dimensions;

        if ($node->getPoint()->equals($point)) {
            if (null !== $node->getRight()) {
                $this->rebuildFoundNode($node, $node->getRight(), $cuttingDimension);
            } elseif (null !== $node->getLeft()) {
                $this->rebuildFoundNode($node, $node->getLeft(), $cuttingDimension);
            } else {
                $node = null;
            }
        } elseif ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
            $node->setLeft($this->deletePoint($point, $node->getLeft(), $nextDimension));
        } else {
            $node->setRight($this->deletePoint($point, $node->getRight(), $nextDimension));
        }

        return $node;
    }

    /**
     * @param NodeInterface $node
     * @param NodeInterface $nextNode
     * @param int $cuttingDimension
     *
     * @throws PointNotFound
     */
    private function rebuildFoundNode(NodeInterface $node, NodeInterface $nextNode, int $cuttingDimension): void
    {
        $nextDimension = ($cuttingDimension + 1) % $this->dimensions;
        $node->setPoint(
            $this->findMin($nextNode, $cuttingDimension, $nextDimension)
        );
        $node->setRight($this->deletePoint($node->getPoint(), $nextNode, $nextDimension));
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			namespace KDTree;
6
7			use KDTree\Exceptions\{InvalidDimensionsCount, PointAlreadyExists, PointNotFound};
8			use KDTree\Structure\{Node, PointsList};
9			use KDTree\Interfaces\{KDTreeInterface, NodeInterface, PointInterface, PointsListInterface};
10
11			class KDTree implements KDTreeInterface
12			{
13			/**
14			* @var PointsListInterface
15			*/
16			private $points;
17
18			/**
19			* @var NodeInterface\|null
20			*/
21			private $root;
22
23			/**
24			* @var int
25			*/
26			private $dimensions;
27
28			/**
29			* @param int $dimensions
30			*
31			* @throws InvalidDimensionsCount
32			*/
33			public function __construct(int $dimensions)
34			{
35			if ($dimensions < 1) {
36			throw new InvalidDimensionsCount();
37			}
38			$this->dimensions = $dimensions;
39			$this->points = new PointsList($dimensions);
40			}
41
42			/**
43			* @inheritDoc
44			*/
45			public function isEmpty(): bool
46			{
47			return null === $this->root;
48			}
49
50			/**
51			* @inheritDoc
52			*/
53			public function size(): int
54			{
55			return $this->points->count();
56			}
57
58			/**
59			* @param PointInterface $point
60			*
61			* @return KDTreeInterface
62			* @throws Exceptions\InvalidPointProvided\|PointAlreadyExists
63			*/
64			public function put(PointInterface $point): KDTreeInterface
65			{
66			if ($this->points->pointExists($point)) {
67			throw new PointAlreadyExists();
68			}
69
70			$this->root = $this->insertNode($this->root, $point, 0);
71			$this->points->addPoint($point);
72
73			return $this;
74			}
75
76			/**
77			* @inheritDoc
78			*/
79			public function contains(PointInterface $point): bool
80			{
81			return $this->points->pointExists($point);
82			}
83
84			/**
85			* @inheritDoc
86			*/
87			public function points(): PointsListInterface
88			{
89			return $this->points;
90			}
91
92			/**
93			* @param PointInterface $point
94			*
95			* @return KDTreeInterface
96			* @throws PointNotFound
97			*/
98			public function delete(PointInterface $point): KDTreeInterface
99			{
100			$this->deletePoint($point, $this->root, 0);
101			$this->points->removePoint($point);
102
103			return $this;
104			}
105
106			/**
107			* @inheritDoc
108			*/
109			public function getDimensions(): int
110			{
111			return $this->dimensions;
112			}
113
114			/**
115			* @return NodeInterface\|null
116			*/
117			public function getRoot(): ?NodeInterface
118			{
119			return $this->root;
120			}
121
122			/**
123			* @param NodeInterface\|null $node
124			* @param PointInterface $point
125			* @param int $cuttingDimension
126			*
127			* @return NodeInterface\|null
128			* @throws PointAlreadyExists
129			*/
130			private function insertNode(?NodeInterface $node, PointInterface $point, int $cuttingDimension): ?NodeInterface
131			{
132			if (null === $node) {
133			return new Node($point);
134			}
135
136			if ($node->getPoint()->equals($point)) {
137			throw new PointAlreadyExists();
138			}
139
140			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
141
142			if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
143			$node->setLeft($this->insertNode($node->getLeft(), $point, $nextDimension));
144			} else {
145			$node->setRight($this->insertNode($node->getRight(), $point, $nextDimension));
146			}
147
148			return $node;
149			}
150
151			/**
152			* @param NodeInterface\|null $node
153			* @param int $dimension
154			* @param int $cuttingDimension
155			*
156			* @return PointInterface\|null
157			*/
158			public function findMin(?NodeInterface $node, int $dimension, int $cuttingDimension): ?PointInterface
159			{
160			if (null === $node) {
161			return null;
162			}
163
164			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
165			if ($cuttingDimension === $dimension) {
166			if (null === $node->getLeft()) {
167			return $node->getPoint();
168			}
169
170			return $this->findMin(
171			$node->getLeft(),
172			$dimension,
173			$nextDimension
174			);
175			}
176
177			$leftMin = $this->findMin($node->getLeft(), $dimension, $nextDimension);
178			$rightMin = $this->findMin($node->getRight(), $dimension, $nextDimension);
179			$current = $node->getPoint()->getDAxis($dimension);
180			$minimums = [
181			$this->getPointAxis($leftMin, $dimension) => $leftMin,
182			$this->getPointAxis($rightMin, $dimension) => $rightMin,
183			$current => $node->getPoint(),
184			];
185			$minKey = min(
186			array_keys(
187			array_filter($minimums)
188			)
189			);
190
191			return $minimums[$minKey];
192			}
193
194			/**
195			* @param PointInterface\|null $point
196			* @param int $dimension
197			*
198			* @return float\|null
199			*/
200			private function getPointAxis(?PointInterface $point, int $dimension): ?float
201			{
202			return null === $point ? null : $point->getDAxis($dimension);
203			}
204
205			/**
206			* @param PointInterface $point
207			* @param NodeInterface\|null $node
208			* @param int $cuttingDimension
209			*
210			* @return NodeInterface\|null
211			* @throws PointNotFound
212			*/
213			private function deletePoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): ?NodeInterface
214			{
215			if (null === $node) {
216			throw new PointNotFound();
217			}
218
219			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
220
221			if ($node->getPoint()->equals($point)) {
222			if (null !== $node->getRight()) {
223			$this->rebuildFoundNode($node, $node->getRight(), $cuttingDimension);
224			} elseif (null !== $node->getLeft()) {
225			$this->rebuildFoundNode($node, $node->getLeft(), $cuttingDimension);
226			} else {
227			$node = null;
228			}
229			} elseif ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
230			$node->setLeft($this->deletePoint($point, $node->getLeft(), $nextDimension));
231			} else {
232			$node->setRight($this->deletePoint($point, $node->getRight(), $nextDimension));
233			}
234
235			return $node;
236			}
237
238			/**
239			* @param NodeInterface $node
240			* @param NodeInterface $nextNode
241			* @param int $cuttingDimension
242			*
243			* @throws PointNotFound
244			*/
245			private function rebuildFoundNode(NodeInterface $node, NodeInterface $nextNode, int $cuttingDimension): void
246			{
247			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
248			$node->setPoint(
249			$this->findMin($nextNode, $cuttingDimension, $nextDimension)
250			);
251			$node->setRight($this->deletePoint($node->getPoint(), $nextNode, $nextDimension));
252			}
253			}
254

f1r3starter / kdtree

Push — master ( 8ddf73...92c967 )

KDTree::delete() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like