Add a QueueList class to the collection package.

pkg/collection/lib/src/queue_list.dart

+// 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 delta = value - length;
if (delta >= 0) {
  if (_table.length <= value) {
    _preGrow(value);
  }
  _head = (_head + delta) & (_table.length - 1)
} else {
  int newTail = _tail + delta;  // `delta` is negative.
  if (newTail >= 0) {
    _table.fillRange(newTail, _tail, null);
  } else { 
    int tableLength = _table.Length;
    newTail += tableLength;
    _table.fillRange(0, _tail, null);
    _table.fillRange(newTail, tableLength, null);
  }
  _tail = newTail;
}

  

[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 grow to buffer that will
immediately be filled anyway. I don't remember, and I haven't documented it.
That just makes the comment wrong.
I think this function should be changed to "<< 1", and the use in _preGrow
should add something to the element count.

[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?
If so, just change "return number" to "break" and put the return after the loop.

[nweiz, 2014/10/29 20:49:35]

It doesn't look like we do. Apparently the analyzer trusts that that return will
be reached.

+  }
+
+  /** 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 we have capacity exceeding the expected number of elements, instead of
relying on nextPowerOf2 to double the result.
Maybe even ensure an overhead, so either:
 -> newElementCount * 2
or just * 1.5:
 -> newElementCount + newElementCount >> 1
 

[nweiz, 2014/10/29 20:49:35]

Done.

+    List<E> newTable = new List<E>(newCapacity);
+    _tail = _writeToList(newTable);
+    _table = newTable;
+    _head = 0;
+  }
+}