From fe6886eb0ec9c02fa666e9e7af09bab92b985d05 Mon Sep 17 00:00:00 2001
From: Rui Gonçalves <ruippeixotog@gmail.com>
Date: Sun, 17 Apr 2016 17:51:17 +0100
Subject: Improve performance and behavior of ListMap and ListSet

Makes the immutable `ListMap` and `ListSet` collections more alike one another, both in their semantics and in their performance.

In terms of semantics, makes the `ListSet` iterator return the elements in their insertion order, as `ListMap` already does. While, as mentioned in SI-8985, `ListMap` and `ListSet` doesn't seem to make any guarantees in terms of iteration order, I believe users expect `ListSet` and `ListMap` to behave in the same way, particularly when they are implemented in the exact same way.

In terms of performance, `ListSet` has a custom builder that avoids creation in O(N^2) time. However, this significantly reduces its performance in the creation of small sets, as its requires the instantiation and usage of an auxilliary HashSet. As `ListMap` and `ListSet` are only suitable for small sizes do to their performance characteristics, the builder is removed, the default `SetBuilder` being used instead.
---
 .../scala/collection/immutable/ListMap.scala       | 34 +++++------
 .../scala/collection/immutable/ListSet.scala       | 67 +++++++---------------
 test/files/jvm/serialization-new.check             |  4 +-
 test/files/jvm/serialization.check                 |  4 +-
 test/files/run/t3822.scala                         | 19 ------
 test/files/run/t6198.scala                         |  7 ---
 test/files/run/t7445.scala                         |  6 --
 .../scala/collection/immutable/ListMapTest.scala   | 48 ++++++++++++++++
 .../scala/collection/immutable/ListSetTest.scala   | 53 +++++++++++++++++
 9 files changed, 144 insertions(+), 98 deletions(-)
 delete mode 100644 test/files/run/t3822.scala
 delete mode 100644 test/files/run/t7445.scala
 create mode 100644 test/junit/scala/collection/immutable/ListMapTest.scala
 create mode 100644 test/junit/scala/collection/immutable/ListSetTest.scala

diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index e1bcc0711c..9af05183dd 100644
--- a/src/library/scala/collection/immutable/ListMap.scala
+++ b/src/library/scala/collection/immutable/ListMap.scala
@@ -113,7 +113,8 @@ extends AbstractMap[A, B]
    *  @param xs     the traversable object.
    */
   override def ++[B1 >: B](xs: GenTraversableOnce[(A, B1)]): ListMap[A, B1] =
-    ((repr: ListMap[A, B1]) /: xs.seq) (_ + _)
+    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
@@ -125,14 +126,18 @@ extends AbstractMap[A, B]
 
   /** Returns an iterator over key-value pairs.
    */
-  def iterator: Iterator[(A,B)] =
-    new AbstractIterator[(A,B)] {
-      var self: ListMap[A,B] = ListMap.this
-      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 }
-    }.toList.reverseIterator
+  def iterator: Iterator[(A, B)] = {
+    def reverseList = {
+      var curr: ListMap[A, B] = this
+      var res: List[(A, B)] = Nil
+      while (!curr.isEmpty) {
+        res = (curr.key, curr.value) :: res
+        curr = curr.next
+      }
+      res
+    }
+    reverseList.iterator
+  }
 
   protected def key: A = throw new NoSuchElementException("empty map")
   protected def value: B = throw new NoSuchElementException("empty map")
@@ -210,14 +215,9 @@ extends AbstractMap[A, B]
     override def - (k: A): ListMap[A, B1] = remove0(k, this, Nil)
 
     @tailrec private def remove0(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) => val tt = t; new tt.Node(h.key, h.value) // SI-7459
-        }
-      else
-        remove0(k, cur.next, cur::acc)
+      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)
 
     override protected def next: ListMap[A, B1] = ListMap.this
 
diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index d20e7bc6d2..7803e055ed 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -12,7 +12,6 @@ package immutable
 
 import generic._
 import scala.annotation.tailrec
