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

# SCM Repository

[smlnj] View of /MLRISC/releases/release-110.60/library/union-find.sml
 [smlnj] / MLRISC / releases / release-110.60 / library / union-find.sml

# View of /MLRISC/releases/release-110.60/library/union-find.sml

Revision 2126 - (download) (annotate)
Thu Nov 2 16:11:29 2006 UTC (12 years, 10 months ago) by blume
Original Path: MLRISC/trunk/library/union-find.sml
File size: 802 byte(s)
`moved MLRISC to toplevel`
```(*
* Union-find
*
* -- Allen
*)

signature UNION_FIND =
sig

type 'a union_find

val union_find : int * (int -> 'a) -> 'a union_find
val find       : 'a union_find -> int -> 'a
val union'     : 'a union_find -> int * int -> bool
val union      : 'a union_find -> ('a * 'a -> 'a) -> int * int -> bool
val ==         : 'a union_find -> int * int -> bool
end

structure Unionfind :> UNION_FIND =
struct

structure A = Array
structure U = UnionFindRef

type 'a union_find = 'a U.uref A.array

fun union_find (n,f) = A.tabulate(n,(fn i => U.uref(f i)))

fun find U x = U.!!(A.sub(U,x))

fun union' U (x,y) = U.union' (A.sub(U,x),A.sub(U,y))

fun union  U f (x,y) = U.union f (A.sub(U,x),A.sub(U,y))

fun == U (x,y) = U.==(A.sub(U,x),A.sub(U,y))

end
```

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