diff options
author | Eugene Vigdorchik <eugene.vigdorchik@gmail.com> | 2013-05-22 19:51:47 +0400 |
---|---|---|
committer | Eugene Vigdorchik <eugene.vigdorchik@gmail.com> | 2013-05-22 21:18:07 +0400 |
commit | 84d9b520c2836488e4e1268ad972d232ab54b1c7 (patch) | |
tree | 8e390d343894fa02f06fb6cbf8955b3c72381130 /src | |
parent | 085b4d9bdb7ba9f9fe00c63e998e93278a34b161 (diff) | |
download | scala-84d9b520c2836488e4e1268ad972d232ab54b1c7.tar.gz scala-84d9b520c2836488e4e1268ad972d232ab54b1c7.tar.bz2 scala-84d9b520c2836488e4e1268ad972d232ab54b1c7.zip |
SI-7502 removing non-existent element from ListMap returns same map.
Current imperative version constructs a new ListMap regardless of
the fact the map doesn't contain the element. Replace it with the
tail-recursive variant that conserves. Also replace some usages with
the invariant now held.
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 39 |
2 files changed, 15 insertions, 28 deletions
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index 44e5304e09..e74a19ef5b 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -247,7 +247,9 @@ object HashMap extends ImmutableMapFactory[HashMap] with BitOperations.Int { override def removed0(key: A, hash: Int, level: Int): HashMap[A, B] = if (hash == this.hash) { val kvs1 = kvs - key - if (kvs1.isEmpty) + if (kvs1 eq kvs) + this + else if (kvs1.isEmpty) HashMap.empty[A,B] else if(kvs1.tail.isEmpty) { val kv = kvs1.head diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 47593a07ab..49295d92dd 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -181,7 +181,7 @@ extends AbstractMap[A, B] * it will be overridden by this function. */ override def updated [B2 >: B1](k: A, v: B2): ListMap[A, B2] = { - val m = if (contains(k)) this - k else this + val m = this - k new m.Node[B2](k, v) } @@ -189,32 +189,17 @@ extends AbstractMap[A, B] * If the map does not contain a mapping for the given key, the * method returns the same map. */ - override def - (k: A): ListMap[A, B1] = { - // This definition used to result in stack overflows - // if (k == key) - // next - // else { - // val tail = next - k - // if (tail eq next) this - // else new tail.Node(key, value) - // } - // we use an imperative one instead (and use an auxiliary list to preserve order!): - var cur: ListMap[A, B1] = this - var lst: List[(A, B1)] = Nil - while (cur.nonEmpty) { - if (k != cur.key) lst ::= ((cur.key, cur.value)) - cur = cur.tail - } - var acc = ListMap[A, B1]() - while (lst != Nil) { - val elem = lst.head - val stbl = acc - acc = new stbl.Node(elem._1, elem._2) - lst = lst.tail - } - acc - } - + override def - (k: A): ListMap[A, B1] = remove0(k, this, Nil) + + @tailrec private def remove0(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] = + if (cur.isEmpty) + acc.last + else if (k == cur.key) + (cur.tail /: acc) { + case (t, h) => val tt = t; new tt.Node(h.key, h.value) // SI-7459 + } + else + remove0(k, cur.tail, cur::acc) override def tail: ListMap[A, B1] = ListMap.this } |