PriorityQueue::__construct() - Code Metrics - Inspection of "Merge pull request #30 from dantudor/patch-11" - php-ds/polyfill - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 30aa88...8c94ac )

by Rudi

created 2016-03-03 20:12 UTC

PriorityQueue::__construct() A

↳ Parent: PriorityQueue

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Metric	Value
dl	0
loc	4
rs	10
cc	1
eloc	2
nc	1
nop	0

<?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;

    /**
     * Initializes a new priority queue.
     */
    public function __construct()
    {
        $this->reset();
    }

    /**
     * @inheritDoc
     */
    public function clear()
    {
        $this->reset();
    }
    
    /**
     * Reset the PriorityQueue to an initialised state.
     */
    private function reset()
    {
        $this->heap     = [];
        $this->stamp    = 0;
        $this->capacity = self::MIN_CAPACITY;
    }

    /**
     * @inheritDoc
     */
    public function copy()
    {
        $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 = $left + 1;

        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			public function __construct($value, int $priority, int $stamp)
34			{
35			$this->value = $value;
36			$this->priority = $priority;
37			$this->stamp = $stamp;
38			}
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;
65
66			/**
67			* Initializes a new priority queue.
68			*/
69			public function __construct()
70			{
71			$this->reset();
72			}
73
74			/**
75			* @inheritDoc
76			*/
77			public function clear()
78			{
79			$this->reset();
80			}
81
82			/**
83			* Reset the PriorityQueue to an initialised state.
84			*/
85			private function reset()
86			{
87			$this->heap = [];
88			$this->stamp = 0;
89			$this->capacity = self::MIN_CAPACITY;
90			}
91
92			/**
93			* @inheritDoc
94			*/
95			public function copy()
96			{
97			$copy = new PriorityQueue();
98
99			$copy->heap = $this->heap;
100			$copy->capacity = $this->capacity;
101
102			return $copy;
103			}
104
105			/**
106			* @inheritDoc
107			*/
108			public function count(): int
109			{
110			return count($this->heap);
111			}
112
113			/**
114			* Returns the value with the highest priority in the priority queue.
115			*
116			* @return mixed
117			*
118			* @throw UnderflowException
119			*/
120			public function peek()
121			{
122			if ($this->isEmpty()) {
123			throw new UnderflowException();
124			}
125
126			return $this->heap[0]->value;
127			}
128
129			/**
130			* Left
131			*
132			* @param int $index
133			*
134			* @return int
135			*/
136			private function left(int $index): int
137			{
138			return ($index * 2) + 1;
139			}
140
141			/**
142			* Right
143			*
144			* @param int $index
145			*
146			* @return int
147			*/
148			private function right(int $index): int
			0 ignored issues – show Unused Code introduced 2016-03-01 00:43 UTC by Report Bug Copy Issue Report This method is not used, and could be removed. Loading history...
149			{
150			return ($index * 2) + 2;
151			}
152
153			/**
154			* Parent
155			*
156			* @param int $index
157			*
158			* @return int
159			*/
160			private function parent(int $index): int
161			{
162			return ($index - 1) / 2;
163			}
164
165			/**
166			* Compare
167			*
168			* @param int $a
169			* @param int $b
170			*
171			* @return integer
172			*/
173			private function compare(int $a, int $b)
174			{
175			$x = $this->heap[$a];
176			$y = $this->heap[$b];
177
178			// Compare priority, using insertion stamp as fallback.
179			return ($x->priority <=> $y->priority) ?: ($y->stamp <=> $x->stamp);
180			}
181
182			/**
183			* Swap
184			*
185			* @param int $a
186			* @param int $b
187			*/
188			private function swap(int $a, int $b)
189			{
190			$temp = $this->heap[$a];
191			$this->heap[$a] = $this->heap[$b];
192			$this->heap[$b] = $temp;
193			}
194
195			/**
196			* Get Largest Leaf
197			*
198			* @param int $parent
199			*
200			* @return int
201			*/
202			private function getLargestLeaf(int $parent)
203			{
204			$left = $this->left($parent);
205			$right = $left + 1;
206
207			if ($right < count($this->heap) && $this->compare($left, $right) < 0) {
208			return $right;
209			}
210
211			return $left;
212			}
213
214			/**
215			* Sift Down
216			*
217			* @param int $node
218			*/
219			private function siftDown(int $node)
220			{
221			$last = floor(count($this->heap) / 2);
222
223			for ($parent = $node; $parent < $last; $parent = $leaf) {
224
225			// Determine the largest leaf to potentially swap with the parent.
226			$leaf = $this->getLargestLeaf($parent);
227
228			// Done if the parent is not greater than its largest leaf
229			if ($this->compare($parent, $leaf) > 0) {
230			break;
231			}
232
233			$this->swap($parent, $leaf);
234			}
235			}
236
237			/**
238			* Set Root
239			*
240			* @param PriorityNode $node
241			*/
242			private function setRoot(PriorityNode $node)
243			{
244			$this->heap[0] = $node;
245			}
246
247			/**
248			* Get Root
249			*
250			* @return PriorityNode
251			*/
252			private function getRoot(): PriorityNode
253			{
254			return $this->heap[0];
255			}
256
257			/**
258			* Returns and removes the value with the highest priority in the queue.
259			*
260			* @return mixed
261			*/
262			public function pop()
263			{
264			if ($this->isEmpty()) {
265			throw new UnderflowException();
266			}
267
268			// Last leaf of the heap to become the new root.
269			$leaf = array_pop($this->heap);
270
271			if (empty($this->heap)) {
272			return $leaf->value;
273			}
274
275			// Cache the current root value to return before replacing with next.
276			$value = $this->getRoot()->value;
277
278			// Replace the root, then sift down.
279			$this->setRoot($leaf);
280			$this->siftDown(0);
281			$this->adjustCapacity();
282
283			return $value;
284			}
285
286			/**
287			* Sift Up
288			*
289			* @param int $leaf
290			*/
291			private function siftUp(int $leaf)
292			{
293			for (; $leaf > 0; $leaf = $parent) {
294			$parent = $this->parent($leaf);
295
296			// Done when parent priority is greater.
297			if ($this->compare($leaf, $parent) < 0) {
298			break;
299			}
300
301			$this->swap($parent, $leaf);
302			}
303			}
304
305			/**
306			* Pushes a value into the queue, with a specified priority.
307			*
308			* @param mixed $value
309			* @param int $priority
310			*/
311			public function push($value, int $priority)
312			{
313			$this->adjustCapacity();
314
315			// Add new leaf, then sift up to maintain heap,
316			$this->heap[] = new PriorityNode($value, $priority, $this->stamp++);
317			$this->siftUp(count($this->heap) - 1);
318			}
319
320			/**
321			* @inheritDoc
322			*/
323			public function toArray(): array
324			{
325			$heap = $this->heap;
326			$array = [];
327
328			while ( ! $this->isEmpty()) {
329			$array[] = $this->pop();
330			}
331
332			$this->heap = $heap;
333			return $array;
334			}
335
336			/**
337			* Get iterator
338			*/
339			public function getIterator()
340			{
341			while ( ! $this->isEmpty()) {
342			yield $this->pop();
343			}
344			}
345			}
346

php-ds / polyfill

Push — master ( 30aa88...8c94ac )

PriorityQueue::__construct() A

Complexity

Size

Duplication

Duplication Side-by-Side

Filter issues like