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