stdlib: Add a simple union-find data structure

2 files changed, 43 insertions, 0 deletions

diff --git a/src/lib/UFind.rs b/src/lib/UFind.rs
new file mode 100644
index 00000000..7c955a92
--- /dev/null
+++ b/src/lib/UFind.rs
@@ -0,0 +1,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);
+}
+
diff --git a/src/lib/std.rc b/src/lib/std.rc
index e691fb9d..b530bd7f 100644
--- a/src/lib/std.rc
+++ b/src/lib/std.rc
@@ -47,6 +47,7 @@ auth _str.pop_char = impure;
 auth _vec.shift = impure;
 auth _vec.unshift = impure;
 auth _vec.pop = impure;
+auth UFind.union = impure;
 
 auth dbg = unsafe;
 
@@ -81,6 +82,7 @@ mod bitv;
 mod sort;
 mod sha1;
 mod ebml;
+mod UFind;
 
 // Local Variables:
 // mode: rust;