(***************************************************************************)
(* Implementation for sets of positive integers implemented as deeply hash-*)
(* consed Patricia trees. Provide fast set operations, fast membership as  *)
(* well as fast min and max elements. Hash consing provides O(1) equality  *)
(* checking                                                                *)
(*                                                                         *)
(***************************************************************************)
INCLUDE "utils.ml"
module type S = 
sig
  include Set.S
  val intersect : t -> t -> bool
  val is_singleton : t -> bool
  val mem_union : t -> t -> t
  val hash : t -> int
  val uid : t -> int
  val uncons : t -> elt*t
  val from_list : elt list -> t 
end

module Int : S with type elt = int = 
struct
  type elt = int
  external hash_elt : elt -> int = "%identity"
  external uid_elt : elt -> int = "%identity"
  let equal_elt : elt -> elt -> bool = (==);;
    
DEFINE USE_PTSET_INCLUDE
INCLUDE "ptset_include.ml"

end
module Make ( H : Hcons.S ) : S with type elt = H.t =
struct
  type elt = H.t
  let hash_elt = H.hash
  let uid_elt = H.uid 
  let equal_elt = H.equal
INCLUDE "ptset_include.ml"
end

(* Have to benchmark wheter this whole include stuff is worth it *)
module I : S with type elt = int = Make ( struct type t = int 
						 type data = t
						 external hash : t -> int = "%identity"
						 external uid : t -> int = "%identity"
						 let equal : t -> t -> bool = (==)
						 external make : t -> int = "%identity"
						 external node : t -> int = "%identity"
						   
					  end
					  )