Debian Codegraph @

vendor/ipl/stdlib/src/PriorityQueue.php

raw
1 <?php
2
3 namespace ipl\Stdlib;
4
5 use Generator;
6 use SplPriorityQueue;
7
8 /**
9 * Stable priority queue that also maintains insertion order for items with the same priority
10 *
11 * @template TPriority
12 * @template TValue
13 * @extends SplPriorityQueue<array{TPriority, int}, TValue>
14 */
15 class PriorityQueue extends SplPriorityQueue
16 {
17 /** @var int Decreasing insertion counter for stable ordering at equal priorities */
18 protected int $serial = PHP_INT_MAX;
19
20 /**
21 * Insert an element in the queue, maintaining insertion order for equal priorities
22 *
23 * @param TValue $value
24 * @param TPriority $priority
25 *
26 * @return true
27 */
28 public function insert(mixed $value, mixed $priority): true
29 {
30 return parent::insert($value, [$priority, $this->serial--]);
31 }
32
33 /**
34 * Yield all items as priority-value pairs
35 *
36 * @return Generator<TPriority, TValue>
37 */
38 public function yieldAll(): Generator
39 {
40 // Clone the queue because SplPriorityQueue acts as a heap and removes items upon iteration.
41 $queue = clone $this;
42
43 $queue->setExtractFlags(static::EXTR_BOTH);
44
45 foreach ($queue as $item) {
46 /** @var array{priority: array{0: TPriority, 1: int}, data: TValue} $item */
47 yield $item['priority'][0] => $item['data'];
48 }
49 }
50 }