From c717e9d642a19ed5f0b9ac4e3c206942ee0b44cc Mon Sep 17 00:00:00 2001
From: Andrea Asperti <andrea.asperti@unibo.it>
Date: Thu, 5 Nov 2009 15:10:55 +0000
Subject: [PATCH] Naif version of the union find

---
 helm/software/components/extlib/hExtlib.ml  | 43 +++++++++++++++++++++
 helm/software/components/extlib/hExtlib.mli |  3 ++
 2 files changed, 46 insertions(+)

diff --git a/helm/software/components/extlib/hExtlib.ml b/helm/software/components/extlib/hExtlib.ml
index 237d4e77f..13dd2f266 100644
--- a/helm/software/components/extlib/hExtlib.ml
+++ b/helm/software/components/extlib/hExtlib.ml
@@ -331,6 +331,49 @@ 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
+;;
+
+(* 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
+  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
+;;
+
+(* f x gives the direct dependencies of x;
+   x must not belong to (f x) and (f x) must
+   be a subset of l *)
+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 = 
+    List.fold_left 
+     (fun (canonicals,elements) x ->
+       let dep = f x in
+	 List.fold_left 
+	   (fun (canonicals,elements) d ->
+	      merge canonicals elements d x) 
+	   (canonicals,elements) dep)
+     (canonicals,elements) l
+  in
+    List.map snd elements
+;;
+
 (** {2 File predicates} *)
 
 let is_dir fname =
diff --git a/helm/software/components/extlib/hExtlib.mli b/helm/software/components/extlib/hExtlib.mli
index 34b4e3103..c0b8c4667 100644
--- a/helm/software/components/extlib/hExtlib.mli
+++ b/helm/software/components/extlib/hExtlib.mli
@@ -133,6 +133,9 @@ 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 clusters : ('a -> 'a list) -> 'a list -> 'a list list
 (** {2 Debugging & Profiling} *)
 
 type profiler = { profile : 'a 'b. ('a -> 'b) -> 'a -> 'b }
-- 
2.39.2