1 files changed, 62 insertions, 0 deletions
diff --git a/aoc2023/src/utilities/prioqueue.gleam b/aoc2023/src/utilities/prioqueue.gleam
new file mode 100644
index 0000000..640748b
--- /dev/null
+++ b/aoc2023/src/utilities/prioqueue.gleam
@@ -0,0 +1,62 @@
+//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)
+    }
+  }
+}