Merge pull request #21 from dart-lang/queue
Add typed queue classes
diff --git a/.travis.yml b/.travis.yml
index 1c702c8..0d83a59 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -1,6 +1,6 @@
language: dart
dart:
- - 2.4.0
+ - stable
- dev
dart_task:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index f6f0c0d..7edf873 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,4 +1,8 @@
-## 1.1.7-dev
+## 1.2.0
+
+* Add typed queue classes such as `Uint8Queue`. These classes implement both
+ `Queue` and `List` with a highly-efficient typed-data-backed implementation.
+ Their `sublist()` methods also return typed data classes.
* Update min Dart SDK to `2.4.0`.
diff --git a/lib/src/typed_queue.dart b/lib/src/typed_queue.dart
new file mode 100644
index 0000000..8d83944
--- /dev/null
+++ b/lib/src/typed_queue.dart
@@ -0,0 +1,654 @@
+// Copyright (c) 2019, 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.
+
+import "dart:collection";
+import "dart:typed_data";
+
+import "package:collection/collection.dart";
+
+import '../typed_buffers.dart';
+
+/// The shared superclass of all the typed queue subclasses.
+abstract class _TypedQueue<E, L extends List<E>> with ListMixin<E> {
+ /// The underlying data buffer.
+ ///
+ /// This is always both a List<E> and a TypedData, which we don't have a type
+ /// for that. For example, for a `Uint8Queue`, this is a `Uint8List`.
+ L _table;
+
+ int _head;
+ int _tail;
+
+ /// Create an empty queue.
+ _TypedQueue(this._table)
+ : _head = 0,
+ _tail = 0;
+
+ // Iterable interface.
+
+ int get length => (_tail - _head) & (_table.length - 1);
+
+ List<E> toList({bool growable = true}) {
+ var list = growable ? _createBuffer(length) : _createList(length);
+ _writeToList(list);
+ return list;
+ }
+
+ QueueList<T> cast<T>() {
+ if (this is QueueList<T>) return this as QueueList<T>;
+ throw UnsupportedError("$this cannot be cast to the desired type.");
+ }
+
+ @deprecated
+ QueueList<T> retype<T>() => cast<T>();
+
+ // Queue interface.
+
+ void addLast(E value) {
+ _table[_tail] = value;
+ _tail = (_tail + 1) & (_table.length - 1);
+ if (_head == _tail) _growAtCapacity();
+ }
+
+ void addFirst(E value) {
+ _head = (_head - 1) & (_table.length - 1);
+ _table[_head] = value;
+ if (_head == _tail) _growAtCapacity();
+ }
+
+ E removeFirst() {
+ if (_head == _tail) throw StateError("No element");
+ var result = _table[_head];
+ _head = (_head + 1) & (_table.length - 1);
+ return result;
+ }
+
+ E removeLast() {
+ if (_head == _tail) throw StateError("No element");
+ _tail = (_tail - 1) & (_table.length - 1);
+ return _table[_tail];
+ }
+
+ // List interface.
+
+ void add(E value) => addLast(value);
+
+ set length(int value) {
+ RangeError.checkNotNegative(value, "length");
+
+ var delta = value - length;
+ if (delta >= 0) {
+ var needsToGrow = _table.length <= value;
+ if (needsToGrow) _growTo(value);
+ _tail = (_tail + delta) & (_table.length - 1);
+
+ // If we didn't copy into a new table, make sure that we overwrite the
+ // existing data so that users don't accidentally depend on it still
+ // existing.
+ if (!needsToGrow) fillRange(value - delta, value, _defaultValue);
+ } else {
+ removeRange(value, length);
+ }
+ }
+
+ E operator [](int index) {
+ RangeError.checkValidIndex(index, this, null, length);
+ return _table[(_head + index) & (_table.length - 1)];
+ }
+
+ void operator []=(int index, E value) {
+ RangeError.checkValidIndex(index, this);
+ _table[(_head + index) & (_table.length - 1)] = value;
+ }
+
+ void removeRange(int start, int end) {
+ var length = this.length;
+ RangeError.checkValidRange(start, end, length);
+
+ // Special-case removing an initial or final range because we can do it very
+ // efficiently by adjusting `_head` or `_tail`.
+ if (start == 0) {
+ _head = (_head + end) & (_table.length - 1);
+ return;
+ }
+
+ var elementsAfter = length - end;
+ if (elementsAfter == 0) {
+ _tail = (_head + start) & (_table.length - 1);
+ return;
+ }
+
+ // Choose whether to copy from the beginning of the end of the queue based
+ // on which will require fewer copied elements.
+ var removedElements = end - start;
+ if (start < elementsAfter) {
+ setRange(removedElements, end, this);
+ _head = (_head + removedElements) & (_table.length - 1);
+ } else {
+ setRange(start, length - removedElements, this, end);
+ _tail = (_tail - removedElements) & (_table.length - 1);
+ }
+ }
+
+ void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]) {
+ RangeError.checkValidRange(start, end, length);
+ if (start == end) return;
+
+ var targetStart = (_head + start) & (_table.length - 1);
+ var targetEnd = (_head + end) & (_table.length - 1);
+ var targetIsContiguous = targetStart < targetEnd;
+ if (identical(iterable, this)) {
+ // If we're copying this queue to itself, we can copy [_table] in directly
+ // which requires some annoying case analysis but in return bottoms out on
+ // an extremely efficient `memmove` call. However, we may need to do three
+ // copies to avoid overwriting data we'll need to use later.
+ var sourceStart = (_head + skipCount) & (_table.length - 1);
+ var sourceEnd = (sourceStart + (end - start)) & (_table.length - 1);
+ if (sourceStart == targetStart) return;
+
+ var sourceIsContiguous = sourceStart < sourceEnd;
+ if (targetIsContiguous && sourceIsContiguous) {
+ // If both the source and destination ranges are contiguous, we can
+ // do a single [setRange]. Hooray!
+ _table.setRange(targetStart, targetEnd, _table, sourceStart);
+ } else if (!targetIsContiguous && !sourceIsContiguous) {
+ // If neither range is contiguous, we need to do three copies.
+ if (sourceStart > targetStart) {
+ // [=====| targetEnd targetStart |======]
+ // [========| sourceEnd sourceStart |===]
+
+ // Copy front to back.
+ var startGap = sourceStart - targetStart;
+ var firstEnd = _table.length - startGap;
+ _table.setRange(targetStart, firstEnd, _table, sourceStart);
+ _table.setRange(firstEnd, _table.length, _table);
+ _table.setRange(0, targetEnd, _table, startGap);
+ } else if (sourceEnd < targetEnd) {
+ // [=====| targetEnd targetStart |======]
+ // [==| sourceEnd sourceStart |=========]
+
+ // Copy back to front.
+ var firstStart = targetEnd - sourceEnd;
+ _table.setRange(firstStart, targetEnd, _table);
+ _table.setRange(0, firstStart, _table, _table.length - firstStart);
+ _table.setRange(targetStart, _table.length, _table, sourceStart);
+ }
+ } else if (sourceStart < targetEnd) {
+ // Copying twice is safe here as long as we copy front to back.
+ if (sourceIsContiguous) {
+ // [=====| targetEnd targetStart |======]
+ // [ |===========| sourceEnd ]
+ // sourceStart
+ _table.setRange(targetStart, _table.length, _table, sourceStart);
+ _table.setRange(0, targetEnd, _table,
+ sourceStart + (_table.length - targetStart));
+ } else {
+ // targetEnd
+ // [ targetStart |===========| ]
+ // [=====| sourceEnd sourceStart |======]
+ var firstEnd = _table.length - sourceStart;
+ _table.setRange(targetStart, firstEnd, _table, sourceStart);
+ _table.setRange(firstEnd, targetEnd, _table);
+ }
+ } else {
+ // Copying twice is safe here as long as we copy back to front. This
+ // also covers the case where there's no overlap between the source and
+ // target ranges, in which case the direction doesn't matter.
+ if (sourceIsContiguous) {
+ // [=====| targetEnd targetStart |======]
+ // [ sourceStart |===========| ]
+ // sourceEnd
+ _table.setRange(0, targetEnd, _table,
+ sourceStart + (_table.length - targetStart));
+ _table.setRange(targetStart, _table.length, _table, sourceStart);
+ } else {
+ // targetStart
+ // [ |===========| targetEnd ]
+ // [=====| sourceEnd sourceStart |======]
+ var firstStart = targetEnd - sourceEnd;
+ _table.setRange(firstStart, targetEnd, _table);
+ _table.setRange(targetStart, firstStart, _table, sourceStart);
+ }
+ }
+ } else if (targetIsContiguous) {
+ // If the range is contiguous within the table, we can set it with a single
+ // underlying [setRange] call.
+ _table.setRange(targetStart, targetEnd, iterable, skipCount);
+ } else if (iterable is List<E>) {
+ // If the range isn't contiguous and [iterable] is actually a [List] (but
+ // not this queue), set it with two underlying [setRange] calls.
+ _table.setRange(targetStart, _table.length, iterable, skipCount);
+ _table.setRange(
+ 0, targetEnd, iterable, skipCount + (_table.length - targetStart));
+ } else {
+ // If [iterable] isn't a [List], we don't want to make two different
+ // [setRange] calls because it could materialize a lazy iterable twice.
+ // Instead we just fall back to the default iteration-based
+ // implementation.
+ super.setRange(start, end, iterable, skipCount);
+ }
+ }
+
+ void fillRange(int start, int end, [E value]) {
+ var startInTable = (_head + start) & (_table.length - 1);
+ var endInTable = (_head + end) & (_table.length - 1);
+ if (startInTable <= endInTable) {
+ _table.fillRange(startInTable, endInTable, value);
+ } else {
+ _table.fillRange(startInTable, _table.length, value);
+ _table.fillRange(0, endInTable, value);
+ }
+ }
+
+ L sublist(int start, [int end]) {
+ var length = this.length;
+ end = RangeError.checkValidRange(start, end, length);
+
+ var list = _createList(end - start);
+ _writeToList(list, start, end);
+ return list;
+ }
+
+ // Internal helper functions.
+
+ /// Writes the contents of `this` between [start] (which defaults to 0) and
+ /// [end] (which defaults to [length]) to the beginning of [target].
+ ///
+ /// This is functionally identical to `target.setRange(0, end - start, this,
+ /// start)`, but it's more efficient when [target] is typed data.
+ ///
+ /// Returns the number of elements written to [target].
+ int _writeToList(List<E> target, [int start, int end]) {
+ start ??= 0;
+ end ??= length;
+ assert(target.length >= end - start);
+ assert(start <= end);
+
+ var elementsToWrite = end - start;
+ var startInTable = (_head + start) & (_table.length - 1);
+ var endInTable = (_head + end) & (_table.length - 1);
+ if (startInTable <= endInTable) {
+ target.setRange(0, elementsToWrite, _table, startInTable);
+ } else {
+ var firstPartSize = _table.length - startInTable;
+ target.setRange(0, firstPartSize, _table, startInTable);
+ target.setRange(firstPartSize, firstPartSize + endInTable, _table, 0);
+ }
+ return elementsToWrite;
+ }
+
+ /// Assumes the table is currently full to capacity, and grows it to the next
+ /// power of two.
+ void _growAtCapacity() {
+ assert(_head == _tail);
+
+ var newTable = _createList(_table.length * 2);
+
+ // We can't use [_writeToList] here because when `_head == _tail` it thinks
+ // the queue is empty rather than full.
+ var partitionPoint = _table.length - _head;
+ newTable.setRange(0, partitionPoint, _table, _head);
+ if (partitionPoint != _table.length) {
+ newTable.setRange(partitionPoint, _table.length, _table);
+ }
+ _head = 0;
+ _tail = _table.length;
+ _table = newTable;
+ }
+
+ /// Grows the tableso it's at least large enough size to include that many
+ /// elements.
+ void _growTo(int newElementCount) {
+ assert(newElementCount >= length);
+
+ // Add some extra room to ensure that there's room for more elements after
+ // expansion.
+ newElementCount += newElementCount >> 1;
+ var newTable = _createList(_nextPowerOf2(newElementCount));
+ _tail = _writeToList(newTable);
+ _table = newTable;
+ _head = 0;
+ }
+
+ // Specialization for the specific type.
+
+ // Create a new typed list.
+ L _createList(int size);
+
+ // Create a new typed buffer of the given type.
+ List<E> _createBuffer(int size);
+
+ /// The default value used to fill the queue when changing length.
+ E get _defaultValue;
+}
+
+abstract class _IntQueue<L extends List<int>> extends _TypedQueue<int, L> {
+ _IntQueue(List<int> queue) : super(queue);
+
+ int get _defaultValue => 0;
+}
+
+abstract class _FloatQueue<L extends List<double>>
+ extends _TypedQueue<double, L> {
+ _FloatQueue(List<double> queue) : super(queue);
+
+ double get _defaultValue => 0.0;
+}
+
+/// A [QueueList] that efficiently stores 8-bit unsigned integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low eight bits, interpreted
+/// as an unsigned 8-bit integer with values in the range 0 to 255.
+class Uint8Queue extends _IntQueue<Uint8List> implements QueueList<int> {
+ /// Creates an empty [Uint8Queue] with the given initial internal capacity (in
+ /// elements).
+ Uint8Queue([int initialCapacity])
+ : super(Uint8List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Uint8Queue] with the same length and contents as [elements].
+ factory Uint8Queue.fromList(List<int> elements) =>
+ Uint8Queue(elements.length)..addAll(elements);
+
+ Uint8List _createList(int size) => Uint8List(size);
+ Uint8Buffer _createBuffer(int size) => Uint8Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 8-bit signed integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low eight bits, interpreted
+/// as a signed 8-bit two's complement integer with values in the range -128 to
+/// +127.
+class Int8Queue extends _IntQueue<Int8List> implements QueueList<int> {
+ /// Creates an empty [Int8Queue] with the given initial internal capacity (in
+ /// elements).
+ Int8Queue([int initialCapacity])
+ : super(Int8List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Int8Queue] with the same length and contents as [elements].
+ factory Int8Queue.fromList(List<int> elements) =>
+ Int8Queue(elements.length)..addAll(elements);
+
+ Int8List _createList(int size) => Int8List(size);
+ Int8Buffer _createBuffer(int size) => Int8Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 8-bit unsigned integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are clamped to an unsigned eight bit value. That is,
+/// all values below zero are stored as zero and all values above 255 are stored
+/// as 255.
+class Uint8ClampedQueue extends _IntQueue<Uint8ClampedList>
+ implements QueueList<int> {
+ /// Creates an empty [Uint8ClampedQueue] with the given initial internal
+ /// capacity (in elements).
+ Uint8ClampedQueue([int initialCapacity])
+ : super(Uint8ClampedList(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Uint8ClampedQueue] with the same length and contents as
+ /// [elements].
+ factory Uint8ClampedQueue.fromList(List<int> elements) =>
+ Uint8ClampedQueue(elements.length)..addAll(elements);
+
+ Uint8ClampedList _createList(int size) => Uint8ClampedList(size);
+ Uint8ClampedBuffer _createBuffer(int size) => Uint8ClampedBuffer(size);
+}
+
+/// A [QueueList] that efficiently stores 16-bit unsigned integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low 16 bits, interpreted as
+/// an unsigned 16-bit integer with values in the range 0 to 65535.
+class Uint16Queue extends _IntQueue<Uint16List> implements QueueList<int> {
+ /// Creates an empty [Uint16Queue] with the given initial internal capacity
+ /// (in elements).
+ Uint16Queue([int initialCapacity])
+ : super(Uint16List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Uint16Queue] with the same length and contents as [elements].
+ factory Uint16Queue.fromList(List<int> elements) =>
+ Uint16Queue(elements.length)..addAll(elements);
+
+ Uint16List _createList(int size) => Uint16List(size);
+ Uint16Buffer _createBuffer(int size) => Uint16Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 16-bit signed integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low 16 bits, interpreted as a
+/// signed 16-bit two's complement integer with values in the range -32768 to
+/// +32767.
+class Int16Queue extends _IntQueue<Int16List> implements QueueList<int> {
+ /// Creates an empty [Int16Queue] with the given initial internal capacity (in
+ /// elements).
+ Int16Queue([int initialCapacity])
+ : super(Int16List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Int16Queue] with the same length and contents as [elements].
+ factory Int16Queue.fromList(List<int> elements) =>
+ Int16Queue(elements.length)..addAll(elements);
+
+ Int16List _createList(int size) => Int16List(size);
+ Int16Buffer _createBuffer(int size) => Int16Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 32-bit unsigned integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low 32 bits, interpreted as
+/// an unsigned 32-bit integer with values in the range 0 to 4294967295.
+class Uint32Queue extends _IntQueue<Uint32List> implements QueueList<int> {
+ /// Creates an empty [Uint32Queue] with the given initial internal capacity
+ /// (in elements).
+ Uint32Queue([int initialCapacity])
+ : super(Uint32List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Uint32Queue] with the same length and contents as [elements].
+ factory Uint32Queue.fromList(List<int> elements) =>
+ Uint32Queue(elements.length)..addAll(elements);
+
+ Uint32List _createList(int size) => Uint32List(size);
+ Uint32Buffer _createBuffer(int size) => Uint32Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 32-bit signed integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low 32 bits, interpreted as a
+/// signed 32-bit two's complement integer with values in the range -2147483648
+/// to 2147483647.
+class Int32Queue extends _IntQueue<Int32List> implements QueueList<int> {
+ /// Creates an empty [Int32Queue] with the given initial internal capacity (in
+ /// elements).
+ Int32Queue([int initialCapacity])
+ : super(Int32List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Int32Queue] with the same length and contents as [elements].
+ factory Int32Queue.fromList(List<int> elements) =>
+ Int32Queue(elements.length)..addAll(elements);
+
+ Int32List _createList(int size) => Int32List(size);
+ Int32Buffer _createBuffer(int size) => Int32Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 64-bit unsigned integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low 64 bits, interpreted as
+/// an unsigned 64-bit integer with values in the range 0 to
+/// 18446744073709551615.
+class Uint64Queue extends _IntQueue<Uint64List> implements QueueList<int> {
+ /// Creates an empty [Uint64Queue] with the given initial internal capacity
+ /// (in elements).
+ Uint64Queue([int initialCapacity])
+ : super(Uint64List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Uint64Queue] with the same length and contents as [elements].
+ factory Uint64Queue.fromList(List<int> elements) =>
+ Uint64Queue(elements.length)..addAll(elements);
+
+ Uint64List _createList(int size) => Uint64List(size);
+ Uint64Buffer _createBuffer(int size) => Uint64Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores 64-bit signed integers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Integers stored in this are truncated to their low 64 bits, interpreted as a
+/// signed 64-bit two's complement integer with values in the range
+/// -9223372036854775808 to +9223372036854775807.
+class Int64Queue extends _IntQueue<Int64List> implements QueueList<int> {
+ /// Creates an empty [Int64Queue] with the given initial internal capacity (in
+ /// elements).
+ Int64Queue([int initialCapacity])
+ : super(Int64List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Int64Queue] with the same length and contents as [elements].
+ factory Int64Queue.fromList(List<int> elements) =>
+ Int64Queue(elements.length)..addAll(elements);
+
+ Int64List _createList(int size) => Int64List(size);
+ Int64Buffer _createBuffer(int size) => Int64Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores IEEE 754 single-precision binary
+/// floating-point numbers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+///
+/// Doubles stored in this are converted to the nearest single-precision value.
+/// Values read are converted to a double value with the same value.
+class Float32Queue extends _FloatQueue<Float32List>
+ implements QueueList<double> {
+ /// Creates an empty [Float32Queue] with the given initial internal capacity
+ /// (in elements).
+ Float32Queue([int initialCapacity])
+ : super(Float32List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Float32Queue] with the same length and contents as [elements].
+ factory Float32Queue.fromList(List<double> elements) =>
+ Float32Queue(elements.length)..addAll(elements);
+
+ Float32List _createList(int size) => Float32List(size);
+ Float32Buffer _createBuffer(int size) => Float32Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores IEEE 754 double-precision binary
+/// floating-point numbers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+class Float64Queue extends _FloatQueue<Float64List>
+ implements QueueList<double> {
+ /// Creates an empty [Float64Queue] with the given initial internal capacity
+ /// (in elements).
+ Float64Queue([int initialCapacity])
+ : super(Float64List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Float64Queue] with the same length and contents as [elements].
+ factory Float64Queue.fromList(List<double> elements) =>
+ Float64Queue(elements.length)..addAll(elements);
+
+ Float64List _createList(int size) => Float64List(size);
+ Float64Buffer _createBuffer(int size) => Float64Buffer(size);
+}
+
+/// A [QueueList] that efficiently stores [Int32x4] numbers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+class Int32x4Queue extends _TypedQueue<Int32x4, Int32x4List>
+ implements QueueList<Int32x4> {
+ static final Int32x4 _zero = Int32x4(0, 0, 0, 0);
+
+ /// Creates an empty [Int32x4Queue] with the given initial internal capacity
+ /// (in elements).
+ Int32x4Queue([int initialCapacity])
+ : super(Int32x4List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Int32x4Queue] with the same length and contents as [elements].
+ factory Int32x4Queue.fromList(List<Int32x4> elements) =>
+ Int32x4Queue(elements.length)..addAll(elements);
+
+ Int32x4List _createList(int size) => Int32x4List(size);
+ Int32x4Buffer _createBuffer(int size) => Int32x4Buffer(size);
+ Int32x4 get _defaultValue => _zero;
+}
+
+/// A [QueueList] that efficiently stores [Float32x4] numbers.
+///
+/// For long queues, this implementation can be considerably more space- and
+/// time-efficient than a default [QueueList] implementation.
+class Float32x4Queue extends _TypedQueue<Float32x4, Float32x4List>
+ implements QueueList<Float32x4> {
+ /// Creates an empty [Float32x4Queue] with the given initial internal capacity (in
+ /// elements).
+ Float32x4Queue([int initialCapacity])
+ : super(Float32x4List(_chooseRealInitialCapacity(initialCapacity)));
+
+ /// Creates a [Float32x4Queue] with the same length and contents as [elements].
+ factory Float32x4Queue.fromList(List<Float32x4> elements) =>
+ Float32x4Queue(elements.length)..addAll(elements);
+
+ Float32x4List _createList(int size) => Float32x4List(size);
+ Float32x4Buffer _createBuffer(int size) => Float32x4Buffer(size);
+ Float32x4 get _defaultValue => Float32x4.zero();
+}
+
+/// The initial capacity of queues if the user doesn't specify one.
+const _defaultInitialCapacity = 16;
+
+/// Choose the next-highest power of two given a user-specified
+/// [initialCapacity] for a queue.
+int _chooseRealInitialCapacity(int initialCapacity) {
+ if (initialCapacity == null || initialCapacity < _defaultInitialCapacity) {
+ return _defaultInitialCapacity;
+ } else if (!_isPowerOf2(initialCapacity)) {
+ return _nextPowerOf2(initialCapacity);
+ } else {
+ return initialCapacity;
+ }
+}
+
+/// Whether [number] is a power of two.
+///
+/// Only works for positive numbers.
+bool _isPowerOf2(int number) => (number & (number - 1)) == 0;
+
+/// Rounds [number] up to the nearest power of 2.
+///
+/// If [number] is a power of 2 already, it is returned.
+///
+/// Only works for positive numbers.
+int _nextPowerOf2(int number) {
+ assert(number > 0);
+ number = (number << 1) - 1;
+ for (;;) {
+ var nextNumber = number & (number - 1);
+ if (nextNumber == 0) return number;
+ number = nextNumber;
+ }
+}
diff --git a/lib/typed_data.dart b/lib/typed_data.dart
index d7c7393..b23fdf0 100644
--- a/lib/typed_data.dart
+++ b/lib/typed_data.dart
@@ -5,4 +5,5 @@
/// Utilities and functionality related to the "dart:typed_data" library.
library typed_data;
-export 'package:typed_data/typed_buffers.dart';
+export "src/typed_queue.dart";
+export "typed_buffers.dart";
diff --git a/pubspec.yaml b/pubspec.yaml
index 1a4cd2c..8952141 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: typed_data
-version: 1.1.7-dev
+version: 1.2.0
description: >-
Utility functions and classes related to the dart:typed_data library.
@@ -9,6 +9,9 @@
environment:
sdk: '>=2.4.0 <3.0.0'
+dependencies:
+ collection: ^1.1.0
+
dev_dependencies:
- pedantic: ^1.0.0
+ pedantic: '>=1.7.0 <1.8.0'
test: ^1.0.0
diff --git a/test/queue_test.dart b/test/queue_test.dart
new file mode 100644
index 0000000..82d96f6
--- /dev/null
+++ b/test/queue_test.dart
@@ -0,0 +1,316 @@
+// Copyright (c) 2019, 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.
+
+// ignore_for_file: avoid_function_literals_in_foreach_calls
+
+import "package:test/test.dart";
+
+import "package:typed_data/typed_data.dart";
+
+/// The initial capacity of queues if the user doesn't specify one.
+const capacity = 16;
+
+void main() {
+ group("Uint8Queue()", () {
+ test("creates an empty Uint8Queue", () {
+ expect(Uint8Queue(), isEmpty);
+ });
+
+ test("takes an initial capacity", () {
+ expect(Uint8Queue(100), isEmpty);
+ });
+ });
+
+ group("add() adds an element to the end", () {
+ forEachInternalRepresentation((queue) {
+ queue.add(16);
+ expect(queue, equals(oneThrough(capacity)));
+ });
+ });
+
+ group("addFirst() adds an element to the beginning", () {
+ forEachInternalRepresentation((queue) {
+ queue.addFirst(0);
+ expect(queue, equals([0, ...oneThrough(capacity - 1)]));
+ });
+ });
+
+ group("removeFirst() removes an element from the beginning", () {
+ forEachInternalRepresentation((queue) {
+ expect(queue.removeFirst(), equals(1));
+ expect(queue, equals(oneThrough(capacity - 1).skip(1)));
+ });
+
+ test("throws a StateError for an empty queue", () {
+ expect(Uint8Queue().removeFirst, throwsStateError);
+ });
+ });
+
+ group("removeLast() removes an element from the end", () {
+ forEachInternalRepresentation((queue) {
+ expect(queue.removeLast(), equals(15));
+ expect(queue, equals(oneThrough(capacity - 2)));
+ });
+
+ test("throws a StateError for an empty queue", () {
+ expect(Uint8Queue().removeLast, throwsStateError);
+ });
+ });
+
+ group("removeRange()", () {
+ group("removes a prefix", () {
+ forEachInternalRepresentation((queue) {
+ queue.removeRange(0, 5);
+ expect(queue, equals(oneThrough(capacity - 1).skip(5)));
+ });
+ });
+
+ group("removes a suffix", () {
+ forEachInternalRepresentation((queue) {
+ queue.removeRange(10, 15);
+ expect(queue, equals(oneThrough(capacity - 6)));
+ });
+ });
+
+ group("removes from the middle", () {
+ forEachInternalRepresentation((queue) {
+ queue.removeRange(5, 10);
+ expect(queue, equals([1, 2, 3, 4, 5, 11, 12, 13, 14, 15]));
+ });
+ });
+
+ group("removes everything", () {
+ forEachInternalRepresentation((queue) {
+ queue.removeRange(0, 15);
+ expect(queue, isEmpty);
+ });
+ });
+
+ test("throws a RangeError for an invalid range", () {
+ expect(() => Uint8Queue().removeRange(0, 1), throwsRangeError);
+ });
+ });
+
+ group("setRange()", () {
+ group("sets a range to the contents of an iterable", () {
+ forEachInternalRepresentation((queue) {
+ queue.setRange(5, 10, oneThrough(10).map((n) => 100 + n), 2);
+ expect(queue,
+ [1, 2, 3, 4, 5, 103, 104, 105, 106, 107, 11, 12, 13, 14, 15]);
+ });
+ });
+
+ group("sets a range to the contents of a list", () {
+ forEachInternalRepresentation((queue) {
+ queue.setRange(5, 10, oneThrough(10).map((n) => 100 + n).toList(), 2);
+ expect(queue,
+ [1, 2, 3, 4, 5, 103, 104, 105, 106, 107, 11, 12, 13, 14, 15]);
+ });
+ });
+
+ group(
+ "sets a range to a section of the same queue overlapping at the beginning",
+ () {
+ forEachInternalRepresentation((queue) {
+ queue.setRange(5, 10, queue, 2);
+ expect(queue, [1, 2, 3, 4, 5, 3, 4, 5, 6, 7, 11, 12, 13, 14, 15]);
+ });
+ });
+
+ group("sets a range to a section of the same queue overlapping at the end",
+ () {
+ forEachInternalRepresentation((queue) {
+ queue.setRange(5, 10, queue, 6);
+ expect(queue, [1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 11, 12, 13, 14, 15]);
+ });
+ });
+
+ test("throws a RangeError for an invalid range", () {
+ expect(() => Uint8Queue().setRange(0, 1, [1]), throwsRangeError);
+ });
+ });
+
+ group("length returns the length", () {
+ forEachInternalRepresentation((queue) {
+ expect(queue.length, equals(15));
+ });
+ });
+
+ group("length=", () {
+ group("empties", () {
+ forEachInternalRepresentation((queue) {
+ queue.length = 0;
+ expect(queue, isEmpty);
+ });
+ });
+
+ group("shrinks", () {
+ forEachInternalRepresentation((queue) {
+ queue.length = 5;
+ expect(queue, equals([1, 2, 3, 4, 5]));
+ });
+ });
+
+ group("grows", () {
+ forEachInternalRepresentation((queue) {
+ queue.length = 20;
+ expect(
+ queue,
+ equals(oneThrough(capacity - 1) +
+ List.filled(20 - (capacity - 1), 0)));
+ });
+ });
+
+ group("zeroes out existing data", () {
+ forEachInternalRepresentation((queue) {
+ queue.length = 0;
+ queue.length = 15;
+ expect(queue, equals([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]));
+ });
+ });
+
+ test("throws a RangeError if length is less than 0", () {
+ expect(() => Uint8Queue().length = -1, throwsRangeError);
+ });
+ });
+
+ group("[]", () {
+ group("returns individual entries", () {
+ forEachInternalRepresentation((queue) {
+ for (var i = 0; i < capacity - 1; i++) {
+ expect(queue[i], equals(i + 1));
+ }
+ });
+ });
+
+ test("throws a RangeError if the index is less than 0", () {
+ var queue = Uint8Queue.fromList([1, 2, 3]);
+ expect(() => queue[-1], throwsRangeError);
+ });
+
+ test(
+ "throws a RangeError if the index is greater than or equal to the "
+ "length", () {
+ var queue = Uint8Queue.fromList([1, 2, 3]);
+ expect(() => queue[3], throwsRangeError);
+ });
+ });
+
+ group("[]=", () {
+ group("sets individual entries", () {
+ forEachInternalRepresentation((queue) {
+ for (var i = 0; i < capacity - 1; i++) {
+ queue[i] = 100 + i;
+ }
+ expect(queue, equals(List.generate(capacity - 1, (i) => 100 + i)));
+ });
+ });
+
+ test("throws a RangeError if the index is less than 0", () {
+ var queue = Uint8Queue.fromList([1, 2, 3]);
+ expect(() {
+ queue[-1] = 0;
+ }, throwsRangeError);
+ });
+
+ test(
+ "throws a RangeError if the index is greater than or equal to the "
+ "length", () {
+ var queue = Uint8Queue.fromList([1, 2, 3]);
+ expect(() {
+ queue[3] = 4;
+ }, throwsRangeError);
+ });
+ });
+
+ group("throws a modification error for", () {
+ Uint8Queue queue;
+ setUp(() {
+ queue = Uint8Queue.fromList([1, 2, 3]);
+ });
+
+ test("add", () {
+ expect(() => queue.forEach((_) => queue.add(4)),
+ throwsConcurrentModificationError);
+ });
+
+ test("addAll", () {
+ expect(() => queue.forEach((_) => queue.addAll([4, 5, 6])),
+ throwsConcurrentModificationError);
+ });
+
+ test("addFirst", () {
+ expect(() => queue.forEach((_) => queue.addFirst(0)),
+ throwsConcurrentModificationError);
+ });
+
+ test("removeFirst", () {
+ expect(() => queue.forEach((_) => queue.removeFirst()),
+ throwsConcurrentModificationError);
+ });
+
+ test("removeLast", () {
+ expect(() => queue.forEach((_) => queue.removeLast()),
+ throwsConcurrentModificationError);
+ });
+
+ test("length=", () {
+ expect(() => queue.forEach((_) => queue.length = 1),
+ throwsConcurrentModificationError);
+ });
+ });
+}
+
+/// Runs [callback] in multiple tests, all with queues containing numbers from
+/// one through 15 in various different internal states.
+void forEachInternalRepresentation(void Function(Uint8Queue queue) callback) {
+ // Test with a queue whose internal table has plenty of room.
+ group("for a queue that's below capacity", () {
+ // Test with a queue whose elements are in one contiguous block, so `_head <
+ // _tail`.
+ test("with contiguous elements", () {
+ callback(Uint8Queue(capacity * 2)..addAll(oneThrough(capacity - 1)));
+ });
+
+ // Test with a queue whose elements are split across the ends of the table,
+ // so `_head > _tail`.
+ test("with an internal gap", () {
+ var queue = Uint8Queue(capacity * 2);
+ for (var i = capacity ~/ 2; i < capacity; i++) {
+ queue.add(i);
+ }
+ for (var i = capacity ~/ 2 - 1; i > 0; i--) {
+ queue.addFirst(i);
+ }
+ callback(queue);
+ });
+ });
+
+ // Test with a queue whose internal table will need to expand if one more
+ // element is added.
+ group("for a queue that's at capacity", () {
+ test("with contiguous elements", () {
+ callback(Uint8Queue()..addAll(oneThrough(capacity - 1)));
+ });
+
+ test("with an internal gap", () {
+ var queue = Uint8Queue();
+ for (var i = capacity ~/ 2; i < capacity; i++) {
+ queue.add(i);
+ }
+ for (var i = capacity ~/ 2 - 1; i > 0; i--) {
+ queue.addFirst(i);
+ }
+ callback(queue);
+ });
+ });
+}
+
+/// Returns a list containing the integers from one through [n].
+List<int> oneThrough(int n) => List.generate(n, (i) => i + 1);
+
+/// Returns a matcher that expects that a closure throws a
+/// [ConcurrentModificationError].
+final throwsConcurrentModificationError =
+ throwsA(const TypeMatcher<ConcurrentModificationError>());
diff --git a/test/typed_buffers_test.dart b/test/typed_buffers_test.dart
index 3f682b1..3305452 100644
--- a/test/typed_buffers_test.dart
+++ b/test/typed_buffers_test.dart
@@ -534,11 +534,9 @@
MatchesInt32x4(this.result);
- @override
Description describe(Description description) =>
description.add('Int32x4.==');
- @override
bool matches(item, Map matchState) {
if (item is! Int32x4) return false;
Int32x4 value = item;