From 7bac1f2b64e5b1f6e2ef542e6b1f9134fe68c90a Mon Sep 17 00:00:00 2001
From: Andrea Asperti <andrea.asperti@unibo.it>
Date: Tue, 10 Nov 2009 15:11:51 +0000
Subject: [PATCH] Union find slightly more general (f can now point to external
 elements)

---
 helm/software/components/extlib/hExtlib.ml  | 76 +++++++++++++--------
 helm/software/components/extlib/hExtlib.mli |  6 +-
 2 files changed, 51 insertions(+), 31 deletions(-)

diff --git a/helm/software/components/extlib/hExtlib.ml b/helm/software/components/extlib/hExtlib.ml
index 0536a1d6e..0b13cd83e 100644
--- a/helm/software/components/extlib/hExtlib.ml
+++ b/helm/software/components/extlib/hExtlib.ml
@@ -331,49 +331,67 @@ let rec list_assoc_all a = function
    | _ :: tl                 -> list_assoc_all a tl
 ;;
 
-let rec rm_assoc n = function
-  | [] -> assert false
-  | (x,i)::tl when n=x -> i,tl
-  | p::tl -> let i,tl = rm_assoc n tl in i,p::tl
+let rec rm_assoc_option n = function
+  | [] -> None,[]
+  | (x,i)::tl when n=x -> Some i,tl
+  | p::tl -> let i,tl = rm_assoc_option n tl in i,p::tl
+;;
+
+let rm_assoc_assert n l =
+  match rm_assoc_option n l with
+  | None,_ -> assert false
+  | Some i,l -> i,l
 ;;
 
 (* naif implementation of the union-find merge operation
    canonicals maps elements to canonicals
    elements maps canonicals to the classes *)
-let merge canonicals elements n m =
-  let cn,canonicals = rm_assoc n canonicals in
-  let cm,canonicals = rm_assoc m canonicals in
-  if cn=cm then (n,cm)::(m,cm)::canonicals, elements
-  else
-    let ln,elements = rm_assoc cn elements in
-    let lm,elements = rm_assoc cm elements in
-    let canonicals = 
-      (n,cm)::(m,cm)::List.map 
-	(fun ((x,xc) as p)  -> 
-	   if xc = cn then (x,cm) else p) canonicals
-    in 
-    let elements = (cm,ln@lm)::elements 
-    in
-      canonicals,elements
+let merge canonicals elements extern n m =
+  let cn,canonicals = rm_assoc_option n canonicals in
+  let cm,canonicals = rm_assoc_option m canonicals in
+    match cn,cm with
+      | None, None -> canonicals, elements, extern
+      | None, Some c
+      | Some c, None -> 
+	  let l,elements = rm_assoc_assert c elements in
+          let canonicals = 
+	    List.filter (fun (_,xc) -> not (xc = c)) canonicals 
+	  in
+	    canonicals,elements,l@extern
+      | Some cn, Some cm when cn=cm ->
+	  (n,cm)::(m,cm)::canonicals, elements, extern
+      | Some cn, Some cm ->
+	  let ln,elements = rm_assoc_assert cn elements in
+	  let lm,elements = rm_assoc_assert cm elements in
+	  let canonicals = 
+	    (n,cm)::(m,cm)::List.map 
+	      (fun ((x,xc) as p)  -> 
+		 if xc = cn then (x,cm) else p) canonicals
+	  in 
+	  let elements = (cm,ln@lm)::elements 
+	  in
+	    canonicals,elements,extern
 ;;
 
-(* f x gives the direct dependencies of x;
-   x must not belong to (f x) and (f x) must
-   be a subset of l *)
+(* f x gives the direct dependencies of x.
+   x must not belong to (f x). 
+   All elements not in l are merged into a single extern class *)
 let clusters f l =
   let canonicals = List.map (fun x -> (x,x)) l in
   let elements = List.map (fun x -> (x,[x])) l in
-  let _,elements = 
+  let extern = [] in
+  let _,elements,extern = 
     List.fold_left 
-     (fun (canonicals,elements) x ->
+     (fun (canonicals,elements,extern) x ->
        let dep = f x in
 	 List.fold_left 
-	   (fun (canonicals,elements) d ->
-	      merge canonicals elements d x) 
-	   (canonicals,elements) dep)
-     (canonicals,elements) l
+	   (fun (canonicals,elements,extern) d ->
+	      merge canonicals elements extern d x) 
+	   (canonicals,elements,extern) dep)
+     (canonicals,elements,extern) l
   in
-    List.map snd elements
+  let c = (List.map snd elements) in
+  if extern = [] then c else extern::c
 ;;
 
 (** {2 File predicates} *)
diff --git a/helm/software/components/extlib/hExtlib.mli b/helm/software/components/extlib/hExtlib.mli
index c0b8c4667..a772d4a53 100644
--- a/helm/software/components/extlib/hExtlib.mli
+++ b/helm/software/components/extlib/hExtlib.mli
@@ -133,9 +133,11 @@ val list_seq: int -> int -> int list
 (* like List.assoc but returns all bindings *)
 val list_assoc_all: 'a -> ('a * 'b) list -> 'b list
 
-val rm_assoc : 'a -> ('a * 'b) list -> 'b * ('a * 'b) list
+val rm_assoc_option : 'a -> ('a * 'b) list -> 'b option * ('a * 'b) list
 
-val clusters : ('a -> 'a list) -> 'a list -> 'a list list
+val rm_assoc_assert : 'a -> ('a * 'b) list -> 'b * ('a * 'b) list
+
+val clusters : (int -> int list) -> int list -> int list list
 (** {2 Debugging & Profiling} *)
 
 type profiler = { profile : 'a 'b. ('a -> 'b) -> 'a -> 'b }
-- 
2.39.2