diff options
Diffstat (limited to 'src/library/scala/collection/immutable/ListMap.scala')
-rw-r--r-- | src/library/scala/collection/immutable/ListMap.scala | 31 |
1 files changed, 26 insertions, 5 deletions
diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala index 1eedf93269..e1bcc0711c 100644 --- a/src/library/scala/collection/immutable/ListMap.scala +++ b/src/library/scala/collection/immutable/ListMap.scala @@ -13,13 +13,16 @@ package collection package immutable import generic._ -import scala.annotation.{tailrec, bridge} +import scala.annotation.tailrec /** $factoryInfo * @since 1 * @see [[http://docs.scala-lang.org/overviews/collections/concrete-immutable-collection-classes.html#list_maps "Scala's Collection Library overview"]] * section on `List Maps` for more information. * + * Note that `ListMap` is built in reverse order to canonical traversal order (traversal order is oldest first). + * Thus, `head` and `tail` are O(n). To rapidly partition a `ListMap` into elements, use `last` and `init` instead. These are O(1). + * * @define Coll immutable.ListMap * @define coll immutable list map */ @@ -29,7 +32,13 @@ object ListMap extends ImmutableMapFactory[ListMap] { new MapCanBuildFrom[A, B] def empty[A, B]: ListMap[A, B] = EmptyListMap.asInstanceOf[ListMap[A, B]] - private object EmptyListMap extends ListMap[Any, Nothing] { } + @SerialVersionUID(-8256686706655863282L) + private object EmptyListMap extends ListMap[Any, Nothing] { + override def apply(key: Any) = throw new NoSuchElementException("key not found: " + key) + override def contains(key: Any) = false + override def last: (Any, Nothing) = throw new NoSuchElementException("Empty ListMap") + override def init: ListMap[Any, Nothing] = throw new NoSuchElementException("Empty ListMap") + } } /** This class implements immutable maps using a list-based data structure, which preserves insertion order. @@ -49,8 +58,7 @@ object ListMap extends ImmutableMapFactory[ListMap] { * @define willNotTerminateInf */ @SerialVersionUID(301002838095710379L) -@deprecatedInheritance("The semantics of immutable collections makes inheriting from ListMap error-prone.", "2.11.0") -class ListMap[A, +B] +sealed class ListMap[A, +B] extends AbstractMap[A, B] with Map[A, B] with MapLike[A, B, ListMap[A, B]] @@ -159,7 +167,6 @@ 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 (cur.isEmpty) throw new NoSuchElementException("key not found: "+k) else if (k == cur.key) cur.value @@ -177,6 +184,15 @@ extends AbstractMap[A, B] if (k == cur.key) Some(cur.value) else if (cur.next.nonEmpty) get0(cur.next, k) else None + + override def contains(key: A): Boolean = contains0(this, key) + + @tailrec private def contains0(cur: ListMap[A, B1], k: A): Boolean = + if (k == cur.key) true + else if (cur.next.nonEmpty) contains0(cur.next, k) + else false + + /** 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`, * it will be overridden by this function. @@ -186,6 +202,7 @@ extends AbstractMap[A, B] new m.Node[B2](k, v) } + /** Creates a new mapping without the given `key`. * If the map does not contain a mapping for the given key, the * method returns the same map. @@ -203,5 +220,9 @@ extends AbstractMap[A, B] remove0(k, cur.next, cur::acc) override protected def next: ListMap[A, B1] = ListMap.this + + override def last: (A, B1) = (key, value) + + override def init: ListMap[A, B1] = next } } |