From b1dd0048c707c1d459667946912346680e34dd02 Mon Sep 17 00:00:00 2001
From: Huibo SHI <shihuibo19@gmail.com>
Date: Mon, 7 Apr 2014 17:23:04 +0200
Subject: [PATCH] 1) Optimiser les fontions auxiliaires par eviter d'utiliser
 List.mem 2) Ajouter la fonction merge_list pour concatener deux listes
 ordonnees(descendante)

---
 src/table.ml         | 44 +++++++++++++++++++++++++++-----------------
 tests/single_test.sh |  5 +++--
 2 files changed, 30 insertions(+), 19 deletions(-)

diff --git a/src/table.ml b/src/table.ml
index 0c9e119..21ea213 100644
--- a/src/table.ml
+++ b/src/table.ml
@@ -64,6 +64,14 @@ let rec union_list t l1 l2 =
       else if (comp_node t h1 h2) then h1::(union_list t ll1 l2)
       else h1 ::(union_list t ll1 ll2)
 
+let rec merge_list t l1 l2 =
+  match l1,l2 with
+    | [],l2 -> l2
+    | l1,[] -> l1
+    | h1::ll1, h2::ll2 -> if (comp_node t h2 h1) then h1:: (merge_list t ll1 l2)
+      else if (comp_node t h1 h2) then h2:: (merge_list t l1 ll2)
+      else h1::(merge_list t ll1 ll2)
+
 let rec inter_list t l1 l2 =
   match l1,l2 with
     | [],l2 -> []
@@ -114,7 +122,11 @@ let rec compare_node_list tree l1 l2 =
     | n1::ll1,n2::ll2 -> let b = compare_node tree n1 n2 in
 			 if b=0 then compare_node_list tree ll1 ll2 
 			 else b
-			   
+
+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 rec aux n acc =
     if n == Naive_tree.nil then  acc
@@ -124,11 +136,15 @@ let get_descendant tree ln =
 	 let acc2 = aux n2 acc1 in
 	 acc2
   in
-  let l = List.fold_left (fun acc n -> if List.mem n acc then acc 
+  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 l = List.fold_left (fun acc n -> if List.mem n acc then acc 
     else let n1 = Naive_tree.first_child tree n in
 	 aux n1 acc) [] ln 
   in
-  List.rev l 
+  List.rev l *)
 
 let get_child tree ln =
   let rec aux n acc =
@@ -139,10 +155,8 @@ let get_child tree ln =
   in
   let ll = List.map (fun  n->
     let n1 = Naive_tree.first_child tree n in
-    let res = aux n1 [] in
-    List.rev res
-  )  ln in
-  List.fold_left (fun acc l -> union_list tree acc l) [] ll
+    aux n1 [] )  ln in
+  get_list_ordred tree ll
 
   
 let get_followingSibling tree ln =
@@ -151,9 +165,8 @@ let get_followingSibling tree ln =
     if n1 == Naive_tree.nil then acc
     else aux n1 (n1::acc)
   in
-  let ll = List.map (fun n -> let res = aux n [] in
-			      List.rev res ) ln in
-  List.fold_left (fun acc l1 -> union_list tree acc l1) [] ll 
+  let ll = List.map (fun n -> aux n [] ) ln in
+  get_list_ordred tree ll
   
  
 let rec get_firstBling tree n pred =
@@ -161,16 +174,13 @@ let rec get_firstBling tree n pred =
   else get_firstBling tree (Naive_tree.prev_sibling tree n) n
     
 let get_parent tree ln =
-  let l = List.fold_left (fun acc n ->
+  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 or List.mem n2 acc then acc
-    else union_list tree [n2] acc   
+    if n2 != Naive_tree.nil then union_list tree [n2] acc   
+    else acc
   ) [] ln
-  in
-  l
-
-  
+ 
 
 let get_ancestor tree ln =
   let rec aux tree l1 acc =
diff --git a/tests/single_test.sh b/tests/single_test.sh
index d014d88..e46116f 100755
--- a/tests/single_test.sh
+++ b/tests/single_test.sh
@@ -5,13 +5,14 @@ QUERIES="$INPUT".queries
 
 
 
-
+ perl -MTime::HiRes -e 'print Time::HiRes::time(),"\n"';
 cat "$QUERIES" | while read N Q;
 do
  echo Query "$N : $Q"
- src/table_driver.native -c -d "$INPUT" "$Q" > /tmp/huibo.xml
+ src/tatoo.native  -d "$INPUT" "$Q" > /tmp/huibo.xml
 
 
 done
 
+ perl -MTime::HiRes -e 'print Time::HiRes::time(),"\n"';
 
-- 
2.17.1