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

Unified Diff: sdk/lib/core/queue.dart

Issue 11867024: Move some core classes to collection library. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Update status files with bug number. Created 7 years, 11 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
« no previous file with comments | « sdk/lib/core/map.dart ('k') | sdk/lib/core/set.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: sdk/lib/core/queue.dart
diff --git a/sdk/lib/core/queue.dart b/sdk/lib/core/queue.dart
deleted file mode 100644
index 8f20efdcc7cb60614b6922238d85b7278d4d4262..0000000000000000000000000000000000000000
--- a/sdk/lib/core/queue.dart
+++ /dev/null
@@ -1,319 +0,0 @@
-// 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.core;
-
-/**
- * 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 [iterable] at the end of the queue. The
- * length of the queue is extended by the length of [iterable].
- */
- void addAll(Iterable<E> iterable);
-
- /**
- * 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> extends Iterable<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(Iterable<E> iterable) {
- for (final e in iterable) {
- add(e);
- }
- }
-
- E removeLast() {
- return _sentinel._previous.remove();
- }
-
- E removeFirst() {
- return _sentinel._next.remove();
- }
-
- void remove(Object o) {
- DoubleLinkedQueueEntry<E> entry = firstEntry();
- while (!identical(entry, _sentinel)) {
- if (entry.element == o) {
- entry.remove();
- return;
- }
- entry = entry._next;
- }
- }
-
- void removeAll(Iterable elements) {
- // Use this method when remove is slow and removeMatching more efficient.
- IterableMixinWorkaround.removeAllList(this, elements);
- }
-
- void removeMatching(bool test(E element)) {
- DoubleLinkedQueueEntry<E> entry = firstEntry();
- while (!identical(entry, _sentinel)) {
- DoubleLinkedQueueEntry<E> next = entry._next;
- if (test(entry.element)) {
- entry.remove();
- }
- entry = next;
- }
- }
-
- void retainMatching(bool test(E element)) {
- DoubleLinkedQueueEntry<E> entry = firstEntry();
- while (!identical(entry, _sentinel)) {
- DoubleLinkedQueueEntry<E> next = entry._next;
- if (!test(entry.element)) {
- entry.remove();
- }
- entry = next;
- }
- }
-
- E get first {
- return _sentinel._next.element;
- }
-
- E get last {
- return _sentinel._previous.element;
- }
-
- E get single {
- // Note that this also covers the case where the queue is empty.
- if (identical(_sentinel._next, _sentinel._previous)) {
- return _sentinel._next.element;
- }
- throw new StateError("More than one element");
- }
-
- DoubleLinkedQueueEntry<E> lastEntry() {
- return _sentinel.previousEntry();
- }
-
- DoubleLinkedQueueEntry<E> firstEntry() {
- return _sentinel.nextEntry();
- }
-
- bool get isEmpty {
- return (identical(_sentinel._next, _sentinel));
- }
-
- void clear() {
- _sentinel._next = _sentinel;
- _sentinel._previous = _sentinel;
- }
-
- void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) {
- DoubleLinkedQueueEntry<E> entry = _sentinel._next;
- while (!identical(entry, _sentinel)) {
- DoubleLinkedQueueEntry<E> nextEntry = entry._next;
- f(entry);
- entry = nextEntry;
- }
- }
-
- _DoubleLinkedQueueIterator<E> get iterator {
- return new _DoubleLinkedQueueIterator<E>(_sentinel);
- }
-
- String toString() {
- return Collections.collectionToString(this);
- }
-}
-
-class _DoubleLinkedQueueIterator<E> implements Iterator<E> {
- _DoubleLinkedQueueEntrySentinel<E> _sentinel;
- DoubleLinkedQueueEntry<E> _currentEntry = null;
- E _current;
-
- _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel)
- : _sentinel = sentinel, _currentEntry = sentinel;
-
- bool moveNext() {
- // When [_currentEntry] it is set to [:null:] then it is at the end.
- if (_currentEntry == null) {
- assert(_current == null);
- return false;
- }
- _currentEntry = _currentEntry._next;
- if (identical(_currentEntry, _sentinel)) {
- _currentEntry = null;
- _current = null;
- _sentinel = null;
- return false;
- }
- _current = _currentEntry.element;
- return true;
- }
-
- E get current => _current;
-}
« no previous file with comments | « sdk/lib/core/map.dart ('k') | sdk/lib/core/set.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698