Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/branches/SMLNJ/src/MLRISC/mlrisc/unionFind.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/mlrisc/unionFind.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 93 - (view) (download)

1 : monnier 16 (* unionFind.sml
2 :     *
3 :     * COPYRIGHT (c) 1996 Bell Laboratories.
4 :     *
5 :     *)
6 :    
7 :     (** Union Find
8 :     **
9 :     ** Note: root is guaranteed to return the least element
10 :     **)
11 :    
12 :     signature UNIONFIND = sig
13 :     type trees
14 :     val init : int -> trees
15 :     val clear : trees -> unit
16 :     val sets : trees -> (int * int list) list
17 :     val addEdge : trees * int * int -> unit
18 :     val find : trees * int * int -> bool
19 :     val root : trees * int -> int
20 :     val compact : trees -> unit
21 :     end
22 :    
23 :     structure UnionFind : UNIONFIND = struct
24 :     type trees = int Array.array
25 :     val least = ~1
26 :     fun init n = Array.array(n,least)
27 :    
28 :     fun clear tree = let
29 :     fun f n = (Array.update(tree,n,least); f (n+1))
30 :     in f 0 handle _ => ()
31 :     end
32 :    
33 :     fun ascend (trees,u) = let val v = Array.sub(trees,u)
34 :     in
35 :     if v > least then ascend(trees,v) else u
36 :     end
37 :    
38 :     val root = ascend
39 :    
40 :     fun addEdge(trees,x,y) = let
41 :     val xroot = ascend(trees,x)
42 :     val yroot = ascend(trees,y)
43 :     in
44 :     if xroot = yroot then ()
45 :     else if xroot < yroot then
46 :     Array.update(trees,yroot,xroot)
47 :     else Array.update(trees,xroot,yroot)
48 :     end
49 :    
50 :     fun find(trees,x,y) = let
51 :     val xroot = ascend(trees,x)
52 :     val yroot = ascend(trees,y)
53 :     in
54 :     xroot = yroot
55 :     end
56 :    
57 :     fun sets trees = let
58 :     val len = Array.length trees
59 :     exception UnionFind
60 :     val m :int list Intmap.intmap = Intmap.new(16,UnionFind)
61 :     fun getSet n = (Intmap.map m n) handle _ => []
62 :     fun f 0 = Intmap.intMapToList m
63 :     | f n = if Array.sub(trees,n) = least then f (n-1)
64 :     else let val root = ascend(trees,n)
65 :     in
66 :     Intmap.add m (root,n::getSet root);
67 :     f (n-1)
68 :     end
69 :     in f (Array.length trees - 1)
70 :     end
71 :    
72 :     fun compact trees = let
73 :     fun iter 0 = ()
74 :     | iter n = let val m = ascend(trees,n)
75 :     in
76 :     Array.update(trees,n,m); iter(n-1)
77 :     end
78 :     in
79 :     iter(Array.length trees-1)
80 :     end
81 :     end
82 :    
83 :    
84 :    
85 :     (*
86 :     * $Log: unionFind.sml,v $
87 : monnier 93 * Revision 1.1.1.1 1998/04/08 18:39:02 george
88 :     * Version 110.5
89 : monnier 16 *
90 :     *)

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0