Merge pull request #5103 from ruippeixotog/improve-list-map-set-perf

Improve performance and behavior of ListMap and ListSet

10 files changed, 306 insertions, 346 deletions

diff --git a/src/library/scala/collection/immutable/ListMap.scala b/src/library/scala/collection/immutable/ListMap.scala
index e1bcc0711c..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,214 +13,154 @@ 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] =
-    ((repr: ListMap[A, B1]) /: xs.seq) (_ + _)
-
-  /** 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)] =
-    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
-
-  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")
-
-  /** This class represents an entry in the `ListMap`.
-   */
+    if (xs.isEmpty) this
+    else ((repr: ListMap[A, B1]) /: xs) (_ + _)
+
+  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("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"
+
+  /**
+    * 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)
 
-    /** 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 isEmpty: Boolean = false
+
+    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] =
-      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)
+    @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 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 d20e7bc6d2..d9795e9161 100644
--- a/src/library/scala/collection/immutable/ListSet.scala
+++ b/src/library/scala/collection/immutable/ListSet.scala
@@ -12,174 +12,125 @@ package immutable
 
 import generic._
 import scala.annotation.tailrec
-import mutable.{Builder, ReusableBuilder}
 
-/** $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]
 
-  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.
-   *
-   *  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
- *  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
+  */
+@SerialVersionUID(-8417059026623606218L)
 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 (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)
 
-    override def tail: ListSet[A] = self
-  }
+    @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 toSet[B >: A]: Set[B] = this.asInstanceOf[ListSet[B]]
+    override protected def next: ListSet[A] = ListSet.this
+
+    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 cb26446f40..1c5dd4828b 100644
--- a/test/files/jvm/serialization-new.check
+++ b/test/files/jvm/serialization-new.check
@@ -85,12 +85,12 @@ 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(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..1c5dd4828b 100644
--- a/test/files/jvm/serialization.check
+++ b/test/files/jvm/serialization.check
@@ -85,12 +85,12 @@ 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(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/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=")
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)
+  }
+}