diff options
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 4 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 39 | ||||
-rwxr-xr-x | test/files/run/list_map.scala | 26 |
3 files changed, 41 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 } diff --git a/test/files/run/list_map.scala b/test/files/run/list_map.scala new file mode 100755 index 0000000000..fba3aae228 --- /dev/null +++ b/test/files/run/list_map.scala @@ -0,0 +1,26 @@ +import collection.immutable.ListMap + +object Test { + def testImmutableMinus() { + val empty = ListMap.empty[Int, Int] + + val m0 = ListMap(1 -> 1, 2 -> 2) + val m1 = m0 - 3 + assert (m1 eq m0) + val m2 = m0 - 1 + assert (m2.size == 1) + val m3 = m2 - 2 + assert (m3 eq empty) + + val m4 = ListMap(1 -> 1, 2 -> 2, 3 -> 3) + val m5 = m4 - 1 + assert (m5 == ListMap(2 -> 2, 3 -> 3)) + assert (m5.toList == (2, 2)::(3, 3)::Nil) + + assert ((empty - 1) eq empty) + } + + def main(args: Array[String]) { + testImmutableMinus() + } +} |