Growable typed data buffers.

pkg/collection_helpers/lib/typed_buffers.dart

Index: pkg/collection_helpers/lib/typed_buffers.dart
diff --git a/pkg/collection_helpers/lib/typed_buffers.dart b/pkg/collection_helpers/lib/typed_buffers.dart
new file mode 100644
index 0000000000000000000000000000000000000000..b28f9c85cfc3b48e0649a0e4e8b20c4d48822cbe
--- /dev/null
+++ b/pkg/collection_helpers/lib/typed_buffers.dart
@@ -0,0 +1,217 @@
+// 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.
+ *
+ * That means that using the [TypedDataView.buffer] getter is not guaranteed
+ * to return the same result each time it is used, and that the buffer may
+ * be larger than what the list is using.
+ */
+library dart.collection_helper.typed_buffers;
+
+import "dart:collection" show ListBase;
+import "dart:typed_data";
+
+abstract class _TypedDataBuffer<E> extends ListBase<E>
+                                   implements TypedData, List<E> {
+  static const int INITIAL_LENGTH = 8;
+
+  /// This is an Uint8List for Uint8Buffer. It's both a List<E> and a TypedData,
+  /// which we don't have a type for here.
+  var _buffer;
+  /// The length of the list being built.
+  int _length;
+
+  _TypedDataBuffer(List<E> buffer)
+      : this._buffer = buffer, this._length = buffer.length;
+
+  int get length => _length;
+  E operator[](int index) {
+    if (index >= length) throw new RangeError.range(index, 0, length - 1);

[sra1, 2013/10/09 18:49:53]

All other calls use length, not length - 1.
If you want to change what we mean by the third argument to RangeError, please
make that a separate CL.

It would be convenient for our many list-like collections indexable on
[0,length) to have

   new RangeError.list(index, list);

[Lasse Reichstein Nielsen, 2013/10/10 05:54:41]

The meaning if the third argument to RangeError.range is the last valid index,
it's inclusive. If you see any place where it is used differently, please say
so.

For lookup, the last valid index value is length -1.

For insert, and for ranges in general, we allow referring to the position after
the last element - we are referring to places between/besides elements, not to
elements themselves (good old fence-post problem). 

So, the value is correct.

[sra1, 2013/10/15 02:11:41]

There are dozens of places in the dart2js versions of libraries and in the
Dartium DOM libraries.

A problem here is that the documentation for RangeError.range is underspecified.
 It is not clear that [end] is inclusive:

  /** Create a new [RangeError] with a message for a value and a range. */
  RangeError.range(num value, num start, num end)

The DOM has 50 kinds of list. I would like to avoid repeated 'length - 1'
expressions since that will contribute to code size of likely dead code.

[floitsch, 2013/10/15 15:28:05]

I agree with Stephen. I definitely didn't see it as "end is valid".

+    return _buffer[index];
+  }
+
+  void operator[]=(int index, E value) {
+    if (index >= length) throw new RangeError.range(index, 0, length - 1);
+    _buffer[index] = value;
+  }
+
+  void set length(int newLength) {
+    if (newLength < _length) {
+      E defaultValue = _defaultValue;
+      for (int i = newLength; i < _length; i++) {
+        _buffer[i] = defaultValue;
+      }
+    } else if (newLength > _buffer.length) {
+      List<E> newBuffer = _createBuffer(newLength);
+      newBuffer.setRange(0, _length, _buffer);
+      _buffer = newBuffer;
+    } else {
+      E defaultValue = _defaultValue;
+      for (int i = _length; i < newLength; i++) {
+        _buffer[i] = defaultValue;

[floitsch, 2013/10/15 15:28:05]

shouldn't these already be set to the default value?

[Lasse Reichstein Nielsen, 2013/11/18 14:32:51]

Yes, they should, because we set the above.
Removing.

+      }
+    }
+    _length = newLength;
+  }
+
+  void _add(E value) {
+    if (_length == _buffer.length) _grow();
+    _buffer[_length++] = value;
+  }
+
+  // Override default implementation of add to not grow by one element at

[floitsch, 2013/10/15 15:28:05]

We override the default ...

Otherwise it sounds like a suggestion: "if you don't want to grow by one
element, override...".

[Lasse Reichstein Nielsen, 2013/11/18 14:32:51]

Done.

+  // a time.
+  void add(E value) { _add(value); }
+
+  void addAll(Iterable<E> values) {
+    for (E value in values) _add(value);
+  }
+
+  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;
+    }
+    int newLength = _buffer.length * 2;
+    if (newLength < INITIAL_LENGTH) newLength = INITIAL_LENGTH;

[sra1, 2013/10/09 18:49:53]

This growth policy should be in one place (there is an identical *2 and clamping
in _grow)

[Lasse Reichstein Nielsen, 2013/10/10 05:54:41]

Ack, a generic _newLength would be better.

[Lasse Reichstein Nielsen, 2013/11/18 14:32:51]

Done.

