+external tree_unserialize : string -> tree = "caml_xml_tree_unserialize"
+
+external tree_root : tree -> [`Tree] node = "caml_xml_tree_root"
+
+let tree_is_nil x = equal_node x nil
+
+external tree_parent : tree -> [`Tree] node -> [`Tree] node = "caml_xml_tree_parent"
+external tree_parent_doc : tree -> [`Text ] node -> [`Tree ] node = "caml_xml_tree_parent_doc"
+external tree_prev_doc : tree -> [`Text ] node -> [`Tree ] node = "caml_xml_tree_prev_doc"
+external tree_first_child : tree -> [`Tree] node -> [`Tree] node = "caml_xml_tree_first_child"
+external tree_next_sibling : tree -> [`Tree] node -> [`Tree] node = "caml_xml_tree_next_sibling"
+external tree_prev_sibling : tree -> [`Tree] node -> [`Tree] node = "caml_xml_tree_prev_sibling"
+external tree_is_leaf : tree -> [`Tree] node -> bool = "caml_xml_tree_is_leaf"
+external tree_last_child : tree -> [`Tree] node -> [`Tree] node = "caml_xml_tree_last_child"
+external tree_is_first_child : tree -> [`Tree] node -> bool = "caml_xml_tree_is_first_child"
+
+(* external tag : tree -> [`Tree ] node -> T = "caml_xml_tree_tag"*)
+external tree_tag_id : tree -> [`Tree ] node -> Tag.t = "caml_xml_tree_tag_id"
+
+
+let tree_is_last t n = equal_node nil (tree_next_sibling t n)
+
+external tree_prev_text : tree -> [`Tree] node -> [`Text ] node = "caml_xml_tree_prev_text"
+
+external tree_my_text : tree -> [`Tree] node -> [`Text ] node = "caml_xml_tree_my_text"
+external tree_next_text : tree -> [`Tree] node -> [`Text ] node = "caml_xml_tree_next_text"
+external tree_doc_ids : tree -> [`Tree ] node -> [`Text ] node * [`Text ] node = "caml_xml_tree_doc_ids"
+
+let text_size tree = int_of_node (snd ( tree_doc_ids tree (Obj.magic 0) ))
+
+let get_cached_text t x =
+ if x == -1 then ""
+ else
+ get_cached_text t x
+
+
+external tree_text_xml_id : tree -> [`Text ] node -> int = "caml_xml_tree_text_xml_id"
+external tree_node_xml_id : tree -> [`Tree ] node -> int = "caml_xml_tree_node_xml_id"
+external tree_is_ancestor : tree -> [`Tree ] node -> [`Tree ] node -> bool = "caml_xml_tree_is_ancestor"
+external tree_tagged_desc : tree -> [`Tree ] node -> Tag.t -> [`Tree ] node = "caml_xml_tree_tagged_desc"
+external tree_tagged_foll_below : tree -> [`Tree ] node -> Tag.t -> [`Tree ] node -> [`Tree ] node = "caml_xml_tree_tagged_foll_below"
+external tree_subtree_tags : tree -> [`Tree ] node -> Tag.t -> int = "caml_xml_tree_subtree_tags"
+(*
+external tree_select_below : tree -> [`Tree ] node -> Ptset.int_vector -> Ptset.int_vector -> [`Tree ] node = "caml_xml_tree_select_below"
+external tree_select_desc_only : tree -> [`Tree ] node -> Ptset.int_vector -> [`Tree ] node = "caml_xml_tree_select_desc_only"
+external tree_select_next : tree -> [`Tree ] node -> Ptset.int_vector -> Ptset.int_vector -> [`Tree ] node -> [`Tree ] node = "caml_xml_tree_select_next"
+external tree_select_foll_only : tree -> [`Tree ] node -> Ptset.int_vector -> [`Tree ] node -> [`Tree ] node = "caml_xml_tree_select_foll_only"
+external tree_select_desc_or_foll_only : tree -> [`Tree ] node -> Ptset.int_vector -> [`Tree ] node -> [`Tree ] node = "caml_xml_tree_select_foll_only" *)
+
+type descr =
+ | Nil
+ | Node of [`Tree] node
+ | Text of [`Text] node * [`Tree] node
+
+type t = { doc : tree;
+ node : descr;
+ ttable : (Tag.t,(Ptset.Int.t*Ptset.Int.t)) Hashtbl.t;
+ }
+
+let text_size t = text_size t.doc
+
+let collect_tags tree =
+ let h_union = Hashtbl.create 511 in
+ let pt_cup s1 s2 =
+ (* special case, since this is a union we want hash(s1,s2) = hash(s2,s1) *)
+ let x = Ptset.Int.hash s1
+ and y = Ptset.Int.hash s2 in
+ let h = if x < y then HASHINT2(x,y) else HASHINT2(y,x)in
+ try
+ Hashtbl.find h_union h
+ with
+ | Not_found -> let s = Ptset.Int.union s1 s2
+ in
+ Hashtbl.add h_union h s;s
+ in
+ let h_add = Hashtbl.create 511 in
+ let pt_add t s =
+ let k = HASHINT2(Tag.hash t,Ptset.Int.hash s) in
+ try
+ Hashtbl.find h_add k
+ with
+ | Not_found -> let r = Ptset.Int.add t s in
+ Hashtbl.add h_add k r;r
+ in
+ let h = Hashtbl.create 511 in
+ let sing = Ptset.Int.singleton Tag.pcdata in
+ let update t sb sa =
+ let sbelow,safter =
+ try
+ Hashtbl.find h t
+ with
+ | Not_found ->
+ (sing,sing)
+ in
+ Hashtbl.replace h t (pt_cup sbelow sb, pt_cup safter sa)