PriorityNode - Code Metrics - Inspection of "Updated internal class" - MBHFramework/structures - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — 1.x ( d6cfb5...49e776 )

by Ulises Jeremias

created 2017-12-30 23:34 UTC

PriorityNode A

↳ Parent: Project

Complexity

Total Complexity

Size/Duplication

Total Lines	27
Duplicated Lines	0 %

Importance

Changes

Metric	Value
dl	0
loc	27
rs	10
c	0
b	0
f	0
wmc	1

<?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\Interfaces\Allocated as AllocatedInterface;
use Mbh\Traits\SquaredCapacity;
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;

    /**
     * @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()
    {
        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)
filter:
    dependency_paths: ["lib/*"]
    {
        $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();
        }
    }
}


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

MBHFramework / structures

Push — 1.x ( d6cfb5...49e776 )

PriorityNode A

Complexity

Size/Duplication

Importance

Duplication Side-by-Side

Filter issues like