1 files changed, 87 insertions, 135 deletions
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index adc975479a..d9795e9161 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -11,174 +11,126 @@ package collection
 package immutable
 
 import generic._
-import scala.annotation.{tailrec, bridge}
-import mutable.{ ListBuffer, Builder }
-
-/** $factoryInfo
- *  @define Coll immutable.ListSet
- *  @define coll immutable list set
- *  @since 1
- */
+import scala.annotation.tailrec
+
+/**
+  * $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]
 
-  override def newBuilder[A]: Builder[A, ListSet[A]] = new ListSetBuilder[A]
+  /**
+    * $setCanBuildFromInfo
+    */
+  implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] =
+    setCanBuildFrom[A]
 
-  private object EmptyListSet extends ListSet[Any] { }
+  @SerialVersionUID(5010379588739277132L)
+  private object EmptyListSet extends ListSet[Any]
   private[collection] def emptyInstance: ListSet[Any] = EmptyListSet
-
-  /** A custom builder because forgetfully adding elements one at
-   *  a time to a list backed set puts the "squared" in N^2.  There is a
-   *  temporary space cost, but it's improbable a list backed set could
-   *  become large enough for this to matter given its pricy element lookup.
-   */
-  class ListSetBuilder[Elem](initial: ListSet[Elem]) extends Builder[Elem, ListSet[Elem]] {
-    def this() = this(empty[Elem])
-    protected val elems = (new mutable.ListBuffer[Elem] ++= initial).reverse
-    protected val seen  = new mutable.HashSet[Elem] ++= initial
-
-    def +=(x: Elem): this.type = {
-      if (!seen(x)) {
-        elems += x
-        seen += x
-      }
-      this
-    }
-    def clear() = { elems.clear() ; seen.clear() }
-    def result() = elems.foldLeft(empty[Elem])(_ unchecked_+ _)
-  }
 }
 
-/** 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
- */
-@deprecatedInheritance("The semantics of immutable collections makes inheriting from ListSet error-prone.", "2.11.0")
-class ListSet[A] extends AbstractSet[A]
-                    with Set[A]
-                    with GenericSetTemplate[A, ListSet]
-                    with SetLike[A, ListSet[A]]
-                    with Serializable{ self =>
+/**
+  * 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
+  */
+@SerialVersionUID(-8417059026623606218L)
+sealed class ListSet[A] extends AbstractSet[A]
+  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 (new ListSet.ListSetBuilder(this) ++= xs.seq).result()
-
-  private[ListSet] def unchecked_+(e: A): ListSet[A] = new Node(e)
-  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] = new AbstractIterator[A] {
-    var that: ListSet[A] = self
-    def hasNext = that.nonEmpty
-    def next: A =
-      if (hasNext) {
-        val res = that.head
-        that = that.tail
-        res
+    else (repr /: xs) (_ + _)
+
+  def iterator: Iterator[A] = {
+    def reverseList = {
+      var curr: ListSet[A] = this
+      var res: List[A] = Nil
+      while (!curr.isEmpty) {
+        res = curr.elem :: res
+        curr = curr.next
       }
-      else Iterator.empty.next()
+      res
+    }
+    reverseList.iterator
   }
 
-  /**
-   *  @throws java.util.NoSuchElementException
-   */
-  override def head: A = throw new NoSuchElementException("Set has no elements")
+  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
-   */
-  override def tail: 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 head: A) extends ListSet[A] with Serializable {
-    override private[ListSet] def unchecked_outer = self
+  /**
+    * Represents an entry in the `ListSet`.
+    */
+  @SerialVersionUID(-787710309854855049L)
+  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.head == 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] = if (e == head) self else {
-      val tail = self - e; new tail.Node(head)
-    }
+    override def -(e: A): ListSet[A] = removeInternal(e, this, Nil)
+
+    @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 def tail: ListSet[A] = self
+    override protected def next: ListSet[A] = ListSet.this
+
+    override def last: A = elem
+    override def init: ListSet[A] = next
   }
-  
-  override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
 }