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.

1 files changed, 65 insertions, 94 deletions

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