module type OrderedType = sig
  include Map.OrderedType
end

module type S = sig
  include Map.S

  val merge_f : ('a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t
  val split_couple : ('a * 'b) t -> 'a t * 'b t
  val combine : 'a t -> 'b t -> ('a * 'b) t
  val error_find : key -> 'a t -> exn -> 'a
  val of_list : (key * 'a) list -> 'a t
  val to_list : 'a t -> (key * 'a) list
end

module Make (Ord : OrderedType) : S with type key = Ord.t = struct
  include Map.Make (Ord)

  let merge_f f map1 map2 =
    let f_merge _ e1 e2 = match e1, e2 with
      | None, None -> None
      | Some e, None | None, Some e -> Some e
      | Some e1, Some e2 -> Some (f e1 e2) in
    merge f_merge map1 map2

  let split_couple map =
    let f key (a, b) (resa, resb) = (add key a resa, add key b resb) in
    fold f map (empty, empty)

  let combine mapa mapb =
    let f key a res =
      if mem key mapb then add key (a, find key mapb) res
      else res in
    fold f mapa empty

  let error_find x map error = if mem x map then find x map else raise error

  let of_list l =
    let f map (key, binding) = add key binding map in
    List.fold_left f empty l

  let to_list = bindings
end


module type S1 = sig
  type key
  type img
  type t
  val empty : t
  val is_empty : t -> bool
  val mem : key -> t -> bool
  val add : key -> img -> t -> t
  val singleton : key -> img -> t
  val remove : key -> t -> t
  val merge_f : (img -> img -> img) -> t -> t -> t
  val merge : (key -> img option -> img option -> img option) -> t -> t -> t
  val compare : t -> t -> int
  val equal : t -> t -> bool
  val iter : (key -> img -> unit) -> t -> unit
  val fold : (key -> img -> 'b -> 'b) -> t -> 'b -> 'b
  val for_all : (key -> img -> bool) -> t -> bool
  val exists : (key -> img -> bool) -> t -> bool
  val filter : (key -> img -> bool) -> t -> t
  val partition : (key -> img -> bool) -> t -> t * t
  val cardinal : t -> int
  val bindings : t -> (key * img) list
  val min_binding : t -> key * img
  val max_binding : t -> key * img
  val choose : t -> key * img
  val split : key -> t -> t * img option * t
  val find : key -> t -> img
  val map : (img -> img) -> t -> t
  val mapi : (key -> img -> img) -> t -> t
  val error_find : key -> t -> exn -> img
  val of_list : (key * img) list -> t
  val to_list : t -> (key * img) list
end

module Make1 (Key : OrderedType) (Img : OrderedType)
  : S1 with type key = Key.t and type img = Img.t =
struct

  module M = Make (Key)

  type key = M.key
  type img = Img.t
  type t = img M.t

  let empty = M.empty
  let is_empty = M.is_empty
  let mem = M.mem
  let add = M.add
  let singleton = M.singleton
  let remove = M.remove
  let merge_f = M.merge_f
  let merge = M.merge
  let compare = M.compare Img.compare
  let equal = M.equal (fun img1 img2 -> Img.compare img1 img2 = 0)
  let iter = M.iter
  let fold = M.fold
  let for_all = M.for_all
  let exists = M.exists
  let filter = M.filter
  let partition = M.partition
  let cardinal = M.cardinal
  let bindings = M.bindings
  let min_binding = M.min_binding
  let max_binding = M.max_binding
  let choose = M.choose
  let split = M.split
  let find = M.find
  let map = M.map
  let mapi = M.mapi
  let error_find = M.error_find
  let of_list = M.of_list
  let to_list = M.to_list

end