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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
//adapted from https://github.com/byronanderson/adventofcode2021/blob/main/gleam_advent/src/priority_queue.gleam
import gleam/dict.{type Dict}
type Ref
@external(erlang, "erlang", "make_ref")
fn make_ref() -> Ref
type PQueue(a)
pub opaque type PriorityQueue(a) {
PriorityQueue(queue: PQueue(#(a, Ref)), refs: Dict(a, Ref))
}
type OutResult(a) {
Empty
Value(a, Int)
}
@external(erlang, "pqueue2", "new")
fn new_() -> PQueue(a)
@external(erlang, "pqueue2", "in")
fn insert_(item: a, prio: Int, queue: PQueue(a)) -> PQueue(a)
@external(erlang, "pqueue2", "pout")
fn pop_(queue: PQueue(a)) -> #(OutResult(a), PQueue(a))
pub fn new() -> PriorityQueue(a) {
PriorityQueue(queue: new_(), refs: dict.new())
}
pub fn insert(
queue: PriorityQueue(a),
value: a,
priority: Int,
) -> PriorityQueue(a) {
let ref = make_ref()
let refs =
queue.refs
|> dict.insert(value, ref)
PriorityQueue(
refs: refs,
queue: insert_(#(value, ref), priority, queue.queue),
)
}
pub fn pop(queue: PriorityQueue(a)) -> Result(#(a, PriorityQueue(a)), Nil) {
case pop_(queue.queue) {
#(Value(#(value, ref), _priority), pqueue) -> {
let assert Ok(recently_enqueued_ref) = dict.get(queue.refs, value)
case recently_enqueued_ref == ref {
True -> Ok(#(value, PriorityQueue(refs: queue.refs, queue: pqueue)))
False -> pop(PriorityQueue(refs: queue.refs, queue: pqueue))
}
}
#(Empty, _pqueue) -> {
Error(Nil)
}
}
}
|
