diff options
author | Vinicius Miana <vinicius@miana.com.br> | 2013-01-23 22:18:27 -0200 |
---|---|---|
committer | Vinicius Miana <vinicius@miana.com.br> | 2013-01-25 17:56:39 -0200 |
commit | e36327ac2af54e70a391b4dbf036a5e627d65fee (patch) | |
tree | dc25ebaf753d2218f3064062bba02f4893766e3e /src/library | |
parent | 1a63cf8b9b48c98fa754a1eb6dcfe35220016c74 (diff) | |
download | scala-e36327ac2af54e70a391b4dbf036a5e627d65fee.tar.gz scala-e36327ac2af54e70a391b4dbf036a5e627d65fee.tar.bz2 scala-e36327ac2af54e70a391b4dbf036a5e627d65fee.zip |
SI-6853 changed private method remove to be tail recursive.
Operations += and -= on mutable.ListMap rely on the private method remove to perform. This methods was implemented using recursion, but it was not tail recursive. When the ListMap got too big the += caused a StackOverflowError.
Diffstat (limited to 'src/library')
-rw-r--r-- | src/library/scala/collection/mutable/ListMap.scala | 17 |
1 files changed, 11 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 |