stdlib: Added a treemap traversal function.

1 files changed, 23 insertions, 0 deletions

diff --git a/src/lib/treemap.rs b/src/lib/treemap.rs
index 97ab1353c6b..6f73df36ef2 100644
--- a/src/lib/treemap.rs
+++ b/src/lib/treemap.rs
@@ -15,6 +15,7 @@ export treemap;
 export init;
 export insert;
 export find;
+export traverse;
 
 tag tree_node<@K, @V> {
     empty;
@@ -74,3 +75,25 @@ fn find<@K, @V>(m : &treemap<K, V>, k : &K) -> option<V> {
     }
   }
 }
+
+// Performs an in-order traversal
+fn traverse<@K, @V>(m : &treemap<K, V>, f : fn(&K, &V)) {
+  alt *m {
+    empty. { }
+    node(@k, @v, _, _) {
+      // copy v to make aliases work out
+      let v1 = v;
+      alt *m {
+        node(_, _, left, _) {
+          traverse(left, f);
+        }
+      }
+      f(k, v1);
+      alt *m {
+        node(_, _, _, right) {
+          traverse(right, f);
+        }
+      }
+    }
+  }
+}