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

KDTree::exch() A
last analyzed 2024-09-15 21:17 UTC

↳ Parent: KDTree

Complexity

Conditions	1
Paths	1

Size

Total Lines	5
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	4
CRAP Score	1

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
eloc	3
c	1
b	0
f	0
dl	0
loc	5
ccs	4
cts	4
cp	1
rs	10
cc	1
nc	1
nop	2
crap	1

<?php

namespace Hexogen\KDTree;

use Hexogen\KDTree\Interfaces\ItemInterface;
use Hexogen\KDTree\Interfaces\ItemListInterface;
use Hexogen\KDTree\Interfaces\KDTreeInterface;
use Hexogen\KDTree\Interfaces\NodeInterface;

class KDTree implements KDTreeInterface
{
    /**
     * @var NodeInterface
     */
    private $root;

    /**
     * @var ItemInterface[]|null array of items or null after tree has been built
     */
    private $items;

    /**
     * @var array
     */
    private $maxBoundary;

    /**
     * @var array
     */
    private $minBoundary;

    /**
     * @var int number of items in the tree
     */
    private $length;

    /**
     * @var int
     */
    private $dimensions;

    /**
     * KDTree constructor.
     * @param ItemListInterface $itemList
     */
    public function __construct(ItemListInterface $itemList)
    {
        $this->dimensions = $itemList->getDimensionCount();
        $this->items = $itemList->getItems();
        $this->length = count($this->items);

        $this->setBoundaries($this->items);

        $this->buildTree();

        unset($this->items);
    }

    /**
     * Get number of items in the tree
     * @return int
     */
    public function getItemCount(): int
    {
        return $this->length;
    }

    /**
     * Get root node
     * @return NodeInterface|null return node or null if there is no nodes in the tree
     */
    public function getRoot(): ?NodeInterface
    {
        return $this->root;
    }

    /**
     * Get lower boundary coordinate
     * @return array
     */
    public function getMinBoundary(): array
    {
        return $this->minBoundary;
    }

    /**
     * Get upper boundary coordinate
     * @return array
     */
    public function getMaxBoundary(): array
    {
        return $this->maxBoundary;
    }

    /**
     * Get number of dimensions in the tree
     * @return int
     */
    public function getDimensionCount(): int
    {
        return $this->dimensions;
    }

    /**
     * @param int $lo
     * @param int $hi
     * @param int $d
     * @return Node
     */
    private function buildSubTree(int $lo, int $hi, int $d): Node
    {
        $mid = (int)(($hi - $lo) / 2) + $lo;

        $item = $this->select($mid, $lo, $hi, $d);
        $node = new Node($item);

        $d++;
        $d = $d % $this->dimensions;

        if ($mid > $lo) {
            $node->setLeft($this->buildSubTree($lo, $mid - 1, $d));
        }
        if ($mid < $hi) {
            $node->setRight($this->buildSubTree($mid + 1, $hi, $d));
        }
        return $node;
    }

    private function exch(int $i, int $j)
    {
        $tmp = $this->items[$i];
        $this->items[$i] = $this->items[$j];
        $this->items[$j] = $tmp;
    }

    /**
     * @param int $k
     * @param int $lo
     * @param int $hi
     * @param int $d
     * @return ItemInterface
     */
    private function select(int $k, int $lo, int $hi, int $d)
    {
        while ($hi > $lo) {
            $j = $this->partition($lo, $hi, $d);
            if ($j > $k) {
                $hi = $j - 1;
            } elseif ($j < $k) {
                $lo = $j + 1;
            } else {
                return $this->items[$k];
            }
        }
        return $this->items[$k];
    }

    /**
     * @param int $lo
     * @param int $hi
     * @param int $d
     * @return int
     */
    private function partition(int $lo, int $hi, int $d)
    {
        $i = $lo;
        $j = $hi + 1;
        $v = $this->items[$lo];
        $val = $v->getNthDimension($d);

        do {
            while ($this->items[++$i]->getNthDimension($d) < $val && $i != $hi) {
            }

            while ($this->items[--$j]->getNthDimension($d) > $val) {
            }

            if ($i < $j) {
                $this->exch($i, $j);
            }
        } while ($i < $j);

        $this->exch($lo, $j);

        return $j;
    }

