Fix bug in DoubleLinkedQueue where removing from empty queue throws.

sdk/lib/collection/queue.dart

 // Copyright (c) 2011, 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.
 
 part of dart.collection;
 
 /**
  * A [Queue] is a collection that can be manipulated at both ends. One
  * can iterate over the elements of a queue through [forEach] or with
  * an [Iterator].
@@ skipping 83 matching lines @@
 
 /**
  * An entry in a doubly linked list. It contains a pointer to the next
  * entry, the previous entry, and the boxed element.
  */
 class DoubleLinkedQueueEntry<E> {
   DoubleLinkedQueueEntry<E> _previous;
   DoubleLinkedQueueEntry<E> _next;
   E _element;
 
-  DoubleLinkedQueueEntry(E e) {
-    _element = e;
-  }
+  DoubleLinkedQueueEntry(E e) : _element = e;
 
-  void _link(DoubleLinkedQueueEntry<E> p,
-             DoubleLinkedQueueEntry<E> n) {
-    _next = n;
-    _previous = p;
-    p._next = this;
-    n._previous = this;
+  void _link(DoubleLinkedQueueEntry<E> previous,
+             DoubleLinkedQueueEntry<E> next) {
+    _next = next;
+    _previous = previous;
+    previous._next = this;
+    next._previous = this;
   }
 
   void append(E e) {
     new DoubleLinkedQueueEntry<E>(e)._link(this, _next);
   }
 
   void prepend(E e) {
     new DoubleLinkedQueueEntry<E>(e)._link(_previous, this);
   }
 
@@ skipping 21 matching lines @@
     return _element;
   }
 
   void set element(E e) {
     _element = e;
   }
 }
 
 /**
  * A sentinel in a double linked list is used to manipulate the list
- * at both ends. A double linked list has exactly one sentinel, which
- * is the only entry when the list is constructed. Initially, a
- * sentinel has its next and previous entry point to itself. A
- * sentinel does not box any user element.
+ * at both ends.
+ * A double linked list has exactly one sentinel,
+ * which is the only entry when the list is constructed.
+ * Initially, a sentinel has its next and previous entry point to itself.
+ * A sentinel does not box any user element.
  */
 class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> {
   _DoubleLinkedQueueEntrySentinel() : super(null) {
     _link(this, this);
   }
 
   E remove() {
     throw new StateError("Empty queue");
   }
 
   DoubleLinkedQueueEntry<E> _asNonSentinelEntry() {
     return null;
   }
 
   void set element(E e) {
     // This setter is unreachable.
+    // TODO(lrn): Don't inherit the field if we don't use it.
     assert(false);
   }
 
   E get element {
     throw new StateError("Empty queue");
   }
 }
 
 /**
  * A [Queue] implementation based on a double-linked list.
  *
  * Allows constant time add, remove-at-ends and peek operations.
- *
- * Can do [removeAll] and [retainAll] in linear time.
  */
 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
   _DoubleLinkedQueueEntrySentinel<E> _sentinel;
   int _elementCount = 0;
 
   DoubleLinkedQueue() {
     _sentinel = new _DoubleLinkedQueueEntrySentinel<E>();
   }
 
   factory DoubleLinkedQueue.from(Iterable<E> other) {
@@ skipping 34 matching lines @@
     return result;
   }
 
   E removeFirst() {
     E result = _sentinel._next.remove();
     _elementCount--;
     return result;
   }
 
   bool remove(Object o) {
-    DoubleLinkedQueueEntry<E> entry = firstEntry();
+    DoubleLinkedQueueEntry<E> entry = _sentinel._next;
     while (!identical(entry, _sentinel)) {
       if (entry.element == o) {
         entry.remove();
         _elementCount--;
         return true;
       }
       entry = entry._next;
     }
     return false;
   }
 
   void _filter(bool test(E element), bool removeMatching) {
-    DoubleLinkedQueueEntry<E> entry = firstEntry();
+    DoubleLinkedQueueEntry<E> entry = _sentinel._next;
     while (!identical(entry, _sentinel)) {
       DoubleLinkedQueueEntry<E> next = entry._next;
       if (identical(removeMatching, test(entry.element))) {
         entry.remove();
         _elementCount--;
       }
       entry = next;
     }
   }
 
@@ skipping 80 matching lines @@
 }
 
 /**
  * List based [Queue].
  *
  * Keeps a cyclic buffer of elements, and grows to a larger buffer when
  * it fills up. This guarantees constant time peek and remove operations, and
  * amortized constant time add operations.
  *
  * The structure is efficient for any queue or stack usage.
- *
- * Operations like [removeAll] and [removeWhere] are very
- * inefficient. If those are needed, use a [DoubleLinkedQueue] instead.
  */
 class ListQueue<E> extends IterableBase<E> implements Queue<E> {
   static const int _INITIAL_CAPACITY = 8;
   List<E> _table;
   int _head;
   int _tail;
   int _modificationCount = 0;
 
   /**
    * Create an empty queue.
@@ skipping 342 matching lines @@
     _queue._checkModification(_modificationCount);
     if (_position == _end) {
       _current = null;
       return false;
     }
     _current = _queue._table[_position];
     _position = (_position + 1) & (_queue._table.length - 1);
     return true;
   }
 }