Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1536)

Unified Diff: pkg/collection/lib/src/queue_list.dart

Issue 660373002: Add a QueueList class to the collection package. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: pkg/collection/lib/src/queue_list.dart
diff --git a/pkg/collection/lib/src/queue_list.dart b/pkg/collection/lib/src/queue_list.dart
new file mode 100644
index 0000000000000000000000000000000000000000..5ae963147d970664775a1720317abc2df082128e
--- /dev/null
+++ b/pkg/collection/lib/src/queue_list.dart
@@ -0,0 +1,208 @@
+// 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.");
+
+ if (value <= length) {
+ while (length > value) {
+ removeLast();
+ }
Lasse Reichstein Nielsen 2014/10/29 07:04:44 This could probably be more efficient. Maybe: int
Lasse Reichstein Nielsen 2014/10/29 08:15:30 (But warning: Not tested!)
nweiz 2014/10/29 20:49:35 Done.
+ } else {
+ while (length < value) {
+ add(null);
+ }
+ }
+ }
+
+ E operator [](int index) => _table[(_head + index) & (_table.length - 1)];
Lasse Reichstein Nielsen 2014/10/29 07:04:44 This, and []=, needs bounds checks.
nweiz 2014/10/29 20:49:35 Done.
+
+ void operator[]=(int index, E value) {
+ _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 << 2) - 1;
Lasse Reichstein Nielsen 2014/10/29 07:04:44 I think it should only be "<< 1".
Lasse Reichstein Nielsen 2014/10/29 08:15:30 Alternatively it is deliberate in order to not gro
nweiz 2014/10/29 20:49:35 Done; also changed in Queue itself.
+ for(;;) {
+ int nextNumber = number & (number - 1);
+ if (nextNumber == 0) return number;
+ number = nextNumber;
+ }
Lasse Reichstein Nielsen 2014/10/29 07:04:44 Do we get a warning here for not returning a value
nweiz 2014/10/29 20:49:35 It doesn't look like we do. Apparently the analyze
+ }
+
+ /** 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);
+ int newCapacity = _nextPowerOf2(newElementCount);
Lasse Reichstein Nielsen 2014/10/29 08:15:30 newElementCount -> newElementCount + 1 to ensure w
nweiz 2014/10/29 20:49:35 Done.
+ List<E> newTable = new List<E>(newCapacity);
+ _tail = _writeToList(newTable);
+ _table = newTable;
+ _head = 0;
+ }
+}

Powered by Google App Engine
This is Rietveld 408576698