+
+
+
+module Partial(N : S) : S =
+struct
+
+ type elt = Tree.node
+ type t = { env : ((int*State.t), t) Hashtbl.t;
+ elem : list;
+ opened : bool;
+ }
+ and list =
+ | Var of (int * State.t)
+ | Nil
+ | Cons of elt * list
+ | Concat of list * list
+ | Lambda of t
+
+ let dummy = Hashtbl.create 0
+ let empty = { env = dummy;
+ elem = Nil;
+ opened = false }
+ let is_open t = t.opened
+
+
+ let close h t =
+ {empty with elem =
+ Lambda { t with env = h; opened = false } }
+
+ let singleton i = { empty with elem = Cons(i, Nil) }
+ let cons e t = { t with elem = Cons(e, t.elem) }
+ let concat t1 t2 =
+ { t1 with elem = Concat (t1.elem, t2.elem) }
+
+ let snoc t e = concat t (singleton e)
+ let concat3 t1 t2 t3 = concat t1 (concat t2 t3)
+ let concat4 t1 t2 t3 t4 = concat (concat t1 t2) (concat t3 t4)
+ let conscat e t1 t2 = cons e (concat t1 t2)
+ let conscat3 e t1 t2 t3 = cons e (concat3 t1 t2 t3)
+ let conscat4 e t1 t2 t3 t4 = cons e (concat4 t1 t2 t3 t4)
+ let subtree_tags _ = failwith "not implemented"
+ let subtree_elements _ = failwith "not_implemented"
+
+ let iter f t =
+ let rec loop t =
+ loop_list t.env t.elem
+ and loop_list h = function
+ | Nil -> ()
+ | Var i -> loop (Hashtbl.find h i)
+ | Cons (e, l) -> f e; loop_list h l
+ | Concat (l1, l2) -> loop_list h l1; loop_list h l2
+ | Lambda t -> loop t
+ in
+ loop t
+
+ let fold f t acc =
+ let rec loop t acc =
+ loop_list t.env acc t.elem
+ and loop_list h acc = function
+ | Nil -> acc
+ | Var i -> loop (try Hashtbl.find h i with Not_found -> let a,b = i in Printf.eprintf "%i,%i not found\n%!" a b; empty) acc
+ | Cons (e, l) -> loop_list h (f e acc) l
+ | Concat (l1, l2) -> loop_list h (loop_list h acc l1) l2
+ | Lambda t -> loop t acc
+ in
+ loop t acc
+
+
+ let rec dump t =
+ Hashtbl.iter (fun (i,j) t ->
+ Format.eprintf "%i, %a ->" i State.print j;
+ dump t;
+ Format.eprintf "----------------\n%!";
+ ) t.env;
+ dump_list t.elem
+ and dump_list = function
+ | Nil -> ()
+ | Var (i,j) -> Format.eprintf "Var(%i, %a) " i State.print j;
+ | Cons (e, l) -> Format.eprintf "%i " (Node.to_int e); dump_list l
+ | Concat (l1, l2) -> dump_list l1 ; dump_list l2
+ | Lambda t -> dump t
+
+
+ let length t = fold (fun _ acc -> 1 + acc) t 0
+
+
+ let var i =
+ { empty with elem = Var i; opened = true }
+
+ let serialize _ = failwith "not implemented"
+end