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

Passed

Push — master ( 1df370...dc6623 )

by Andrii

created 2019-12-20 21:14 UTC

KDTree::insertNode() A

↳ Parent: KDTree

Complexity

Conditions	4
Paths	4

Size

Total Lines	19
Code Lines	10

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

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

<?php

declare(strict_types=1);

namespace KDTree;

use KDTree\Exceptions\{InvalidDimensionsCount, PointAlreadyExists, PointNotFound};
use KDTree\Structure\{Node, PointsList};
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);
        $leftMinIndex = null === $leftMin ? null : $leftMin->getDAxis($dimension);
        $rightMinIndex = null === $rightMin ? null : $rightMin->getDAxis($dimension);
        $mins = [
            $leftMinIndex  => $leftMin,
            $rightMinIndex => $rightMin,
            $current       => $node->getPoint(),
        ];
        $minKey = min(
            array_keys(
                array_filter($mins)
            )
        );

        return $mins[$minKey];
    }

    /**
     * @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()) {
                $node->setPoint(
                    $this->findMin($node->getRight(), $cuttingDimension, $nextDimension)
                );
                $node->setRight($this->deletePoint($node->getPoint(), $node->getRight(), $nextDimension));
            } elseif (null !== $node->getLeft()) {
                $node->setPoint(
                    $this->findMin($node->getLeft(), $cuttingDimension, $nextDimension)
                );
                $node->setRight($this->deletePoint($node->getPoint(), $node->getLeft(), $nextDimension));
            } 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;
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			namespace KDTree;
6
7			use KDTree\Exceptions\{InvalidDimensionsCount, PointAlreadyExists, PointNotFound};
8			use KDTree\Structure\{Node, PointsList};
9			use KDTree\Interfaces\{KDTreeInterface, NodeInterface, PointInterface, PointsListInterface};
10
11			class KDTree implements KDTreeInterface
12			{
13			/**
14			* @var PointsListInterface
15			*/
16			private $points;
17
18			/**
19			* @var NodeInterface\|null
20			*/
21			private $root;
22
23			/**
24			* @var int
25			*/
26			private $dimensions;
27
28			/**
29			* @param int $dimensions
30			*
31			* @throws InvalidDimensionsCount
32			*/
33			public function __construct(int $dimensions)
34			{
35			if ($dimensions < 1) {
36			throw new InvalidDimensionsCount();
37			}
38			$this->dimensions = $dimensions;
39			$this->points = new PointsList($dimensions);
40			}
41
42			/**
43			* @inheritDoc
44			*/
45			public function isEmpty(): bool
46			{
47			return null === $this->root;
48			}
49
50			/**
51			* @inheritDoc
52			*/
53			public function size(): int
54			{
55			return $this->points->count();
56			}
57
58			/**
59			* @param PointInterface $point
60			*
61			* @return KDTreeInterface
62			* @throws Exceptions\InvalidPointProvided\|PointAlreadyExists
63			*/
64			public function put(PointInterface $point): KDTreeInterface
65			{
66			if ($this->points->pointExists($point)) {
67			throw new PointAlreadyExists();
68			}
69
70			$this->root = $this->insertNode($this->root, $point, 0);
71			$this->points->addPoint($point);
72
73			return $this;
74			}
75
76			/**
77			* @inheritDoc
78			*/
79			public function contains(PointInterface $point): bool
80			{
81			return $this->points->pointExists($point);
82			}
83
84			/**
85			* @inheritDoc
86			*/
87			public function points(): PointsListInterface
88			{
89			return $this->points;
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->deletePoint($point, $this->root, 0);
101			$this->points->removePoint($point);
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\|null
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\|null $node
153			* @param int $dimension
154			* @param int $cuttingDimension
155			*
156			* @return PointInterface\|null
157			*/
158			public function findMin(?NodeInterface $node, int $dimension, int $cuttingDimension): ?PointInterface
159			{
160			if (null === $node) {
161			return null;
162			}
163
164			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
165			if ($cuttingDimension === $dimension) {
166			if (null === $node->getLeft()) {
167			return $node->getPoint();
168			}
169
170			return $this->findMin(
171			$node->getLeft(),
172			$dimension,
173			$nextDimension
174			);
175			}
176
177			$leftMin = $this->findMin($node->getLeft(), $dimension, $nextDimension);
178			$rightMin = $this->findMin($node->getRight(), $dimension, $nextDimension);
179			$current = $node->getPoint()->getDAxis($dimension);
180			$leftMinIndex = null === $leftMin ? null : $leftMin->getDAxis($dimension);
181			$rightMinIndex = null === $rightMin ? null : $rightMin->getDAxis($dimension);
182			$mins = [
183			$leftMinIndex => $leftMin,
184			$rightMinIndex => $rightMin,
185			$current => $node->getPoint(),
186			];
187			$minKey = min(
188			array_keys(
189			array_filter($mins)
190			)
191			);
192
193			return $mins[$minKey];
194			}
195
196			/**
197			* @param PointInterface $point
198			* @param NodeInterface\|null $node
199			* @param int $cuttingDimension
200			*
201			* @return NodeInterface\|null
202			* @throws PointNotFound
203			*/
204			private function deletePoint(PointInterface $point, ?NodeInterface $node, int $cuttingDimension): ?NodeInterface
205			{
206			if (null === $node) {
207			throw new PointNotFound();
208			}
209
210			$nextDimension = ($cuttingDimension + 1) % $this->dimensions;
211
212			if ($node->getPoint()->equals($point)) {
213			if (null !== $node->getRight()) {
214			$node->setPoint(
215			$this->findMin($node->getRight(), $cuttingDimension, $nextDimension)
216			);
217			$node->setRight($this->deletePoint($node->getPoint(), $node->getRight(), $nextDimension));
218			} elseif (null !== $node->getLeft()) {
219			$node->setPoint(
220			$this->findMin($node->getLeft(), $cuttingDimension, $nextDimension)
221			);
222			$node->setRight($this->deletePoint($node->getPoint(), $node->getLeft(), $nextDimension));
223			} else {
224			$node = null;
225			}
226			} elseif ($point->getDAxis($cuttingDimension) < $node->getPoint()->getDAxis($cuttingDimension)) {
227			$node->setLeft($this->deletePoint($point, $node->getLeft(), $nextDimension));
228			} else {
229			$node->setRight($this->deletePoint($point, $node->getRight(), $nextDimension));
230			}
231
232			return $node;
233			}
234			}
235

f1r3starter / kdtree

Push — master ( 1df370...dc6623 )

KDTree::insertNode() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like