KDTree::setBoundaries() - Code Metrics - Inspection of "Tree refactoring done" - hexogen/kdtree - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Branch — master (2d6bff)

by Basarab

created 2016-12-22 15:49 UTC

KDTree::setBoundaries() A

↳ Parent: KDTree

Complexity

Conditions	4
Paths	6

Size

Total Lines	17
Code Lines	10

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	11
CRAP Score	4

Importance

Changes

Metric	Value
dl	0
loc	17
ccs	11
cts	11
cp	1
rs	9.2
c	0
b	0
f	0
cc	4
eloc	10
nc	6
nop	0
crap	4

<?php

namespace Hexogen\KDTree;

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;

    public function __construct(ItemList $itemList)
    {
        $this->dimensions = $itemList->getDimensionCount();
        $this->items = $itemList->getItems();
        $this->length = count($this->items);

        $this->setBoundaries();

        $this->buildTree();

        $this->items = null;
    }

    public function getItemCount(): int
    {
        return $this->length;
    }

    public function getRoot(): NodeInterface
    {
        return $this->root;
    }

    public function getMinBoundary(): array
    {
        return $this->minBoundary;
    }

    public function getMaxBoundary(): array
    {
        return $this->maxBoundary;
    }

    public function getDimensionCount(): int
    {
        return $this->dimensions;
    }

    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);
        while (true) {
            while ($this->items[++$i]->getNthDimension($d) < $val) {
                if ($i == $hi) {
                    break;
                }
            }

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

            if ($i >= $j) {
                break;
            }

            $this->exch($i, $j);
        }

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

        return $j;
    }

    private function setBoundaries()
    {
        $this->maxBoundary = [];
        $this->minBoundary = [];

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

        foreach ($this->items as $item) {
$collection = json_decode($data, true);
if ( ! is_array($collection)) {
    throw new \RuntimeException('$collection must be an array.');
}

foreach ($collection 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));
            }
        }
    }

    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		class KDTree implements KDTreeInterface
