Optimizie the insertion of an iterable.

lib/typed_buffers.dart

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 /**
  * Growable typed-data lists.
  *
  * These lists works just as a typed-data list, except that they are growable.
  * They use an underlying buffer, and when that buffer becomes too small, it
  * is replaced by a new buffer.
@@ skipping 82 matching lines @@
   /// This adds values from [start] (inclusive) to [end] (exclusive) in
   /// [values]. If [end] is omitted, it defaults to adding all elements of
   /// [values] after [start].
   ///
   /// The [start] value must be non-negative. The [values] iterable must have at
   /// least [start] elements, and if [end] is specified, it must be greater than
   /// or equal to [start] and [values] must have at least [end] elements.
   void insertAll(int index, Iterable<E> values, [int start = 0, int end]) {
     RangeError.checkValidIndex(index, this, "index", _length + 1);
     RangeError.checkNotNegative(start, "start");
-    if (end != null && start > end) {
-      throw new RangeError.range(end, start, null, "end");
+    if (end != null) {
+      if (start > end) {
+        throw new RangeError.range(end, start, null, "end");
+      }
+      if (start == end) return;

[nweiz, 2015/10/28 21:43:30]

This has the same issue as calling [values.start]: it will fail to throw an
error if start = end > _length.

[Lasse Reichstein Nielsen, 2015/10/29 09:24:42]

I think that's acceptable - you are asking for zero values to be inserted. There
*are* zero values at position [start], so "too few elements" would be incorrect.

     }
 
+
     // If we're adding to the end of the list anyway, use [_addAll]. This lets
     // us avoid converting [values] into a list even if [end] is null, since we
     // can add values iteratively to the end of the list. We can't do so in the
     // center because copying the trailing elements every time is non-linear.
     if (index == _length) {
       _addAll(values, start, end);
       return;
     }
 
-    // If we don't know how much room to make for [values], convert it to a list
-    // so we can tell.
-    if (end == null) {
-      if (values is! List) values = values.toList(growable: false);
+    if (end == null && values is List) {
       end = values.length;
     }
+    if (end != null) {
+      _insertKnownLength(index, values, start, end);
+      return;
+    }
 
-    _insertKnownLength(index, values, start, end);
+    // Add elements at end, growing as appropriate, then put them back at
+    // position [index] using flip-by-double-reverse.
+    if (end != null) values = values.take(end);
+    int writeIndex = _length;
+    int skipCount = start;
+    for (var value in values) {
+      if (skipCount > 0) {
+        skipCount--;
+        continue;
+      }
+      if (writeIndex == _buffer.length) {
+        _grow();
+      }
+      _buffer[writeIndex++] = value;
+    }
+    if (skipCount > 0) {
+      throw new StateError("Too few elements");
+    }
+    if (end != null && writeIndex < end) {
+      throw new RangeError.range(end, start, writeIndex, "end");

[floitsch, 2015/10/28 18:20:51]

Add comment, that throwing now leaves the array in an unchanged state, because
the _length hasn't been updated yet.

[Lasse Reichstein Nielsen, 2015/10/29 09:24:42]

Done.

+    }
+    // Swap [index.._length) and [_length..writeIndex) by double-reversing.
+    _reverse(_buffer, index, _length);
+    _reverse(_buffer, _length, writeIndex);
+    _reverse(_buffer, index, writeIndex);
+    _length = writeIndex;
+    return;
+  }
+
+  // Reverses the range [start..end) of buffer.
+  static void _reverse(List<int> buffer, int start, int end) {
+    end--;  // Point to last element, not after last element.
+    while (start < end) {
+      var first = buffer[start];
+      var last = buffer[end];
+      buffer[end] = first;
+      buffer[start] = last;
+      start++;
+      end--;
+    }
   }
 
   /// Does the same thing as [addAll].
   ///
   /// This allows [addAll] and [insertAll] to share implementation without a
   /// subclass unexpectedly overriding both when it intended to only override
   /// [addAll].
   void _addAll(Iterable<E> values, [int start = 0, int end]) {
     if (values is List) end ??= values.length;
 
@@ skipping 202 matching lines @@
   Int32x4 get _defaultValue => _zero;
   Int32x4List _createBuffer(int size) => new Int32x4List(size);
 }
 
 class Float32x4Buffer extends _TypedDataBuffer<Float32x4> {
   Float32x4Buffer([int initialLength = 0])
       : super(new Float32x4List(initialLength));
   Float32x4 get _defaultValue => new Float32x4.zero();
   Float32x4List _createBuffer(int size) => new Float32x4List(size);
 }