module type OrderedType = Eset.OrderedType

module type S = sig

  type elt
  type t

  val compare : t -> t -> int
  val empty : t
  val is_empty : t -> bool
  val singleton : elt -> t
  val upd : elt -> int -> t -> t
  val add : elt -> t -> t
  val add_occ : elt -> int -> t -> t
  val find : elt -> t -> int
  val union : t -> t -> t
  val merge_f : (int -> int -> int) -> t -> t -> t
  val fold : (elt -> int -> 'a -> 'a) -> t -> 'a -> 'a
  val for_all : (elt -> int -> bool) -> t -> bool
  val exists : (elt -> int -> bool) -> t -> bool
  val subset : t -> t -> bool
  val to_list : t -> (elt * int) list

end

module OrdInt = struct
  type t = int let compare = Pervasives.compare
end

module Make (Ord : OrderedType) : S with type elt = Ord.t = struct

  module M = Emap.Make1 (Ord) (OrdInt)
  include M

  type elt = Ord.t

  let compare = M.compare

  let singleton x = M.add x 1 empty

  let upd = M.add

  let add_occ x occ mset =
    let occ' = if mem x mset then find x mset else 0 in
    upd x (occ+occ') mset

  let add x mset = add_occ x 1 mset

  let find x mset = if mem x mset then M.find x mset else 0

  let union = merge_f (+)

  let subset mset1 mset2 =
    let f x occ res = res && (occ <= find x mset2) in
    M.fold f mset1 true

end