stdlib: Add an interior vector version of union-find for now

2 files changed, 55 insertions, 0 deletions

diff --git a/src/lib/std.rc b/src/lib/std.rc
index 24cae023c69..21fd2cbbbc6 100644
--- a/src/lib/std.rc
+++ b/src/lib/std.rc
@@ -78,6 +78,7 @@ mod sort;
 mod sha1;
 mod ebml;
 mod ufind;
+mod ufindivec;
 mod extfmt;
 mod box;
 mod getopts;
diff --git a/src/lib/ufindivec.rs b/src/lib/ufindivec.rs
new file mode 100644
index 00000000000..9759820222a
--- /dev/null
+++ b/src/lib/ufindivec.rs
@@ -0,0 +1,54 @@
+
+import option::none;
+import option::some;
+
+
+// A very naive implementation of union-find with unsigned integer nodes.
+// Maintains the invariant that the root of a node is always equal to or less
+// than the node itself.
+type node = option::t[uint];
+
+type ufind = rec(mutable node[mutable] nodes);
+
+fn make() -> ufind {
+    ret rec(mutable nodes=~[mutable]);
+}
+
+fn make_set(&ufind ufnd) -> uint {
+    auto idx = ivec::len(ufnd.nodes);
+    ufnd.nodes += ~[mutable none[uint]];
+    ret idx;
+}
+
+
+/// Creates sets as necessary to ensure that least `n` sets are present in the
+/// data structure.
+fn grow(&ufind ufnd, uint n) {
+    while (set_count(ufnd) < n) { make_set(ufnd); }
+}
+
+fn find(&ufind ufnd, uint n) -> uint {
+    alt (ufnd.nodes.(n)) {
+        case (none) { ret n; }
+        case (some(?m)) { auto m_ = m; be find(ufnd, m_); }
+    }
+}
+
+fn union(&ufind ufnd, uint m, uint n) {
+    auto m_root = find(ufnd, m);
+    auto n_root = find(ufnd, n);
+    if (m_root < n_root) {
+        ufnd.nodes.(n_root) = some[uint](m_root);
+    } else if (m_root > n_root) { ufnd.nodes.(m_root) = some[uint](n_root); }
+}
+
+fn set_count(&ufind ufnd) -> uint { ret ivec::len[node](ufnd.nodes); }
+
+
+// Removes all sets with IDs greater than or equal to the given value.
+fn prune(&ufind ufnd, uint n) {
+    // TODO: Use "slice" once we get rid of "mutable?"
+
+    auto len = ivec::len[node](ufnd.nodes);
+    while (len != n) { ivec::pop[node](ufnd.nodes); len -= 1u; }
+}