Introduce new LinkedList to dart:collection.

sdk/lib/collection/linked_list.dart

Index: sdk/lib/collection/linked_list.dart
diff --git a/sdk/lib/collection/linked_list.dart b/sdk/lib/collection/linked_list.dart
new file mode 100644
index 0000000000000000000000000000000000000000..4394db42dc18694305bebef379d96110e0170414
--- /dev/null
+++ b/sdk/lib/collection/linked_list.dart
@@ -0,0 +1,82 @@
+// Copyright (c) 2012, 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;
+
+class LinkedList

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

<E extends LinkedListEntry>

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+    extends Collection<LinkedListEntry>
+    implements _LinkedListEntry {
+  int _length;
+  LinkedList _list;
+  _LinkedListEntry _next;
+  _LinkedListEntry _prev;
+
+  LinkedList() {
+    _next = _prev = _list = this;

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

No need for _list here.

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+  }
+
+  void add(LinkedListEntry entry) {

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

(E entry)

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+    _insertAfter(_prev, entry);
+    _length++;

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

void remove(E entry) {
  if (entry._list != this) return;
  entry._unlink();
  _length--;
}

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+  }
+
+  void _insertAfter(_LinkedListEntry entry, _LinkedListEntry newEntry) {

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

Last _LinkedListEntry -> E

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+    newEntry._list = this;

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

assert(newEntry.list == null);

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+    entry._next._prev = entry;
+    newEntry._prev = entry;
+    newEntry._next = entry._next;
+    entry._next = newEntry;
+  }
+
+  Iterator<LinkedListEntry> get iterator {
+    return new _LinkedListIterator(this);
+  }
+
+  int get length => _length;
+}
+
+class _LinkedListIterator implements Iterator<LinkedListEntry> {

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

_LinkedListIterator<E extends LinkedListEntry> implements Itertator<E>
ensure correct return type E for 'current'.

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+  LinkedList _list;
+  _LinkedListEntry _current;

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

Consider having:
  E _current = null;
  _LinkedListEntry _next;
  _LinkedListITerator(LinkedList<E> list) : _list = list, _next = list._next;
  moveNext() {
    if (identical(_next, _list)) {
      _current = null;
      return false;
    }
    _current = _next;
    _next = _next._next;
    return true;
  }
One extra field, but simpler logic.

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+
+  _LinkedListIterator(this._list) {
+    _current = _list;
+  }
+
+  LinkedListEntry get current {
+    if (_current == _list) return null;
+    return _current;
+  }
+
+  bool moveNext() {
+    if (_current == null) return false;
+    if (_current._next == _list) return false;

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

if (identical(_current._next, _list) {
  _current = null;
  return false;
}

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+    _current = _current._next;
+    return true;
+  }
+}
+
+class _LinkedListEntry {
+  LinkedList _list;

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

Move to LinkedListEntry

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+  _LinkedListEntry _next;
+  _LinkedListEntry _prev;
+}
+
+abstract class LinkedListEntry extends _LinkedListEntry {
+  void unlink() {
+    _next.prev = _prev;
+    _prev.next = _next;
+    _list._length--;
+    _list = _next = _prev = null;
+  }
+
+  LinkedListEntry get next {
+    return _next;
+  }
+
+  LinkedListEntry get prev {
+    if (_prev == _list) return null;
+    return _prev;
+  }

[Lasse Reichstein Nielsen, 2013/04/02 08:23:44]

Make a "list" getter, so you can go from an element to the list it is part of.

[Anders Johnsen, 2013/05/16 09:17:40]

Done.

+}