Index: sdk/lib/collection/queue.dart |
diff --git a/sdk/lib/collection/queue.dart b/sdk/lib/collection/queue.dart |
index f515392bf8cb4b44cae9598e5e417fe8344dd72d..8156a48fc111f1f7a19e46a56a38be9712aa6b70 100644 |
--- a/sdk/lib/collection/queue.dart |
+++ b/sdk/lib/collection/queue.dart |
@@ -96,24 +96,34 @@ abstract class Queue<E> implements Iterable<E>, EfficientLength { |
} |
+class _DoubleLink { |
+ _DoubleLink _previous; |
+ _DoubleLink _next; |
+ |
+ void _link(_DoubleLink previous, |
+ _DoubleLink next) { |
+ _next = next; |
+ _previous = previous; |
+ if (previous != null) previous._next = this; |
+ if (next != null) next._previous = this; |
+ } |
+ |
+ void _unlink() { |
+ if (_previous != null) _previous._next = _next; |
+ if (_next != null) _next._previous = _previous; |
+ _next = null; |
+ _previous = null; |
+ } |
+} |
+ |
/** |
* 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; |
+class DoubleLinkedQueueEntry<E> extends _DoubleLink { |
+ E element; |
- DoubleLinkedQueueEntry(E e) : _element = e; |
- |
- void _link(DoubleLinkedQueueEntry<E> previous, |
- DoubleLinkedQueueEntry<E> next) { |
- _next = next; |
- _previous = previous; |
- previous._next = this; |
- next._previous = this; |
- } |
+ DoubleLinkedQueueEntry(this.element); |
void append(E e) { |
new DoubleLinkedQueueEntry<E>(e)._link(this, _next); |
@@ -124,31 +134,91 @@ class DoubleLinkedQueueEntry<E> { |
} |
E remove() { |
- _previous._next = _next; |
- _next._previous = _previous; |
- _next = null; |
- _previous = null; |
- return _element; |
+ _unlink(); |
+ return element; |
} |
- DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { |
- return this; |
+ DoubleLinkedQueueEntry<E> previousEntry() { |
+ return _previous; |
} |
- DoubleLinkedQueueEntry<E> previousEntry() { |
- return _previous._asNonSentinelEntry(); |
+ DoubleLinkedQueueEntry<E> nextEntry() { |
+ return _next; |
+ } |
+} |
+ |
+/** |
+ * Interface for the link classes used by [DoubleLinkedQueue]. |
+ * |
+ * Both the [_DoubleLinkedQueueElement] and [_DoubleLinkedQueueSentinel] |
+ * implements this interface. |
+ * The entry contains a link back to the queue, so calling `append` |
+ * or `prepend` can correctly update the element count. |
+ */ |
+abstract class _DoubleLinkedQueueEntry<E> extends _DoubleLink { |
+ DoubleLinkedQueue<E> _queue; |
+ _DoubleLinkedQueueEntry(this._queue); |
+ |
+ _DoubleLinkedQueueElement _asNonSentinelEntry(); |
+ |
+ void _append(E e) { |
+ new _DoubleLinkedQueueElement<E>(e, _queue)._link(this, _next); |
} |
+ void _prepend(E e) { |
+ new _DoubleLinkedQueueElement<E>(e, _queue)._link(_previous, this); |
+ } |
+ |
+ E _remove(); |
+ |
+ E get element; |
+ |
DoubleLinkedQueueEntry<E> nextEntry() { |
- return _next._asNonSentinelEntry(); |
+ _DoubleLinkedQueueEntry next = _next; |
+ return next._asNonSentinelEntry(); |
} |
- E get element { |
- return _element; |
+ DoubleLinkedQueueEntry<E> previousEntry() { |
+ _DoubleLinkedQueueEntry previous = _previous; |
+ return previous._asNonSentinelEntry(); |
+ } |
+} |
+ |
+/** |
+ * The actual entry type used by the [DoubleLinkedQueue]. |
+ * |
+ * The entry contains a reference to the queue, allowing |
+ * [append]/[prepend] to update the list length. |
+ */ |
+class _DoubleLinkedQueueElement<E> extends _DoubleLinkedQueueEntry<E> |
+ implements DoubleLinkedQueueEntry<E> { |
+ E element; |
+ _DoubleLinkedQueueElement(this.element, DoubleLinkedQueue<E> queue) |
+ : super(queue); |
+ |
+ void append(E e) { |
+ _append(e); |
+ if (_queue != null) _queue._elementCount++; |
+ } |
+ |
+ void prepend(E e) { |
+ _prepend(e); |
+ if (_queue != null) _queue._elementCount++; |
+ } |
+ |
+ E _remove() { |
+ _queue = null; |
+ _unlink(); |
+ return element; |
} |
- void set element(E e) { |
- _element = e; |
+ E remove() { |
+ if (_queue != null) _queue._elementCount--; |
+ return _remove(); |
+ } |
+ |
+ _DoubleLinkedQueueElement _asNonSentinelEntry() { |
+ return this; |
} |
} |
@@ -160,25 +230,22 @@ class DoubleLinkedQueueEntry<E> { |
* 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 IterableElementError.noElement(); |
+class _DoubleLinkedQueueSentinel<E> extends _DoubleLinkedQueueEntry<E> { |
+ _DoubleLinkedQueueSentinel(DoubleLinkedQueue queue) : super(queue) { |
+ _previous = this; |
+ _next = this; |
} |
- DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { |
+ _DoubleLinkedQueueElement _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); |
+ /** Hit by, e.g., [DoubleLinkedQueue.removeFirst] if the queue is empty. */ |
+ E _remove() { |
+ throw IterableElementError.noElement(); |
} |
+ /** Hit by, e.g., [DoubleLinkedQueue.first] if the queue is empty. */ |
E get element { |
throw IterableElementError.noElement(); |
} |
@@ -190,11 +257,11 @@ class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> { |
* Allows constant time add, remove-at-ends and peek operations. |
*/ |
class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
- _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
+ _DoubleLinkedQueueSentinel<E> _sentinel; |
int _elementCount = 0; |
DoubleLinkedQueue() { |
- _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); |
+ _sentinel = new _DoubleLinkedQueueSentinel<E>(this); |
} |
/** |
@@ -204,7 +271,7 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
* [addLast] in the order provided by [elements.iterator]. |
*/ |
factory DoubleLinkedQueue.from(Iterable elements) { |
- Queue<E> list = new DoubleLinkedQueue(); |
+ Queue<E> list = new DoubleLinkedQueue<E>(); |
for (final E e in elements) { |
list.addLast(e); |
} |
@@ -214,44 +281,46 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
int get length => _elementCount; |
void addLast(E value) { |
- _sentinel.prepend(value); |
+ _sentinel._prepend(value); |
_elementCount++; |
} |
void addFirst(E value) { |
- _sentinel.append(value); |
+ _sentinel._append(value); |
_elementCount++; |
} |
void add(E value) { |
- _sentinel.prepend(value); |
+ _sentinel._prepend(value); |
_elementCount++; |
} |
void addAll(Iterable<E> iterable) { |
for (final E value in iterable) { |
- _sentinel.prepend(value); |
+ _sentinel._prepend(value); |
_elementCount++; |
} |
} |
E removeLast() { |
- E result = _sentinel._previous.remove(); |
+ _DoubleLinkedQueueEntry lastEntry = _sentinel._previous; |
+ E result = lastEntry._remove(); |
_elementCount--; |
return result; |
} |
E removeFirst() { |
- E result = _sentinel._next.remove(); |
+ _DoubleLinkedQueueEntry firstEntry = _sentinel._next; |
+ E result = firstEntry._remove(); |
_elementCount--; |
return result; |
} |
bool remove(Object o) { |
- DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
+ _DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
while (!identical(entry, _sentinel)) { |
if (entry.element == o) { |
- entry.remove(); |
+ entry._remove(); |
_elementCount--; |
return true; |
} |
@@ -261,11 +330,11 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
} |
void _filter(bool test(E element), bool removeMatching) { |
- DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
+ _DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
while (!identical(entry, _sentinel)) { |
- DoubleLinkedQueueEntry<E> next = entry._next; |
+ _DoubleLinkedQueueEntry<E> next = entry._next; |
if (identical(removeMatching, test(entry.element))) { |
- entry.remove(); |
+ entry._remove(); |
_elementCount--; |
} |
entry = next; |
@@ -281,17 +350,21 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
} |
E get first { |
- return _sentinel._next.element; |
+ _DoubleLinkedQueueEntry firstEntry = _sentinel._next; |
+ return firstEntry.element; |
} |
E get last { |
- return _sentinel._previous.element; |
+ _DoubleLinkedQueueEntry lastEntry = _sentinel._previous; |
+ return lastEntry.element; |
} |
E get single { |
- // Note that this throws correctly if the queue is empty. |
+ // Note that this throws correctly if the queue is empty |
+ // because reading element on the sentinel throws. |
if (identical(_sentinel._next, _sentinel._previous)) { |
- return _sentinel._next.element; |
+ _DoubleLinkedQueueEntry entry = _sentinel._next; |
+ return entry.element; |
} |
throw IterableElementError.tooMany(); |
} |
@@ -331,23 +404,27 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> { |
} |
class _DoubleLinkedQueueIterator<E> implements Iterator<E> { |
- _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
- DoubleLinkedQueueEntry<E> _nextEntry = null; |
+ _DoubleLinkedQueueSentinel<E> _sentinel; |
+ _DoubleLinkedQueueEntry<E> _nextEntry = null; |
E _current; |
- _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel) |
+ _DoubleLinkedQueueIterator(_DoubleLinkedQueueSentinel<E> sentinel) |
: _sentinel = sentinel, _nextEntry = sentinel._next; |
bool moveNext() { |
- // When [_currentEntry] it is set to [:null:] then it is at the end. |
- if (!identical(_nextEntry, _sentinel)) { |
- _current = _nextEntry._element; |
- _nextEntry = _nextEntry._next; |
- return true; |
+ if (identical(_nextEntry, _sentinel)) { |
+ _current = null; |
+ _nextEntry = null; |
+ _sentinel = null; |
+ return false; |
} |
- _current = null; |
- _nextEntry = _sentinel = null; // Still identical. |
- return false; |
+ _DoubleLinkedQueueElement elementEntry = _nextEntry; |
+ if (elementEntry._queue == null) { |
+ throw new ConcurrentModificationError(_sentinel._queue); |
+ } |
+ _current = elementEntry.element; |
+ _nextEntry = elementEntry._next; |
+ return true; |
} |
E get current => _current; |