rustc: Use union-find for variable substitution

1 files changed, 12 insertions, 16 deletions

diff --git a/src/lib/UFind.rs b/src/lib/UFind.rs
index 7c955a92..64cd56b0 100644
--- a/src/lib/UFind.rs
+++ b/src/lib/UFind.rs
@@ -3,32 +3,28 @@ import option.some;
 
 // A very naive implementation of union-find with unsigned integer nodes.
 
-tag node {
-    elem(uint, option.t[uint]);
-}
+type node = 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]));
+    let vec[mutable node] v = vec(mutable 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 make_set(&ufind ufnd) -> uint {
+    auto idx = _vec.len[mutable node](ufnd.nodes);
+    ufnd.nodes += vec(mutable none[uint]);
+    ret idx;
 }
 
 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);
-                }
-            }
-        }
+    case (none[uint]) { ret n; }
+    case (some[uint](?m)) {
+        // TODO: "be"
+        ret find(ufnd, m);
+    }
     }
 }
 
@@ -36,6 +32,6 @@ 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);
+    ufnd.nodes.(m_root) = ptr;
 }