3 files changed, 83 insertions, 91 deletions

diff --git a/src/library/scala/collection/TreeWalker.scala b/src/library/scala/collection/TreeWalker.scala
deleted file mode 100644
index e6be41ad66..0000000000
--- a/src/library/scala/collection/TreeWalker.scala
+++ /dev/null
@@ -1,85 +0,0 @@
-/*                     __                                               *\
-**     ________ ___   / /  ___     Scala API                            **
-**    / __/ __// _ | / /  / _ |    (c) 2007, LAMP/EPFL                  **
-**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
-** /____/\___/_/ |_/____/_/ | |                                         **
-**                          |/                                          **
-\*                                                                      */
-
-// $Id$
-
-package scala.collection
-
-/**
- *  @author Sean McDirmid
- */
-object TreeWalker {
-
-  object Empty extends TreeWalker[Nothing] {
-    def hasNext = None
-    def next = throw new NoSuchElementException
-  }
-
-  private case class NonEmpty[+A](item: A, right: () => TreeWalker[A]) extends TreeWalker[A] {
-    private var spent = false
-    def hasNext = if (spent) right().hasNext else Some(this)
-    def next = if (spent) right().next else {
-      spent = true
-      item
-    }
-  }
-
-  def apply[A](item: A): TreeWalker[A] = NonEmpty(item, () => Empty)
-
-  def apply[A](item: A, right: () => TreeWalker[A]): () => TreeWalker[A] =
-    () => NonEmpty(item, right)
-
-  def apply[A](left: TreeWalker[A], item: A, right: () => TreeWalker[A]): TreeWalker[A] =
-    left match {
-      case Empty =>
-        NonEmpty(item, right)
-      case NonEmpty(first, middle) =>
-        val rest = NonEmpty(item,right)
-        NonEmpty(first, apply(middle, () => rest))
-    }
-
-  def apply[A](left: () => TreeWalker[A], right: () => TreeWalker[A]): () => TreeWalker[A] =
-    () => (left() match {
-      case Empty => right()
-      case NonEmpty(item, middle) =>
-        NonEmpty(item, apply(middle, right))
-    })
-}
-
-/**
- *  @author Sean McDirmid
- */
-sealed abstract class TreeWalker[+A] {
-  def hasNext : Option[TreeWalker[A]]
-  def next: A
-  def append[B >: A](item: B): TreeWalker[B] = append(item, () => TreeWalker.Empty);
-  def append[B >: A](item: B, right: () => TreeWalker[B]): TreeWalker[B] = TreeWalker[B](this, item, right);
-  def append[B >: A](right : () => TreeWalker[B]) = TreeWalker(() => this,right)();
-  class Elements extends Iterator[A] {
-    private var cursor : TreeWalker[Any] = TreeWalker.this;
-    def check = {
-      if (!(cursor eq null)) cursor.hasNext match {
-      case None => cursor = null;
-      case Some(c) if !(c eq cursor) =>
-        cursor = c;
-      case Some(_) =>
-      }
-      cursor;
-    }
-    def hasNext = !(check eq null);
-    def next = check match {
-      case null => throw new NoSuchElementException
-      case cursor => cursor.next.asInstanceOf[A]
-    }
-  }
-  def elements = new Elements
-}
-
-
-
-
diff --git a/src/library/scala/collection/immutable/ImmutableIterator.scala b/src/library/scala/collection/immutable/ImmutableIterator.scala
new file mode 100644
index 0000000000..0218198263
--- /dev/null
+++ b/src/library/scala/collection/immutable/ImmutableIterator.scala
@@ -0,0 +1,80 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2007, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+  package scala.collection.immutable;
+
+/** An object for creating immutable iterators.
+  */
+object ImmutableIterator {
+  object Empty extends ImmutableIterator[Nothing] {
+    def hasNext = false;
+    def next = throw new NoSuchElementException;
+  }
+  private case class NonEmpty[+A](item : A, right : () => ImmutableIterator[A]) extends ImmutableIterator[A] {
+    def hasNext = true;
+    def next = Tuple2(item, right());
+  }
+  /** Creates an empty immutable iterator.
+    */
+  def empty : ImmutableIterator[Nothing] = Empty;
+  /** Creates an immutable iterator with one element.
+    */
+  def apply[A](item : A) : ImmutableIterator[A] = NonEmpty(item, () => Empty);
+  /** Prepends a lazy immutable iterator (right) with an element (item).
+    */
+  def apply[A](item : A, right : () => ImmutableIterator[A]) : () => ImmutableIterator[A] = () => NonEmpty(item, right);
+  /** Appends an immutable iterator (left) with an element (item) followed by a lazy immutable iterator (right).
+    */
+  def apply[A](left : ImmutableIterator[A], item : A, right : () => ImmutableIterator[A]) : ImmutableIterator[A] = left match {
+  case Empty => NonEmpty(item, right);
+  case NonEmpty(first, middle) =>
+    val rest = NonEmpty(item,right);
+    NonEmpty(first, apply(middle, () => rest));
+  }
+  /** Concats a lazy immutable iterator (left) with another lazy immutable iterator (right).
+   */
+  def apply[A](left : () => ImmutableIterator[A], right : () => ImmutableIterator[A]) : () => ImmutableIterator[A] = () => (left() match {
+  case Empty => right();
+  case NonEmpty(item, middle) => NonEmpty(item, apply(middle, right));
+  });
+}
+
+/** A stateless iterator. */
+sealed abstract class ImmutableIterator[+A] {
+  /** queries if this iterator has an element to return.
+    */
+  def hasNext : Boolean;
+  /** returns the next element and immutable iterator as a pair.
+    */
+  def next : Tuple2[A,ImmutableIterator[A]];
+  /** Creates a new immutable iterator that appends item to this immutable iterator.
+    */
+  def append[B >: A](item : B) : ImmutableIterator[B] = append(item, () => ImmutableIterator.Empty);
+  /** Creates a new immutable iterator that appends item  and a lazy immutable iterator (right) to this immutable iterator.
+    */
+  def append[B >: A](item : B, right : () => ImmutableIterator[B]) : ImmutableIterator[B] = ImmutableIterator[B](this, item, right);
+  /** Creates a new immutable iterator that appends a lazy immutable iterator (right) to this immutable iterator.
+    */
+  def append[B >: A](right : () => ImmutableIterator[B]) = ImmutableIterator(() => this,right)();
+  private class Elements extends Iterator[A] {
+    private[this] var cursor : ImmutableIterator[A] = ImmutableIterator.this;
+    def hasNext = cursor.hasNext;
+    def next = {
+      val Tuple2(ret,cursor0) = cursor.next;
+      cursor = cursor0;
+      ret;
+    }
+  }
+  /** Converts this immutable iterator into a conventional iterator.
+    */
+  def elements : Iterator[A] = new Elements;
+}
+
+
+
+
diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index 8a10b324e7..3df5a37ee3 100755
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -7,9 +7,7 @@
 \*                                                                      */
 
 // $Id: $
