| 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 |
} |