Something went wrong. Try again.
An implementation of the PubGrub version solving algorithm in OCaml.
Something went wrong. Try again.
955 B · 36 lines
OCaml
at main
12345678910111213141516171819202122232425262728293031323334353637module Make (N : Types.NameType) (P : Set.OrderedType) = struct module NMap = Map.Make (N)
module Entry = struct type t = P.t * N.t
let compare (p1, n1) (p2, n2) = let c = P.compare p1 p2 in if c <> 0 then c else N.compare n1 n2 end
module EntrySet = Set.Make (Entry)
type t = { priority : P.t NMap.t; by_priority : EntrySet.t }
let empty = { priority = NMap.empty; by_priority = EntrySet.empty }
let insert pq n p = { priority = NMap.add n p pq.priority; by_priority = EntrySet.add (p, n) pq.by_priority; }
let remove pq n = match NMap.find_opt n pq.priority with | None -> pq | Some p -> { priority = NMap.remove n pq.priority; by_priority = EntrySet.remove (p, n) pq.by_priority; }
let update pq n p = insert (remove pq n) n p let min_elt pq = EntrySet.min_elt_opt pq.by_priority let to_list pq = EntrySet.elements pq.by_priorityend