une version marché et correcte avec bitvector

diff --git a/src/bitvector.ml b/src/bitvector.ml
index 73d2aee..6a0152a 100644 (file)
--- 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 (file)
--- 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 (file)
--- 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 (file)
--- 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 (file)
--- 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 "<xml_result num=\"1\" >\n";
-    print_node_list doc res;
-    print_string "</xml_result>\n";
+    if !display then begin
+      let res = decode_bit doc v in
+      
+      print_string "<xml_result num=\"1\" >\n";
+      print_node_list doc res;
+      print_string "</xml_result>\n";
+    end;
+    ()
   ) mini_qtree_list ;
   
   let t2 = Unix.gettimeofday () in