X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=helm%2Focaml%2Fmathql_interpreter%2Funion.ml;h=2e83b7a7df4f8b9537ca98addbd238899d3a50d1;hb=6a1e520744f0554f3001eb89b0e0466d718b73f4;hp=bf402a2f17359ef6ba398dafd2b97c82dff3e913;hpb=6a1d05b388683befc860b48b4f2bbaf42f58a112;p=helm.git

diff --git a/helm/ocaml/mathql_interpreter/union.ml b/helm/ocaml/mathql_interpreter/union.ml
index bf402a2f1..2e83b7a7d 100644
--- a/helm/ocaml/mathql_interpreter/union.ml
+++ b/helm/ocaml/mathql_interpreter/union.ml
@@ -1,8 +1,33 @@
+(* Copyright (C) 2000, HELM Team.
+ * 
+ * This file is part of HELM, an Hypertextual, Electronic
+ * Library of Mathematics, developed at the Computer Science
+ * Department, University of Bologna, Italy.
+ * 
+ * HELM is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ * 
+ * HELM is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HELM; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA  02111-1307, USA.
+ * 
+ * For details, see the HELM World-Wide-Web page,
+ * http://cs.unibo.it/helm/.
+ *)
 
 (*
  * implementazione del comando UNION
  *)
 
+(*
 (*
  * 
  *)
@@ -40,54 +65,75 @@ let union_ex alist1 alist2 =
 			     head1)
 			    ) in (* header del risultato finale *)
       List.append (* il risultato finale e' la concatenazione ...*)
-       [headr] (* ... dell'header costruito prima ...*)
-       (match (tail1, tail2) with (* e di una coda "unione" *)
-           ([], _) -> tail2 (* va bene perche' l'altra lista e' vuota *)
-        |  (_, []) -> tail1 (* va bene perche' l'altra lista e' vuota *)
-        |  (_,  _) ->
-	    let first = (* parte dell'unione che riguarda solo il primo set *)
-	     List.map (fun l -> [List.hd l] @
-	               xres_fill_context
-	                (List.tl headr) (List.tl head1) (List.tl l)
-		      ) tail1
-            in
-	     List.fold_left
-	      (fun par x ->
-	       let y = (* elemento candidato ad entrare *)
-	        [List.hd x]
-		@
-	        xres_fill_context
-	         (List.tl headr) (List.tl head2) (List.tl x)
-	       in
-	        par @ if (List.find_all (fun t -> t = y) par) = [] then
-		       [y]
-		      else
-		       []
-	      )
-	      first
-	      tail2
+       [headr]             (* ... dell'header costruito prima ...*)
+       (Sort.list
+        (fun l m -> List.hd l < List.hd m)
+        (match (tail1, tail2) with      (* e di una coda "unione" *)
+            ([], _) -> tail2 (* va bene perche' l'altra lista e' vuota *)
+         |  (_, []) -> tail1 (* va bene perche' l'altra lista e' vuota *)
+         |  (_,  _) ->
+	     let first = (* parte dell'unione che riguarda solo il primo set *)
+	      List.map
+	       (
+	        fun l ->
+	         [List.hd l] @
+	         xres_fill_context (List.tl headr) (List.tl head1) (List.tl l)
+	       )
+	       tail1
+             in
+	      List.fold_left
+	       (fun par x ->
+	        let y = (* elemento candidato ad entrare *)
+	         [List.hd x]
+		 @
+	         xres_fill_context
+	          (List.tl headr) (List.tl head2) (List.tl x)
+	        in
+	         par @ if (List.find_all (fun t -> t = y) par) = [] then
+		        [y]
+		       else
+		        []
+	       )
+	       first (* List.fold_left *)
+	       tail2 (* List.fold_left *)
 (*	     first @
 	     List.map (fun l -> [List.hd l] @
 	               xres_fill_context
 	                (List.tl headr) (List.tl head2) (List.tl l)
 		      ) tail2
 *)
-       ) (* match *)
+        ) (* match *)
+       )
 ;;
+*)
 
-(** TEST **)
-
-(*
-let h1 = ["retVal";     "a";      "b"];;
-let l1 = ["pippo";      "3";      "3"];;
-let l3 = ["pluto";      "7";      "8"]
-let r1 = [h1; l1; l3];;
-
-(*let h2 = ["retVal";               "b";      "c"];;
-let l2 = ["pippo";                "3";      "1"];;*)
-let h2 = ["retVal";     "a";      "b"];;
-let l2 = ["pippo";      "3";      "3"];;
-let r2 = [h2; l2];;
+(* preserves order and gets rid of duplicates *)
+let rec union_ex l1 l2 =
+ let module S = Mathql_semantics in
+  match (l1, l2) with
+     [],l
+   | l,[] -> l
+   | ({S.uri = uri1} as entry1)::tl1,
+     ({S.uri = uri2} as entry2)::_ when uri1 < uri2 ->
+       entry1::(union_ex tl1 l2)
+   | ({S.uri = uri1} as entry1)::_,
+     ({S.uri = uri2} as entry2)::tl2 when uri2 < uri1 ->
+       entry2::(union_ex l1 tl2)
+   | entry1::tl1,entry2::tl2 -> (* same entry *)
+      if entry1 = entry2 then (* same attributes *)
+       entry1::(union_ex tl1 tl2)
+      else
+       assert false
+;;
 
-List.map (fun l -> List.iter print_endline l) (xres_union (r1, r2));;
-*)
+let union_ex l1 l2 =
+ let before = Unix.time () in
+ let res = union_ex l1 l2 in
+ let after = Unix.time () in
+  let ll1 = string_of_int (List.length l1) in
+  let ll2 = string_of_int (List.length l2) in
+  let diff = string_of_float (after -. before) in
+  prerr_endline ("UNION(" ^ ll1 ^ "," ^ ll2 ^ "): " ^ diff ^ "s") ;
+  flush stderr ;
+  res
+;;