| // 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. |
| |
| /** |
| * 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]. |
| */ |
| abstract class Queue<E> extends Collection<E> { |
| |
| /** |
| * Creates a queue. |
| */ |
| factory Queue() => new DoubleLinkedQueue<E>(); |
| |
| /** |
| * Creates a queue with the elements of [other]. The order in |
| * the queue will be the order provided by the iterator of [other]. |
| */ |
| factory Queue.from(Iterable<E> other) => new DoubleLinkedQueue<E>.from(other); |
| |
| /** |
| * Removes and returns the first element of this queue. Throws an |
| * [StateError] exception if this queue is empty. |
| */ |
| E removeFirst(); |
| |
| /** |
| * Removes and returns the last element of the queue. Throws an |
| * [StateError] exception if this queue is empty. |
| */ |
| E removeLast(); |
| |
| /** |
| * Adds [value] at the beginning of the queue. |
| */ |
| void addFirst(E value); |
| |
| /** |
| * Adds [value] at the end of the queue. |
| */ |
| void addLast(E value); |
| |
| /** |
| * Adds [value] at the end of the queue. |
| */ |
| void add(E value); |
| |
| /** |
| * Adds all elements of [collection] at the end of the queue. The |
| * length of the queue is extended by the length of [collection]. |
| */ |
| void addAll(Collection<E> collection); |
| |
| /** |
| * Returns the first element of the queue. Throws an |
| * [StateError] exception if this queue is empty. |
| */ |
| E get first; |
| |
| /** |
| * Returns the last element of the queue. Throws an |
| * [StateError] exception if this queue is empty. |
| */ |
| E get last; |
| |
| /** |
| * Removes all elements in the queue. The size of the queue becomes zero. |
| */ |
| void clear(); |
| } |
| |
| |
| /** |
| * An entry in a doubly linked list. It contains a pointer to the next |
| * entry, the previous entry, and the boxed element. |
| * |
| * WARNING: This class is temporary located in dart:core. It'll be removed |
| * at some point in the near future. |
| */ |
| class DoubleLinkedQueueEntry<E> { |
| DoubleLinkedQueueEntry<E> _previous; |
| DoubleLinkedQueueEntry<E> _next; |
| E _element; |
| |
| DoubleLinkedQueueEntry(E e) { |
| _element = e; |
| } |
| |
| void _link(DoubleLinkedQueueEntry<E> p, |
| DoubleLinkedQueueEntry<E> n) { |
| _next = n; |
| _previous = p; |
| p._next = this; |
| n._previous = this; |
| } |
| |
| void append(E e) { |
| new DoubleLinkedQueueEntry<E>(e)._link(this, _next); |
| } |
| |
| void prepend(E e) { |
| new DoubleLinkedQueueEntry<E>(e)._link(_previous, this); |
| } |
| |
| E remove() { |
| _previous._next = _next; |
| _next._previous = _previous; |
| _next = null; |
| _previous = null; |
| return _element; |
| } |
| |
| DoubleLinkedQueueEntry<E> _asNonSentinelEntry() { |
| return this; |
| } |
| |
| DoubleLinkedQueueEntry<E> previousEntry() { |
| return _previous._asNonSentinelEntry(); |
| } |
| |
| DoubleLinkedQueueEntry<E> nextEntry() { |
| return _next._asNonSentinelEntry(); |
| } |
| |
| E get element { |
| 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. |
| */ |
| 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. |
| assert(false); |
| } |
| |
| E get element { |
| throw new StateError("Empty queue"); |
| } |
| } |
| |
| /** |
| * Implementation of a double linked list that box list elements into |
| * DoubleLinkedQueueEntry objects. |
| * |
| * WARNING: This class is temporary located in dart:core. It'll be removed |
| * at some point in the near future. |
| */ |
| class DoubleLinkedQueue<E> implements Queue<E> { |
| _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
| |
| DoubleLinkedQueue() { |
| _sentinel = new _DoubleLinkedQueueEntrySentinel<E>(); |
| } |
| |
| factory DoubleLinkedQueue.from(Iterable<E> other) { |
| Queue<E> list = new DoubleLinkedQueue(); |
| for (final e in other) { |
| list.addLast(e); |
| } |
| return list; |
| } |
| |
| void addLast(E value) { |
| _sentinel.prepend(value); |
| } |
| |
| void addFirst(E value) { |
| _sentinel.append(value); |
| } |
| |
| void add(E value) { |
| addLast(value); |
| } |
| |
| void addAll(Collection<E> collection) { |
| for (final e in collection) { |
| add(e); |
| } |
| } |
| |
| E removeLast() { |
| return _sentinel._previous.remove(); |
| } |
| |
| E removeFirst() { |
| return _sentinel._next.remove(); |
| } |
| |
| E get first { |
| return _sentinel._next.element; |
| } |
| |
| E get last { |
| return _sentinel._previous.element; |
| } |
| |
| DoubleLinkedQueueEntry<E> lastEntry() { |
| return _sentinel.previousEntry(); |
| } |
| |
| DoubleLinkedQueueEntry<E> firstEntry() { |
| return _sentinel.nextEntry(); |
| } |
| |
| int get length { |
| int counter = 0; |
| forEach(void _(E element) { counter++; }); |
| return counter; |
| } |
| |
| bool get isEmpty { |
| return (_sentinel._next === _sentinel); |
| } |
| |
| void clear() { |
| _sentinel._next = _sentinel; |
| _sentinel._previous = _sentinel; |
| } |
| |
| void forEach(void f(E element)) { |
| DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| while (entry !== _sentinel) { |
| DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| f(entry._element); |
| entry = nextEntry; |
| } |
| } |
| |
| void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) { |
| DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| while (entry !== _sentinel) { |
| DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| f(entry); |
| entry = nextEntry; |
| } |
| } |
| |
| bool every(bool f(E element)) { |
| DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| while (entry !== _sentinel) { |
| DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| if (!f(entry._element)) return false; |
| entry = nextEntry; |
| } |
| return true; |
| } |
| |
| bool some(bool f(E element)) { |
| DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| while (entry !== _sentinel) { |
| DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| if (f(entry._element)) return true; |
| entry = nextEntry; |
| } |
| return false; |
| } |
| |
| Queue map(f(E element)) { |
| Queue other = new Queue(); |
| DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| while (entry !== _sentinel) { |
| DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| other.addLast(f(entry._element)); |
| entry = nextEntry; |
| } |
| return other; |
| } |
| |
| Dynamic reduce(Dynamic initialValue, |
| Dynamic combine(Dynamic previousValue, E element)) { |
| return Collections.reduce(this, initialValue, combine); |
| } |
| |
| Queue<E> filter(bool f(E element)) { |
| Queue<E> other = new Queue<E>(); |
| DoubleLinkedQueueEntry<E> entry = _sentinel._next; |
| while (entry !== _sentinel) { |
| DoubleLinkedQueueEntry<E> nextEntry = entry._next; |
| if (f(entry._element)) other.addLast(entry._element); |
| entry = nextEntry; |
| } |
| return other; |
| } |
| |
| _DoubleLinkedQueueIterator<E> iterator() { |
| return new _DoubleLinkedQueueIterator<E>(_sentinel); |
| } |
| |
| String toString() { |
| return Collections.collectionToString(this); |
| } |
| } |
| |
| class _DoubleLinkedQueueIterator<E> implements Iterator<E> { |
| final _DoubleLinkedQueueEntrySentinel<E> _sentinel; |
| DoubleLinkedQueueEntry<E> _currentEntry; |
| |
| _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel this._sentinel) { |
| _currentEntry = _sentinel; |
| } |
| |
| bool get hasNext { |
| return _currentEntry._next !== _sentinel; |
| } |
| |
| E next() { |
| if (!hasNext) { |
| throw new StateError("No more elements"); |
| } |
| _currentEntry = _currentEntry._next; |
| return _currentEntry.element; |
| } |
| } |