1) ecrire la fonction hash et equal

2) creer un module QTree dans le fichier table.ml
3) definir notre propre hashtbl---->QTreeHash
4) ajouter la fonction minimize_qtree pour minimizer le query_tree
5) ameliorer la fonction eval_qtree en utilisant un QTreeHash pour partager maximalement les informations.
6) mise a jour l'interface query_tree.mli
7) mise a jour le main

diff --git a/src/query_tree.ml b/src/query_tree.ml
index 9297d3a..6d9e6bd 100644 (file)
--- a/src/query_tree.ml
+++ b/src/query_tree.ml
@@ -1,6 +1,8 @@
 open Table
 
 let compteur = ref 0
+let table_query_tree = Hashtbl.create 97 
+let table_qtree = QTreeHash.create 97
 
 let all_nodes tree = let root = Naive_tree.root tree in
                     eval_axis tree [root] (Descendant true)
@@ -131,7 +133,7 @@ let debug tree q l =
     Format.pp_print_flush Format.std_formatter ();
   end
 
-let table_query_tree = Hashtbl.create 97 
+
 
 
 let rec compare_query_tree q1 q2 =
@@ -184,3 +186,61 @@ let rec eval_query_tree tree start q =
   in
   debug tree q resultat;
   resultat
+
+let mini_id = ref 0
+let mini_table = QTreeHash.create 17 
+
+let rec minimize_qtree q =
+   if q.id != -1 then q
+   else
+    try
+      QTreeHash.find mini_table q
+    with Not_found ->
+      let mdesc =
+       match q.desc with
+           (Start | Dom | Tag _) as d -> d
+         | Binop(op,q1,q2) -> let mq1 = minimize_qtree q1 in
+                              let mq2 = minimize_qtree q2 in
+                              Binop(op,mq1,mq2)
+         | Axis(a,q1) -> let mq1 = minimize_qtree q1 in
+                         Axis(a,mq1)         
+      in
+      q.desc <- mdesc;
+      q.hash <- QTree.hash q;
+      q.id <- !mini_id;
+      incr mini_id;
+      QTreeHash.add mini_table q q;
+      q
+
+
+         
+let rec eval_qtree tree start q =
+  let resultat = 
+    begin
+      try
+       QTreeHash.find table_qtree q
+      with Not_found ->        
+       let res =
+       match q.desc with
+         | Start -> start
+         | Dom ->  all_nodes tree          
+         | Tag (t,k) -> element_by_tag tree t k                     
+         | Axis (a,q1) -> let ls = eval_qtree tree start q1 in
+                          eval_axis tree ls a                     
+         | Binop (op,q1,q2)-> begin
+           let ls1 = eval_qtree tree start q1 in
+           let ls2 = eval_qtree tree start q2 in
+           match op with         
+             | Union -> union_list tree ls1 ls2            
+             | Inter -> inter_list tree ls1 ls2
+             | Diff -> diff_list tree ls1 ls2
+         end
+       in
+       let res = List.sort (Table.compare_node tree) res in
+       QTreeHash.add table_qtree q res;
+       compteur := !compteur + (List.length res);
+       res
+    end
+  in
+  debug tree q resultat;
+  resultat

diff --git a/src/query_tree.mli b/src/query_tree.mli
index ea520c4..f34cc3b 100644 (file)
--- a/src/query_tree.mli
+++ b/src/query_tree.mli
@@ -34,3 +34,7 @@ val eval_query_tree : Naive_tree.t -> Naive_tree.node list ->Table.query_tree ->
     [start] the set of nodes departing.
     [q] query_tree
 *)
+
+val minimize_qtree : Table.query_tree -> Table.query_tree
+
+val eval_qtree : Naive_tree.t -> Naive_tree.node list ->Table.query_tree -> Naive_tree.node list

diff --git a/src/table.ml b/src/table.ml
index 3d372ec..f0e24ee 100644 (file)
--- a/src/table.ml
+++ b/src/table.ml
@@ -20,8 +20,41 @@ and query_tree = {
 }
 
 
-
-
+module QTree = struct
+  type t = query_tree
+  let rec equal q1 q2 =
+    q1 == q2 ||
+      (q1.id == q2.id && q1.id != -1) ||
+      match q1.desc, q2.desc with
+       | Binop(op1,qt1,qt2),Binop(op2,qt3,qt4)-> op1==op2&& (equal qt1 qt3 && equal qt2 qt4) 
+                                                          
+       | Axis(a1,qt1),Axis(a2,qt2) -> compare_axis a1 a2 && equal qt1 qt2
+       | Tag(t1,k1),Tag(t2,k2) -> t1==t2&& k1==k2
+       | Dom,Dom | Start,Start -> true
+       | _,_ ->false
+  and compare_axis a1 a2 =
+    match a1,a2 with
+       Self ,Self | Attribute, Attribute | Child , Child | Parent , Parent
+      | FollowingSibling , FollowingSibling       
+      | PrecedingSibling , PrecedingSibling
+      | Preceding , Preceding | Following , Following -> true
+      | Descendant b1, Descendant b2 -> b1==b2 
+      | Ancestor b1, Ancestor b2 -> b1==b2
+      | _,_ -> false
+
+  let rec hash q = 
+    if q.hash != -1 then q.hash
+    else match q.desc with
+       Dom -> 1
+      | Start -> 3
+      | Tag(s,_) -> 5 + 17*QNameSet.hash s
+      | Axis(a,q) -> 7 + 17 * Hashtbl.hash a + 23* hash q
+      | Binop(op,q1,q2) -> 11 + 17* Hashtbl.hash op + 23* hash q1 + 27* hash q2
+
+end
+
+
+module QTreeHash = Hashtbl.Make(QTree)
 
 
 

diff --git a/src/table_driver.ml b/src/table_driver.ml
index 64d1a1d..767cfdc 100644 (file)
--- a/src/table_driver.ml
+++ b/src/table_driver.ml
@@ -27,12 +27,15 @@ let main () =
   let query_tree_list =
     List.map (fun query -> compile_xpath query) queries
   in
-     List.iter ( fun q -> 
-      let res = eval_query_tree doc [ (Naive_tree.root doc) ] q in
-      print_string "<xml_result num=\"1\" >\n";
-      print_node_list doc res;
-      print_string "</xml_result>\n"
-    ) query_tree_list ;
+  let mini_qtree_list = 
+    List.map (fun qtree -> Query_tree.minimize_qtree qtree) query_tree_list 
+  in
+  List.iter ( fun q -> 
+    let res = eval_qtree doc [ (Naive_tree.root doc) ] q in
+    print_string "<xml_result num=\"1\" >\n";
+    print_node_list doc res;
+    print_string "</xml_result>\n";
+  ) mini_qtree_list ;
   
   let _ = if !Table_options.count then 
        Format.fprintf Format.std_formatter "there are %i nodes\n" !Query_tree.compteur;