work in progress: observable implementation using detailed change records

lib/src/linked_list.dart

+// 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.
+
+/**
+ * A doubly-linked list, adapted from DoubleLinkedQueueEntry in
+ * sdk/lib/collection/queue.dart.
+ */
+// TODO(jmesserly): this should be in a shared pkg somewhere. Surely I am not
+// the only person who will want to use a linked list :)
+library linked_list;
+
+/**
+ * An entry in a doubly linked list. It contains a pointer to the next
+ * entry, the previous entry, and the boxed value.
+ */
+class LinkedListNode<E> {
+  LinkedListNode<E> _previous;
+  LinkedListNode<E> _next;
+  E _value;
+
+  LinkedListNode._(E e) {
+    _value = e;
+  }
+
+  void _link(LinkedListNode<E> p, LinkedListNode<E> n) {
+    _next = n;
+    _previous = p;
+    p._next = this;
+    n._previous = this;
+  }
+
+  LinkedListNode<E> append(E e) =>
+      new LinkedListNode<E>._(e).._link(this, _next);
+
+  LinkedListNode<E> prepend(E e) =>
+      new LinkedListNode<E>._(e).._link(_previous, this);
+
+  void remove() {
+    _previous._next = _next;
+    _next._previous = _previous;
+    _next = null;
+    _previous = null;
+  }
+
+  LinkedListNode<E> get _nonSentinel => this;
+
+  LinkedListNode<E> get previous => _previous._nonSentinel;
+
+  LinkedListNode<E> get next => _next._nonSentinel;
+
+  E get value => _value;
+
+  set value(E e) => _value = 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 value.
+ */
+class LinkedListSentinel<E> extends LinkedListNode<E> {
+  LinkedListSentinel() : super._(null) {
+    _link(this, this);
+  }
+
+  void remove() {
+    throw new StateError("Empty list");
+  }
+
+  LinkedListNode<E> get _nonSentinel => null;
+
+  void set value(E e) {
+    throw new StateError("Empty list");
+  }
+
+  E get value {
+    throw new StateError("Empty list");
+  }
+}