Introduce new LinkedList to dart:collection.

sdk/lib/collection/linked_list.dart

+// Copyright (c) 2013, 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 linked list implementation, providing O(1) removal(unlink) of elements and
+ * manual traversal through [next] and [previous].
+ *
+ * The list elements must extend [LinkedListEntry].
+ */
+class LinkedList<E extends LinkedListEntry<E>>
+    extends IterableBase<E>
+    implements _LinkedListLink {
+  int _modificationCount = 0;
+  int _length = 0;
+  _LinkedListLink _next;
+  _LinkedListLink _previous;
+
+  /**
+   * Construct a new empty linked list.
+   */
+  LinkedList() {
+    _next = _previous = this;
+  }
+
+  /**
+   * Add [entry] to the beginning of the list.
+   */
+  void addFirst(E entry) {
+    _insertAfter(this, entry);
+  }
+
+  /**
+   * Add [entry] to the end of the list.
+   */
+  void add(E entry) {
+    _insertAfter(_previous, entry);
+  }
+
+  /**
+   * Add [entries] to the end of the list.
+   */
+  void addAll(Iterable<E> entries) {
+    entries.forEach((entry) => _insertAfter(_previous, entry));
+  }
+
+  /**
+   * Remove [entry] from the list. This is the same as calling `entry.unlink()`.
+   *
+   * If [entry] is not in the list, `false` is returned.
+   */
+  bool remove(E entry) {
+    if (entry._list != this) return false;
+    _unlink(entry);  // Unlink will decrement length.
+    return true;
+  }
+
+  Iterator<E> get iterator => new _LinkedListIterator<E>(this);
+
+  String toString() => ToString.iterableToString(this);
+
+  int get length => _length;
+
+  void clear() {
+    _modificationCount++;
+    _LinkedListLink next = _next;
+    while (!identical(next, this)) {
+      _LinkedListLink entry = next;
+      next = entry._next;
+      entry._next = entry._previous = entry._list = null;
+    }
+    _next = _previous = this;
+    _length = 0;
+  }
+
+  E get first {
+    if (identical(_next, this)) {
+      throw new StateError('No such element');
+    }
+    return _next;
+  }
+
+  E get last {
+    if (identical(_previous, this)) {
+      throw new StateError('No such element');
+    }
+    return _previous;
+  }
+
+  E get single {
+    if (identical(_previous, this)) {
+      throw new StateError('No such element');
+    }
+    if (!identical(_previous, _next)) {
+      throw new StateError('Too many elements');
+    }
+    return _next;
+  }
+
+  /**
+   * Call [action] with each entry in the list.
+   *
+   * It's an error if [action] modify the list.
+   */
+  void forEach(void action(E entry)) {
+    int modificationCount = _modificationCount;
+    _LinkedListLink current = _next;
+    while (!identical(current, this)) {
+      action(current);
+      if (modificationCount != _modificationCount) {
+        throw new ConcurrentModificationError(this);
+      }
+      current = current._next;
+    }
+  }
+
+  bool get isEmpty => _length == 0;
+
+  void _insertAfter(_LinkedListLink entry, E newEntry) {
+    if (newEntry.list != null) {
+      throw new StateError(
+          'LinkedListEntry is already in a LinkedList');
+    }
+    _modificationCount++;
+    newEntry._list = this;
+    var predecessor = entry;
+    var successor = entry._next;
+    successor._previous = newEntry;
+    newEntry._previous = predecessor;
+    newEntry._next = successor;
+    predecessor._next = newEntry;
+    _length++;
+  }
+
+  void _unlink(E entry) {
+    _modificationCount++;
+    entry._next._previous = entry._previous;
+    entry._previous._next = entry._next;
+    _length--;
+    entry._list = entry._next = entry._previous = null;
+  }
+}
+
+
+class _LinkedListIterator<E extends LinkedListEntry>
+    implements Iterator<E> {
+  final LinkedList<E> _list;
+  final int _modificationCount;
+  E _current;
+  _LinkedListLink _next;
+
+  _LinkedListIterator(LinkedList<E> list)
+    : _list = list,
+      _modificationCount = list._modificationCount,
+      _next = list._next;
+
+  E get current => _current;
+
+  bool moveNext() {
+    if (identical(_next, _list)) {
+      _current = null;
+      return false;
+    }
+    if (_modificationCount != _list._modificationCount) {
+      throw new ConcurrentModificationError(this);
+    }
+    _current = _next;
+    _next = _next._next;
+    return true;
+  }
+}
+
+
+class _LinkedListLink {
+  _LinkedListLink _next;
+  _LinkedListLink _previous;
+}
+
+
+/**
+ * Entry element for a [LinkedList]. Any entry must extend this class.
+ */
+abstract class LinkedListEntry<E> implements _LinkedListLink {
+  LinkedList<E> _list;
+  _LinkedListLink _next;
+  _LinkedListLink _previous;
+
+  /**
+   * Get the list containing this element.
+   */
+  LinkedList<E> get list => _list;
+
+  /**
+   * Unlink the element from the list.
+   */
+  void unlink() {
+    _list._unlink(this);
+  }
+
+  /**
+   * Return the succeeding element in the list.
+   */
+  E get next {
+    if (_next == _list) return null;
+    return _next;
+  }
+
+  /**
+   * Return the preceeding element in the list.
+   */
+  E get previous {
+    if (_previous == _list) return null;
+    return _previous;
+  }
+
+  /**
+   * insert an element after this.
+   */
+  void insertAfter(E entry) {
+    _list._insertAfter(this, entry);
+  }
+
+  /**
+   * Insert an element before this.
+   */
+  void insertBefore(E entry) {
+    _list._insertAfter(_previous, entry);
+  }
+}