ptset.ml

   1 (***************************************************************************)
   2 (* Implementation for sets of positive integers implemented as deeply hash-*)
   3 (* consed Patricia trees. Provide fast set operations, fast membership as  *)
   4 (* well as fast min and max elements. Hash consing provides O(1) equality  *)
   5 (* checking                                                                *)
   6 (*                                                                         *)
   7 (***************************************************************************)
   8 INCLUDE "utils.ml"
   9 module type S =
  10 sig
  11   include Set.S
  12   val intersect : t -> t -> bool
  13   val is_singleton : t -> bool
  14   val mem_union : t -> t -> t
  15   val hash : t -> int
  16   val uid : t -> int
  17   val uncons : t -> elt*t
  18   val from_list : elt list -> t
  19 end
  20
  21 module Int : S with type elt = int =
  22 struct
  23   type elt = int
  24   external hash_elt : elt -> int = "%identity"
  25   external uid_elt : elt -> int = "%identity"
  26   let equal_elt : elt -> elt -> bool = (==);;
  27
  28 DEFINE USE_PTSET_INCLUDE
  29 INCLUDE "ptset_include.ml"
  30
  31 end
  32 module Make ( H : Hcons.S ) : S with type elt = H.t =
  33 struct
  34   type elt = H.t
  35   let hash_elt = H.hash
  36   let uid_elt = H.uid
  37   let equal_elt = H.equal
  38 INCLUDE "ptset_include.ml"
  39 end
  40
  41 (* Have to benchmark wheter this whole include stuff is worth it *)
  42 module I : S with type elt = int = Make ( struct type t = int
  43                                                  type data = t
  44                                                  external hash : t -> int = "%identity"
  45                                                  external uid : t -> int = "%identity"
  46                                                  let equal : t -> t -> bool = (==)
  47                                                  external make : t -> int = "%identity"
  48                                                  external node : t -> int = "%identity"
  49
  50                                           end
  51                                           )