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;