diff options
Diffstat (limited to 'aoc2023-gleam/src/utilities/prioqueue.gleam')
-rw-r--r-- | aoc2023-gleam/src/utilities/prioqueue.gleam | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/aoc2023-gleam/src/utilities/prioqueue.gleam b/aoc2023-gleam/src/utilities/prioqueue.gleam new file mode 100644 index 0000000..abf21b9 --- /dev/null +++ b/aoc2023-gleam/src/utilities/prioqueue.gleam @@ -0,0 +1,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) + } + } +} |