diff options
author | Ruediger Klaehn <rklaehn@gmail.com> | 2014-01-20 21:37:21 +0100 |
---|---|---|
committer | Ruediger Klaehn <rklaehn@gmail.com> | 2014-01-20 23:42:16 +0100 |
commit | 7f65b37a30cb0162711e3889edd35b2608ffa729 (patch) | |
tree | a02c7fc1bad6ddb5e5f15b9435eb8bff8f51cc59 | |
parent | 8f6f4032b5c026fd9301cebe28dde5bb7c8e264c (diff) | |
download | scala-7f65b37a30cb0162711e3889edd35b2608ffa729.tar.gz scala-7f65b37a30cb0162711e3889edd35b2608ffa729.tar.bz2 scala-7f65b37a30cb0162711e3889edd35b2608ffa729.zip |
SI-7445 ListMap.tail is returning wrong result
Reverted the commit that introduced the bug, and modified HashMap to no
longer assume that tail is O(1).
Review by @Ichoran, @soc
-rw-r--r-- | src/library/scala/collection/immutable/HashMap.scala | 20 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 16 | ||||
-rw-r--r-- | test/files/run/t6261.scala | 7 | ||||
-rw-r--r-- | test/files/run/t7445.scala | 6 |
4 files changed, 25 insertions, 24 deletions
diff --git a/src/library/scala/collection/immutable/HashMap.scala b/src/library/scala/collection/immutable/HashMap.scala index e7d87dd3fe..8a24f721d7 100644 --- a/src/library/scala/collection/immutable/HashMap.scala +++ b/src/library/scala/collection/immutable/HashMap.scala @@ -247,15 +247,17 @@ 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 eq kvs) - this - else if (kvs1.isEmpty) - HashMap.empty[A,B] - else if(kvs1.tail.isEmpty) { - val kv = kvs1.head - new HashMap1[A,B](kv._1,hash,kv._2,kv) - } else - new HashMapCollision1(hash, kvs1) + kvs1.size match { + case 0 => + HashMap.empty[A,B] + case 1 => + val kv = kvs1.head + new HashMap1(kv._1,hash,kv._2,kv) + case x if x == kvs.size => + this + case _ => + new HashMapCollision1(hash, kvs1) + } } else this override protected def filter0(p: ((A, B)) => Boolean, negate: Boolean, level: Int, buffer: Array[HashMap[A, B @uV]], offset0: Int): HashMap[A, B] = { diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index b2a1b1ce29..7c40e84280 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -123,12 +123,12 @@ extends AbstractMap[A, B] def hasNext = !self.isEmpty def next(): (A,B) = if (!hasNext) throw new NoSuchElementException("next on empty iterator") - else { val res = (self.key, self.value); self = self.tail; res } + else { val res = (self.key, self.value); self = self.next; res } }.toList.reverseIterator protected def key: A = throw new NoSuchElementException("empty map") protected def value: B = throw new NoSuchElementException("empty map") - override def tail: ListMap[A, B] = throw new NoSuchElementException("empty map") + protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map") /** This class represents an entry in the `ListMap`. */ @@ -142,7 +142,7 @@ extends AbstractMap[A, B] override def size: Int = size0(this, 0) // to allow tail recursion and prevent stack overflows - @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.tail, acc + 1) + @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.next, acc + 1) /** Is this an empty map? * @@ -163,7 +163,7 @@ extends AbstractMap[A, B] @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (cur.isEmpty) throw new NoSuchElementException("key not found: "+k) else if (k == cur.key) cur.value - else apply0(cur.tail, k) + else apply0(cur.next, k) /** Checks if this map maps `key` to a value and return the * value if it exists. @@ -175,7 +175,7 @@ extends AbstractMap[A, B] @tailrec private def get0(cur: ListMap[A, B1], k: A): Option[B1] = if (k == cur.key) Some(cur.value) - else if (cur.tail.nonEmpty) get0(cur.tail, k) else None + else if (cur.next.nonEmpty) get0(cur.next, k) else None /** This method allows one to create a new map with an additional mapping * from `key` to `value`. If the map contains already a mapping for `key`, @@ -196,12 +196,12 @@ extends AbstractMap[A, B] if (cur.isEmpty) acc.last else if (k == cur.key) - (cur.tail /: acc) { + (cur.next /: acc) { case (t, h) => val tt = t; new tt.Node(h.key, h.value) // SI-7459 } else - remove0(k, cur.tail, cur::acc) + remove0(k, cur.next, cur::acc) - override def tail: ListMap[A, B1] = ListMap.this + override protected def next: ListMap[A, B1] = ListMap.this } } diff --git a/test/files/run/t6261.scala b/test/files/run/t6261.scala index b4463256c9..bf6d640de3 100644 --- a/test/files/run/t6261.scala +++ b/test/files/run/t6261.scala @@ -2,12 +2,6 @@ import scala.collection.immutable._ object Test extends App { - def test0() { - val m=ListMap(1->2,3->4) - if(m.tail ne m.tail) - println("ListMap.tail uses a builder, so it is not O(1)") - } - def test1() { // test that a HashTrieMap with one leaf element is not created! val x = HashMap.empty + (1->1) + (2->2) @@ -92,7 +86,6 @@ object Test extends App { // StructureTests.printStructure(z) require(z.size == 2 && z.contains(a._1) && z.contains(c._1)) } - test0() test1() test2() test3() diff --git a/test/files/run/t7445.scala b/test/files/run/t7445.scala new file mode 100644 index 0000000000..e4ffeb8e1a --- /dev/null +++ b/test/files/run/t7445.scala @@ -0,0 +1,6 @@ +import scala.collection.immutable.ListMap + +object Test extends App { + val a = ListMap(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5); + require(a.tail == ListMap(2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)); +} |