summaryrefslogtreecommitdiffstats
path: root/vendor/ipl/stdlib/src/PriorityQueue.php
blob: a50b31d4c1396696a39cee949490250223b314ba (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
<?php

namespace ipl\Stdlib;

use Generator;
use SplPriorityQueue;

/**
 * Stable priority queue that also maintains insertion order for items with the same priority
 */
class PriorityQueue extends SplPriorityQueue
{
    protected $serial = PHP_INT_MAX;

    /**
     * @inheritDoc
     *
     * Maintains insertion order for items with the same priority.
     */
    public function insert($value, $priority): bool
    {
        return parent::insert($value, [$priority, $this->serial--]);
    }

    /**
     * Yield all items as priority-value pairs
     *
     * @return Generator
     */
    public function yieldAll()
    {
        // Clone queue because the SplPriorityQueue acts as a heap and thus items are removed upon iteration
        $queue = clone $this;

        $queue->setExtractFlags(static::EXTR_BOTH);

        foreach ($queue as $item) {
            yield $item['priority'][0] => $item['data'];
        }
    }
}