Make ListMap and ListSet implementations similar

ListSet and ListMap are two collections which share the exact same internal structure. This commit makes the two approaches as similar as possible by renaming and reordering internal methods, improving their Scaladoc and their code style. The Scaladoc of the classes and companion objects is also improved in order to alert users of the time complexity of the collections' operations.

4 files changed, 160 insertions, 251 deletions

diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index 9af05183dd..589f8bbba9 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -6,8 +6,6 @@
 **                          |/                                          **
 \*                                                                      */
 
-
-
 package scala
 package collection
 package immutable
@@ -15,117 +13,79 @@ package immutable
 import generic._
 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
- */
+/**
+  * $factoryInfo
+  *
+  * Note that each element insertion takes O(n) time, which means that creating a list map with
+  * n elements will take O(n^2^) time. This makes the builder suitable only for a small number of
+  * elements.
+  *
+  * @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.
+  * @since 1
+  * @define Coll ListMap
+  * @define coll list map
+  */
 object ListMap extends ImmutableMapFactory[ListMap] {
-  /** $mapCanBuildFromInfo */
+
+  /**
+    * $mapCanBuildFromInfo
+    */
   implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), ListMap[A, B]] =
     new MapCanBuildFrom[A, B]
+
   def empty[A, B]: ListMap[A, B] = EmptyListMap.asInstanceOf[ListMap[A, B]]
 
   @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")
-  }
+  private object EmptyListMap extends ListMap[Any, Nothing]
 }
 
-/** This class implements immutable maps using a list-based data structure, which preserves insertion order.
- *  Instances of `ListMap` represent empty maps; they can be either created by
- *  calling the constructor directly, or by applying the function `ListMap.empty`.
- *
- *  @tparam A     the type of the keys in this list map.
- *  @tparam B     the type of the values associated with the keys.
- *
- *  @author  Matthias Zenger
- *  @author  Martin Odersky
- *  @version 2.0, 01/01/2007
- *  @since   1
- *  @define Coll immutable.ListMap
- *  @define coll immutable list map
- *  @define mayNotTerminateInf
- *  @define willNotTerminateInf
- */
+/**
+  * This class implements immutable maps using a list-based data structure. List map iterators and
+  * traversal methods visit key-value pairs in the order whey were first inserted.
+  *
+  * Entries are stored internally in reversed insertion order, which means the newest key is at the
+  * head of the list. As such, methods such as `head` and `tail` are O(n), while `last` and `init`
+  * are O(1). Other operations, such as inserting or removing entries, are also O(n), which makes
+  * this collection suitable only for a small number of elements.
+  *
+  * Instances of `ListMap` represent empty maps; they can be either created by calling the
+  * constructor directly, or by applying the function `ListMap.empty`.
+  *
+  * @tparam A the type of the keys contained in this list map
+  * @tparam B the type of the values associated with the keys
+  *
+  * @author Matthias Zenger
+  * @author Martin Odersky
+  * @version 2.0, 01/01/2007
+  * @since 1
+  * @define Coll ListMap
+  * @define coll list map
+  * @define mayNotTerminateInf
+  * @define willNotTerminateInf
+  */
 @SerialVersionUID(301002838095710379L)
