KDTree::deletePoint() - Code Metrics - Inspection of "reverse null value" - f1r3starter/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( a0aac2...7c8bac )

by Andrii

created 2020-01-28 20:10 UTC

KDTree::deletePoint() A

↳ Parent: KDTree

Complexity

Conditions	6
Paths	6

Size

Total Lines	23
Code Lines	15

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	6
eloc	15
nc	6
nop	3
dl	0
loc	23
rs	9.2222
c	0
b	0
f	0

<?php

declare(strict_types=1);

namespace KDTree\Structure;

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

final class KDTree implements KDTreeInterface
{
    /**
     * @var NodeInterface|null
     */
    private $root;

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

    /**
     * @var int
     */
    private $size = 0;

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

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

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

    /**
     * @param PointInterface $point
     *
     * @return KDTreeInterface
     * @throws PointAlreadyExists|InvalidPointProvided
     */
    public function put(PointInterface $point): KDTreeInterface
    {
        $this->root = $this->insertNode($this->root, $point, 0);
        ++$this->size;

        return $this;
    }

    /**
     * @inheritDoc
     */
    public function contains(PointInterface $point): bool
    {
        return $this->findPoint($point, $this->root, 0);
    }

    /**
     * @return PointsListInterface<PointInterface>
     * @throws InvalidDimensionsCount
     */
    public function points(): PointsListInterface
    {
        return $this->getAllPoints($this->root, new PointsList($this->dimensions));
    }

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

        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
     * @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
     */
    private 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;
        $point = $this->findMin($nextNode, $cuttingDimension, $nextDimension);

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

        $node->setPoint($point);
        $node->setRight($this->deletePoint($point, $nextNode, $nextDimension));
    }

    /**
     * @param PointInterface $point
     * @param NodeInterface|null $node
     * @param int $cuttingDimension
     *
     * @return bool
     */
    private function findPoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): bool
    {
        if (null === $node) {
            return false;
        }

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

        if ($node->getPoint()->equals($point)) {
            return true;
        }

        if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
            return $this->findPoint($point, $node->getLeft(), $nextDimension);
        }

        return $this->findPoint($point, $node->getRight(), $nextDimension);
    }

    /**
     * @param NodeInterface|null                  $node
     * @param PointsListInterface<PointInterface> $pointsList
     *
     * @return PointsListInterface<PointInterface>
     */
    private function getAllPoints(?NodeInterface $node, PointsListInterface $pointsList): PointsListInterface
    {
        if (null === $node) {
            return $pointsList;
        }

        $pointsList->addPoint($node->getPoint());

        if (null !== $node->getLeft()) {
            $this->getAllPoints($node->getLeft(), $pointsList);
        }

        if (null !== $node->getRight()) {
            $this->getAllPoints($node->getRight(), $pointsList);
        }

        return $pointsList;
    }
}


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

f1r3starter / kdtree

Push — master ( a0aac2...7c8bac )

KDTree::deletePoint() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like