diff options
author | Paul Phillips <paulp@improving.org> | 2009-11-21 17:24:29 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2009-11-21 17:24:29 +0000 |
commit | 2ea21b6ca0a68ef9015668579d6e0eee1e9ae4be (patch) | |
tree | a973e0ad1afff34f4e4003c381e28f437a71b418 | |
parent | b408d0e98f694add637fc867433c627ca3191062 (diff) | |
download | scala-2ea21b6ca0a68ef9015668579d6e0eee1e9ae4be.tar.gz scala-2ea21b6ca0a68ef9015668579d6e0eee1e9ae4be.tar.bz2 scala-2ea21b6ca0a68ef9015668579d6e0eee1e9ae4be.zip |
Applied performance patch and test case from ij...
Applied performance patch and test case from ijuma; closes #2526.
-rw-r--r-- | src/library/scala/collection/MapLike.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/HashMap.scala | 26 | ||||
-rw-r--r-- | src/library/scala/collection/mutable/HashTable.scala | 13 | ||||
-rw-r--r-- | test/files/run/t2526.scala | 54 |
4 files changed, 95 insertions, 2 deletions
diff --git a/src/library/scala/collection/MapLike.scala b/src/library/scala/collection/MapLike.scala index 3b188acab6..3287a4524c 100644 --- a/src/library/scala/collection/MapLike.scala +++ b/src/library/scala/collection/MapLike.scala @@ -129,7 +129,7 @@ self => protected class DefaultKeySet extends Set[A] { def contains(key : A) = self.contains(key) - def iterator = self.iterator.map(_._1) + def iterator = keysIterator def + (elem: A): Set[A] = (Set[A]() ++ this + elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem def - (elem: A): Set[A] = (Set[A]() ++ this - elem).asInstanceOf[Set[A]] // !!! concrete overrides abstract problem override def size = self.size @@ -158,7 +158,7 @@ self => def valuesIterable: Iterable[B] = new DefaultValuesIterable protected class DefaultValuesIterable extends Iterable[B] { - def iterator = self.iterator.map(_._2) + def iterator = valuesIterator override def size = self.size override def foreach[C](f: B => C) = for ((k, v) <- self) f(v) } diff --git a/src/library/scala/collection/mutable/HashMap.scala b/src/library/scala/collection/mutable/HashMap.scala index b2f259e4e9..e4969a3af0 100644 --- a/src/library/scala/collection/mutable/HashMap.scala +++ b/src/library/scala/collection/mutable/HashMap.scala @@ -58,6 +58,32 @@ class HashMap[A, B] extends Map[A, B] def -=(key: A): this.type = { removeEntry(key); this } def iterator = entriesIterator map {e => (e.key, e.value)} + + override def foreach[C](f: ((A, B)) => C): Unit = foreachEntry(e => f(e.key, e.value)) + + /* Override to avoid tuple allocation in foreach */ + override def keySet: collection.Set[A] = new DefaultKeySet { + override def foreach[C](f: A => C) = foreachEntry(e => f(e.key)) + } + + /* Override to avoid tuple allocation in foreach */ + override def valuesIterable: collection.Iterable[B] = new DefaultValuesIterable { + override def foreach[C](f: B => C) = foreachEntry(e => f(e.value)) + } + + /* Override to avoid tuple allocation */ + override def keysIterator: Iterator[A] = new Iterator[A] { + val iter = entriesIterator + def hasNext = iter.hasNext + def next = iter.next.key + } + + /* Override to avoid tuple allocation */ + override def valuesIterator: Iterator[B] = new Iterator[B] { + val iter = entriesIterator + def hasNext = iter.hasNext + def next = iter.next.value + } } /** This class implements mutable maps using a hashtable. diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 9dd8a7aeb0..db4e100634 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -144,6 +144,19 @@ trait HashTable[A] { } } + protected final def foreachEntry[C](f: Entry => C) { + val t = table + var index = t.length - 1 + while (index >= 0) { + var entry = t(index) + while (entry ne null) { + f(entry.asInstanceOf[Entry]) + entry = entry.next + } + index -= 1 + } + } + /** An iterator returning all entries */ @deprecated("use entriesIterator instead") protected def entries: Iterator[Entry] = entriesIterator diff --git a/test/files/run/t2526.scala b/test/files/run/t2526.scala new file mode 100644 index 0000000000..5f6d60546a --- /dev/null +++ b/test/files/run/t2526.scala @@ -0,0 +1,54 @@ +/** + * Checks that various foreach methods overridden in mutable.HashMap as part of ticket #2526 + * still work correctly. + */ +object Test { + import collection._ + + def main(args: Array[String]) { + val m = new mutable.HashMap[String, String] + + /* Use non hash-based structure for verification */ + val keys = List("a", "b", "c", "d", "e") + val valueSuffix = "value" + val values = keys.map(_ + valueSuffix) + val entries = keys.zip(values) + + for (k <- keys) m(k) = k + valueSuffix + + assertForeach(keys, m.keySet.iterator) + assertForeach(keys, m.keysIterator) + assertForeach(keys, m.keySet) + + assertForeach(values, m.valuesIterable.iterator) + assertForeach(values, m.valuesIterator) + assertForeach(values, m.valuesIterable) + + assertForeach(entries, m) + } + + /* Checks foreach of `actual` goes over all the elements in `expected` */ + private def assertForeach[E](expected: Traversable[E], actual: Iterator[E]): Unit = { + val notYetFound = new mutable.ArrayBuffer[E]() ++= expected + actual.foreach { e => + assert(notYetFound.contains(e)) + notYetFound -= e + } + assert(notYetFound.size == 0, "mutable.HashMap.foreach should have iterated over: " + notYetFound) + } + + /* + * Checks foreach of `actual` goes over all the elements in `expected` + * We duplicate the method above because there is no common inteface between Traverable and + * Iterator and we want to avoid converting between collections to ensure that we test what + * we mean to test. + */ + private def assertForeach[E](expected: Traversable[E], actual: Traversable[E]): Unit = { + val notYetFound = new mutable.ArrayBuffer[E]() ++= expected + actual.foreach { e => + assert(notYetFound.contains(e)) + notYetFound -= e + } + assert(notYetFound.size == 0, "mutable.HashMap.foreach should have iterated over: " + notYetFound) + } +} |