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

Passed

Push — master ( 0beaa6...94f0c6 )

by Andrii

created 2019-12-25 19:47 UTC

KDTree::getAllPoints() A

↳ Parent: KDTree

Complexity

Conditions	4
Paths	5

Size

Total Lines	17
Code Lines	8

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
eloc	8
c	1
b	0
f	0
nc	5
nop	2
dl	0
loc	17
rs	10

<?php

declare(strict_types=1);

namespace KDTree\Structure;

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

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);
    }

    /**
     * @inheritDoc
     */
    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|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
     */
    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;
        $node->setPoint(
            $this->findMin($nextNode, $cuttingDimension, $nextDimension)
        );
        $node->setRight($this->deletePoint($node->getPoint(), $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);
    }

    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			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			* @inheritDoc
80			*/
81			public function points(): PointsListInterface
82			{
83			return $this->getAllPoints($this->root, new PointsList($this->dimensions));
84			}
85
86			/**
87			* @param PointInterface $point
88			*
89			* @return KDTreeInterface
90			* @throws PointNotFound
91			*/
92			public function delete(PointInterface $point): KDTreeInterface
93			{
94			$this->root = $this->deletePoint($point, $this->root, 0);
95			--$this->size;
96
97			return $this;
98			}
99
100			/**
101			* @inheritDoc
102			*/
103			public function getDimensions(): int
104			{
105			return $this->dimensions;
106			}
107
108			/**
109			* @return NodeInterface\|null
110			*/
111			public function getRoot(): ?NodeInterface
112			{
113			return $this->root;
114			}
115
116			/**
117			* @param NodeInterface\|null $node
118			* @param PointInterface $point
119			* @param int $cuttingDimension
120			*
121			* @return NodeInterface\|null
122			* @throws PointAlreadyExists
123			*/
124			private function insertNode(?NodeInterface $node, PointInterface $point, int $cuttingDimension): ?NodeInterface
125			{
126			if (null === $node) {
127			return new Node($point);
128			}
129
130			if ($node->getPoint()->equals($point)) {
131			throw new PointAlreadyExists();
132			}
133
134			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
135
136			if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
137			$node->setLeft($this->insertNode($node->getLeft(), $point, $nextDimension));
138			} else {
139			$node->setRight($this->insertNode($node->getRight(), $point, $nextDimension));
140			}
141
142			return $node;
143			}
144
145			/**
146			* @param NodeInterface\|null $node
147			* @param int $dimension
148			* @param int $cuttingDimension
149			*
150			* @return PointInterface\|null
151			*/
152			private function findMin(?NodeInterface $node, int $dimension, int $cuttingDimension): ?PointInterface
153			{
154			if (null === $node) {
155			return null;
156			}
157
158			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
159			if ($cuttingDimension === $dimension) {
160			if (null === $node->getLeft()) {
161			return $node->getPoint();
162			}
163
164			return $this->findMin(
165			$node->getLeft(),
166			$dimension,
167			$nextDimension
168			);
169			}
170
171			$leftMin = $this->findMin($node->getLeft(), $dimension, $nextDimension);
172			$rightMin = $this->findMin($node->getRight(), $dimension, $nextDimension);
173			$current = $node->getPoint()->getDAxis($dimension);
174			$minimums = [
175			$this->getPointAxis($leftMin, $dimension) => $leftMin,
176			$this->getPointAxis($rightMin, $dimension) => $rightMin,
177			$current => $node->getPoint(),
178			];
179			$minKey = min(
180			array_keys(
181			array_filter($minimums)
182			)
183			);
184
185			return $minimums[$minKey];
186			}
187
188			/**
189			* @param PointInterface\|null $point
190			* @param int $dimension
191			*
192			* @return float\|null
193			*/
194			private function getPointAxis(?PointInterface $point, int $dimension): ?float
195			{
196			return null === $point ? null : $point->getDAxis($dimension);
197			}
198
199			/**
200			* @param PointInterface $point
201			* @param NodeInterface\|null $node
202			* @param int $cuttingDimension
203			*
204			* @return NodeInterface\|null
205			* @throws PointNotFound
206			*/
207			private function deletePoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): ?NodeInterface
208			{
209			if (null === $node) {
210			throw new PointNotFound();
211			}
212
213			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
214
215			if ($node->getPoint()->equals($point)) {
216			if (null !== $node->getRight()) {
217			$this->rebuildFoundNode($node, $node->getRight(), $cuttingDimension);
218			} elseif (null !== $node->getLeft()) {
219			$this->rebuildFoundNode($node, $node->getLeft(), $cuttingDimension);
220			} else {
221			$node = null;
222			}
223			} elseif ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
224			$node->setLeft($this->deletePoint($point, $node->getLeft(), $nextDimension));
225			} else {
226			$node->setRight($this->deletePoint($point, $node->getRight(), $nextDimension));
227			}
228
229			return $node;
230			}
231
232			/**
233			* @param NodeInterface $node
234			* @param NodeInterface $nextNode
235			* @param int $cuttingDimension
236			*
237			* @throws PointNotFound
238			*/
239			private function rebuildFoundNode(NodeInterface $node, NodeInterface $nextNode, int $cuttingDimension): void
240			{
241			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
242			$node->setPoint(
243			$this->findMin($nextNode, $cuttingDimension, $nextDimension)
244			);
245			$node->setRight($this->deletePoint($node->getPoint(), $nextNode, $nextDimension));
246			}
247
248			/**
249			* @param PointInterface $point
250			* @param NodeInterface\|null $node
251			* @param int $cuttingDimension
252			*
253			* @return bool
254			*/
255			private function findPoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): bool
256			{
257			if (null === $node) {
258			return false;
259			}
260
261			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
262
263			if ($node->getPoint()->equals($point)) {
264			return true;
265			}
266
267			if ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
268			return $this->findPoint($point, $node->getLeft(), $nextDimension);
269			}
270
271			return $this->findPoint($point, $node->getRight(), $nextDimension);
272			}
273
274			private function getAllPoints(?NodeInterface $node, PointsListInterface $pointsList): PointsListInterface
275			{
276			if (null === $node) {
277			return $pointsList;
278			}
279
280			$pointsList->addPoint($node->getPoint());
281
282			if (null !== $node->getLeft()) {
283			$this->getAllPoints($node->getLeft(), $pointsList);
284			}
285
286			if (null !== $node->getRight()) {
287			$this->getAllPoints($node->getRight(), $pointsList);
288			}
289
290			return $pointsList;
291			}
292			}
293

f1r3starter / kdtree

Push — master ( 0beaa6...94f0c6 )

KDTree::getAllPoints() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like