X-Git-Url: http://git.nguyen.vg/gitweb/?p=tatoo.git;a=blobdiff_plain;f=src%2Ftable.ml;fp=src%2Ftable.ml;h=64d4103ba64558375126848ae1914c2c993d0561;hp=15d39bcb712b6ae08870ad844bc302b2392ce678;hb=72818d02fb469c39a3d8043300152beae3e7e162;hpb=c7229e6e3c000938a74abeb52749f62a65c3bbfd diff --git a/src/table.ml b/src/table.ml index 15d39bc..64d4103 100644 --- a/src/table.ml +++ b/src/table.ml @@ -123,121 +123,175 @@ let rec compare_node_list tree l1 l2 = if b=0 then compare_node_list tree ll1 ll2 else b + + +let bitvector_of_nodes tree l = + let v = Bitvector.create (Naive_tree.size tree) in + List.iter(fun n -> let j = Naive_tree.preorder tree n in + Bitvector.set v j true ) l; + v + +let decode_bit tree v = + let l = ref [] 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 + l := n::!l + done; + List.rev !l + 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 ln = +let get_descendant tree v = let rec aux n acc = - if n == Naive_tree.nil then acc - else let n1 = Naive_tree.first_child tree n in - let acc1 = aux n1 (n::acc) in + if n == Naive_tree.nil then acc + else let n1 = Naive_tree.first_child tree n in + let j = Naive_tree.preorder tree n in + Bitvector.set acc j true; + let acc1 = aux n1 acc in let n2 = Naive_tree.next_sibling tree n in - let acc2 = aux n2 acc1 in - acc2 - in - let ll = List.map (fun n -> - let n1 = Naive_tree.first_child tree n in - aux n1 [] ) ln in - get_list_ordred tree ll + aux n2 acc1 + 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; + v0 -let get_child tree ln = +let get_child tree v = let rec aux n acc = if n == Naive_tree.nil then acc - else + else let n1 = Naive_tree.next_sibling tree n in - aux n1 (n::acc) + Bitvector.set acc (Naive_tree.preorder tree n) true; + aux n1 acc in - let ll = List.map (fun n-> - let n1 = Naive_tree.first_child tree n in - aux n1 [] ) ln in - get_list_ordred tree ll + 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; + v0 -let get_followingSibling tree ln = +let get_followingSibling tree v = let rec aux n acc = let n1 = Naive_tree.next_sibling tree n in if n1 == Naive_tree.nil then acc - else aux n1 (n1::acc) + else begin + Bitvector.set acc (Naive_tree.preorder tree n1) true; + aux n1 acc end in - let ll = List.map (fun n -> aux n [] ) ln in - get_list_ordred tree ll + 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 _ = aux n v0 in (); + done; + v0 - let rec get_firstBling tree n pred = if n== Naive_tree.nil then pred else get_firstBling tree (Naive_tree.prev_sibling tree n) n -let get_parent tree ln = - List.fold_left (fun acc n -> - let n1 = get_firstBling tree n Naive_tree.nil in - let n2 = Naive_tree.parent_of_first tree n1 in - if n2 != Naive_tree.nil then union_list tree [n2] acc - else acc - ) [] ln - +let get_parent tree v = + 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 = get_firstBling tree n Naive_tree.nil in + let n2 = Naive_tree.parent_of_first tree n1 in + if n2 != Naive_tree.nil then begin let j = Naive_tree.preorder tree n2 in + Bitvector.set v0 j true + end + done; + v0 + +let get_ancestor tree 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 + done; + done; + v0 -let get_ancestor tree ln = - let rec aux tree l1 acc = - match l1 with - [] -> acc - | _ -> let ll1 = get_parent tree l1 in - let acc1 = union_list tree acc ll1 in - aux tree ll1 acc1 - in - let l = aux tree ln [] in - l - -let get_preSibling tree ln = +let get_preSibling tree v = let rec aux n acc = let n1 = Naive_tree.prev_sibling tree n in if n1 == Naive_tree.nil then acc - else aux n1 (n1::acc) + else begin + Bitvector.set acc (Naive_tree.preorder tree n1) true; + aux n1 acc end in - let ll = List.map (fun n -> aux n [] ) ln in - List.fold_left (fun acc l1 -> union_list tree acc l1) [] ll + 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 _ = aux n v0 in () + done; + v0 + -let rec eval_axis tree ls a = +let rec eval_axis tree v a = let open Xpath.Ast in match a with - Self -> ls + Self -> v - | Attribute -> get_child tree ls + | Attribute -> get_child tree v - | Child -> get_child tree ls + | Child -> get_child tree v - | Descendant c -> let ls2 = get_descendant tree ls in - let ldes = - if not c then ls2 - else union_list tree ls2 ls - in - ldes + | Descendant c -> let v2 = get_descendant tree v in + if not c then v2 + else Bitvector.union v2 v + - | FollowingSibling -> get_followingSibling tree ls + | FollowingSibling -> get_followingSibling tree v - | Parent -> get_parent tree ls + | Parent -> get_parent tree v - | Ancestor b -> - let ls3 = get_ancestor tree ls in - let lac = - if not b then ls3 - else union_list tree ls3 ls - in - lac + | Ancestor b -> let v2 = get_ancestor tree v in + if not b then v2 + else Bitvector.union v2 v + - | PrecedingSibling -> get_preSibling tree ls + | PrecedingSibling -> get_preSibling tree v - | Preceding -> let ls2 = eval_axis tree ls (Ancestor true) in - let ls3 = eval_axis tree ls2 PrecedingSibling in - let lp = eval_axis tree ls3 (Descendant true) in - lp + | Preceding -> let v2 = eval_axis tree v (Ancestor true) in + let v3 = eval_axis tree v2 PrecedingSibling in + eval_axis tree v3 (Descendant true) + - | Following -> let ls2 = eval_axis tree ls (Ancestor true) in - let ls3 = eval_axis tree ls2 FollowingSibling in - let lf = eval_axis tree ls3 (Descendant true) in - lf + | Following -> let v2 = eval_axis tree v (Ancestor true) in + let v3 = eval_axis tree v2 FollowingSibling in + eval_axis tree v3 (Descendant true) +