-sealed class ListMap[A, +B]
-extends AbstractMap[A, B]
-   with Map[A, B]
-   with MapLike[A, B, ListMap[A, B]]
-   with Serializable {
+sealed class ListMap[A, +B] extends AbstractMap[A, B]
+  with Map[A, B]
+  with MapLike[A, B, ListMap[A, B]]
+  with Serializable {
 
   override def empty = ListMap.empty
 
-  /** Returns the number of mappings in this map.
-   *
-   *  @return number of mappings in this map.
-   */
   override def size: Int = 0
+  override def isEmpty: Boolean = true
 
-  /** Checks if this map maps `key` to a value and return the
-   *  value if it exists.
-   *
-   *  @param  key the key of the mapping of interest
-   *  @return     the value of the mapping, if it exists
-   */
   def get(key: A): Option[B] = 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`,
-   *  it will be overridden by this function.
-   *
-   *  @param key  the key element of the updated entry.
-   *  @param value the value element of the updated entry.
-   */
-  override def updated [B1 >: B] (key: A, value: B1): ListMap[A, B1] =
-    new Node[B1](key, value)
-
-  /** Add a key/value pair to this map.
-   *  @param    kv the key/value pair
-   *  @return   A new map with the new binding added to this map
-   */
-  def + [B1 >: B] (kv: (A, B1)): ListMap[A, B1] = updated(kv._1, kv._2)
-
-  /** Adds two or more elements to this collection and returns
-   *  either the collection itself (if it is mutable), or a new collection
-   *  with the added elements.
-   *
-   *  @param elem1 the first element to add.
-   *  @param elem2 the second element to add.
-   *  @param elems the remaining elements to add.
-   */
-  override def + [B1 >: B] (elem1: (A, B1), elem2: (A, B1), elems: (A, B1) *): ListMap[A, B1] =
-    this + elem1 + elem2 ++ elems
-
-  /** Adds a number of elements provided by a traversable object
-   *  and returns a new collection with the added elements.
-   *
-   *  @param xs     the traversable object.
-   */
+  override def updated[B1 >: B](key: A, value: B1): ListMap[A, B1] = new Node[B1](key, value)
+
+  def +[B1 >: B](kv: (A, B1)): ListMap[A, B1] = new Node[B1](kv._1, kv._2)
+  def -(key: A): ListMap[A, B] = this
+
   override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): ListMap[A, B1] =
     if (xs.isEmpty) this
     else ((repr: ListMap[A, B1]) /: xs) (_ + _)
 
-  /** This 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.
-   *
-   *  @param key a map without a mapping for the given key.
-   */
-  def - (key: A): ListMap[A, B] = this
-
-  /** Returns an iterator over key-value pairs.
-   */
   def iterator: Iterator[(A, B)] = {
     def reverseList = {
       var curr: ListMap[A, B] = this
@@ -139,90 +99,68 @@ extends AbstractMap[A, B]
     reverseList.iterator
   }
 
-  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")
+  protected def key: A = throw new NoSuchElementException("key of empty map")
+  protected def value: B = throw new NoSuchElementException("value of empty map")
+  protected def next: ListMap[A, B] = throw new NoSuchElementException("next of empty map")
+
+  override def stringPrefix = "ListMap"
 
-  /** This class represents an entry in the `ListMap`.
-   */
+  /**
+    * Represents an entry in the `ListMap`.
+    */
   @SerialVersionUID(-6453056603889598734L)
   protected class Node[B1 >: B](override protected val key: A,
                                 override protected val value: B1) extends ListMap[A, B1] with Serializable {
-    /** Returns the number of mappings in this map.
-     *
-     *  @return number of mappings.
-     */
-    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?
-     *
-     *  @return true, iff the map is empty.
-     */
-    override def isEmpty: Boolean = false
 
-    /** Retrieves the value which is associated with the given key. This
-     *  method throws an exception if there is no mapping from the given
-     *  key to a value.
-     *
-     *  @param  k   the key
-     *  @return     the value associated with the given key.
-     */
-    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
-      else apply0(cur.next, k)
+    override def size: Int = sizeInternal(this, 0)
+
+    @tailrec private[this] def sizeInternal(cur: ListMap[A, B1], acc: Int): Int =
+      if (cur.isEmpty) acc
+      else sizeInternal(cur.next, acc + 1)
+
+    override def isEmpty: Boolean = false
 
-    /** Checks if this map maps `key` to a value and return the
-     *  value if it exists.
-     *
-     *  @param  k   the key of the mapping of interest
-     *  @return     the value of the mapping, if it exists
-     */
-    override def get(k: A): Option[B1] = get0(this, k)
+    override def apply(k: A): B1 = applyInternal(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
+    @tailrec private[this] def applyInternal(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 applyInternal(cur.next, k)
 
+    override def get(k: A): Option[B1] = getInternal(this, k)
 
-    override def contains(key: A): Boolean = contains0(this, key)
+    @tailrec private[this] def getInternal(cur: ListMap[A, B1], k: A): Option[B1] =
+      if (cur.isEmpty) None
+      else if (k == cur.key) Some(cur.value)
+      else getInternal(cur.next, k)
 
-    @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
+    override def contains(k: A): Boolean = containsInternal(this, k)
 
+    @tailrec private[this] def containsInternal(cur: ListMap[A, B1], k: A): Boolean =
+      if(cur.isEmpty) false
+      else if (k == cur.key) true
+      else containsInternal(cur.next, k)
 
-    /** 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.
-     */
-    override def updated [B2 >: B1](k: A, v: B2): ListMap[A, B2] = {
+    override def updated[B2 >: B1](k: A, v: B2): ListMap[A, B2] = {
       val m = this - k
       new m.Node[B2](k, v)
     }
 
+    override def +[B2 >: B1](kv: (A, B2)): ListMap[A, B2] = {
+      val m = this - kv._1
+      new m.Node[B2](kv._1, kv._2)
+    }
 
-    /** 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.
-     */
-    override def - (k: A): ListMap[A, B1] = remove0(k, this, Nil)
+    override def -(k: A): ListMap[A, B1] = removeInternal(k, this, Nil)
 
-    @tailrec private def remove0(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] =
+    @tailrec private[this] def removeInternal(k: A, cur: ListMap[A, B1], acc: List[ListMap[A, B1]]): ListMap[A, B1] =
       if (cur.isEmpty) acc.last
       else if (k == cur.key) (cur.next /: acc) { case (t, h) => new t.Node(h.key, h.value) }
-      else remove0(k, cur.next, cur::acc)
+      else removeInternal(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
   }
 }
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index 7803e055ed..c9c6558bb9 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -13,84 +13,74 @@ package immutable
 import generic._
 import scala.annotation.tailrec
 
-/** $factoryInfo
- *  @define Coll immutable.ListSet
- *  @define coll immutable list set
- *  @since 1
- */
+/**
+  * $factoryInfo
+  *
+  * Note that each element insertion takes O(n) time, which means that creating a list set with
+  * n elements will take O(n^2^) time. This makes the builder suitable only for a small number of
+  * elements.
+  *
+  * @since 1
+  * @define Coll ListSet
+  * @define coll list set
+  */
 object ListSet extends ImmutableSetFactory[ListSet] {
-  /** setCanBuildFromInfo */
-  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] = setCanBuildFrom[A]
 
-  private object EmptyListSet extends ListSet[Any] { }
+  /**
+    * $setCanBuildFromInfo
+    */
+  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] =
+    setCanBuildFrom[A]
+
+  private object EmptyListSet extends ListSet[Any]
   private[collection] def emptyInstance: ListSet[Any] = EmptyListSet
 }
 
-/** This class implements immutable sets using a list-based data
- *  structure. Instances of `ListSet` represent
- *  empty sets; they can be either created by calling the constructor
- *  directly, or by applying the function `ListSet.empty`.
- *
- *  @tparam A    the type of the elements contained in this list set.
- *
- *  @author  Matthias Zenger
- *  @version 1.0, 09/07/2003
- *  @since   1
- *  @define Coll immutable.ListSet
- *  @define coll immutable list set
- *  @define mayNotTerminateInf
- *  @define willNotTerminateInf
- */
+/**
+  * This class implements immutable sets using a list-based data structure. List set iterators and
+  * traversal methods visit elements in the order whey were first inserted.
+  *
+  * Elements are stored internally in reversed insertion order, which means the newest element is at
+  * the head of the list. As such, methods such as `head` and `tail` are O(n), while `last` and
+  * `init` are O(1). Other operations, such as inserting or removing entries, are also O(n), which
+  * makes this collection suitable only for a small number of elements.
+  *
+  * Instances of `ListSet` represent empty sets; they can be either created by calling the
+  * constructor directly, or by applying the function `ListSet.empty`.
+  *
+  * @tparam A the type of the elements contained in this list set
+  *
+  * @author Matthias Zenger
+  * @version 1.0, 09/07/2003
+  * @since 1
+  * @define Coll ListSet
+  * @define coll list set
+  * @define mayNotTerminateInf
+  * @define willNotTerminateInf
+  */
 sealed class ListSet[A] extends AbstractSet[A]
-                    with Set[A]
-                    with GenericSetTemplate[A, ListSet]
-                    with SetLike[A, ListSet[A]]
-                    with Serializable{ self =>
+  with Set[A]
+  with GenericSetTemplate[A, ListSet]
+  with SetLike[A, ListSet[A]]
+  with Serializable {
+
   override def companion: GenericCompanion[ListSet] = ListSet
 
-  /** Returns the number of elements in this set.
-   *
-   *  @return number of set elements.
-   */
   override def size: Int = 0
   override def isEmpty: Boolean = true
 
-  /** Checks if this set contains element `elem`.
-   *
-   *  @param  elem    the element to check for membership.
-   *  @return `'''true'''`, iff `elem` is contained in this set.
-   */
   def contains(elem: A): Boolean = false
 
-  /** This method creates a new set with an additional element.
-   */
-  def + (elem: A): ListSet[A] = new Node(elem)
-
-  /** `-` can be used to remove a single element.
-   */
-  def - (elem: A): ListSet[A] = this
+  def +(elem: A): ListSet[A] = new Node(elem)
+  def -(elem: A): ListSet[A] = this
 
-  /** If we are bulk adding elements and desire a runtime measured in
-   *  sub-interstellar time units, we better find a way to avoid traversing
-   *  the collection on each element.  That's what the custom builder does,
-   *  so we take the easy way out and add ourselves and the argument to
-   *  a new builder.
-   */
   override def ++(xs: GenTraversableOnce[A]): ListSet[A] =
     if (xs.isEmpty) this
     else (repr /: xs) (_ + _)
 
-  private[ListSet] def unchecked_outer: ListSet[A] =
-    throw new NoSuchElementException("Empty ListSet has no outer pointer")
-
-  /** Creates a new iterator over all elements contained in this set.
-   *
-   *  @throws java.util.NoSuchElementException
-   *  @return the new iterator
-   */
   def iterator: Iterator[A] = {
     def reverseList = {
-      var curr: ListSet[A] = self
+      var curr: ListSet[A] = this
       var res: List[A] = Nil
       while (!curr.isEmpty) {
         res = curr.elem :: res
@@ -101,62 +91,43 @@ sealed class ListSet[A] extends AbstractSet[A]
     reverseList.iterator
   }
 
-  /**
-   *  @throws java.util.NoSuchElementException
-   */
   protected def elem: A = throw new NoSuchElementException("elem of empty set")
+  protected def next: ListSet[A] = throw new NoSuchElementException("next of empty set")
 
-  /**
-   *  @throws java.util.NoSuchElementException
-   */
-  protected def next: ListSet[A] = throw new NoSuchElementException("Next of an empty set")
+  override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
 
   override def stringPrefix = "ListSet"
 
-  /** Represents an entry in the `ListSet`.
-   */
-  protected class Node(override val elem: A) extends ListSet[A] with Serializable {
-    override private[ListSet] def unchecked_outer = self
+  /**
+    * Represents an entry in the `ListSet`.
+    */
+  protected class Node(override protected val elem: A) extends ListSet[A] with Serializable {
 
-    /** Returns the number of elements in this set.
-     *
-     *  @return number of set elements.
-     */
     override def size = sizeInternal(this, 0)
-    @tailrec private def sizeInternal(n: ListSet[A], acc: Int): Int =
+
+    @tailrec private[this] def sizeInternal(n: ListSet[A], acc: Int): Int =
       if (n.isEmpty) acc
-      else sizeInternal(n.unchecked_outer, acc + 1)
+      else sizeInternal(n.next, acc + 1)
 
-    /** Checks if this set is empty.
-     *
-     *  @return true, iff there is no element in the set.
-     */
     override def isEmpty: Boolean = false
 
-    /** Checks if this set contains element `elem`.
-     *
-     *  @param  e       the element to check for membership.
-     *  @return `'''true'''`, iff `elem` is contained in this set.
-     */
     override def contains(e: A) = containsInternal(this, e)
-    @tailrec private def containsInternal(n: ListSet[A], e: A): Boolean =
-      !n.isEmpty && (n.elem == e || containsInternal(n.unchecked_outer, e))
 
-    /** This method creates a new set with an additional element.
-     */
+    @tailrec private[this] def containsInternal(n: ListSet[A], e: A): Boolean =
+      !n.isEmpty && (n.elem == e || containsInternal(n.next, e))
+
     override def +(e: A): ListSet[A] = if (contains(e)) this else new Node(e)
 
-    /** `-` can be used to remove a single element from a set.
-     */
     override def -(e: A): ListSet[A] = removeInternal(e, this, Nil)
 
-    @tailrec private def removeInternal(k: A, cur: ListSet[A], acc: List[ListSet[A]]): ListSet[A] =
+    @tailrec private[this] def removeInternal(k: A, cur: ListSet[A], acc: List[ListSet[A]]): ListSet[A] =
       if (cur.isEmpty) acc.last
       else if (k == cur.elem) (cur.next /: acc) { case (t, h) => new t.Node(h.elem) }
       else removeInternal(k, cur.next, cur :: acc)
 
-    override protected def next: ListSet[A] = self
-  }
+    override protected def next: ListSet[A] = ListSet.this
 
-  override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
+    override def last: A = elem
+    override def init: ListSet[A] = next
+  }
 }
diff --git a/test/files/jvm/serialization-new.check b/test/files/jvm/serialization-new.check
index 91248320d4..1c5dd4828b 100644
--- a/test/files/jvm/serialization-new.check
+++ b/test/files/jvm/serialization-new.check
@@ -85,8 +85,8 @@ x = List((buffers,20), (layers,2), (title,3))
 y = List((buffers,20), (layers,2), (title,3))
 x equals y: true, y equals x: true
 
-x = Map(buffers -> 20, layers -> 2, title -> 3)
-y = Map(buffers -> 20, layers -> 2, title -> 3)
+x = ListMap(buffers -> 20, layers -> 2, title -> 3)
+y = ListMap(buffers -> 20, layers -> 2, title -> 3)
 x equals y: true, y equals x: true
 
 x = ListSet(3, 5)
diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check
index 91248320d4..1c5dd4828b 100644
--- a/test/files/jvm/serialization.check
+++ b/test/files/jvm/serialization.check
@@ -85,8 +85,8 @@ x = List((buffers,20), (layers,2), (title,3))
 y = List((buffers,20), (layers,2), (title,3))
 x equals y: true, y equals x: true
 
-x = Map(buffers -> 20, layers -> 2, title -> 3)
-y = Map(buffers -> 20, layers -> 2, title -> 3)
+x = ListMap(buffers -> 20, layers -> 2, title -> 3)
+y = ListMap(buffers -> 20, layers -> 2, title -> 3)
 x equals y: true, y equals x: true
 
 x = ListSet(3, 5)