PriorityQueue::siftUp() - Code Metrics - Inspection of "Fix map apply" - php-ds/polyfill - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 6b7d9f...bc2135 )

by Rudi

created 2016-07-28 09:59 UTC

PriorityQueue::siftUp() A

↳ Parent: PriorityQueue

Complexity

Conditions	3
Paths	3

Size

Total Lines	13
Code Lines	6

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
dl	0
loc	13
rs	9.4285
c	0
b	0
f	0
cc	3
eloc	6
nc	3
nop	1

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

    /**
     * Initializes a new priority queue.
     */
    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;
    }

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

php-ds / polyfill

Push — master ( 6b7d9f...bc2135 )

PriorityQueue::siftUp() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like