KDTree::deletePoint() - Code Metrics - Inspection of "fix readme, change structure of files" - f1r3starter/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( bb1c36...645ae2 )

by Andrii

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

f1r3starter / kdtree

Push — master ( bb1c36...645ae2 )

KDTree::deletePoint() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like