+    List<E> newBuffer = _createBuffer(newLength);
+    newBuffer.setRange(0, index, _buffer);
+    newBuffer.setRange(index + 1, _length + 1, _buffer, index);
+    newBuffer[index] = element;
+    _length++;
+    _buffer = newBuffer;
+  }
+
+  void _grow() {
+    int newLength = _buffer.length * 2;
+    if (newLength < INITIAL_LENGTH) newLength = INITIAL_LENGTH;
+    List<E> newBuffer = _createBuffer(newLength);
+    newBuffer.setRange(0, _length, _buffer);
+    _buffer = newBuffer;
+  }
+
+  void setRange(int start, int end, Iterable source, [int skipCount = 0]) {
+    if (end > _length) throw new RangeError.range(end, 0, _length);
+    if (!identical(source, this)) {
+      _buffer.setRange(start, end, source, skipCount);
+    } else {
+      // Make internal moves work correctly.
+      _buffer.setRange(start, end, buffer, skipCount);
+    }
+  }
+
+  // TypedData.
+
+  int get elementSizeInBytes => _buffer.elementSizeInBytes;
+
+  int get lengthInBytes => _length * _buffer.elementSizeInBytes;
+
+  int get offsetInBytes => _buffer.offsetInBytes;
+
+  /**
+    * Returns the underlying [ByteBuffer].
+    *
+    * The returned buffer may be replaced by operations that change the [length]
+    * of this list.
+    *
+    * The buffer may be larger than [lengthInBytes] bytes, but never smaller.
+    */
+  ByteBuffer get buffer => _buffer.buffer;
+
+  // Specialization for the specific type.
+
+  // Return zero for integers, 0.0 for floats, etc.
+  // Used to fill buffer when changing length.
+  E get _defaultValue;
+
+  // Create a new typed list to use as buffer.
+  List<E> _createBuffer(int size);
+}
+
+class _IntBuffer extends _TypedDataBuffer<int> {
+  _IntBuffer(buffer): super(buffer);
+  int get _defaultValue => 0;
+}
+
+class _FloatBuffer extends _TypedDataBuffer<double> {
+  _FloatBuffer(buffer): super(buffer);
+  double get _defaultValue => 0.0;
+}
+
+class Uint8Buffer extends _IntBuffer implements Uint8List {
+  Uint8Buffer([int initialLength = 0]) : super(new Uint8List(initialLength));
+  Uint8List _createBuffer(int size) => new Uint8List(size);
+}
+
+class Int8Buffer extends _IntBuffer implements Int8List {
+  Int8Buffer([int initialLength = 0]) : super(new Int8List(initialLength));
+  Int8List _createBuffer(int size) => new Int8List(size);
+}
+
+class Uint8ClampedBuffer extends _IntBuffer implements Uint8ClampedList {

[sra1, 2013/10/09 18:49:53]

I'm concerned that having two concrete classes that implement Uint8ClampedList,
one that can be indexed in JavaScript and another that requires calling the
indexer defined above, will prevent dart2js from any meaningful optimizations.

[Lasse Reichstein Nielsen, 2013/10/10 05:54:41]

I have no problem removing the "implements" here. It's still a List<int> and a
TypedData, which should be fine.

[sra1, 2013/10/15 02:11:41]

TypedData corresponds to ArrayBufferView.
http://www.khronos.org/registry/typedarray/specs/latest/#6
http://www.khronos.org/registry/typedarray/specs/latest/#9.3

Not that the spec says so, but since ArrayBufferView is de facto abstract, it
should be OK.

+  Uint8ClampedBuffer([int initialLength = 0])
+      : super(new Uint8ClampedList(initialLength));
+  Uint8ClampedList _createBuffer(int size) => new Uint8ClampedList(size);
+}
+
+class Uint16Buffer extends _IntBuffer implements Uint16List {
+  Uint16Buffer([int initialLength = 0]) : super(new Uint16List(initialLength));
+  Uint16List _createBuffer(int size) => new Uint16List(size);
+}
+
+class Int16Buffer extends _IntBuffer implements Int16List {
+  Int16Buffer([int initialLength = 0]) : super(new Int16List(initialLength));
+  Int16List _createBuffer(int size) => new Int16List(size);
+}
+
+class Uint32Buffer extends _IntBuffer implements Uint32List {
+  Uint32Buffer([int initialLength = 0]) : super(new Uint32List(initialLength));
+  Uint32List _createBuffer(int size) => new Uint32List(size);
+}
+
+class Int32Buffer extends _IntBuffer implements Int32List {
+  Int32Buffer([int initialLength = 0]) : super(new Int32List(initialLength));
+  Int32List _createBuffer(int size) => new Int32List(size);
+}
+
+class Uint64Buffer extends _IntBuffer implements Uint64List {
+  Uint64Buffer([int initialLength = 0]) : super(new Uint64List(initialLength));
+  Uint64List _createBuffer(int size) => new Uint64List(size);
+}
+
+class Int64Buffer extends _IntBuffer implements Int64List {
+  Int64Buffer([int initialLength = 0]) : super(new Int64List(initialLength));
+  Int64List _createBuffer(int size) => new Int64List(size);
+}
+
+class Float32Buffer extends _FloatBuffer implements Float32List {
+  Float32Buffer([int initialLength = 0])
+      : super(new Float32List(initialLength));
+  Float32List _createBuffer(int size) => new Float32List(size);
+}
+
+class Float64Buffer extends _FloatBuffer implements Float64List {
+  Float64Buffer([int initialLength = 0])
+      : super(new Float64List(initialLength));
+  Float64List _createBuffer(int size) => new Float64List(size);
+}
+
+class Float32x4Buffer extends _TypedDataBuffer<Float32x4>
+                      implements Float32x4List {
+  Float32x4Buffer([int initialLength = 0])
+      : super(new Float32x4List(initialLength));
+  Float32x4 get _defaultValue => new Float32x4.zero();
+  Float32x4List _createBuffer(int size) => new Float32x4List(size);
+}