-
-
-type elt = int
-
-type t = { id : int;
- key : int; (* hash *)
- node : node;
- }
-and node =
- | Empty
- | Leaf of int
- | Branch of int * int * t * t
-
-
-(* faster if outside of a module *)
-let hash_node x = match x with
- | Empty -> 0
- | Leaf i -> (i+1) land max_int
- (* power of 2 +/- 1 are fast ! *)
- | Branch (b,i,l,r) ->
- ((b lsl 1)+ b + i+(i lsl 4) + (l.key lsl 5)-l.key
- + (r.key lsl 7) - r.key) land max_int
-
-module Node =
- struct
- type _t = t
- type t = _t
- external hash : t -> int = "%field1"
+INCLUDE "utils.ml"
+module type S =
+sig
+ type elt
+
+ type 'a node
+ module rec Node : sig
+ include Hcons.S with type data = Data.t
+ end
+ and Data : sig
+ include
+ Hashtbl.HashedType with type t = Node.t node
+ end
+ type data = Data.t
+ type t = Node.t
+
+
+ val empty : t
+ val is_empty : t -> bool
+ val mem : elt -> t -> bool
+ val add : elt -> t -> t
+ val singleton : elt -> t
+ val remove : elt -> t -> t
+ val union : t -> t -> t
+ val inter : t -> t -> t
+ val diff : t -> t -> t
+ val compare : t -> t -> int
+ val equal : t -> t -> bool
+ val subset : t -> t -> bool
+ val iter : (elt -> unit) -> t -> unit
+ val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
+ val for_all : (elt -> bool) -> t -> bool
+ val exists : (elt -> bool) -> t -> bool
+ val filter : (elt -> bool) -> t -> t
+ val partition : (elt -> bool) -> t -> t * t
+ val cardinal : t -> int
+ val elements : t -> elt list
+ val min_elt : t -> elt
+ val max_elt : t -> elt
+ val choose : t -> elt
+ val split : elt -> t -> t * bool * t
+
+ val intersect : t -> t -> bool
+ val is_singleton : t -> bool
+ val mem_union : t -> t -> t
+ val hash : t -> int
+ val uid : t -> Uid.t
+ val uncons : t -> elt*t
+ val from_list : elt list -> t
+ val make : data -> t
+ val node : t -> data
+
+ val with_id : Uid.t -> t
+end
+
+module Make ( H : Hcons.SA ) : S with type elt = H.t =
+struct
+ type elt = H.t
+ type 'a node =
+ | Empty
+ | Leaf of elt
+ | Branch of int * int * 'a * 'a
+
+ module rec Node : Hcons.S with type data = Data.t = Hcons.Make (Data)
+ and Data : Hashtbl.HashedType with type t = Node.t node =
+ struct
+ type t = Node.t node