From 2fab948e01477a9862142993be486bca36aa8152 Mon Sep 17 00:00:00 2001
From: Eric Holk <eholk@mozilla.com>
Date: Fri, 26 Aug 2011 10:50:02 -0700
Subject: stdlib: Added a treemap traversal function.

---
 src/lib/treemap.rs | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

(limited to 'src/lib')

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);
+        }
+      }
+    }
+  }
+}
-- 
cgit 1.4.1-3-g733a5