Add a QueueList class to the collection package.
This class is based on the ListQueue implementation and implements both the
Queue and List interfaces.
R=lrn@google.com
Review URL: https://codereview.chromium.org//660373002
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart/pkg/collection@41467 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 1ed9863..6742b4c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,7 @@
+## 1.1.0
+
+* Add a `QueueList` class that implements both `Queue` and `List`.
+
## 0.9.4
* Add a `CanonicalizedMap` class that canonicalizes its keys to provide a custom
diff --git a/lib/collection.dart b/lib/collection.dart
index d24dd39..45d3867 100644
--- a/lib/collection.dart
+++ b/lib/collection.dart
@@ -22,4 +22,5 @@
export "iterable_zip.dart";
export "priority_queue.dart";
export "src/canonicalized_map.dart";
+export "src/queue_list.dart";
export "wrappers.dart";
diff --git a/lib/src/queue_list.dart b/lib/src/queue_list.dart
new file mode 100644
index 0000000..0ef888f
--- /dev/null
+++ b/lib/src/queue_list.dart
@@ -0,0 +1,231 @@
+// Copyright (c) 2014, 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';
+
+/**
+ * A class that efficiently implements both [Queue] and [List].
+ */
+// TODO(nweiz): Currently this code is copied almost verbatim from
+// dart:collection. The only changes are to implement List and to remove methods
+// that are redundant with ListMixin. Remove or simplify it when issue 21330 is
+// fixed.
+class QueueList<E> extends Object with ListMixin<E> implements Queue<E> {
+ static const int _INITIAL_CAPACITY = 8;
+ List<E> _table;
+ int _head;
+ int _tail;
+
+ /**
+ * Create an empty queue.
+ *
+ * If [initialCapacity] is given, prepare the queue for at least that many
+ * elements.
+ */
+ QueueList([int initialCapacity]) : _head = 0, _tail = 0 {
+ if (initialCapacity == null || initialCapacity < _INITIAL_CAPACITY) {
+ initialCapacity = _INITIAL_CAPACITY;
+ } else if (!_isPowerOf2(initialCapacity)) {
+ initialCapacity = _nextPowerOf2(initialCapacity);
+ }
+ assert(_isPowerOf2(initialCapacity));
+ _table = new List<E>(initialCapacity);
+ }
+
+ /**
+ * Create a queue initially containing the elements of [source].
+ */
+ factory QueueList.from(Iterable<E> source) {
+ if (source is List) {
+ int length = source.length;
+ QueueList<E> queue = new QueueList(length + 1);
+ assert(queue._table.length > length);
+ List sourceList = source;
+ queue._table.setRange(0, length, sourceList, 0);
+ queue._tail = length;
+ return queue;
+ } else {
+ return new QueueList<E>()..addAll(source);
+ }
+ }
+
+ // Collection interface.
+
+ void add(E element) {
+ _add(element);
+ }
+
+ void addAll(Iterable<E> elements) {
+ if (elements is List) {
+ List list = elements;
+ int addCount = list.length;
+ int length = this.length;
+ if (length + addCount >= _table.length) {
+ _preGrow(length + addCount);
+ // After preGrow, all elements are at the start of the list.
+ _table.setRange(length, length + addCount, list, 0);
+ _tail += addCount;
+ } else {
+ // Adding addCount elements won't reach _head.
+ int endSpace = _table.length - _tail;
+ if (addCount < endSpace) {
+ _table.setRange(_tail, _tail + addCount, list, 0);
+ _tail += addCount;
+ } else {
+ int preSpace = addCount - endSpace;
+ _table.setRange(_tail, _tail + endSpace, list, 0);
+ _table.setRange(0, preSpace, list, endSpace);
+ _tail = preSpace;
+ }
+ }
+ } else {
+ for (E element in elements) _add(element);
+ }
+ }
+
+ String toString() => IterableBase.iterableToFullString(this, "{", "}");
+
+ // Queue interface.
+
+ void addLast(E element) { _add(element); }
+
+ void addFirst(E element) {
+ _head = (_head - 1) & (_table.length - 1);
+ _table[_head] = element;
+ if (_head == _tail) _grow();
+ }
+
+ E removeFirst() {
+ if (_head == _tail) throw new StateError("No element");
+ E result = _table[_head];
+ _table[_head] = null;
+ _head = (_head + 1) & (_table.length - 1);
+ return result;
+ }
+
+ E removeLast() {
+ if (_head == _tail) throw new StateError("No element");
+ _tail = (_tail - 1) & (_table.length - 1);
+ E result = _table[_tail];
+ _table[_tail] = null;
+ return result;
+ }
+
+ // List interface.
+
+ int get length => (_tail - _head) & (_table.length - 1);
+
+ void set length(int value) {
+ if (value < 0) throw new RangeError("Length $value may not be negative.");
+
+ int delta = value - length;
+ if (delta >= 0) {
+ if (_table.length <= value) {
+ _preGrow(value);
+ }
+ _tail = (_tail + delta) & (_table.length - 1);
+ return;
+ }
+
+ int newTail = _tail + delta; // [delta] is negative.
+ if (newTail >= 0) {
+ _table.fillRange(newTail, _tail, null);
+ } else {
+ newTail += _table.length;
+ _table.fillRange(0, _tail, null);
+ _table.fillRange(newTail, _table.length, null);
+ }
+ _tail = newTail;
+ }
+
+ E operator [](int index) {
+ if (index < 0 || index >= length) {
+ throw new RangeError("Index $index must be in the range [0..$length).");
+ }
+
+ return _table[(_head + index) & (_table.length - 1)];
+ }
+
+ void operator[]=(int index, E value) {
+ if (index < 0 || index >= length) {
+ throw new RangeError("Index $index must be in the range [0..$length).");
+ }
+
+ _table[(_head + index) & (_table.length - 1)] = value;
+ }
+
+ // Internal helper functions.
+
+ /**
+ * Whether [number] is a power of two.
+ *
+ * Only works for positive numbers.
+ */
+ static 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.
+ */
+ static int _nextPowerOf2(int number) {
+ assert(number > 0);
+ number = (number << 1) - 1;
+ for(;;) {
+ int nextNumber = number & (number - 1);
+ if (nextNumber == 0) return number;
+ number = nextNumber;
+ }
+ }
+
+ /** Adds element at end of queue. Used by both [add] and [addAll]. */
+ void _add(E element) {
+ _table[_tail] = element;
+ _tail = (_tail + 1) & (_table.length - 1);
+ if (_head == _tail) _grow();
+ }
+
+ /**
+ * Grow the table when full.
+ */
+ void _grow() {
+ List<E> newTable = new List<E>(_table.length * 2);
+ int split = _table.length - _head;
+ newTable.setRange(0, split, _table, _head);
+ newTable.setRange(split, split + _head, _table, 0);
+ _head = 0;
+ _tail = _table.length;
+ _table = newTable;
+ }
+
+ int _writeToList(List<E> target) {
+ assert(target.length >= length);
+ if (_head <= _tail) {
+ int length = _tail - _head;
+ target.setRange(0, length, _table, _head);
+ return length;
+ } else {
+ int firstPartSize = _table.length - _head;
+ target.setRange(0, firstPartSize, _table, _head);
+ target.setRange(firstPartSize, firstPartSize + _tail, _table, 0);
+ return _tail + firstPartSize;
+ }
+ }
+
+ /** Grows the table even if it is not full. */
+ void _preGrow(int newElementCount) {
+ assert(newElementCount >= length);
+
+ // Add 1.5x extra room to ensure that there's room for more elements after
+ // expansion.
+ newElementCount += newElementCount >> 1;
+ int newCapacity = _nextPowerOf2(newElementCount);
+ List<E> newTable = new List<E>(newCapacity);
+ _tail = _writeToList(newTable);
+ _table = newTable;
+ _head = 0;
+ }
+}
diff --git a/pubspec.yaml b/pubspec.yaml
index 9ec80f4..b4396b9 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,5 +1,5 @@
name: collection
-version: 1.0.0
+version: 1.1.0
author: Dart Team <misc@dartlang.org>
description: Collections and utilities functions and classes related to collections.
homepage: http://www.dartlang.org
diff --git a/test/queue_list_test.dart b/test/queue_list_test.dart
new file mode 100644
index 0000000..6b213c8
--- /dev/null
+++ b/test/queue_list_test.dart
@@ -0,0 +1,276 @@
+// Copyright (c) 2014, 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 "package:collection/collection.dart";
+import "package:unittest/unittest.dart";
+
+void main() {
+ group("new QueueList()", () {
+ test("creates an empty QueueList", () {
+ expect(new QueueList(), isEmpty);
+ });
+
+ test("takes an initial capacity", () {
+ expect(new QueueList(100), isEmpty);
+ });
+ });
+
+ test("new QueueList.from() copies the contents of an iterable", () {
+ expect(new QueueList.from([1, 2, 3].skip(1)), equals([2, 3]));
+ });
+
+ group("add()", () {
+ test("adds an element to the end of the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ queue.add(4);
+ expect(queue, equals([1, 2, 3, 4]));
+ });
+
+ test("expands a full queue", () {
+ var queue = atCapacity();
+ queue.add(8);
+ expect(queue, equals([1, 2, 3, 4, 5, 6, 7, 8]));
+ });
+ });
+
+ group("addAll()", () {
+ test("adds elements to the end of the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ queue.addAll([4, 5, 6]);
+ expect(queue, equals([1, 2, 3, 4, 5, 6]));
+ });
+
+ test("expands a full queue", () {
+ var queue = atCapacity();
+ queue.addAll([8, 9]);
+ expect(queue, equals([1, 2, 3, 4, 5, 6, 7, 8, 9]));
+ });
+ });
+
+ group("addFirst()", () {
+ test("adds an element to the beginning of the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ queue.addFirst(0);
+ expect(queue, equals([0, 1, 2, 3]));
+ });
+
+ test("expands a full queue", () {
+ var queue = atCapacity();
+ queue.addFirst(0);
+ expect(queue, equals([0, 1, 2, 3, 4, 5, 6, 7]));
+ });
+ });
+
+ group("removeFirst()", () {
+ test("removes an element from the beginning of the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ expect(queue.removeFirst(), equals(1));
+ expect(queue, equals([2, 3]));
+ });
+
+ test("removes an element from the beginning of a queue with an internal "
+ "gap", () {
+ var queue = withInternalGap();
+ expect(queue.removeFirst(), equals(1));
+ expect(queue, equals([2, 3, 4, 5, 6, 7]));
+ });
+
+ test("removes an element from the beginning of a queue at capacity", () {
+ var queue = atCapacity();
+ expect(queue.removeFirst(), equals(1));
+ expect(queue, equals([2, 3, 4, 5, 6, 7]));
+ });
+
+ test("throws a StateError for an empty queue", () {
+ expect(new QueueList().removeFirst, throwsStateError);
+ });
+ });
+
+ group("removeLast()", () {
+ test("removes an element from the end of the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ expect(queue.removeLast(), equals(3));
+ expect(queue, equals([1, 2]));
+ });
+
+ test("removes an element from the end of a queue with an internal gap", () {
+ var queue = withInternalGap();
+ expect(queue.removeLast(), equals(7));
+ expect(queue, equals([1, 2, 3, 4, 5, 6]));
+ });
+
+ test("removes an element from the end of a queue at capacity", () {
+ var queue = atCapacity();
+ expect(queue.removeLast(), equals(7));
+ expect(queue, equals([1, 2, 3, 4, 5, 6]));
+ });
+
+ test("throws a StateError for an empty queue", () {
+ expect(new QueueList().removeLast, throwsStateError);
+ });
+ });
+
+ group("length", () {
+ test("returns the length of a queue", () {
+ expect(new QueueList.from([1, 2, 3]).length, equals(3));
+ });
+
+ test("returns the length of a queue with an internal gap", () {
+ expect(withInternalGap().length, equals(7));
+ });
+
+ test("returns the length of a queue at capacity", () {
+ expect(atCapacity().length, equals(7));
+ });
+ });
+
+ group("length=", () {
+ test("shrinks a larger queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ queue.length = 1;
+ expect(queue, equals([1]));
+ });
+
+ test("grows a smaller queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ queue.length = 5;
+ expect(queue, equals([1, 2, 3, null, null]));
+ });
+
+ test("throws a RangeError if length is less than 0", () {
+ expect(() => new QueueList().length = -1, throwsRangeError);
+ });
+ });
+
+ group("[]", () {
+ test("returns individual entries in the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ expect(queue[0], equals(1));
+ expect(queue[1], equals(2));
+ expect(queue[2], equals(3));
+ });
+
+ test("returns individual entries in a queue with an internal gap", () {
+ var queue = withInternalGap();
+ expect(queue[0], equals(1));
+ expect(queue[1], equals(2));
+ expect(queue[2], equals(3));
+ expect(queue[3], equals(4));
+ expect(queue[4], equals(5));
+ expect(queue[5], equals(6));
+ expect(queue[6], equals(7));
+ });
+
+ test("throws a RangeError if the index is less than 0", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ expect(() => queue[-1], throwsRangeError);
+ });
+
+ test("throws a RangeError if the index is greater than or equal to the "
+ "length", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ expect(() => queue[3], throwsRangeError);
+ });
+ });
+
+ group("[]=", () {
+ test("sets individual entries in the queue", () {
+ var queue = new QueueList.from([1, 2, 3]);
+ queue[0] = "a";
+ queue[1] = "b";
+ queue[2] = "c";
+ expect(queue, equals(["a", "b", "c"]));
+ });
+
+ test("sets individual entries in a queue with an internal gap", () {
+ var queue = withInternalGap();
+ queue[0] = "a";
+ queue[1] = "b";
+ queue[2] = "c";
+ queue[3] = "d";
+ queue[4] = "e";
+ queue[5] = "f";
+ queue[6] = "g";
+ expect(queue, equals(["a", "b", "c", "d", "e", "f", "g"]));
+ });
+
+ test("throws a RangeError if the index is less than 0", () {
+ var queue = new QueueList.from([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 = new QueueList.from([1, 2, 3]);
+ expect(() {
+ queue[3] = 4;
+ }, throwsRangeError);
+ });
+ });
+
+ group("throws a modification error for", () {
+ var queue;
+ setUp(() {
+ queue = new QueueList.from([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);
+ });
+ });
+}
+
+/// Returns a queue whose internal ring buffer is full enough that adding a new
+/// element will expand it.
+QueueList atCapacity() {
+ // Use addAll because [new QueueList.from(List)] won't use the default initial
+ // capacity of 8.
+ return new QueueList()..addAll([1, 2, 3, 4, 5, 6, 7]);
+}
+
+/// Returns a queue whose internal tail has a lower index than its head.
+QueueList withInternalGap() {
+ var queue = new QueueList.from([null, null, null, null, 1, 2, 3, 4]);
+ for (var i = 0; i < 4; i++) {
+ queue.removeFirst();
+ }
+ for (var i = 5; i < 8; i++) {
+ queue.addLast(i);
+ }
+ return queue;
+}
+
+/// Returns a matcher that expects that a closure throws a
+/// [ConcurrentModificationError].
+final throwsConcurrentModificationError = throwsA(
+ new isInstanceOf<ConcurrentModificationError>(
+ "ConcurrentModificationError"));
