KDTree::findMin() - Code Metrics - f1r3starter/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

KDTree::findMin() A
last analyzed 2020-03-22 19:05 UTC

↳ Parent: KDTree

Complexity

Conditions	3
Paths	3

Size

Total Lines	21
Code Lines	14

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	14
c	1
b	0
f	0
dl	0
loc	21
rs	9.7998
cc	3
nc	3
nop	3

<?php

declare(strict_types=1);

namespace KDTree\Structure;

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

/**
 * Class KDTree
 *
 * @package KDTree\Structure
 */
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 $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			/**
11			* Class KDTree
12			*
13			* @package KDTree\Structure
14			*/
15			final class KDTree implements KDTreeInterface
16			{
17			/**
18			* @var NodeInterface\|null
19			*/
20			private $root;
21
22			/**
23			* @var int
24			*/
25			private $dimensions;
26
27			/**
28			* @var int
29			*/
30			private $size = 0;
31
32			/**
33			* @param int $dimensions
34			*
35			* @throws InvalidDimensionsCount
36			*/
37			public function __construct(int $dimensions)
38			{
39			if ($dimensions < 1) {
40			throw new InvalidDimensionsCount();
41			}
42			$this->dimensions = $dimensions;
43			}
44
45			/**
46			* @inheritDoc
47			*/
48			public function isEmpty(): bool
49			{
50			return null === $this->root;
51			}
52
53			/**
54			* @inheritDoc
55			*/
56			public function size(): int
57			{
58			return $this->size;
59			}
60
61			/**
62			* @param PointInterface $point
63			*
64			* @return KDTreeInterface
65			* @throws PointAlreadyExists\|InvalidPointProvided
66			*/
67			public function put(PointInterface $point): KDTreeInterface
68			{
69			$this->root = $this->insertNode($this->root, $point, 0);
70			++$this->size;
71
72			return $this;
73			}
74
75			/**
76			* @inheritDoc
77			*/
78			public function contains(PointInterface $point): bool
79			{
80			return $this->findPoint($point, $this->root, 0);
81			}
82
83			/**
84			* @return PointsListInterface<PointInterface>
85			* @throws InvalidDimensionsCount
86			*/
87			public function points(): PointsListInterface
88			{
89			return $this->getAllPoints($this->root, new PointsList($this->dimensions));
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->root = $this->deletePoint($point, $this->root, 0);
101			--$this->size;
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
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 $node
153			* @param int $dimension
154			* @param int $cuttingDimension
155			*
156			* @return PointInterface
157			*/
158			private function findMin(NodeInterface $node, int $dimension, int $cuttingDimension): PointInterface
159			{
160			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
161			if ($cuttingDimension === $dimension) {
162			if (null === $node->getLeft()) {
163			return $node->getPoint();
164			}
165
166			return $this->findMin(
167			$node->getLeft(),
168			$dimension,
169			$nextDimension
170			);
171			}
172
173			return $this->chooseMin(
174			$dimension,
175			$nextDimension,
176			$node,
177			$node->getLeft(),
178			$node->getRight()
179			);
180			}
181
182			/**
183			* @param PointInterface\|null $point
184			* @param int $dimension
185			*
186			* @return float\|null
187			*/
188			private function getPointAxis(?PointInterface $point, int $dimension): ?float
189			{
190			return null === $point ? null : $point->getDAxis($dimension);
191			}
192
193			/**
194			* @param PointInterface $point
195			* @param NodeInterface\|null $node
196			* @param int $cuttingDimension
197			*
198			* @return NodeInterface\|null
199			* @throws PointNotFound
200			*/
201			private function deletePoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): ?NodeInterface
202			{
203			if (null === $node) {
204			throw new PointNotFound();
205			}
206
207			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
208
209			if ($node->getPoint()->equals($point)) {
210			if (null !== $node->getRight()) {
211			$this->rebuildFoundNode($node, $node->getRight(), $cuttingDimension);
212			} elseif (null !== $node->getLeft()) {
213			$this->rebuildFoundNode($node, $node->getLeft(), $cuttingDimension);
214			} else {
215			$node = null;
216			}
217			} elseif ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
218			$node->setLeft($this->deletePoint($point, $node->getLeft(), $nextDimension));
219			} else {
220			$node->setRight($this->deletePoint($point, $node->getRight(), $nextDimension));
221			}
222
223			return $node;
224			}
225
226			/**
227			* @param NodeInterface $node
228			* @param NodeInterface $nextNode
229			* @param int $cuttingDimension
230			*
231			* @throws PointNotFound
232			*/
233			private function rebuildFoundNode(NodeInterface $node, NodeInterface $nextNode, int $cuttingDimension): void
234			{
235			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
236			$point = $this->findMin($nextNode, $cuttingDimension, $nextDimension);
237			$node->setPoint($point);
238			$node->setRight($this->deletePoint($point, $nextNode, $nextDimension));
239			}
240
241			/**
242			* @param PointInterface $point
243			* @param NodeInterface\|null $node
244			* @param int $cuttingDimension
245			*
246			* @return bool
247			*/
248			private function findPoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): bool
249			{
250			if (null === $node) {
251			return false;
252			}
253
254			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
255
256			if ($node->getPoint()->equals($point)) {
257			return true;
258			}
259
260			if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
261			return $this->findPoint($point, $node->getLeft(), $nextDimension);
262			}
263
264			return $this->findPoint($point, $node->getRight(), $nextDimension);
265			}
266
267			/**
268			* @param NodeInterface\|null $node
269			* @param PointsListInterface<PointInterface> $pointsList
270			*
271			* @return PointsListInterface<PointInterface>
272			*/
273			private function getAllPoints(?NodeInterface $node, PointsListInterface $pointsList): PointsListInterface
274			{
275			if (null === $node) {
276			return $pointsList;
277			}
278
279			$pointsList->addPoint($node->getPoint());
280
281			if (null !== $node->getLeft()) {
282			$this->getAllPoints($node->getLeft(), $pointsList);
283			}
284
285			if (null !== $node->getRight()) {
286			$this->getAllPoints($node->getRight(), $pointsList);
287			}
288
289			return $pointsList;
290			}
291
292			/**
293			* @param int $dimension
294			* @param int $nextDimension
295			* @param NodeInterface $currentNode
296			* @param NodeInterface\|null ...$nodes
297			*
298			* @return PointInterface
299			*/
300			private function chooseMin(
301			int $dimension,
302			int $nextDimension,
303			NodeInterface $currentNode,
304			?NodeInterface ...$nodes
305			): PointInterface {
306			$nodes = array_filter($nodes);
307
308			$minAxis = $currentNode->getPoint()->getDAxis($dimension);
309			$minPoint = $currentNode->getPoint();
310
311			foreach ($nodes as $node) {
312			$currentPoint = $this->findMin($node, $dimension, $nextDimension);
313			$currentAxis = $this->getPointAxis($currentPoint, $dimension);
314			if ($currentAxis < $minAxis) {
315			$minPoint = $currentPoint;
316			$minAxis = $currentAxis;
317			}
318			}
319
320			return $minPoint;
321			}
322			}
323

f1r3starter / kdtree

KDTree::findMin() A last analyzed 2020-03-22 19:05 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

KDTree::findMin() A
last analyzed 2020-03-22 19:05 UTC