Merge pull request scala#4202 from kanielc/SI-9043

gkossakowski · gkossakowski · commit 7ba38a079164 · 2014-12-15T16:16:19.000+01:00
SI-9043 ArrayBuffer.insert and insertAll are very slow
diff --git a/src/library/scala/collection/mutable/ArrayBuffer.scala b/src/library/scala/collection/mutable/ArrayBuffer.scala
@@ -128,7 +128,7 @@ class ArrayBuffer[A](override protected val initialSize: Int)
   override def ++=:(xs: TraversableOnce[A]): this.type = { insertAll(0, xs.toTraversable); this }
 
   /** Inserts new elements at the index `n`. Opposed to method
-   *  `update`, this method will not replace an element with a
+   *  `update`, this method will not replace an element with a new
    *  one. Instead, it will insert a new element at index `n`.
    *
    *  @param n     the index where a new element will be inserted.
@@ -137,12 +137,13 @@ class ArrayBuffer[A](override protected val initialSize: Int)
    */
   def insertAll(n: Int, seq: Traversable[A]) {
     if (n < 0 || n > size0) throw new IndexOutOfBoundsException(n.toString)
-    val xs = seq.toList
-    val len = xs.length
-    ensureSize(size0 + len)
+    val len = seq.size
+    val newSize = size0 + len
+    ensureSize(newSize)
+
     copy(n, n + len, size0 - n)
-    xs.copyToArray(array.asInstanceOf[scala.Array[Any]], n)
-    size0 += len
+    seq.copyToArray(array.asInstanceOf[Array[Any]], n)
+    size0 = newSize
   }
 
   /** Removes the element on a given index position. It takes time linear in
diff --git a/test/junit/scala/collection/mutable/ArrayBufferTest.scala b/test/junit/scala/collection/mutable/ArrayBufferTest.scala
@@ -0,0 +1,36 @@
+package scala.collection.mutable
+
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.{Assert, Test}
+
+import scala.tools.testing.AssertUtil
+
+/* Test for SI-9043 */
+@RunWith(classOf[JUnit4])
+class ArrayBufferTest {
+  @Test
+  def testInsertAll: Unit = {
+    val traver = ArrayBuffer(2, 4, 5, 7)
+    val testSeq = List(1, 3, 6, 9)
+
+    def insertAt(x: Int) = {
+      val clone = traver.clone()
+      clone.insertAll(x, testSeq)
+      clone
+    }
+
+    // Just insert some at position 0
+    Assert.assertEquals(ArrayBuffer(1, 3, 6, 9, 2, 4, 5, 7), insertAt(0))
+
+    // Insert in the middle
+    Assert.assertEquals(ArrayBuffer(2, 4, 1, 3, 6, 9, 5, 7), insertAt(2))
+
+    // No strange last position weirdness
+    Assert.assertEquals(ArrayBuffer(2, 4, 5, 7, 1, 3, 6, 9), insertAt(traver.size))
+
+    // Overflow is caught
+    AssertUtil.assertThrows[IndexOutOfBoundsException] { insertAt(-1) }
+    AssertUtil.assertThrows[IndexOutOfBoundsException] { insertAt(traver.size + 10) }
+  }
+}
