4 type 'a node = Nil | Cons of elt * 'a
8 include Hcons.S with type data = Data.t
11 include Hashtbl.HashedType with type t = Node.t node
18 val equal : t -> t -> bool
20 val node : t -> t node
21 val cons : ?sorted:bool -> elt -> t -> t
24 val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a
25 val map : (elt -> elt) -> t -> t
26 val iter : (elt -> 'a) -> t -> unit
28 val rev_map : (elt -> elt) -> t -> t
30 val mem : elt -> t -> bool
31 val stats : unit -> unit
32 val init : unit -> unit
35 module Make (H : Hcons.SA) : S with type elt = H.t =
38 type 'a node = Nil | Cons of elt * 'a
39 module rec Node : Hcons.S with type data = Data.t = Hcons.Make (Data)
40 and Data : Hashtbl.HashedType with type t = Node.t node =
45 | _,_ when x==y -> true
46 | Cons (a,aa), Cons(b,bb) -> (aa==bb) && (H.equal a b)
50 | Cons(a,aa) -> HASHINT3(PRIME3,Uid.to_int (H.uid a),Uid.to_int( aa.Node.id))
55 let node x = x.Node.node
56 let hash x = x.Node.key
57 let equal = Node.equal
59 let nil = Node.make Nil
60 let stats = Node.stats
62 (* doing sorted insertion allows to make better use of hash consing *)
63 let rec sorted_cons e l =
64 match l.Node.node with
65 | Nil -> Node.make (Cons(e, l))
68 then Node.make (Cons(e, l))
69 else Node.make (Cons(x, sorted_cons e ll))
74 let cons ?(sorted=true) e l =
75 if sorted then sorted_cons e l else cons e l
77 let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
78 let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"
81 let rec loop acc l = match l.Node.node with
83 | Cons (a, aa) -> loop (f a acc) aa
88 let rec loop l = match l.Node.node with
90 | Cons(a, aa) -> cons (f a) (loop aa)
95 let rec loop l = match l.Node.node with
97 | Cons(a,aa) -> (f a);(loop aa)
101 let rev l = fold cons l nil
102 let rev_map f l = fold (fun x acc -> cons (f x) acc) l nil
103 let length l = fold (fun _ c -> c+1) l 0
105 match l.Node.node with
107 | Cons (x, ll) -> x == e || mem e ll