- { n with node = node'}
-
-
- let left = first_child
- let right = next_sibling
-
- let id =
- function { doc=d; node=Node(NC n)} -> node_xml_id d n
- | { doc=d; node=Node(SC (i,_) )} -> text_xml_id d i
- | _ -> -1 (*
- Format.fprintf Format.err_formatter "Failure id on %s\n%!" (nts x.node);
- failwith "id" *)
-
- let tag =
- function { node=Node(SC _) } -> Tag.pcdata
- | { doc=d; node=Node(NC n)} -> tag_id d n
- | _ -> failwith "tag"
-
- let string_below t id =
- let strid = parent_doc t.doc id in
- match t.node with
- | Node(NC(i)) ->
- (Tree.equal i strid) || (is_ancestor t.doc i strid)
- | Node(SC(i,_)) -> Text.equal i id
- | _ -> false
-
-
- let tagged_foll t tag =
- if tag = Tag.attribute || tag = Tag.pcdata then failwith "tagged_foll"
- else match t with
- | { doc=d; node=Node(NC n) } -> { t with node = norm (tagged_foll d n tag) }
- | { doc=d; node=Node(SC (_,n)) } when is_nil n -> { t with node= Nil }
- | { doc=d; node=Node(SC (_,n)) } ->
- let nnode =
- if tag_id d n == tag then n
- else
- let n' = tagged_desc d n tag in
- if is_nil n' then tagged_foll d n tag
- else n'
- in {t with node= norm nnode}
- | _ -> { t with node=Nil }
-
-
- let tagged_desc t tag =
- if tag = Tag.attribute || tag = Tag.pcdata then failwith "tagged_desc"
- else match t with
- | { doc=d; node=Node(NC n) } -> { t with node = norm (tagged_desc d n tag) }
- | _ -> { t with node=Nil }
-
-(*
- let tagged_next t tag =
- if tag == Tag.attribute || tag == Tag.pcdata then failwith "tagged_next"
- else
- match tagged_desc t tag with
- | { doc = d; node=Nil } -> tagged_foll t tag
- | x -> x
+ if matching s
+ then loop (nodei ((inode n)+1)) (n::acc) (l+1)
+ else loop (nodei ((inode n)+1)) acc l
+ in
+ let acc,l = loop i [] 0 in
+ let a = Array.create l nulldoc in
+ let _ = List.fold_left (fun cpt e -> a.(cpt) <- e; (cpt-1)) (l-1) acc
+ in
+ contains_array := a
+
+let last_idx = ref 0
+
+let array_find a i j =
+ let l = Array.length a in
+ let rec loop idx x y =
+ if x > y || idx >= l then nulldoc
+ else
+ if a.(idx) >= x then if a.(idx) > y then nulldoc else (last_idx := idx;a.(idx))
+ else loop (idx+1) x y
+ in
+ if a.(0) > j || a.(l-1) < i then nulldoc
+ else loop !last_idx i j
+
+let text_below tree t =
+ let l = Array.length !contains_array in
+ let i,j = tree_doc_ids tree.doc t in
+ let id = if l == 0 then i else (array_find !contains_array i j) in
+ tree_parent_node tree.doc id
+
+let text_next tree t root =
+ let l = Array.length !contains_array in
+ let inf = nodei((inode(snd(tree_doc_ids tree.doc t)))+1) in
+ let _,j = tree_doc_ids tree.doc root in
+ let id = if l == 0 then if inf > j then nulldoc else inf
+ else array_find !contains_array inf j
+ in
+ tree_parent_node tree.doc id
+
+
+
+module DocIdSet = struct
+ include Set.Make (struct type t = [`Text] node
+ let compare = compare_node end)
+
+end
+let is_nil t = t == nil
+
+let is_node t = t != nil
+let is_root t = t == root
+
+let node_of_t t =
+ let _ = Tag.init (Obj.magic t) in
+ let table = collect_tags t
+ in (*
+ let _ = Hashtbl.iter (fun t (c,d,ns,f) ->
+ Printf.eprintf "Tag %s has:\n" (Tag.to_string t);
+ Printf.eprintf "Child tags: ";
+ Ptset.Int.iter (fun t -> Printf.eprintf "%s "(Tag.to_string t)) c;
+ Printf.eprintf "\nDescendant tags: ";
+ Ptset.Int.iter (fun t -> Printf.eprintf "%s "(Tag.to_string t)) d;
+ Printf.eprintf "\nNextSibling tags: ";
+ Ptset.Int.iter (fun t -> Printf.eprintf "%s "(Tag.to_string t)) ns;
+ Printf.eprintf "\nFollowing tags: ";
+ Ptset.Int.iter (fun t -> Printf.eprintf "%s "(Tag.to_string t)) f;
+ Printf.eprintf "\n\n%!";) table
+ in
+
+ *)
+ { doc= t;
+ ttable = table;
+ }
+
+let finalize _ = Printf.eprintf "Release the string list !\n%!"
+;;
+
+let parse f str =
+ node_of_t
+ (f str
+ !Options.sample_factor
+ !Options.index_empty_texts
+ !Options.disable_text_collection)
+
+let parse_xml_uri str = parse parse_xml_uri str
+let parse_xml_string str = parse parse_xml_string str
+
+let size t = tree_size t.doc;;
+
+external pool : tree -> Tag.pool = "%identity"
+
+let magic_string = "SXSI_INDEX"
+let version_string = "2"
+
+let pos fd =
+ Unix.lseek fd 0 Unix.SEEK_CUR
+
+let pr_pos fd = Printf.eprintf "At position %i\n%!" (pos fd)
+
+let write fd s =
+ let sl = String.length s in
+ let ssl = Printf.sprintf "%020i" sl in
+ ignore (Unix.write fd ssl 0 20);
+ ignore (Unix.write fd s 0 (String.length s))
+
+let rec really_read fd buffer start length =
+ if length <= 0 then () else
+ match Unix.read fd buffer start length with
+ 0 -> raise End_of_file
+ | r -> really_read fd buffer (start + r) (length - r);;
+
+let read fd =
+ let buffer = String.create 20 in
+ let _ = really_read fd buffer 0 20 in
+ let size = int_of_string buffer in
+ let buffer = String.create size in
+ let _ = really_read fd buffer 0 size in
+ buffer
+
+
+let save t str =
+ let fd = Unix.openfile str [ Unix.O_WRONLY;Unix.O_TRUNC;Unix.O_CREAT] 0o644 in
+ let out_c = Unix.out_channel_of_descr fd in
+ let _ = set_binary_mode_out out_c true in
+ output_string out_c magic_string;
+ output_char out_c '\n';
+ output_string out_c version_string;
+ output_char out_c '\n';
+ Marshal.to_channel out_c t.ttable [ ];
+ (* we need to move the fd to the correct position *)
+ flush out_c;
+ ignore (Unix.lseek fd (pos_out out_c) Unix.SEEK_SET);
+ tree_save t.doc fd str;
+ close_out out_c
+;;
+
+let load ?(sample=64) ?(load_text=true) str =
+ let fd = Unix.openfile str [ Unix.O_RDONLY ] 0o644 in
+ let in_c = Unix.in_channel_of_descr fd in
+ let _ = set_binary_mode_in in_c true in
+ let load_table () =
+ (let ms = input_line in_c in if ms <> magic_string then failwith "Invalid index file");
+ (let vs = input_line in_c in if vs <> version_string then failwith "Invalid version file");
+ let table : (Tag.t,(Ptset.Int.t*Ptset.Int.t*Ptset.Int.t*Ptset.Int.t)) Hashtbl.t =
+ Marshal.from_channel in_c
+ in
+ let ntable = Hashtbl.create (Hashtbl.length table) in
+ Hashtbl.iter (fun k (s1,s2,s3,s4) ->
+ let ss1 = Ptset.Int.fold (Ptset.Int.add) s1 Ptset.Int.empty
+ and ss2 = Ptset.Int.fold (Ptset.Int.add) s2 Ptset.Int.empty
+ and ss3 = Ptset.Int.fold (Ptset.Int.add) s3 Ptset.Int.empty
+ and ss4 = Ptset.Int.fold (Ptset.Int.add) s4 Ptset.Int.empty
+ in Hashtbl.add ntable k (ss1,ss2,ss3,ss4)
+ ) table;
+ Hashtbl.clear table;
+ (* The in_channel read a chunk of fd, so we might be after
+ the start of the XMLTree save file. Reset to the correct
+ position *)
+ ntable
+ in
+ let _ = Printf.eprintf "\nLoading tag table : " in
+ let ntable = time (load_table) () in
+ ignore(Unix.lseek fd (pos_in in_c) Unix.SEEK_SET);
+ let tree = { doc = tree_load fd str load_text sample;
+ ttable = ntable;}
+ in close_in in_c;
+ tree
+
+
+
+
+let tag_pool t = pool t.doc
+
+let compare = compare_node
+
+let equal a b = a == b
+
+let nts = function
+ -1 -> "Nil"
+ | i -> Printf.sprintf "Node (%i)" i
+
+let dump_node t = nts (inode t)
+
+let is_left t n = tree_is_first_child t.doc n
+
+
+
+let is_below_right t n1 n2 =
+ tree_is_ancestor t.doc (tree_parent t.doc n1) n2
+ && not (tree_is_ancestor t.doc n1 n2)
+
+let is_binary_ancestor t n1 n2 =
+ let p = tree_parent t.doc n1 in
+ let fin = tree_closing t.doc p in
+ n2 > n1 && n2 < fin
+(* (is_below_right t n1 n2) ||
+ (tree_is_ancestor t.doc n1 n2) *)
+
+let parent t n = tree_parent t.doc n
+
+let first_child t = let doc = t.doc in ();fun n -> tree_first_child doc n
+let first_element t = let doc = t.doc in (); fun n -> tree_first_element doc n
+let first_element t n = tree_first_element t.doc n
+(* these function will be called in two times: first partial application
+ on the tag, then application of the tag and the tree, then application of
+ the other arguments. We use the trick to let the compiler optimize application