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.

1 files changed, 53 insertions, 0 deletions

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