module type S =
sig
include Map.S
val minimum: 'a t -> key * 'a
val find_remove: key -> 'a t -> 'a * 'a t
val update: key -> ('a -> 'a) -> 'a t -> 'a t
val restrict: (key -> bool) -> 'a t -> 'a t
end
module Make(Ord: Map.OrderedType) = struct
include Map.Make(Ord)
exception Minimum
let minimum m =
let r = ref None in
try
iter (fun key data -> r := Some (key, data); raise Minimum) m;
raise Not_found
with Minimum ->
match !r with
| Some binding ->
binding
| None ->
assert false
let find_remove x m =
find x m, remove x m
let rec update x f m =
let data = find x m in
let data' = f data in
if data == data' then m else add x data' m
let restrict p m =
fold (fun x d m ->
if p x then
add x d m
else
m
) m empty
end