From 540ad0223ae26c0deae250c3ace2092904290a8b Mon Sep 17 00:00:00 2001 From: Erik Rozendaal Date: Sat, 17 Dec 2011 19:36:49 +0100 Subject: Use RedBlack.iterator to create iterators for TreeSet/TreeMap. This turns iterator creation from an O(n) operation into an O(log n) operation. Unfortunately, it halves actual iteration speed (consuming the iterator fully), probably due to the many by-name closures that are needed. --- src/library/scala/collection/immutable/TreeMap.scala | 2 +- src/library/scala/collection/immutable/TreeSet.scala | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala index ef0eac3701..2fd5208991 100644 --- a/src/library/scala/collection/immutable/TreeMap.scala +++ b/src/library/scala/collection/immutable/TreeMap.scala @@ -153,7 +153,7 @@ class TreeMap[A, +B](override val size: Int, t: RedBlack[A]#Tree[B])(implicit va * * @return the new iterator */ - def iterator: Iterator[(A, B)] = tree.toStream.iterator + def iterator: Iterator[(A, B)] = tree.iterator override def toStream: Stream[(A, B)] = tree.toStream diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala index 8b90ece143..05f27d0d93 100644 --- a/src/library/scala/collection/immutable/TreeSet.scala +++ b/src/library/scala/collection/immutable/TreeSet.scala @@ -107,7 +107,7 @@ class TreeSet[A](override val size: Int, t: RedBlack[A]#Tree[Unit]) * * @return the new iterator */ - def iterator: Iterator[A] = tree.toStream.iterator map (_._1) + def iterator: Iterator[A] = tree.iterator map (_._1) override def toStream: Stream[A] = tree.toStream map (_._1) -- cgit v1.2.3