6		{
7		/**
8		* @var NodeInterface
9		*/
10		private $root;
11
12		/**
13		* @var ItemInterface[]\|null array of items or null after tree has been built
14		*/
15		private $items;
16
17		/**
18		* @var array
19		*/
20		private $maxBoundary;
21
22		/**
23		* @var array
24		*/
25		private $minBoundary;
26
27		/**
28		* @var int number of items in the tree
29		*/
30		private $length;
31
32		/**
33		* @var int
34		*/
35		private $dimensions;
36
37	42	public function __construct(ItemList $itemList)
38		{
39	42	$this->dimensions = $itemList->getDimensionCount();
40	42	$this->items = $itemList->getItems();
41	42	$this->length = count($this->items);
42
43	42	$this->setBoundaries();
44
45	42	$this->buildTree();
46
47	42	$this->items = null;
48	42	}
49
50	3	public function getItemCount(): int
51		{
52	3	return $this->length;
53		}
54
55	27	public function getRoot(): NodeInterface
56		{
57	27	return $this->root;
58		}
59
60	3	public function getMinBoundary(): array
61		{
62	3	return $this->minBoundary;
63		}
64
65	3	public function getMaxBoundary(): array
66		{
67	3	return $this->maxBoundary;
68		}
69
70	3	public function getDimensionCount(): int
71		{
72	3	return $this->dimensions;
73		}
74
75	36	private function buildSubTree(int $lo, int $hi, int $d): Node
76		{
77	36	$mid = (int)(($hi - $lo) / 2) + $lo;
78
79	36	$item = $this->select($mid, $lo, $hi, $d);
80	36	$node = new Node($item);
81
82	36	$d++;
83	36	$d = $d % $this->dimensions;
84
85	36	if ($mid > $lo) {
86	30	$node->setLeft($this->buildSubTree($lo, $mid - 1, $d));
87		}
88	36	if ($mid < $hi) {
89	36	$node->setRight($this->buildSubTree($mid + 1, $hi, $d));
90		}
91	36	return $node;
92		}
93
94	36	private function exch(int $i, int $j)
95		{
96	36	$tmp = $this->items[$i];
97	36	$this->items[$i] = $this->items[$j];
98	36	$this->items[$j] = $tmp;
99	36	}
100
101		/**
102		* @param int $k
103		* @param int $lo
104		* @param int $hi
105		* @param int $d
106		* @return ItemInterface
107		*/
108	39	private function select(int $k, int $lo, int $hi, int $d)
109		{
110	39	while ($hi > $lo) {
111	36	$j = $this->partition($lo, $hi, $d);
112	36	if ($j > $k) {
113	33	$hi = $j - 1;
114	36	} elseif ($j < $k) {
115	36	$lo = $j + 1;
116		} else {
117	36	return $this->items[$k];
118		}
119		}
120	39	return $this->items[$k];
121		}
122
123		/**
124		* @param int $lo
125		* @param int $hi
126		* @param int $d
127		* @return int
128		*/
129	36	private function partition(int $lo, int $hi, int $d)
130		{
131	36	$i = $lo;
132	36	$j = $hi + 1;
133	36	$v = $this->items[$lo];
134	36	$val = $v->getNthDimension($d);
135	36	while (true) {
136	36	while ($this->items[++$i]->getNthDimension($d) < $val) {
137	33	if ($i == $hi) {
138	33	break;
139		}
140		}
141
142	36	while ($this->items[--$j]->getNthDimension($d) > $val) {
143		}
144
145	36	if ($i >= $j) {
146	36	break;
147		}
148
149	30	$this->exch($i, $j);
150		}
151
152	36	$this->exch($lo, $j);
153
154	36	return $j;
155		}
156
157	42	private function setBoundaries()
158		{
159	42	$this->maxBoundary = [];
160	42	$this->minBoundary = [];
161
162	42	for ($i = 0; $i < $this->dimensions; $i++) {
163	42	$this->maxBoundary[$i] = -INF;
164	42	$this->minBoundary[$i] = INF;
165		}
166
167	42	foreach ($this->items as $item) {
		0 ignored issues – show Bug introduced 2016-12-22 15:52 UTC by Report Bug Copy Issue Report The expression `$this->items` of type `array<integer,object<Hex...ee\ItemInterface>>\|null` is not guaranteed to be traversable. How about adding an additional type check? There are different options of fixing this problem. If you want to be on the safe side, you can add an additional type-check: $collection = json_decode($data, true); if ( ! is_array($collection)) { throw new \RuntimeException('$collection must be an array.'); } foreach ($collection as $item) { /** ... / } If you are sure that the expression is traversable, you might want to add a doc comment cast* to improve IDE auto-completion and static analysis: /** @var array $collection / $collection = json_decode($data, true); foreach ($collection as $item) { /* .. / } Mark the issue as a false-positive*: Just hover the remove button, in the top-right corner of this issue for more options. Loading history...
168	39	for ($i = 0; $i < $this->dimensions; $i++) {
169	39	$this->maxBoundary[$i] = max($this->maxBoundary[$i], $item->getNthDimension($i));
170	39	$this->minBoundary[$i] = min($this->minBoundary[$i], $item->getNthDimension($i));
171		}
172		}
173	42	}
174
175	42	private function buildTree()
176		{
177	42	if ($this->length > 0) {
178	39	$hi = $this->length - 1;
179	39	$mid = (int)($hi / 2);
180	39	$item = $this->select($mid, 0, $hi, 0);
181
182	39	$this->root = new Node($item);
183
184	39	$nextDimension = 1 % $this->dimensions;
185	39	if ($mid > 0) {
186	36	$this->root->setLeft($this->buildSubTree(0, $mid - 1, $nextDimension));
187		}
188	39	if ($mid < $hi) {
189	36	$this->root->setRight($this->buildSubTree($mid + 1, $hi, $nextDimension));
190		}
191		}
192	42	}
193		}
194

hexogen / kdtree

Branch — master (2d6bff)

KDTree::setBoundaries() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like