PriorityQueue::toArray() - Code Metrics - Inspection of "Fix errors thrown when accessing stack and queue b..." - php-ds/polyfill - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 8d1df5...05ea10 )

by Rudi

created 2016-08-08 12:24 UTC

PriorityQueue::toArray() A

↳ Parent: PriorityQueue

Complexity

Conditions	2
Paths	2

Size

Total Lines	12
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	7
CRAP Score	2

Importance

Changes

Metric	Value
dl	0
loc	12
ccs	7
cts	7
cp	1
rs	9.4285
c	0
b	0
f	0
cc	2
eloc	7
nc	2
nop	0
crap	2

<?php
namespace Ds;

use UnderflowException;

/**
 * PriorityNode
 *
 * @package Ds
 */
final class PriorityNode
{
    /**
     * @var mixed
     */
    public $value;

    /**
     * @var int
     */
    public $priority;

    /**
     * @var int
     */
    public $stamp;

    /**
     * @param mixed $value
     * @param int   $priority
     * @param int   $stamp
     */
    public function __construct($value, int $priority, int $stamp)
    {
        $this->value    = $value;
        $this->priority = $priority;
        $this->stamp    = $stamp;
    }
}

/**
 * PriorityQueue
 *
 * @package Ds
 */
final class PriorityQueue implements \IteratorAggregate, Collection

{
    use Traits\Collection;
    use Traits\SquaredCapacity;

    /**
     * @var int
     */
    const MIN_CAPACITY = 8;

    /**
     * @var array
     */
    private $heap = [];

    /**
     * @var int
     */
    private $stamp = 0;

    /**
     * Initializes a new priority queue.
     */
    public function __construct()
    {

    }

    /**
     * @inheritDoc
     */
    public function clear()
    {
        $this->heap     = [];
        $this->stamp    = 0;
        $this->capacity = self::MIN_CAPACITY;
    }

    /**
     * @inheritDoc
     */
    public function copy(): \Ds\Collection
    {
        $copy = new PriorityQueue();

        $copy->heap     = $this->heap;
        $copy->capacity = $this->capacity;

        return $copy;
    }

    /**
     * @inheritDoc
     */
    public function count(): int
    {
        return count($this->heap);
    }

    /**
     * Returns the value with the highest priority in the priority queue.
     *
     * @return mixed
     *
     * @throw UnderflowException
     */
    public function peek()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException();
        }

        return $this->heap[0]->value;
    }

    /**
     * Left
     *
     * @param int $index
     *
     * @return int
     */
    private function left(int $index): int
    {
        return ($index * 2) + 1;
    }

    /**
     * Right
     *
     * @param int $index
     *
     * @return int
     */
    private function right(int $index): int
    {
        return ($index * 2) + 2;
    }

    /**
     * Parent
     *
     * @param int $index
     *
     * @return int
     */
    private function parent(int $index): int
    {
        return ($index - 1) / 2;
    }

    /**
     * Compare
     *
     * @param int $a
     * @param int $b
     *
     * @return integer
     */
    private function compare(int $a, int $b)
    {
        $x = $this->heap[$a];
        $y = $this->heap[$b];

        // Compare priority, using insertion stamp as fallback.
        return ($x->priority <=> $y->priority) ?: ($y->stamp <=> $x->stamp);
    }

    /**
     * Swap
     *
     * @param int $a
     * @param int $b
     */
    private function swap(int $a, int $b)
    {
        $temp           = $this->heap[$a];
        $this->heap[$a] = $this->heap[$b];
        $this->heap[$b] = $temp;
    }

    /**
     * Get Largest Leaf
     *
     * @param int $parent
     *
     * @return int
     */
    private function getLargestLeaf(int $parent)
    {
        $left  = $this->left($parent);
        $right = $this->right($parent);

        if ($right < count($this->heap) && $this->compare($left, $right) < 0) {
            return $right;
        }

        return $left;
    }

    /**
     * Sift Down
     *
     * @param int $node
     */
    private function siftDown(int $node)
    {
        $last = floor(count($this->heap) / 2);

        for ($parent = $node; $parent < $last; $parent = $leaf) {

            // Determine the largest leaf to potentially swap with the parent.
            $leaf = $this->getLargestLeaf($parent);

            // Done if the parent is not greater than its largest leaf
            if ($this->compare($parent, $leaf) > 0) {
                break;
            }

            $this->swap($parent, $leaf);
        }
    }

    /**
     * Set Root
     *
     * @param PriorityNode $node
     */
    private function setRoot(PriorityNode $node)
    {
        $this->heap[0] = $node;
    }

    /**
     * Get Root
     *
     * @return PriorityNode
     */
    private function getRoot(): PriorityNode
    {
        return $this->heap[0];
    }

    /**
     * Returns and removes the value with the highest priority in the queue.
     *
     * @return mixed
     */
    public function pop()
    {
        if ($this->isEmpty()) {
            throw new UnderflowException();
        }

        // Last leaf of the heap to become the new root.
        $leaf = array_pop($this->heap);

        if (empty($this->heap)) {
            return $leaf->value;
        }

        // Cache the current root value to return before replacing with next.
        $value = $this->getRoot()->value;

        // Replace the root, then sift down.
        $this->setRoot($leaf);
        $this->siftDown(0);
        $this->adjustCapacity();

        return $value;
    }

    /**
     * Sift Up
     *
     * @param int $leaf
     */
    private function siftUp(int $leaf)
    {
        for (; $leaf > 0; $leaf = $parent) {
            $parent = $this->parent($leaf);

            // Done when parent priority is greater.
            if ($this->compare($leaf, $parent) < 0) {
                break;
            }

            $this->swap($parent, $leaf);
        }
    }

    /**
     * Pushes a value into the queue, with a specified priority.
     *
     * @param mixed $value
     * @param int   $priority
     */
    public function push($value, int $priority)
    {
        $this->adjustCapacity();

        // Add new leaf, then sift up to maintain heap,
        $this->heap[] = new PriorityNode($value, $priority, $this->stamp++);
        $this->siftUp(count($this->heap) - 1);
    }

    /**
     * @inheritDoc
     */
    public function toArray(): array
    {
        $heap  = $this->heap;
        $array = [];

        while ( ! $this->isEmpty()) {
            $array[] = $this->pop();
        }

        $this->heap = $heap;
        return $array;
    }

    /**
     * Get iterator
     */
    public function getIterator()
    {
        while ( ! $this->isEmpty()) {
            yield $this->pop();
        }
    }
}


