Completed
Pull Request — master (#43)
by
unknown
08:27
created

PriorityNode::__construct()   A

Complexity

Conditions 1
Paths 1

Size

Total Lines 6
Code Lines 4

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 0
CRAP Score 2

Importance

Changes 0
Metric Value
dl 0
loc 6
ccs 0
cts 6
cp 0
rs 9.4285
c 0
b 0
f 0
cc 1
eloc 4
nc 1
nop 3
crap 2
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 by
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