-
 package scala.collection.immutable
-import scala.collection.TreeWalker
 
 @serializable
 abstract class RedBlack[A] {
@@ -32,7 +30,7 @@ abstract class RedBlack[A] {
     def delete(k: A): Tree[B] = del(k)
 
     def visit[T](input : T)(f : (T,A,B) => Tuple2[Boolean,T]) : Tuple2[Boolean,T];
-    def elements : TreeWalker[Pair[A,B]];
+    def elements : ImmutableIterator[Pair[A,B]];
     def elementsSlow: Iterator[Pair[A, B]];
     def upd[B1 >: B](k: A, v: B1): Tree[B1]
     def del(k: A): Tree[B]
@@ -85,7 +83,7 @@ abstract class RedBlack[A] {
       }
     }
     def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
-    def elements : TreeWalker[Pair[A,B]] =
+    def elements : ImmutableIterator[Pair[A,B]] =
       left.elements.append(Pair(key,value), () => right.elements)
 
     def elementsSlow: Iterator[Pair[A, B]] =
@@ -123,8 +121,7 @@ abstract class RedBlack[A] {
     def del(k: A): Tree[Nothing] = this
     def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
     def elementsSlow: Iterator[Pair[A, Nothing]] = Iterator.empty
-    def elements : TreeWalker[Pair[A,Nothing]] = TreeWalker.Empty
-
+    def elements : ImmutableIterator[Pair[A,Nothing]] = ImmutableIterator.empty
     def visit[T](input : T)(f : (T,A,Nothing) => Tuple2[Boolean,T]) = Tuple2(true,input)
 
     def range(from : Option[A], until : Option[A]) = this