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!

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
   }
 }