plugin/multiset.ml

   1
   2 module type OrderedType = Eset.OrderedType
   3
   4 module type S = sig
   5
   6   type elt
   7   type t
   8
   9   val compare : t -> t -> int
  10   val empty : t
  11   val is_empty : t -> bool
  12   val singleton : elt -> t
  13   val upd : elt -> int -> t -> t
  14   val add : elt -> t -> t
  15   val add_occ : elt -> int -> t -> t
  16   val find : elt -> t -> int
  17   val union : t -> t -> t
  18   val merge_f : (int -> int -> int) -> t -> t -> t
  19   val fold : (elt -> int -> 'a -> 'a) -> t -> 'a -> 'a
  20   val for_all : (elt -> int -> bool) -> t -> bool
  21   val exists : (elt -> int -> bool) -> t -> bool
  22   val subset : t -> t -> bool
  23   val to_list : t -> (elt * int) list
  24
  25 end
  26
  27 module OrdInt = struct
  28   type t = int let compare = Pervasives.compare
  29 end
  30
  31 module Make (Ord : OrderedType) : S with type elt = Ord.t = struct
  32
  33   module M = Emap.Make1 (Ord) (OrdInt)
  34   include M
  35
  36   type elt = Ord.t
  37
  38   let compare = M.compare
  39
  40   let singleton x = M.add x 1 empty
  41
  42   let upd = M.add
  43
  44   let add_occ x occ mset =
  45     let occ' = if mem x mset then find x mset else 0 in
  46     upd x (occ+occ') mset
  47
  48   let add x mset = add_occ x 1 mset
  49
  50   let find x mset = if mem x mset then M.find x mset else 0
  51
  52   let union = merge_f (+)
  53
  54   let subset mset1 mset2 =
  55     let f x occ res = res && (occ <= find x mset2) in
  56     M.fold f mset1 true
  57
  58 end