src/lib/UFind.rs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import option.none;
import option.some;

// A very naive implementation of union-find with unsigned integer nodes.

tag node {
    elem(uint, option.t[uint]);
}
type ufind = rec(mutable vec[mutable node] nodes);

fn make() -> ufind {
    let vec[mutable node] v = vec(mutable elem(0u, none[uint]));
    _vec.pop[mutable node](v);  // FIXME: botch
    ret rec(mutable nodes=v);
}

fn make_set(&ufind ufnd, uint n) {
    ufnd.nodes += vec(mutable elem(n, none[uint]));
}

fn find(&ufind ufnd, uint n) -> uint {
    alt (ufnd.nodes.(n)) {
        case (elem(_, ?parent_opt)) {
            alt (parent_opt) {
                case (none[uint]) { ret n; }
                case (some[uint](?m)) {
                    // TODO: "be"
                    ret find(ufnd, m);
                }
            }
        }
    }
}

fn union(&ufind ufnd, uint m, uint n) {
    auto m_root = find(ufnd, m);
    auto n_root = find(ufnd, n);
    auto ptr = some[uint](n_root);
    ufnd.nodes.(m_root) = elem(m_root, ptr);
}