.

[SXSI/xpathcomp.git] / hlist.ml

diff --git a/hlist.ml b/hlist.ml
index cd3c90d..0e50d61 100644 (file)
--- a/hlist.ml
+++ b/hlist.ml
@@ -2,9 +2,19 @@ INCLUDE "utils.ml"
 module type S = sig
   type elt 
   type 'a node = Nil | Cons of elt * 'a
-  type t
+
+  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 hash : t -> int
-  val uid : t -> int
+  val uid : t -> Uid.t
+  val make : data -> t
   val equal : t -> t -> bool
   val nil : t
   val node : t -> t node
@@ -16,61 +26,56 @@ module type S = sig
   val iter : (elt -> 'a) -> t -> unit
   val rev : t -> t
   val rev_map : (elt -> elt) -> t -> t
+  val length : t -> int
+
+  val with_id : Uid.t -> t
 end
 
-module Make ( H : Hcons.S ) : S with type elt = H.t =
+module Make ( H : Hcons.SA ) : S with type elt = H.t =
 struct
   type elt = H.t
   type 'a node = Nil | Cons of elt * 'a
-  module rec HNode : Hcons.S with type data = Node.t = Hcons.Make (Node)
-  and Node : Hashtbl.HashedType  with type t = HNode.t node =
+  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 =  HNode.t node
+    type t = Node.t node
     let equal x y = 
       match x,y with
-       | Nil,Nil -> true
-       | Cons (a,aa), Cons(b,bb) -> (H.equal a b) && (HNode.equal aa bb)
+       | _,_ when x==y -> true
+       | Cons (a,aa), Cons(b,bb) -> (aa==bb) && (H.equal a b)
        | _ -> false
     let hash = function 
       | Nil -> 0
-      | Cons(a,aa) -> HASHINT3(PRIME3,H.uid a, HNode.uid aa)
+      | Cons(a,aa) -> HASHINT3(PRIME3,Uid.to_int (H.uid a),Uid.to_int( aa.Node.id))
   end
- ;;
-                            
-  type t = HNode.t
-  let node = HNode.node
-  let hash = HNode.hash 
-  let equal = HNode.equal
-  let uid = HNode.uid
-  let nil = HNode.make Nil
-  let cons a b = HNode.make (Cons(a,b))
-  let hd a = 
-    match HNode.node a with
-      | Nil -> failwith "hd"
-      | Cons(a,_) -> a
-
-  let tl a = 
-    match HNode.node a with
-      | Nil -> failwith "tl"
-      | Cons(_,a) -> a
-
+  type data = Data.t
+  type t = Node.t
+  let make = Node.make
+  let node x = x.Node.node
+  let hash x = x.Node.key
+  let equal = Node.equal
+  let uid x= x.Node.id
+  let nil = Node.make Nil
+  let cons a b = Node.make (Cons(a,b))
+  let hd = function { Node.node = Cons(a,_) } -> a | _ -> failwith "hd"
+  let tl = function { Node.node = Cons(_,a) } -> a | _ -> failwith "tl"
 
   let fold f l acc =
-    let rec loop acc l = match HNode.node l with
+    let rec loop acc l = match l.Node.node with
       | Nil -> acc
       | Cons(a,aa) -> loop (f a acc) aa
     in
       loop acc l
        
   let map f l  =
-    let rec loop l = match HNode.node l with
+    let rec loop l = match l.Node.node with
       | Nil -> nil
       | Cons(a,aa) -> cons (f a) (loop aa)
     in
       loop l
 
   let iter f l = 
-    let rec loop l = match HNode.node l with
+    let rec loop l = match l.Node.node with
       | Nil -> ()
       | Cons(a,aa) ->  (f a);(loop aa)
     in
@@ -78,5 +83,8 @@ struct
        
   let rev l = fold cons l nil
   let rev_map f l = fold (fun x acc -> cons (f x) acc) l nil
-         
+  let length l = fold (fun _ c -> c+1) l 0 
+    
+
+  let with_id = Node.with_id
 end