intersect improved in speed

[helm.git] / helm / ocaml / mathql_interpreter / union.ml

diff --git a/helm/ocaml/mathql_interpreter/union.ml b/helm/ocaml/mathql_interpreter/union.ml
index bf402a2f17359ef6ba398dafd2b97c82dff3e913..5573c192ed74d77d3dcaaec436c84f4d23e00090 100644 (file)
--- a/helm/ocaml/mathql_interpreter/union.ml
+++ b/helm/ocaml/mathql_interpreter/union.ml
@@ -1,3 +1,27 @@
+(* 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 +64,44 @@ 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];;
-
-List.map (fun l -> List.iter print_endline l) (xres_union (r1, r2));;
-*)