    /**
     *  Set boundaries for given item list
     * @param ItemInterface[] $items
     */
    private function setBoundaries(array $items)
    {
        $this->maxBoundary = [];
        $this->minBoundary = [];

        for ($i = 0; $i < $this->dimensions; $i++) {
            $this->maxBoundary[$i] = -INF;
            $this->minBoundary[$i] = INF;
        }

        foreach ($items as $item) {
            for ($i = 0; $i < $this->dimensions; $i++) {
                $this->maxBoundary[$i] = max($this->maxBoundary[$i], $item->getNthDimension($i));
                $this->minBoundary[$i] = min($this->minBoundary[$i], $item->getNthDimension($i));
            }
        }
    }

    /**
     *  Build kd tree
     */
    private function buildTree()
    {
        if ($this->length > 0) {
            $hi = $this->length - 1;
            $mid = (int)($hi / 2);
            $item = $this->select($mid, 0, $hi, 0);

            $this->root = new Node($item);

            $nextDimension = 1 % $this->dimensions;
            if ($mid > 0) {
                $this->root->setLeft($this->buildSubTree(0, $mid - 1, $nextDimension));
            }
            if ($mid < $hi) {
                $this->root->setRight($this->buildSubTree($mid + 1, $hi, $nextDimension));
            }
        }
    }
}