1		<?php
2		namespace Ds;
3
4		use UnderflowException;
5
6		/**
7		* PriorityNode
8		*
9		* @package Ds
10		*/
11		final class PriorityNode
12		{
13		/**
14		* @var mixed
15		*/
16		public $value;
17
18		/**
19		* @var int
20		*/
21		public $priority;
22
23		/**
24		* @var int
25		*/
26		public $stamp;
27
28		/**
29		* @param mixed $value
30		* @param int $priority
31		* @param int $stamp
32		*/
33	44	public function __construct($value, int $priority, int $stamp)
34		{
35	44	$this->value = $value;
36	44	$this->priority = $priority;
37	44	$this->stamp = $stamp;
38	44	}
39		}
40
41		/**
42		* PriorityQueue
43		*
44		* @package Ds
45		*/
46		final class PriorityQueue implements \IteratorAggregate, Collection
		0 ignored issues – show Coding Style Compatibility introduced 2016-03-01 00:43 UTC by Report Bug Copy Issue Report PSR1 recommends that each class should be in its own file to aid autoloaders. Having each class in a dedicated file usually plays nice with PSR autoloaders and is therefore a well established practice. If you use other autoloaders, you might not want to follow this rule. Loading history...
47		{
48		use Traits\Collection;
49		use Traits\SquaredCapacity;
50
51		/**
52		* @var int
53		*/
54		const MIN_CAPACITY = 8;
55
56		/**
57		* @var array
58		*/
59		private $heap = [];
60
61		/**
62		* @var int
63		*/
64		private $stamp = 0;
65
66		/**
67		* Initializes a new priority queue.
68		*/
69	63	public function __construct()
70		{
71
72	63	}
73
74		/**
75		* @inheritDoc
76		*/
77	2	public function clear()
78		{
79	2	$this->heap = [];
80	2	$this->stamp = 0;
81	2	$this->capacity = self::MIN_CAPACITY;
82	2	}
83
84		/**
85		* @inheritDoc
86		*/
87	5	public function copy(): \Ds\Collection
88		{
89	5	$copy = new PriorityQueue();
90
91	5	$copy->heap = $this->heap;
92	5	$copy->capacity = $this->capacity;
93
94	5	return $copy;
95		}
96
97		/**
98		* @inheritDoc
99		*/
100	53	public function count(): int
101		{
102	53	return count($this->heap);
103		}
104
105		/**
106		* Returns the value with the highest priority in the priority queue.
107		*
108		* @return mixed
109		*
110		* @throw UnderflowException
111		*/
112	4	public function peek()
113		{
114	4	if ($this->isEmpty()) {
115	1	throw new UnderflowException();
116		}
117
118	3	return $this->heap[0]->value;
119		}
120
121		/**
122		* Left
123		*
124		* @param int $index
125		*
126		* @return int
127		*/
128	10	private function left(int $index): int
129		{
130	10	return ($index * 2) + 1;
131		}
132
133		/**
134		* Right
135		*
136		* @param int $index
137		*
138		* @return int
139		*/
140	10	private function right(int $index): int
141		{
142	10	return ($index * 2) + 2;
143		}
144
145		/**
146		* Parent
147		*
148		* @param int $index
149		*
150		* @return int
151		*/
152	36	private function parent(int $index): int
153		{
154	36	return ($index - 1) / 2;
155		}
156
157		/**
158		* Compare
159		*
160		* @param int $a
161		* @param int $b
162		*
163		* @return integer
164		*/
165	36	private function compare(int $a, int $b)
166		{
167	36	$x = $this->heap[$a];
168	36	$y = $this->heap[$b];
169
170		// Compare priority, using insertion stamp as fallback.
171	36	return ($x->priority <=> $y->priority) ?: ($y->stamp <=> $x->stamp);
172		}
173
174		/**
175		* Swap
176		*
177		* @param int $a
178		* @param int $b
179		*/
180	23	private function swap(int $a, int $b)
181		{
182	23	$temp = $this->heap[$a];
183	23	$this->heap[$a] = $this->heap[$b];
184	23	$this->heap[$b] = $temp;
185	23	}
186
187		/**
188		* Get Largest Leaf
189		*
190		* @param int $parent
191		*
192		* @return int
193		*/
194	10	private function getLargestLeaf(int $parent)
195		{
196	10	$left = $this->left($parent);
197	10	$right = $this->right($parent);
198
199	10	if ($right < count($this->heap) && $this->compare($left, $right) < 0) {
200	6	return $right;
201		}
202
203	10	return $left;
204		}
205
206		/**
207		* Sift Down
208		*
209		* @param int $node
210		*/
211	29	private function siftDown(int $node)
212		{
213	29	$last = floor(count($this->heap) / 2);
214
215	29	for ($parent = $node; $parent < $last; $parent = $leaf) {
216
217		// Determine the largest leaf to potentially swap with the parent.
218	10	$leaf = $this->getLargestLeaf($parent);
219
220		// Done if the parent is not greater than its largest leaf
221	10	if ($this->compare($parent, $leaf) > 0) {
222	8	break;
223		}
224
225	8	$this->swap($parent, $leaf);
226		}
227	29	}
228
229		/**
230		* Set Root
231		*
232		* @param PriorityNode $node
233		*/
234	29	private function setRoot(PriorityNode $node)
235		{
236	29	$this->heap[0] = $node;
237	29	}
238
239		/**
240		* Get Root
241		*
242		* @return PriorityNode
243		*/
244	29	private function getRoot(): PriorityNode
245		{
246	29	return $this->heap[0];
247		}
248
249		/**
250		* Returns and removes the value with the highest priority in the queue.
251		*
252		* @return mixed
253		*/
254	38	public function pop()
255		{
256	38	if ($this->isEmpty()) {
257	1	throw new UnderflowException();
258		}
259
260		// Last leaf of the heap to become the new root.
261	37	$leaf = array_pop($this->heap);
262
263	37	if (empty($this->heap)) {
264	35	return $leaf->value;
265		}
266
267		// Cache the current root value to return before replacing with next.
268	29	$value = $this->getRoot()->value;
269
270		// Replace the root, then sift down.
271	29	$this->setRoot($leaf);
272	29	$this->siftDown(0);
273	29	$this->adjustCapacity();
274
275	29	return $value;
276		}
277
278		/**
279		* Sift Up
280		*
281		* @param int $leaf
282		*/
283	44	private function siftUp(int $leaf)
284		{
285	44	for (; $leaf > 0; $leaf = $parent) {
286	36	$parent = $this->parent($leaf);
287
288		// Done when parent priority is greater.
289	36	if ($this->compare($leaf, $parent) < 0) {
290	22	break;
291		}
292
293	18	$this->swap($parent, $leaf);
294		}
295	44	}
296
297		/**
298		* Pushes a value into the queue, with a specified priority.
299		*
300		* @param mixed $value
301		* @param int $priority
302		*/
303	44	public function push($value, int $priority)
304		{
305	44	$this->adjustCapacity();
306
307		// Add new leaf, then sift up to maintain heap,
308	44	$this->heap[] = new PriorityNode($value, $priority, $this->stamp++);
309	44	$this->siftUp(count($this->heap) - 1);
310	44	}
311
312		/**
313		* @inheritDoc
314		*/
315	34	public function toArray(): array
316		{
317	34	$heap = $this->heap;
318	34	$array = [];
319
320	34	while ( ! $this->isEmpty()) {
321	26	$array[] = $this->pop();
322		}
323
324	34	$this->heap = $heap;
325	34	return $array;
326		}
327
328		/**
329		* Get iterator
330		*/
331	7	public function getIterator()
332		{
333	7	while ( ! $this->isEmpty()) {
334	6	yield $this->pop();
335		}
336	7	}
337		}
338

php-ds / polyfill

Push — master ( 8d1df5...05ea10 )

PriorityQueue::toArray() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like