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, 48 insertions, 0 deletions

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