1		<?php
2
3		namespace Hexogen\KDTree;
4
5		use Hexogen\KDTree\Interfaces\ItemInterface;
6		use Hexogen\KDTree\Interfaces\ItemListInterface;
7		use Hexogen\KDTree\Interfaces\KDTreeInterface;
8		use Hexogen\KDTree\Interfaces\NodeInterface;
9
10		class KDTree implements KDTreeInterface
11		{
12		/**
13		* @var NodeInterface
14		*/
15		private $root;
16
17		/**
18		* @var ItemInterface[]\|null array of items or null after tree has been built
19		*/
20		private $items;
21
22		/**
23		* @var array
24		*/
25		private $maxBoundary;
26
27		/**
28		* @var array
29		*/
30		private $minBoundary;
31
32		/**
33		* @var int number of items in the tree
34		*/
35		private $length;
36
37		/**
38		* @var int
39		*/
40		private $dimensions;
41
42		/**
43		* KDTree constructor.
44		* @param ItemListInterface $itemList
45		*/
46	93	public function __construct(ItemListInterface $itemList)
47		{
48	93	$this->dimensions = $itemList->getDimensionCount();
49	93	$this->items = $itemList->getItems();
50	93	$this->length = count($this->items);
51
52	93	$this->setBoundaries($this->items);
53
54	93	$this->buildTree();
55
56	93	unset($this->items);
57	93	}
58
59		/**
60		* Get number of items in the tree
61		* @return int
62		*/
63	42	public function getItemCount(): int
64		{
65	42	return $this->length;
66		}
67
68		/**
69		* Get root node
70		* @return NodeInterface\|null return node or null if there is no nodes in the tree
71		*/
72	75	public function getRoot(): ?NodeInterface
73		{
74	75	return $this->root;
75		}
76
77		/**
78		* Get lower boundary coordinate
79		* @return array
80		*/
81	45	public function getMinBoundary(): array
82		{
83	45	return $this->minBoundary;
84		}
85
86		/**
87		* Get upper boundary coordinate
88		* @return array
89		*/
90	45	public function getMaxBoundary(): array
91		{
92	45	return $this->maxBoundary;
93		}
94
95		/**
96		* Get number of dimensions in the tree
97		* @return int
98		*/
99	48	public function getDimensionCount(): int
100		{
101	48	return $this->dimensions;
102		}
103
104		/**
105		* @param int $lo
106		* @param int $hi
107		* @param int $d
108		* @return Node
109		*/
110	72	private function buildSubTree(int $lo, int $hi, int $d): Node
111		{
112	72	$mid = (int)(($hi - $lo) / 2) + $lo;
113
114	72	$item = $this->select($mid, $lo, $hi, $d);
115	72	$node = new Node($item);
116
117	72	$d++;
118	72	$d = $d % $this->dimensions;
119
120	72	if ($mid > $lo) {
121	63	$node->setLeft($this->buildSubTree($lo, $mid - 1, $d));
122		}
123	72	if ($mid < $hi) {
124	72	$node->setRight($this->buildSubTree($mid + 1, $hi, $d));
125		}
126	72	return $node;
127		}
128
129	72	private function exch(int $i, int $j)
130		{
131	72	$tmp = $this->items[$i];
132	72	$this->items[$i] = $this->items[$j];
133	72	$this->items[$j] = $tmp;
134	72	}
135
136		/**
137		* @param int $k
138		* @param int $lo
139		* @param int $hi
140		* @param int $d
141		* @return ItemInterface
142		*/
143	84	private function select(int $k, int $lo, int $hi, int $d)
144		{
145	84	while ($hi > $lo) {
146	72	$j = $this->partition($lo, $hi, $d);
147	72	if ($j > $k) {
148	69	$hi = $j - 1;
149	72	} elseif ($j < $k) {
150	72	$lo = $j + 1;
151		} else {
152	69	return $this->items[$k];
153		}
154		}
155	84	return $this->items[$k];
156		}
157
158		/**
159		* @param int $lo
160		* @param int $hi
161		* @param int $d
162		* @return int
163		*/
164	72	private function partition(int $lo, int $hi, int $d)
165		{
166	72	$i = $lo;
167	72	$j = $hi + 1;
168	72	$v = $this->items[$lo];
169	72	$val = $v->getNthDimension($d);
170
171		do {
172	72	while ($this->items[++$i]->getNthDimension($d) < $val && $i != $hi) {
173		}
174
175	72	while ($this->items[--$j]->getNthDimension($d) > $val) {
176		}
177
178	72	if ($i < $j) {
179	63	$this->exch($i, $j);
180		}
181	72	} while ($i < $j);
182
183	72	$this->exch($lo, $j);
184
185	72	return $j;
186		}
187
188		/**
189		* Set boundaries for given item list
190		* @param ItemInterface[] $items
191		*/
192	93	private function setBoundaries(array $items)
193		{
194	93	$this->maxBoundary = [];
195	93	$this->minBoundary = [];
196
197	93	for ($i = 0; $i < $this->dimensions; $i++) {
198	93	$this->maxBoundary[$i] = -INF;
199	93	$this->minBoundary[$i] = INF;
200		}
201
202	93	foreach ($items as $item) {
203	84	for ($i = 0; $i < $this->dimensions; $i++) {
204	84	$this->maxBoundary[$i] = max($this->maxBoundary[$i], $item->getNthDimension($i));
205	84	$this->minBoundary[$i] = min($this->minBoundary[$i], $item->getNthDimension($i));
206		}
207		}
208	93	}
209
210		/**
211		* Build kd tree
212		*/
213	93	private function buildTree()
214		{
215	93	if ($this->length > 0) {
216	84	$hi = $this->length - 1;
217	84	$mid = (int)($hi / 2);
218	84	$item = $this->select($mid, 0, $hi, 0);
219
220	84	$this->root = new Node($item);
221
222	84	$nextDimension = 1 % $this->dimensions;
223	84	if ($mid > 0) {
224	72	$this->root->setLeft($this->buildSubTree(0, $mid - 1, $nextDimension));
225		}
226	84	if ($mid < $hi) {
227	72	$this->root->setRight($this->buildSubTree($mid + 1, $hi, $nextDimension));
228		}
229		}
230	93	}
231		}
232

hexogen / kdtree

KDTree::exch() A last analyzed 2024-09-15 21:17 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

KDTree::exch() A
last analyzed 2024-09-15 21:17 UTC