Mercurial > urweb

comparison src/union_find_fn.sml @ 2274:0730e217fc9c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First draft of more specific formulas for queries.
author Ziv Scully <ziv@mit.edu>
date Thu, 05 Nov 2015 01:48:42 -0500
parents ff38b3e0cdfd
children
comparison
equal deleted inserted replaced
2273:a3cac6cea625 2274:0730e217fc9c
1 functor UnionFindFn(K : ORD_KEY) :> sig 1 functor UnionFindFn(K : ORD_KEY) :> sig
2 type unionFind 2 type unionFind
3 val empty : unionFind 3 val empty : unionFind
4 val union : unionFind * K.ord_key * K.ord_key -> unionFind 4 val union : unionFind * K.ord_key * K.ord_key -> unionFind
5 val union' : (K.ord_key * K.ord_key) * unionFind -> unionFind 5 val union' : (K.ord_key * K.ord_key) * unionFind -> unionFind
6 val together : unionFind * K.ord_key * K.ord_key -> bool
6 val classes : unionFind -> K.ord_key list list 7 val classes : unionFind -> K.ord_key list list
7 end = struct 8 end = struct
8 9
9 structure M = BinaryMapFn(K) 10 structure M = BinaryMapFn(K)
10 structure S = BinarySetFn(K) 11 structure S = BinarySetFn(K)
32 33
33 fun find ((uf, _), x) = (S.listItems o #1 o findPair) (uf, x) 34 fun find ((uf, _), x) = (S.listItems o #1 o findPair) (uf, x)
34 35
35 fun classes (_, cs) = (map S.listItems o M.listItems) cs 36 fun classes (_, cs) = (map S.listItems o M.listItems) cs
36 37
38 fun together ((uf, _), x, y) = case K.compare (#2 (findPair (uf, x)), #2 (findPair (uf, y))) of
39 EQUAL => true
40 | _ => false
41
37 fun union ((uf, cs), x, y) = 42 fun union ((uf, cs), x, y) =
38 let 43 let
39 val (xSet, xRep) = findPair (uf, x) 44 val (xSet, xRep) = findPair (uf, x)
40 val (ySet, yRep) = findPair (uf, y) 45 val (ySet, yRep) = findPair (uf, y)
41 val xySet = S.union (xSet, ySet) 46 val xySet = S.union (xSet, ySet)