Optimizie the insertion of an iterable.
Avoids creating a list on the side, at the cost of an extra copying
inside the typed-data buffer to move the data into place.
R=floitsch@google.com, nweiz@google.com
Review URL: https://codereview.chromium.org//1408253004 .
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 36fa6b1..6be0b2d 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,5 @@
+## 1.1.1
+* Optimize `insertAll` with an `Iterable` argument and no end-point.
## 1.1.0
* Add `start` and `end` parameters to the `addAll()` and `insertAll()` methods
diff --git a/lib/typed_buffers.dart b/lib/typed_buffers.dart
index ebf5766..c8cc75d 100644
--- a/lib/typed_buffers.dart
+++ b/lib/typed_buffers.dart
@@ -100,10 +100,14 @@
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;
}
+
// 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
@@ -113,14 +117,54 @@
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");
+ }
+ // 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].
diff --git a/pubspec.yaml b/pubspec.yaml
index 4ca6cb2..552b36e 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: typed_data
-version: 1.1.0
+version: 1.1.1
author: Dart Team <misc@dartlang.org>
description: Utility functions and classes related to the 'dart:typed_data' library.
homepage: https://github.com/dart-lang/typed_data
