PriorityQueue::swap() - Code Metrics - MBHFramework/structures - Measure and Improve Code Quality continuously with Scrutinizer

PriorityQueue::swap() A
last analyzed 2018-09-26 02:10 UTC

↳ Parent: PriorityQueue

Complexity

Conditions	1
Paths	1

Size

Total Lines	5
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
eloc	3
dl	0
loc	5
rs	10
c	0
b	0
f	0
cc	1
nc	1
nop	2

<?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 Mbh\Collection\Internal\PriorityNode;
use Mbh\Interfaces\Allocated as AllocatedInterface;
use Mbh\Traits\SquaredCapacity;
use Mbh\Traits\EmptyGuard;
use Traversable;
use ArrayAccess;
use IteratorAggregate;
use Error;
use OutOfBoundsException;
use UnderflowException;

/**
 * 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 AllocatedInterface, ArrayAccess, CollectionInterface, IteratorAggregate
{
    use Traits\Collection;
    use SquaredCapacity;
    use EmptyGuard;

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

    /**
     * @inheritDoc
     */
    protected $capacity = self::MIN_CAPACITY;

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

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

    /**
     * Creates a new instance.
     */
    public function __construct()
    {
        $this->heap = FixedArray::empty();
    }

    /**
     * @inheritDoc
     */
    public function clear()
    {
        $this->heap     = FixedArray::empty();
        $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()
    {
        $this->emptyGuard(__METHOD__);
        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()
    {
        $this->emptyGuard(__METHOD__);

        // 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();
        }
    }
}


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

MBHFramework / structures

PriorityQueue::swap() A last analyzed 2018-09-26 02:10 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

PriorityQueue::swap() A
last analyzed 2018-09-26 02:10 UTC