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/trunk/src/MLRISC/library/union-find.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/library/union-find.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 412 - (view) (download)

1 : monnier 411 (*
2 :     * Union-find
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 : monnier 245 signature UNION_FIND =
8 :     sig
9 :    
10 :     type 'a union_find
11 :    
12 :     val union_find : int * (int -> 'a) -> 'a union_find
13 :     val find : 'a union_find -> int -> 'a
14 :     val union' : 'a union_find -> int * int -> bool
15 :     val union : 'a union_find -> ('a * 'a -> 'a) -> int * int -> bool
16 :     val == : 'a union_find -> int * int -> bool
17 :     end
18 :    
19 :     structure Unionfind :> UNION_FIND =
20 :     struct
21 :    
22 :     structure A = Array
23 :     structure U = UnionFindRef
24 :    
25 :     type 'a union_find = 'a U.uref A.array
26 :    
27 :     fun union_find (n,f) = A.tabulate(n,(fn i => U.uref(f i)))
28 :    
29 :     fun find U x = U.!!(A.sub(U,x))
30 :    
31 :     fun union' U (x,y) = U.union' (A.sub(U,x),A.sub(U,y))
32 :    
33 :     fun union U f (x,y) = U.union f (A.sub(U,x),A.sub(U,y))
34 :    
35 :     fun == U (x,y) = U.==(A.sub(U,x),A.sub(U,y))
36 :    
37 :     end

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