diff options
author | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-11-17 17:04:09 +0000 |
---|---|---|
committer | Aleksandar Pokopec <aleksandar.prokopec@epfl.ch> | 2010-11-17 17:04:09 +0000 |
commit | 9266922e1bfcbbebc9b5926864f7e70e49e142e7 (patch) | |
tree | 594831f5ab6738da2a17190f52641fb9e0eb45d9 /src | |
parent | 048abea8290d2bbb689196e68ada76d5ad368ba9 (diff) | |
download | scala-9266922e1bfcbbebc9b5926864f7e70e49e142e7.tar.gz scala-9266922e1bfcbbebc9b5926864f7e70e49e142e7.tar.bz2 scala-9266922e1bfcbbebc9b5926864f7e70e49e142e7.zip |
Fixes #3989, adding test cases for #3989 and #3...
Fixes #3989, adding test cases for #3989 and #3996.
No review.
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 41 |
1 files changed, 29 insertions, 12 deletions
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 088d7e22cb..4b7e512e47 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -12,6 +12,7 @@ package scala.collection package immutable import generic._ +import annotation.tailrec /** $factoryInfo * @since 1 @@ -129,7 +130,10 @@ class ListMap[A, +B] extends Map[A, B] with MapLike[A, B, ListMap[A, B]] { * * @return number of mappings. */ - override def size: Int = next.size + 1 + 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.next, acc + 1) /** Is this an empty map? * @@ -144,7 +148,9 @@ class ListMap[A, +B] extends Map[A, B] with MapLike[A, B, ListMap[A, B]] { * @param key the key * @return the value associated with the given key. */ - override def apply(k: A): B1 = if (k == key) value else next(k) + override def apply(k: A): B1 = apply0(this, k) + + @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.next, k) /** Checks if this map maps <code>key</code> to a value and return the * value if it exists. @@ -152,8 +158,11 @@ class ListMap[A, +B] extends Map[A, B] with MapLike[A, B, ListMap[A, B]] { * @param key the key of the mapping of interest * @return the value of the mapping, if it exists */ - override def get(k: A): Option[B1] = - if (k == key) Some(value) else next.get(k) + override def get(k: A): Option[B1] = get0(this, k) + + @tailrec private def get0(cur: ListMap[A, B1], k: A): Option[B1] = + if (k == cur.key) Some(cur.value) + 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`, @@ -174,14 +183,22 @@ class ListMap[A, +B] extends Map[A, B] with MapLike[A, B, ListMap[A, B]] { * @param k ... * @return ... */ - override def - (k: A): ListMap[A, B1] = - if (k == key) - next - else { - val tail = next - k - if (tail eq next) this - else new tail.Node(key, value) - } + override def - (k: A): ListMap[A, B1] = remove0(this, k, ListMap[A, B1]()) + + // this solution was nicer and possibly more efficient, but resulted in stack overflows: + // if (k == key) + // next + // else { + // val tail = next - k + // if (tail eq next) this + // else new tail.Node(key, value) + // } + + @tailrec private def remove0(cur: ListMap[A, B1], k: A, acc: ListMap[A, B1]): ListMap[A, B1] = + if (cur.nonEmpty) { + if (k == cur.key) remove0(cur.next, k, acc) + else remove0(cur.next, k, new acc.Node(cur.key, cur.value)) + } else cur override protected def next: ListMap[A, B1] = ListMap.this } |