diff options
author | Ruediger Klaehn <rklaehn@gmail.com> | 2012-08-25 00:27:55 +0200 |
---|---|---|
committer | Ruediger Klaehn <rklaehn@gmail.com> | 2012-08-25 00:27:55 +0200 |
commit | ace7a61e663e8369cc50e527c990ee4c3751cb89 (patch) | |
tree | bf6553943ed416fbd73b5f94bf9c768dd3f2254d /src | |
parent | 460d4f22b04ac1a29a73af16b750252ddce74579 (diff) | |
download | scala-ace7a61e663e8369cc50e527c990ee4c3751cb89.tar.gz scala-ace7a61e663e8369cc50e527c990ee4c3751cb89.tar.bz2 scala-ace7a61e663e8369cc50e527c990ee4c3751cb89.zip |
Made ListMap.tail O(1) instead of O(N)
That way it is possible to check if a ListMap has one element by checking x.tail.isEmpty. Size is O(1), so size==1 won't do!
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 091443f909..c21032603f 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -121,12 +121,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.next; res } + else { val res = (self.key, self.value); self = self.tail; res } }.toList.reverseIterator protected def key: A = throw new NoSuchElementException("empty map") protected def value: B = throw new NoSuchElementException("empty map") - protected def next: ListMap[A, B] = throw new NoSuchElementException("empty map") + override def tail: ListMap[A, B] = throw new NoSuchElementException("empty map") /** This class represents an entry in the `ListMap`. */ @@ -140,7 +140,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.next, acc + 1) + @tailrec private def size0(cur: ListMap[A, B1], acc: Int): Int = if (cur.isEmpty) acc else size0(cur.tail, acc + 1) /** Is this an empty map? * @@ -157,7 +157,7 @@ extends AbstractMap[A, B] */ 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) + @tailrec private def apply0(cur: ListMap[A, B1], k: A): B1 = if (k == cur.key) cur.value else apply0(cur.tail, k) /** Checks if this map maps `key` to a value and return the * value if it exists. @@ -169,7 +169,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.next.nonEmpty) get0(cur.next, k) else None + else if (cur.tail.nonEmpty) get0(cur.tail, 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`, @@ -198,7 +198,7 @@ extends AbstractMap[A, B] var lst: List[(A, B1)] = Nil while (cur.nonEmpty) { if (k != cur.key) lst ::= ((cur.key, cur.value)) - cur = cur.next + cur = cur.tail } var acc = ListMap[A, B1]() while (lst != Nil) { @@ -211,6 +211,6 @@ extends AbstractMap[A, B] } - override protected def next: ListMap[A, B1] = ListMap.this + override def tail: ListMap[A, B1] = ListMap.this } } |