Add _TypedDataBuffer.addRange.

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 47 matching lines @@
       _buffer = newBuffer;
     }
     _length = newLength;
   }
 
   void _add(E value) {
     if (_length == _buffer.length) _grow();
     _buffer[_length++] = value;
   }
 
-  // We override the default implementation of `add` and `addAll` because
-  // they grow by setting the length in increments of one. We want to grow
-  // by doubling capacity in most cases.
+  // We override the default implementation of `add` because it grows the list
+  // by setting the length in increments of one. We want to grow by doubling
+  // capacity in most cases.
   void add(E value) { _add(value); }
 
-  void addAll(Iterable<E> values) {
-    for (E value in values) _add(value);
+  /// Appends all objects of [values] to the end of this buffer.
+  ///
+  /// 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 addAll(Iterable<E> values, [int start = 0, int end]) {
+    _addAll(values, start, end);
+  }
+
+  /// Inserts all objects of [values] at position [index] in this list.
+  ///
+  /// 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);

[Lasse Reichstein Nielsen, 2015/10/27 10:10:19]

Tricky, this "index" is really not an index (0<=index<length).
I guess it's ok to use checkValidIndex anyway since it's named "index" and the
error message will be correct.

+    RangeError.checkNotNegative(start, "start");
+    if (end != null && start > end) {
+      throw new RangeError.range(end, start, null, "end");
+    }
+
+    // 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.

[Lasse Reichstein Nielsen, 2015/10/27 10:10:19]

There are things we can do which is linear, but it will require some copying
(basically this.end-index + min(this.end-index, end-start) elements copies, and
it requires a growing buffer on the side).

+    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 && values is! List) {
+      values = values.toList(growable: false);

[Lasse Reichstein Nielsen, 2015/10/27 10:10:19]

do: 

if (end == null) {
  if (values is! List) {
    values = values.skip(start).toList(); 
    start = 0;
  }
  end = values.length;
}

to avoid wasting space for the values before start and ensure end is set before
calling _insertKnownLength.

[nweiz, 2015/10/27 21:26:07]

Won't calling [skip] avoid throwing an error when start = end > values.length?

[Lasse Reichstein Nielsen, 2015/10/28 07:31:56]

True.
I might try to optimize this more - it annoys me that it is storing the
intermediate numbers in a non-typed-data List, but I guess it's fine for now.

+    }
+
+    _insertKnownLength(index, values, 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]) {
+    RangeError.checkNotNegative(start, "start");

[Lasse Reichstein Nielsen, 2015/10/27 10:10:18]

We already checked this for insertAll. Move these checks to addAll, before
calling _addAll, and remove them here.

[nweiz, 2015/10/27 21:26:07]

Done.

+    if (end != null && start > end) {
+      throw new RangeError.range(end, start, null, "end");
+    }
+
+    // If we can efficiently compute the length of the segment to add, do so
+    // with [addRange]. This can be more efficient for lists and potentially
+    // other well-known types.

[Lasse Reichstein Nielsen, 2015/10/27 10:10:18]

How about:

if (values is List) {
  end ??= values.length;
}
if (end != null) {
  _insertKnownLength(...);
}

Then you can avoid the redundant (values is List) check in _insertKnownLength
because it's always called with a non-null end.

[nweiz, 2015/10/27 21:26:08]

Done.

+    if (end != null || values is List) {
+      _insertKnownLength(_length, values, start, end);
+      return;
+    }
+
+    // Otherwise, just add values one at a time.
+    var i = 0;
+    for (var value in values) {
+      if (i >= start) add(value);
+      i++;
+    }
+    if (i < start) throw new StateError("Too few elements");
+  }
+
+  /// Like [insertAll], but assumes that the length of the slice of [values] is
+  /// known (or easy to calculate).
+  ///
+  /// Specifically, this assumes that if [values] is not a [List], [end] is not
+  /// `null`.
+  void _insertKnownLength(int index, Iterable<E> values, int start, int end) {
+    if (values is List) {
+      end ??= values.length;
+      if (start > values.length || end > values.length) {
+        throw new StateError("Too few elements");
+      }
+    } else {
+      assert(end != null);
+    }
+
+    var valuesLength = end - start;
+    var newLength = _length + valuesLength;
+    _ensureCapacity(newLength);
+
+    _buffer.setRange(
+        index + valuesLength, _length + valuesLength, _buffer, index);
+    _buffer.setRange(index, index + valuesLength, values, start);
+    _length = newLength;
   }
 
   void insert(int index, E element) {
     if (index < 0 || index > _length) {
       throw new RangeError.range(index, 0, _length);
     }
     if (_length < _buffer.length) {
       _buffer.setRange(index + 1, _length + 1, _buffer, index);
       _buffer[index] = element;
       _length++;
       return;
     }
     List<E> newBuffer = _createBiggerBuffer(null);
     newBuffer.setRange(0, index, _buffer);
     newBuffer.setRange(index + 1, _length + 1, _buffer, index);
     newBuffer[index] = element;
     _length++;
     _buffer = newBuffer;
   }
 
+  /// Ensures that [_buffer] is at least [requiredCapacity] long,
+  ///
+  /// Grows the buffer if necessary, preserving existing data.
+  void _ensureCapacity(int requiredCapacity) {
+    if (requiredCapacity <= _buffer.length) return;
+    var newBuffer = _createBiggerBuffer(requiredCapacity);
+    newBuffer.setRange(0, _length, _buffer);
+    _buffer = newBuffer;
+  }
+
   /**
    * Create a bigger buffer.
    *
    * This method determines how much bigger a bigger buffer should
-   * be. If [requiredLength] is not null, it will be at least that
+   * be. If [requiredCapacity] is not null, it will be at least that
    * size. It will always have at least have double the capacity of
    * the current buffer.
    */
-  List<E> _createBiggerBuffer(int requiredLength) {
+  List<E> _createBiggerBuffer(int requiredCapacity) {
     int newLength = _buffer.length * 2;
-    if (requiredLength != null && newLength < requiredLength) {
-      newLength = requiredLength;
+    if (requiredCapacity != null && newLength < requiredCapacity) {
+      newLength = requiredCapacity;
     } else if (newLength < INITIAL_LENGTH) {
       newLength = INITIAL_LENGTH;
     }
     return _createBuffer(newLength);
   }
 
   void _grow() {
     _buffer = _createBiggerBuffer(null)..setRange(0, _length, _buffer);
   }
 
   void setRange(int start, int end, Iterable<E> source, [int skipCount = 0]) {
     if (end > _length) throw new RangeError.range(end, 0, _length);
+    _setRange(start, end, source, skipCount);
+  }
+
+  /// Like [setRange], but with no bounds checking.
+  void _setRange(int start, int end, Iterable<E> source, int skipCount) {
     if (source is _TypedDataBuffer<E>) {
       _buffer.setRange(start, end, source._buffer, skipCount);
     } else {
       _buffer.setRange(start, end, source, skipCount);
     }
   }
 
   // TypedData.
 
   int get elementSizeInBytes => _buffer.elementSizeInBytes;
@@ skipping 97 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);
 }