-import mutable.{Builder, ReusableBuilder}
 
 /** $factoryInfo
  *  @define Coll immutable.ListSet
@@ -23,33 +22,8 @@ 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]
-
   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.
-   *
-   *  This builder is reusable.
-   */
-  class ListSetBuilder[Elem](initial: ListSet[Elem]) extends ReusableBuilder[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
@@ -104,9 +78,8 @@ sealed class ListSet[A] extends AbstractSet[A]
    */
   override def ++(xs: GenTraversableOnce[A]): ListSet[A] =
     if (xs.isEmpty) this
-    else (new ListSet.ListSetBuilder(this) ++= xs.seq).result()
+    else (repr /: xs) (_ + _)
 
-  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")
 
@@ -115,33 +88,34 @@ sealed class ListSet[A] extends AbstractSet[A]
    *  @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
+  def iterator: Iterator[A] = {
+    def reverseList = {
+      var curr: ListSet[A] = self
+      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")
 
   /**
    *  @throws java.util.NoSuchElementException
    */
-  override def tail: ListSet[A] = throw new NoSuchElementException("Next of an empty set")
+  protected def next: ListSet[A] = throw new NoSuchElementException("Next of an empty set")
 
   override def stringPrefix = "ListSet"
 
   /** Represents an entry in the `ListSet`.
    */
-  protected class Node(override val head: A) extends ListSet[A] with Serializable {
+  protected class Node(override val elem: A) extends ListSet[A] with Serializable {
     override private[ListSet] def unchecked_outer = self
 
     /** Returns the number of elements in this set.
@@ -166,7 +140,7 @@ sealed class ListSet[A] extends AbstractSet[A]
      */
     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))
+      !n.isEmpty && (n.elem == e || containsInternal(n.unchecked_outer, e))
 
     /** This method creates a new set with an additional element.
      */
@@ -174,11 +148,14 @@ sealed class ListSet[A] extends AbstractSet[A]
 
     /** `-` 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 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] = self
   }
 
   override def toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
diff --git a/test/files/jvm/serialization-new.check b/test/files/jvm/serialization-new.check
index cb26446f40..91248320d4 100644
--- a/test/files/jvm/serialization-new.check
+++ b/test/files/jvm/serialization-new.check
@@ -89,8 +89,8 @@ x = Map(buffers -> 20, layers -> 2, title -> 3)
 y = Map(buffers -> 20, layers -> 2, title -> 3)
 x equals y: true, y equals x: true
 
-x = ListSet(5, 3)
-y = ListSet(5, 3)
+x = ListSet(3, 5)
+y = ListSet(3, 5)
 x equals y: true, y equals x: true
 
 x = Queue(a, b, c)
diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check
index cb26446f40..91248320d4 100644
--- a/test/files/jvm/serialization.check
+++ b/test/files/jvm/serialization.check
@@ -89,8 +89,8 @@ x = Map(buffers -> 20, layers -> 2, title -> 3)
 y = Map(buffers -> 20, layers -> 2, title -> 3)
 x equals y: true, y equals x: true
 
-x = ListSet(5, 3)
-y = ListSet(5, 3)
+x = ListSet(3, 5)
+y = ListSet(3, 5)
 x equals y: true, y equals x: true
 
 x = Queue(a, b, c)
diff --git a/test/files/run/t3822.scala b/test/files/run/t3822.scala
deleted file mode 100644
index c35804035e..0000000000
--- a/test/files/run/t3822.scala
+++ /dev/null
@@ -1,19 +0,0 @@
-import scala.collection.{ mutable, immutable, generic }
-import immutable.ListSet
-
-object Test {
-  def main(args: Array[String]): Unit = {
-    val xs = ListSet(-100000 to 100001: _*)
-
-    assert(xs.size == 200002)
-    assert(xs.sum == 100001)
-
-    val ys = ListSet[Int]()
-    val ys1 = (1 to 12).grouped(3).foldLeft(ys)(_ ++ _)
-    val ys2 = (1 to 12).foldLeft(ys)(_ + _)
-
-    assert(ys1 == ys2)
-  }
-}
-
-
diff --git a/test/files/run/t6198.scala b/test/files/run/t6198.scala
index 5aa8f1c1cf..65dbaf8160 100644
--- a/test/files/run/t6198.scala
+++ b/test/files/run/t6198.scala
@@ -1,13 +1,6 @@
 import scala.collection.immutable._
 
 object Test extends App {
-  // test that ListSet.tail does not use a builder
-  // we can't test for O(1) behavior, so the best we can do is to
-  // check that ls.tail always returns the same instance
-  val ls = ListSet.empty[Int] + 1 + 2
-
-  if(ls.tail ne ls.tail)
-    println("ListSet.tail should not use a builder!")
 
   // class that always causes hash collisions
   case class Collision(value:Int) { override def hashCode = 0 }
diff --git a/test/files/run/t7445.scala b/test/files/run/t7445.scala
deleted file mode 100644
index e4ffeb8e1a..0000000000
--- a/test/files/run/t7445.scala
+++ /dev/null
@@ -1,6 +0,0 @@
-import scala.collection.immutable.ListMap
-
-object Test extends App {
-	val a = ListMap(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5);
-	require(a.tail == ListMap(2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5));
-}
diff --git a/test/junit/scala/collection/immutable/ListMapTest.scala b/test/junit/scala/collection/immutable/ListMapTest.scala
new file mode 100644
index 0000000000..320a976755
--- /dev/null
+++ b/test/junit/scala/collection/immutable/ListMapTest.scala
@@ -0,0 +1,48 @@
+package scala.collection.immutable
+
+import org.junit.Assert._
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+
+@RunWith(classOf[JUnit4])
+class ListMapTest {
+
+  @Test
+  def t7445(): Unit = {
+    val m = ListMap(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)
+    assertEquals(ListMap(2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5), m.tail)
+  }
+
+  @Test
+  def hasCorrectBuilder(): Unit = {
+    val m = ListMap("a" -> "1", "b" -> "2", "c" -> "3", "b" -> "2.2", "d" -> "4")
+    assertEquals(List("a" -> "1", "c" -> "3", "b" -> "2.2", "d" -> "4"), m.toList)
+  }
+
+  @Test
+  def hasCorrectHeadTailLastInit(): Unit = {
+    val m = ListMap(1 -> 1, 2 -> 2, 3 -> 3)
+    assertEquals(1 -> 1, m.head)
+    assertEquals(ListMap(2 -> 2, 3 -> 3), m.tail)
+    assertEquals(3 -> 3, m.last)
+    assertEquals(ListMap(1 -> 1, 2 -> 2), m.init)
+  }
+
+  @Test
+  def hasCorrectAddRemove(): Unit = {
+    val m = ListMap(1 -> 1, 2 -> 2, 3 -> 3)
+    assertEquals(ListMap(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4), m + (4 -> 4))
+    assertEquals(ListMap(1 -> 1, 3 -> 3, 2 -> 4), m + (2 -> 4))
+    assertEquals(ListMap(1 -> 1, 2 -> 2, 3 -> 3), m + (2 -> 2))
+    assertEquals(ListMap(2 -> 2, 3 -> 3), m - 1)
+    assertEquals(ListMap(1 -> 1, 3 -> 3), m - 2)
+    assertEquals(ListMap(1 -> 1, 2 -> 2, 3 -> 3), m - 4)
+  }
+
+  @Test
+  def hasCorrectIterator(): Unit = {
+    val m = ListMap(1 -> 1, 2 -> 2, 3 -> 3, 5 -> 5, 4 -> 4)
+    assertEquals(List(1 -> 1, 2 -> 2, 3 -> 3, 5 -> 5, 4 -> 4), m.iterator.toList)
+  }
+}
diff --git a/test/junit/scala/collection/immutable/ListSetTest.scala b/test/junit/scala/collection/immutable/ListSetTest.scala
new file mode 100644
index 0000000000..395da88c75
--- /dev/null
+++ b/test/junit/scala/collection/immutable/ListSetTest.scala
@@ -0,0 +1,53 @@
+package scala.collection.immutable
+
+import org.junit.Assert._
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+
+@RunWith(classOf[JUnit4])
+class ListSetTest {
+
+  @Test
+  def t7445(): Unit = {
+    val s = ListSet(1, 2, 3, 4, 5)
+    assertEquals(ListSet(2, 3, 4, 5), s.tail)
+  }
+
+  @Test
+  def hasCorrectBuilder(): Unit = {
+    val m = ListSet("a", "b", "c", "b", "d")
+    assertEquals(List("a", "b", "c", "d"), m.toList)
+  }
+
+  @Test
+  def hasTailRecursiveDelete(): Unit = {
+    val s = ListSet(1 to 50000: _*)
+    try s - 25000 catch { case e: StackOverflowError => fail("A stack overflow occurred") }
+  }
+
+  @Test
+  def hasCorrectHeadTailLastInit(): Unit = {
+    val m = ListSet(1, 2, 3)
+    assertEquals(1, m.head)
+    assertEquals(ListSet(2, 3), m.tail)
+    assertEquals(3, m.last)
+    assertEquals(ListSet(1, 2), m.init)
+  }
+
+  @Test
+  def hasCorrectAddRemove(): Unit = {
+    val m = ListSet(1, 2, 3)
+    assertEquals(ListSet(1, 2, 3, 4), m + 4)
+    assertEquals(ListSet(1, 2, 3), m + 2)
+    assertEquals(ListSet(2, 3), m - 1)
+    assertEquals(ListSet(1, 3), m - 2)
+    assertEquals(ListSet(1, 2, 3), m - 4)
+  }
+
+  @Test
+  def hasCorrectIterator(): Unit = {
+    val s = ListSet(1, 2, 3, 5, 4)
+    assertEquals(List(1, 2, 3, 5, 4), s.iterator.toList)
+  }
+}
-- 
cgit v1.2.3


From ffbf063baf5db46484a23c2b91d2b8769f0f956b Mon Sep 17 00:00:00 2001
From: Rui Gonçalves <ruippeixotog@gmail.com>
Date: Sun, 15 May 2016 00:09:45 +0100
Subject: 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.
---
 .../scala/collection/immutable/ListMap.scala       | 244 ++++++++-------------
 .../scala/collection/immutable/ListSet.scala       | 159 ++++++--------
 test/files/jvm/serialization-new.check             |   4 +-
 test/files/jvm/serialization.check                 |   4 +-
 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)
-- 
cgit v1.2.3


From 4552de451b48b65b8dca42d4167eb6f6aefbf408 Mon Sep 17 00:00:00 2001
From: Rui Gonçalves <ruippeixotog@gmail.com>
Date: Sun, 15 May 2016 00:19:35 +0100
Subject: Add SerialVersionUID to ListSet

---
 src/library/scala/collection/immutable/ListSet.scala | 3 +++
 test/files/run/t8549.scala                           | 4 +++-
 2 files changed, 6 insertions(+), 1 deletion(-)

diff --git a/src/library/scala/collection/immutable/ListSet.scala b/src/library/scala/collection/immutable/ListSet.scala
index c9c6558bb9..d9795e9161 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -32,6 +32,7 @@ object ListSet extends ImmutableSetFactory[ListSet] {
   implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, ListSet[A]] =
     setCanBuildFrom[A]
 
+  @SerialVersionUID(5010379588739277132L)
   private object EmptyListSet extends ListSet[Any]
   private[collection] def emptyInstance: ListSet[Any] = EmptyListSet
 }
@@ -58,6 +59,7 @@ object ListSet extends ImmutableSetFactory[ListSet] {
   * @define mayNotTerminateInf
   * @define willNotTerminateInf
   */
+@SerialVersionUID(-8417059026623606218L)
 sealed class ListSet[A] extends AbstractSet[A]
   with Set[A]
   with GenericSetTemplate[A, ListSet]
@@ -101,6 +103,7 @@ sealed class ListSet[A] extends AbstractSet[A]
   /**
     * Represents an entry in the `ListSet`.
     */
+  @SerialVersionUID(-787710309854855049L)
   protected class Node(override protected val elem: A) extends ListSet[A] with Serializable {
 
     override def size = sizeInternal(this, 0)
diff --git a/test/files/run/t8549.scala b/test/files/run/t8549.scala
index e2d0d335b0..1ce8933efb 100644
--- a/test/files/run/t8549.scala
+++ b/test/files/run/t8549.scala
@@ -79,7 +79,7 @@ object Test extends App {
     }
   }
 
-  // Generated on 20160328-17:47:35 with Scala version 2.12.0-20160328-174205-d46145c)
+  // Generated on 20160515-00:17:51 with Scala version 2.12.0-SNAPSHOT)
   overwrite.foreach(updateComment)
 
   check(Some(1))("rO0ABXNyAApzY2FsYS5Tb21lESLyaV6hi3QCAAFMAAF4dAASTGphdmEvbGFuZy9PYmplY3Q7eHIADHNjYWxhLk9wdGlvbv5pN/3bDmZ0AgAAeHBzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAQ==")
@@ -145,6 +145,8 @@ object Test extends App {
   check(immutable.HashSet(1, 2, 3))( "rO0ABXNyADVzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5IYXNoU2V0JFNlcmlhbGl6YXRpb25Qcm94eQAAAAAAAAACAwAAeHB3BAAAAANzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXNxAH4AAgAAAAJzcQB+AAIAAAADeA==")
   // TODO provoke HashSetCollision1
 
+  check(immutable.ListSet())(       "rO0ABXNyADBzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0U2V0JEVtcHR5TGlzdFNldCRFiHGwmKwhTAIAAHhyACJzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0U2V0izCZaSia0jYCAAB4cA==")
+  check(immutable.ListSet(1))(      "rO0ABXNyACdzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0U2V0JE5vZGX1EX2lizBAdwIAAkwABiRvdXRlcnQAJExzY2FsYS9jb2xsZWN0aW9uL2ltbXV0YWJsZS9MaXN0U2V0O0wABGVsZW10ABJMamF2YS9sYW5nL09iamVjdDt4cgAic2NhbGEuY29sbGVjdGlvbi5pbW11dGFibGUuTGlzdFNldIswmWkomtI2AgAAeHBzcgAwc2NhbGEuY29sbGVjdGlvbi5pbW11dGFibGUuTGlzdFNldCRFbXB0eUxpc3RTZXQkRYhxsJisIUwCAAB4cQB+AANzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAQ==")
   check(immutable.ListMap())(       "rO0ABXNyADBzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0TWFwJEVtcHR5TGlzdE1hcCSNalsvpBZeDgIAAHhyACJzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0TWFwBC1gfIkUSKsCAAB4cA==")
   check(immutable.ListMap(1 -> 2))( "rO0ABXNyACdzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0TWFwJE5vZGWmciM1Yav+8gIAA0wABiRvdXRlcnQAJExzY2FsYS9jb2xsZWN0aW9uL2ltbXV0YWJsZS9MaXN0TWFwO0wAA2tleXQAEkxqYXZhL2xhbmcvT2JqZWN0O0wABXZhbHVlcQB+AAJ4cgAic2NhbGEuY29sbGVjdGlvbi5pbW11dGFibGUuTGlzdE1hcAQtYHyJFEirAgAAeHBzcgAwc2NhbGEuY29sbGVjdGlvbi5pbW11dGFibGUuTGlzdE1hcCRFbXB0eUxpc3RNYXAkjWpbL6QWXg4CAAB4cQB+AANzcgARamF2YS5sYW5nLkludGVnZXIS4qCk94GHOAIAAUkABXZhbHVleHIAEGphdmEubGFuZy5OdW1iZXKGrJUdC5TgiwIAAHhwAAAAAXNxAH4ABwAAAAI=")
   check(immutable.Queue())(         "rO0ABXNyACBzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5RdWV1ZZY146W3qSuhAgACTAACaW50ACFMc2NhbGEvY29sbGVjdGlvbi9pbW11dGFibGUvTGlzdDtMAANvdXRxAH4AAXhwc3IAMnNjYWxhLmNvbGxlY3Rpb24uaW1tdXRhYmxlLkxpc3QkU2VyaWFsaXphdGlvblByb3h5AAAAAAAAAAEDAAB4cHNyACxzY2FsYS5jb2xsZWN0aW9uLmltbXV0YWJsZS5MaXN0U2VyaWFsaXplRW5kJIpcY1v3UwttAgAAeHB4cQB+AAQ=")
-- 
cgit v1.2.3