PriorityQueue::toArray() - Code Metrics - Inspection of "Added Priority Queue class - not tested yet" - MBHFramework/structures - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 1.x ( 35650c...267a25 )

by Ulises Jeremias

created 2017-12-26 02:51 UTC

PriorityQueue::toArray() A

↳ Parent: PriorityQueue

Complexity

Conditions	2
Paths	2

Size

Total Lines	12
Code Lines	6

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	2
eloc	6
nc	2
nop	0
dl	0
loc	12
rs	9.4285
c	0
b	0
f	0

<?php namespace Mbh\Collection;

/**
 * MBHFramework
 *
 * @link      https://github.com/MBHFramework/mbh-framework
 * @copyright Copyright (c) 2017 Ulises Jeremias Cornejo Fandos
 * @license   https://github.com/MBHFramework/mbh-framework/blob/master/LICENSE (MIT License)
 */

use Mbh\Collection\Interfaces\Collection as CollectionInterface;
use Traversable;
use ArrayAccess;
use IteratorAggregate;
use Error;
use OutOfBoundsException;

/**
 * A PriorityQueue is very similar to a Queue. Values are pushed into the queue
 * with an assigned priority, and the value with the highest priority will
 * always be at the front of the queue.
 *
 * @package structures
 * @author Ulises Jeremias Cornejo Fandos <[email protected]>
 */

class PriorityQueue implements ArrayAccess, CollectionInterface, IteratorAggregate
{
    use Traits\Collection;
    use Traits\SquaredCapacity;

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

    /**
     * @var FixedArray
     */
    private $heap;

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

    /**
     * Creates a new instance.
     */
    public function __construct()
    {
        $heap = FixedArray::fromArray([]);

    }

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

    }

    /**
     * @inheritDoc
     */
    public function copy()
    {
        $copy = new PriorityQueue;
        $copy->heap     = $this->heap->copy();
        $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->first()->value;
    }

    /**
     * Returns the index of a node's left leaf.
     *
     * @param int $index The index of the node.
     *
     * @return int The index of the left leaf.
     */
    private function left(int $index): int
    {
        return ($index * 2) + 1;
    }

    /**
     * Returns the index of a node's right leaf.
     *
     * @param int $index The index of the node.
     *
     * @return int The index of the right leaf.
     */
    private function right(int $index): int
    {
        return ($index * 2) + 2;
    }

    /**
     * Returns the index of a node's parent node.
     *
     * @param int $index The index of the node.
     *
     * @return int The index of the parent.
     */
    private function parent(int $index): int
    {
        return ($index - 1) / 2;
    }

    /**
     * Compares two indices of the heap.
     *
     * @param int $a
     * @param int $b
     *
     * @return int
     */
    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);
    }

    /**
     * Swaps the nodes at two indices of the heap.
     *
     * @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;
    }

    /**
     * Returns the index of a node's largest leaf node.
     *
     * @param int $parent the parent node.
     *
     * @return int the index of the node's largest leaf node.
     */
    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;
    }

    /**
     * Starts the process of sifting down a given node index to ensure that
     * the heap's properties are preserved.
     *
     * @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);
        }
    }

    /**
     * Sets the root node and sifts it down the heap.
     *
     * @param PriorityNode $node
     */
    private function setRoot(PriorityNode $node)
    {
        $this->heap->set(0, $node);
        $this->siftDown(0);
    }

    /**
     * Returns the root node of the heap.
     *
     * @return PriorityNode
     */
    private function getRoot(): PriorityNode
    {
        return $this->heap->first();
    }

    /**
     * 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 = $this->heap->pop();

        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->checkCapacity();

        return $value;
    }

    /**
     * Sifts a node up the heap until it's in the right position.
     *
     * @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->checkCapacity();

        // 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->copy();
        $array = [];

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

        $this->heap = $heap;

        return $array;
    }

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

/**
 * @internal
 */
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;
    }
}


