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

Passed

Push — master ( c01a96...bfc690 )

by Andrii

created 2020-02-05 21:00 UTC

KDTree::chooseMin() A

↳ Parent: KDTree

Complexity

Conditions	3
Paths	3

Size

Total Lines	17
Code Lines	10

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

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

<?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
     */
    private function findMin(NodeInterface $node, int $dimension, int $cuttingDimension): PointInterface
    {
        $nextDimension = ($cuttingDimension + 1) % $this->dimensions;
        if ($cuttingDimension === $dimension) {
            if (null === $node->getLeft()) {
                return $node->getPoint();
            }

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

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

    /**
     * @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);
        $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;
    }

    /**
     * @param int $dimension
     * @param int $nextDimension
     * @param NodeInterface $currentNode
     * @param NodeInterface|null ...$nodes
     *
     * @return PointInterface
     */
    private function chooseMin(int $dimension, int $nextDimension, NodeInterface $currentNode, ?NodeInterface ... $nodes): PointInterface
    {
        $nodes = array_filter($nodes);

        $minAxis = $currentNode->getPoint()->getDAxis($dimension);
        $minPoint = $currentNode->getPoint();

        foreach ($nodes as $node) {
            $currentPoint = $this->findMin($node, $dimension, $nextDimension);
            $currentAxis = $this->getPointAxis($currentPoint, $dimension);
            if ($currentAxis < $minAxis) {
                $minPoint = $currentPoint;
                $minAxis = $currentAxis;
            }
        }

        return $minPoint;
    }
}


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
152			*/
153			private function findMin(NodeInterface $node, int $dimension, int $cuttingDimension): PointInterface
154			{
155			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
156			if ($cuttingDimension === $dimension) {
157			if (null === $node->getLeft()) {
158			return $node->getPoint();
159			}
160
161			return $this->findMin(
162			$node->getLeft(),
163			$dimension,
164			$nextDimension
165			);
166			}
167
168			return $this->chooseMin(
169			$dimension,
170			$nextDimension,
171			$node,
172			$node->getLeft(),
173			$node->getRight()
174			);
175			}
176
177			/**
178			* @param PointInterface\|null $point
179			* @param int $dimension
180			*
181			* @return float\|null
182			*/
183			private function getPointAxis(?PointInterface $point, int $dimension): ?float
184			{
185			return null === $point ? null : $point->getDAxis($dimension);
186			}
187
188			/**
189			* @param PointInterface $point
190			* @param NodeInterface\|null $node
191			* @param int $cuttingDimension
192			*
193			* @return NodeInterface\|null
194			* @throws PointNotFound
195			*/
196			private function deletePoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): ?NodeInterface
197			{
198			if (null === $node) {
199			throw new PointNotFound();
200			}
201
202			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
203
204			if ($node->getPoint()->equals($point)) {
205			if (null !== $node->getRight()) {
206			$this->rebuildFoundNode($node, $node->getRight(), $cuttingDimension);
207			} elseif (null !== $node->getLeft()) {
208			$this->rebuildFoundNode($node, $node->getLeft(), $cuttingDimension);
209			} else {
210			$node = null;
211			}
212			} elseif ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
213			$node->setLeft($this->deletePoint($point, $node->getLeft(), $nextDimension));
214			} else {
215			$node->setRight($this->deletePoint($point, $node->getRight(), $nextDimension));
216			}
217
218			return $node;
219			}
220
221			/**
222			* @param NodeInterface $node
223			* @param NodeInterface $nextNode
224			* @param int $cuttingDimension
225			*
226			* @throws PointNotFound
227			*/
228			private function rebuildFoundNode(NodeInterface $node, NodeInterface $nextNode, int $cuttingDimension): void
229			{
230			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
231			$point = $this->findMin($nextNode, $cuttingDimension, $nextDimension);
232			$node->setPoint($point);
233			$node->setRight($this->deletePoint($point, $nextNode, $nextDimension));
234			}
235
236			/**
237			* @param PointInterface $point
238			* @param NodeInterface\|null $node
239			* @param int $cuttingDimension
240			*
241			* @return bool
242			*/
243			private function findPoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): bool
244			{
245			if (null === $node) {
246			return false;
247			}
248
249			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
250
251			if ($node->getPoint()->equals($point)) {
252			return true;
253			}
254
255			if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
256			return $this->findPoint($point, $node->getLeft(), $nextDimension);
257			}
258
259			return $this->findPoint($point, $node->getRight(), $nextDimension);
260			}
261
262			/**
263			* @param NodeInterface\|null $node
264			* @param PointsListInterface<PointInterface> $pointsList
265			*
266			* @return PointsListInterface<PointInterface>
267			*/
268			private function getAllPoints(?NodeInterface $node, PointsListInterface $pointsList): PointsListInterface
269			{
270			if (null === $node) {
271			return $pointsList;
272			}
273
274			$pointsList->addPoint($node->getPoint());
275
276			if (null !== $node->getLeft()) {
277			$this->getAllPoints($node->getLeft(), $pointsList);
278			}
279
280			if (null !== $node->getRight()) {
281			$this->getAllPoints($node->getRight(), $pointsList);
282			}
283
284			return $pointsList;
285			}
286
287			/**
288			* @param int $dimension
289			* @param int $nextDimension
290			* @param NodeInterface $currentNode
291			* @param NodeInterface\|null ...$nodes
292			*
293			* @return PointInterface
294			*/
295			private function chooseMin(int $dimension, int $nextDimension, NodeInterface $currentNode, ?NodeInterface ... $nodes): PointInterface
296			{
297			$nodes = array_filter($nodes);
298
299			$minAxis = $currentNode->getPoint()->getDAxis($dimension);
300			$minPoint = $currentNode->getPoint();
301
302			foreach ($nodes as $node) {
303			$currentPoint = $this->findMin($node, $dimension, $nextDimension);
304			$currentAxis = $this->getPointAxis($currentPoint, $dimension);
305			if ($currentAxis < $minAxis) {
306			$minPoint = $currentPoint;
307			$minAxis = $currentAxis;
308			}
309			}
310
311			return $minPoint;
312			}
313			}
314

f1r3starter / kdtree

Push — master ( c01a96...bfc690 )

KDTree::chooseMin() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like