From: Huibo SHI Date: Sat, 12 Apr 2014 21:40:57 +0000 (+0200) Subject: une version marché et correcte avec bitvector X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=commitdiff_plain;h=c5480c3711c7431e70f78871c738f2d86ecb96ac une version marché et correcte avec bitvector --- diff --git a/src/bitvector.ml b/src/bitvector.ml index 73d2aee..6a0152a 100644 --- a/src/bitvector.ml +++ b/src/bitvector.ml @@ -7,6 +7,11 @@ let create ?(init=false) size = bits = String.make (1 + size / 8) i } +let alloc size = + { length = size; + bits = String.create (1 + size / 8); + } + let length v = v.length let unsafe_get v n = @@ -16,7 +21,7 @@ let unsafe_get v n = let union v1 v2 = assert ( v1.length == v2.length ); - let res = create v1.length in + let res = alloc v1.length in (* Format.printf "size %d@." (String.length res.bits);*) for i = 0 to String.length v1.bits - 1 do res.bits.[i] <- Char.chr ((Char.code v1.bits.[i]) lor (Char.code v2.bits.[i])) @@ -25,7 +30,7 @@ let union v1 v2 = let inter v1 v2 = assert ( v1.length == v2.length ); - let res = create v1.length in + let res = alloc v1.length in for i = 0 to String.length v1.bits - 1 do res.bits.[i] <- Char.chr ((Char.code v1.bits.[i]) land (Char.code v2.bits.[i])) done; @@ -33,10 +38,9 @@ let inter v1 v2 = let diff v1 v2 = assert ( v1.length == v2.length ); - let res = create v1.length in + let res = alloc v1.length in for i = 0 to String.length v1.bits - 1 do - res.bits.[i] <- Char.chr (if (Char.code v1.bits.[i]) != ( (Char.code v2.bits.[i])) then 1 - else 0 ) + res.bits.[i] <- Char.chr ((Char.code v1.bits.[i]) land (lnot (Char.code v2.bits.[i]))) done; res diff --git a/src/bitvector.mli b/src/bitvector.mli index a713185..b56ff2c 100644 --- a/src/bitvector.mli +++ b/src/bitvector.mli @@ -1,6 +1,7 @@ type t val create : ?init:bool -> int -> t +val alloc : int -> t val length : t -> int val set : t -> int -> bool -> unit val get : t -> int -> bool diff --git a/src/query_tree.ml b/src/query_tree.ml index d9a226f..679d992 100644 --- a/src/query_tree.ml +++ b/src/query_tree.ml @@ -146,12 +146,12 @@ let rec eval_qtree tree start q = let res = match q.desc with | Start -> start - | Dom -> (* Bitvector.create true (Naive_tree.size tree)*) - let v = Bitvector.create (Naive_tree.size tree) in + | Dom -> Bitvector.create ~init:true (Naive_tree.size tree) + (*let v = Bitvector.create (Naive_tree.size tree) in for i=0 to (Bitvector.length v)-1 do Bitvector.set v i true done; - v + v*) | Tag (t,k) -> element_by_tag tree t k | Axis (a,q1) -> let v = eval_qtree tree start q1 in eval_axis tree v a diff --git a/src/table.ml b/src/table.ml index 64d4103..c40e93b 100644 --- a/src/table.ml +++ b/src/table.ml @@ -144,7 +144,7 @@ let get_list_ordred tree ll = let l1 = List.fold_left (fun acc l -> merge_list tree acc l) [] ll in List.rev l1 -let get_descendant tree v = +let get_descendant tree c v = let rec aux n acc = if n == Naive_tree.nil then acc else let n1 = Naive_tree.first_child tree n in @@ -156,12 +156,21 @@ let get_descendant tree v = in let v0 = Bitvector.create (Naive_tree.size tree) in (* let v = bitvector_of_nodes tree ln in*) - for i = 0 to (Bitvector.length v)-1 do - if Bitvector.get v i then - let n = Naive_tree.by_preorder tree i in - let n1 = Naive_tree.first_child tree n in - let _ = aux n1 v0 in (); - done; + if c then begin + for i = 0 to (Bitvector.length v)-1 do + if Bitvector.get v i then + let n = Naive_tree.by_preorder tree i in + let n1 = Naive_tree.first_child tree n in + let _ = aux n1 v0 in + Bitvector.set v0 i true + done; end + else + for i = 0 to (Bitvector.length v)-1 do + if Bitvector.get v i then + let n = Naive_tree.by_preorder tree i in + let n1 = Naive_tree.first_child tree n in + let _ = aux n1 v0 in () + done; v0 let get_child tree v = @@ -218,24 +227,46 @@ let get_parent tree v = done; v0 -let get_ancestor tree v = +let get_ancestor tree b v = let v0 = Bitvector.create (Naive_tree.size tree) in (* let v = bitvector_of_nodes tree ln in *) - - for i = (Bitvector.length v)-1 downto 0 do - if Bitvector.get v i then - let n = Naive_tree.by_preorder tree i in - let n0 = ref n in - while !n0 != Naive_tree.nil do - let n1 = get_firstBling tree !n0 Naive_tree.nil in - let n2 = Naive_tree.parent_of_first tree n1 in - n0 := n2; - if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in - Bitvector.set v0 j true; - Bitvector.set v j true; - end + if b then + begin + for i = (Bitvector.length v)-1 downto 0 do + if Bitvector.get v i then + begin + Bitvector.set v0 i true; + let n = Naive_tree.by_preorder tree i in + let n0 = ref n in + while !n0 != Naive_tree.nil do + let n1 = get_firstBling tree !n0 Naive_tree.nil in + let n2 = Naive_tree.parent_of_first tree n1 in + n0 := n2; + if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in + Bitvector.set v0 j true; + Bitvector.set v j true; + end + done; + end done; - done; + end + else + for i = (Bitvector.length v)-1 downto 0 do + if Bitvector.get v i then + begin + let n = Naive_tree.by_preorder tree i in + let n0 = ref n in + while !n0 != Naive_tree.nil do + let n1 = get_firstBling tree !n0 Naive_tree.nil in + let n2 = Naive_tree.parent_of_first tree n1 in + n0 := n2; + if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in + Bitvector.set v0 j true; + Bitvector.set v j true; + end + done; + end + done; v0 let get_preSibling tree v = @@ -267,18 +298,16 @@ let rec eval_axis tree v a = | Child -> get_child tree v - | Descendant c -> let v2 = get_descendant tree v in - if not c then v2 - else Bitvector.union v2 v + | Descendant c -> get_descendant tree c v + | FollowingSibling -> get_followingSibling tree v | Parent -> get_parent tree v - | Ancestor b -> let v2 = get_ancestor tree v in - if not b then v2 - else Bitvector.union v2 v + | Ancestor b -> get_ancestor tree b v + | PrecedingSibling -> get_preSibling tree v diff --git a/src/table_driver.ml b/src/table_driver.ml index d42743e..e961abb 100644 --- a/src/table_driver.ml +++ b/src/table_driver.ml @@ -5,6 +5,8 @@ open Query_tree let parse_xpath p = Xpath.Parser.parse (Ulexing.from_utf8_string p) +let display = ref false + let main () = let () = Table_options.parse () in let doc = @@ -34,10 +36,14 @@ let main () = Bitvector.set root 0 true; List.iter ( fun q -> let v = eval_qtree doc root q in - let res = decode_bit doc v in - print_string "\n"; - print_node_list doc res; - print_string "\n"; + if !display then begin + let res = decode_bit doc v in + + print_string "\n"; + print_node_list doc res; + print_string "\n"; + end; + () ) mini_qtree_list ; let t2 = Unix.gettimeofday () in