PriorityQueue::count() - Code Metrics - Inspection of "Removed constructor declaration from the sequence..." - php-ds/polyfill - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Pull Request — master (#43)

unknown

created 2017-09-02 12:29 UTC

PriorityQueue::count() A

↳ Parent: PriorityQueue

Complexity

Conditions	1
Paths	1

Size

Total Lines	4
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	2

Importance

Changes

Metric	Value
dl	0
loc	4
ccs	0
cts	4
cp	0
rs	10
c	0
b	0
f	0
cc	1
eloc	2
nc	1
nop	0
crap	2

<?php
namespace Ds;

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 Ds
 */
final class PriorityQueue implements \IteratorAggregate, Collection
{
    use Traits\GenericCollection;
    use Traits\SquaredCapacity;

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

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

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

    /**
     * Creates a new instance.
     */
    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;
    }

    /**
     * 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[0] = $node;
        $this->siftDown(0);
    }

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

php-ds / polyfill

Pull Request — master (#43)

PriorityQueue::count() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like