diff options
author | Erik Rozendaal <erik@deler.org> | 2011-12-17 19:36:49 +0100 |
---|---|---|
committer | Erik Rozendaal <erik@deler.org> | 2011-12-28 13:12:33 +0100 |
commit | 540ad0223ae26c0deae250c3ace2092904290a8b (patch) | |
tree | 67758dd7423b31699b621903816921e35034e94a | |
parent | 99c5d831613bf49afc702dc6aca7ce47b30eab7b (diff) | |
download | scala-540ad0223ae26c0deae250c3ace2092904290a8b.tar.gz scala-540ad0223ae26c0deae250c3ace2092904290a8b.tar.bz2 scala-540ad0223ae26c0deae250c3ace2092904290a8b.zip |
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.
-rw-r--r-- | src/library/scala/collection/immutable/TreeMap.scala | 2 | ||||
-rw-r--r-- | 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) |