diff options
author | James Iry <jamesiry@gmail.com> | 2013-02-01 09:00:50 -0800 |
---|---|---|
committer | James Iry <jamesiry@gmail.com> | 2013-02-01 09:00:50 -0800 |
commit | 06295f9682b3292b9fca367a559c000fcf0c782d (patch) | |
tree | 37fb1097854a5f8cd283b7687d12bd99b6d17009 | |
parent | 309ff57ba62b6a6ec1a9c1b28b8bbabfd1b47b72 (diff) | |
parent | e36327ac2af54e70a391b4dbf036a5e627d65fee (diff) | |
download | scala-06295f9682b3292b9fca367a559c000fcf0c782d.tar.gz scala-06295f9682b3292b9fca367a559c000fcf0c782d.tar.bz2 scala-06295f9682b3292b9fca367a559c000fcf0c782d.zip |
Merge pull request #1960 from ViniciusMiana/2.10.x
SI-6853 changed private method remove to be tail recursive.
-rw-r--r-- | src/library/scala/collection/mutable/ListMap.scala | 17 | ||||
-rw-r--r-- | test/files/run/t6853.scala | 18 |
2 files changed, 29 insertions, 6 deletions
diff --git a/src/library/scala/collection/mutable/ListMap.scala b/src/library/scala/collection/mutable/ListMap.scala index 212ee917c5..7f05deffc8 100644 --- a/src/library/scala/collection/mutable/ListMap.scala +++ b/src/library/scala/collection/mutable/ListMap.scala @@ -12,6 +12,7 @@ package scala.collection package mutable import generic._ +import annotation.tailrec /** A simple mutable map backed by a list. * @@ -47,13 +48,17 @@ extends AbstractMap[A, B] def get(key: A): Option[B] = elems find (_._1 == key) map (_._2) def iterator: Iterator[(A, B)] = elems.iterator - def += (kv: (A, B)) = { elems = remove(kv._1, elems); elems = kv :: elems; siz += 1; this } - def -= (key: A) = { elems = remove(key, elems); this } - private def remove(key: A, elems: List[(A, B)]): List[(A, B)] = - if (elems.isEmpty) elems - else if (elems.head._1 == key) { siz -= 1; elems.tail } - else elems.head :: remove(key, elems.tail) + def += (kv: (A, B)) = { elems = remove(kv._1, elems, List()); elems = kv :: elems; siz += 1; this } + def -= (key: A) = { elems = remove(key, elems, List()); this } + + @tailrec + private def remove(key: A, elems: List[(A, B)], acc: List[(A, B)]): List[(A, B)] = { + if (elems.isEmpty) acc + else if (elems.head._1 == key) { siz -= 1; acc ::: elems.tail } + else remove(key, elems.tail, elems.head :: acc) + } + override def clear() = { elems = List(); siz = 0 } override def size: Int = siz diff --git a/test/files/run/t6853.scala b/test/files/run/t6853.scala new file mode 100644 index 0000000000..352375c99c --- /dev/null +++ b/test/files/run/t6853.scala @@ -0,0 +1,18 @@ +// Test cases: the only place we can cut and paste without crying +// ourself to sleep. +object Test { + + def main(args: Array[String]): Unit = { + // First testing the basic operations + val m = collection.mutable.ListMap[String, Int]() + var i = 0 + while(i < 2) { m += ("foo" + i) -> i; i = i+1} + assert(m == Map("foo1"->1,"foo0"->0)) + m-= "foo0" + assert(m == Map("foo1"->1)) + // Now checking if it scales as described in SI-6853 + i = 0 + while(i < 80000) { m += ("foo" + i) -> i; i = i+1} + assert(m.size == 80000) + } +} |