1			<?php namespace Mbh\Collection;
2
3			/**
4			* MBHFramework
5			*
6			* @link https://github.com/MBHFramework/mbh-framework
7			* @copyright Copyright (c) 2017 Ulises Jeremias Cornejo Fandos
8			* @license https://github.com/MBHFramework/mbh-framework/blob/master/LICENSE (MIT License)
9			*/
10
11			use Mbh\Collection\Interfaces\Collection as CollectionInterface;
12			use Traversable;
13			use ArrayAccess;
14			use IteratorAggregate;
15			use Error;
16			use OutOfBoundsException;
17
18			/**
19			* A PriorityQueue is very similar to a Queue. Values are pushed into the queue
20			* with an assigned priority, and the value with the highest priority will
21			* always be at the front of the queue.
22			*
23			* @package structures
24			* @author Ulises Jeremias Cornejo Fandos <[email protected]>
25			*/
26
27			class PriorityQueue implements ArrayAccess, CollectionInterface, IteratorAggregate
28			{
29			use Traits\Collection;
30			use Traits\SquaredCapacity;
31
32			/**
33			* @var int
34			*/
35			const MIN_CAPACITY = 8;
36
37			/**
38			* @var FixedArray
39			*/
40			private $heap;
41
42			/**
43			* @var int
44			*/
45			private $stamp = 0;
46
47			/**
48			* Creates a new instance.
49			*/
50			public function __construct()
51			{
52			$heap = FixedArray::fromArray([]);
			0 ignored issues – show Unused Code introduced 2017-12-26 02:54 UTC by Report Bug Copy Issue Report The assignment to `$heap` is dead and can be removed. Loading history...
53			}
54
55			/**
56			* @inheritDoc
57			*/
58			public function clear()
59			{
60			$this->heap = FixedArray::fromArray([]);
61			$this->stamp = 0;
62			$this->capacity = self::MIN_CAPACITY;
			0 ignored issues – show Bug Best Practice introduced 2017-12-26 02:54 UTC by Report Bug Copy Issue Report The property `capacity` does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly. Loading history...
63			}
64
65			/**
66			* @inheritDoc
67			*/
68			public function copy()
69			{
70			$copy = new PriorityQueue;
71			$copy->heap = $this->heap->copy();
72			$copy->capacity = $this->capacity;
			0 ignored issues – show Bug Best Practice introduced 2017-12-26 02:54 UTC by Report Bug Copy Issue Report The property `capacity` does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly. Loading history...
73			return $copy;
74			}
75
76			/**
77			* @inheritDoc
78			*/
79			public function count(): int
80			{
81			return count($this->heap);
82			}
83
84			/**
85			* Returns the value with the highest priority in the priority queue.
86			*
87			* @return mixed
88			*
89			* @throw UnderflowException
90			*/
91			public function peek()
92			{
93			if ($this->isEmpty()) {
94			throw new UnderflowException();
			0 ignored issues – show Bug introduced 2017-12-26 02:54 UTC by Report Bug Copy Issue Report The type `Mbh\Collection\UnderflowException` was not found. Did you mean `UnderflowException`? If so, make sure to prefix the type with `\`. Loading history...
95			}
96			return $this->heap->first()->value;
97			}
98
99			/**
100			* Returns the index of a node's left leaf.
101			*
102			* @param int $index The index of the node.
103			*
104			* @return int The index of the left leaf.
105			*/
106			private function left(int $index): int
107			{
108			return ($index * 2) + 1;
109			}
110
111			/**
112			* Returns the index of a node's right leaf.
113			*
114			* @param int $index The index of the node.
115			*
116			* @return int The index of the right leaf.
117			*/
118			private function right(int $index): int
119			{
120			return ($index * 2) + 2;
121			}
122
123			/**
124			* Returns the index of a node's parent node.
125			*
126			* @param int $index The index of the node.
127			*
128			* @return int The index of the parent.
129			*/
130			private function parent(int $index): int
131			{
132			return ($index - 1) / 2;
133			}
134
135			/**
136			* Compares two indices of the heap.
137			*
138			* @param int $a
139			* @param int $b
140			*
141			* @return int
142			*/
143			private function compare(int $a, int $b)
144			{
145			$x = $this->heap[$a];
146			$y = $this->heap[$b];
147
148			// Compare priority, using insertion stamp as fallback.
149			return ($x->priority <=> $y->priority) ?: ($y->stamp <=> $x->stamp);
150			}
151
152			/**
153			* Swaps the nodes at two indices of the heap.
154			*
155			* @param int $a
156			* @param int $b
157			*/
158			private function swap(int $a, int $b)
159			{
160			$temp = $this->heap[$a];
161			$this->heap[$a] = $this->heap[$b];
162			$this->heap[$b] = $temp;
163			}
164
165			/**
166			* Returns the index of a node's largest leaf node.
167			*
168			* @param int $parent the parent node.
169			*
170			* @return int the index of the node's largest leaf node.
171			*/
172			private function getLargestLeaf(int $parent)
173			{
174			$left = $this->left($parent);
175			$right = $this->right($parent);
176
177			if ($right < count($this->heap) && $this->compare($left, $right) < 0) {
178			return $right;
179			}
180
181			return $left;
182			}
183
184			/**
185			* Starts the process of sifting down a given node index to ensure that
186			* the heap's properties are preserved.
187			*
188			* @param int $node
189			*/
190			private function siftDown(int $node)
191			{
192			$last = floor(count($this->heap) / 2);
193
194			for ($parent = $node; $parent < $last; $parent = $leaf) {
195			// Determine the largest leaf to potentially swap with the parent.
196			$leaf = $this->getLargestLeaf($parent);
197
198			// Done if the parent is not greater than its largest leaf
199			if ($this->compare($parent, $leaf) > 0) {
200			break;
201			}
202
203			$this->swap($parent, $leaf);
204			}
205			}
206
207			/**
208			* Sets the root node and sifts it down the heap.
209			*
210			* @param PriorityNode $node
211			*/
212			private function setRoot(PriorityNode $node)
213			{
214			$this->heap->set(0, $node);
215			$this->siftDown(0);
216			}
217
218			/**
219			* Returns the root node of the heap.
220			*
221			* @return PriorityNode
222			*/
223			private function getRoot(): PriorityNode
224			{
225			return $this->heap->first();
226			}
227
228			/**
229			* Returns and removes the value with the highest priority in the queue.
230			*
231			* @return mixed
232			*/
233			public function pop()
234			{
235			if ($this->isEmpty()) {
236			throw new UnderflowException();
237			}
238
239			// Last leaf of the heap to become the new root.
240			$leaf = $this->heap->pop();
241
242			if (empty($this->heap)) {
243			return $leaf->value;
244			}
245
246			// Cache the current root value to return before replacing with next.
247			$value = $this->getRoot()->value;
248			// Replace the root, then sift down.
249			$this->setRoot($leaf);
250			$this->checkCapacity();
251
252			return $value;
253			}
254
255			/**
256			* Sifts a node up the heap until it's in the right position.
257			*
258			* @param int $leaf
259			*/
260			private function siftUp(int $leaf)
261			{
262			for (; $leaf > 0; $leaf = $parent) {
263			$parent = $this->parent($leaf);
264
265			// Done when parent priority is greater.
266			if ($this->compare($leaf, $parent) < 0) {
267			break;
268			}
269
270			$this->swap($parent, $leaf);
271			}
272			}
273
274			/**
275			* Pushes a value into the queue, with a specified priority.
276			*
277			* @param mixed $value
278			* @param int $priority
279			*/
280			public function push($value, int $priority)
281			{
282			$this->checkCapacity();
283
284			// Add new leaf, then sift up to maintain heap,
285			$this->heap[] = new PriorityNode($value, $priority, $this->stamp++);
286
287			$this->siftUp(count($this->heap) - 1);
288			}
289
290			/**
291			* @inheritDoc
292			*/
293			public function toArray(): array
294			{
295			$heap = $this->heap->copy();
296			$array = [];
297
298			while (!$this->isEmpty()) {
299			$array[] = $this->pop();
300			}
301
302			$this->heap = $heap;
303
304			return $array;
305			}
306
307			/**
308			* @inheritDoc
309			*/
310			public function getIterator()
311			{
312			while (!$this->isEmpty()) {
313			yield $this->pop();
314			}
315			}
316			}
317
318			/**
319			* @internal
320			*/
321			final class PriorityNode
322			{
323			/**
324			* @var mixed
325			*/
326			public $value;
327
328			/**
329			* @var int
330			*/
331			public $priority;
332
333			/**
334			* @var int
335			*/
336			public $stamp;
337
338			/**
339			* @param mixed $value
340			* @param int $priority
341			* @param int $stamp
342			*/
343			public function __construct($value, int $priority, int $stamp)
344			{
345			$this->value = $value;
346			$this->priority = $priority;
347			$this->stamp = $stamp;
348			}
349			}
350

MBHFramework / structures

Push — 1.x ( 35650c...267a25 )

PriorityQueue::toArray() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like