Implement Model-Driven-Views spec for Dart

pkg/mdv_observe/lib/src/observable_list.dart

Index: pkg/mdv_observe/lib/src/observable_list.dart
diff --git a/pkg/mdv_observe/lib/src/observable_list.dart b/pkg/mdv_observe/lib/src/observable_list.dart
new file mode 100644
index 0000000000000000000000000000000000000000..3737dcdc18f66fb5146e336258a044ad09a44f47
--- /dev/null
+++ b/pkg/mdv_observe/lib/src/observable_list.dart
@@ -0,0 +1,288 @@
+// 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 mdv_observe;
+
+/**
+ * Represents an observable list of model values. If any items are added,
+ * removed, or replaced, then observers that are listening to [changes]
+ * will be notified.
+ */
+// TODO(jmesserly): remove implements List<E> once we can extend ListBase<E>
+class ObservableList<E> extends _ListBaseWorkaround with ObservableMixin
+    implements List<E> {
+  List<ListChangeRecord> _records;
+
+  static const _LENGTH = const Symbol('length');
+
+  /** The inner [List<E>] with the actual storage. */
+  final List<E> _list;
+
+  /**
+   * Creates an observable list of the given [length].
+   *
+   * If no [length] argument is supplied an extendable list of
+   * length 0 is created.
+   *
+   * If a [length] argument is supplied, a fixed size list of that
+   * length is created.
+   */
+  ObservableList([int length])
+      : _list = length != null ? new List<E>(length) : <E>[];
+
+  /**
+   * Creates an observable list with the elements of [other]. The order in
+   * the list will be the order provided by the iterator of [other].
+   */
+  factory ObservableList.from(Iterable<E> other) =>
+      new ObservableList<E>()..addAll(other);
+
+  // TODO(jmesserly): remove once we have mirrors
+  getValueWorkaround(key) => key == _LENGTH ? length : null;
+
+  setValueWorkaround(key, value) {
+    if (key == _LENGTH) length = value;
+  }
+
+  int get length => _list.length;
+
+  set length(int value) {
+    int len = _list.length;
+    if (len == value) return;
+
+    // Produce notifications if needed
+    if (hasObservers) {
+      if (value < len) {
+        // Remove items, then adjust length. Note the reverse order.
+        _recordChange(new ListChangeRecord(value, removedCount: len - value));
+      } else {
+        // Adjust length then add items
+        _recordChange(new ListChangeRecord(len, addedCount: value - len));
+      }
+    }
+
+    _list.length = value;
+  }
+
+  E operator [](int index) => _list[index];
+
+  void operator []=(int index, E value) {
+    var oldValue = _list[index];
+    if (hasObservers) {
+      _recordChange(new ListChangeRecord(index, addedCount: 1, removedCount: 1));
+    }
+    _list[index] = value;
+  }
+
+  // The following methods are here so that we can provide nice change events.
+
+  void setAll(int index, Iterable<E> iterable) {
+    if (iterable is! List && iterable is! Set) {
+      iterable = iterable.toList();
+    }
+    var len = iterable.length;
+    _list.setAll(index, iterable);
+    if (hasObservers && len > 0) {
+      _recordChange(
+          new ListChangeRecord(index, addedCount: len, removedCount: len));
+    }
+  }
+
+  void add(E value) {
+    int len = _list.length;
+    if (hasObservers) {
+      _recordChange(new ListChangeRecord(len, addedCount: 1));
+    }
+
+    _list.add(value);
+  }
+
+  void addAll(Iterable<E> iterable) {
+    int len = _list.length;
+    _list.addAll(iterable);
+    int added = _list.length - len;
+    if (hasObservers && added > 0) {
+      _recordChange(new ListChangeRecord(len, addedCount: added));
+    }
+  }
+
+  bool remove(Object element) {
+    for (int i = 0; i < this.length; i++) {
+      if (this[i] == element) {
+        removeRange(i, 1);
+        return true;
+      }
+    }
+    return false;
+  }
+
+  void removeRange(int start, int end) {
+    _rangeCheck(start, end);
+    int length = end - start;
+    _list.setRange(start, this.length - length, this, end);
+
+    int len = _list.length;
+    _list.length -= length;
+    if (hasObservers && length > 0) {
+      _recordChange(new ListChangeRecord(start, removedCount: length));
+    }
+  }
+
+  void insertAll(int index, Iterable<E> iterable) {
+    if (index < 0 || index > length) {
+      throw new RangeError.range(index, 0, length);
+    }
+    // TODO(floitsch): we can probably detect more cases.
+    if (iterable is! List && iterable is! Set) {
+      iterable = iterable.toList();
+    }
+    int insertionLength = iterable.length;
+    // There might be errors after the length change, in which case the list
+    // will end up being modified but the operation not complete. Unless we
+    // always go through a "toList" we can't really avoid that.
+    int len = _list.length;
+    _list.length += insertionLength;
+
+    _list.setRange(index + insertionLength, this.length, this, index);
+    _list.setAll(index, iterable);
+
+    if (hasObservers && insertionLength > 0) {
+      _recordChange(new ListChangeRecord(index, addedCount: insertionLength));
+    }
+  }
+
+  void insert(int index, E element) {
+    if (index < 0 || index > length) {
+      throw new RangeError.range(index, 0, length);
+    }
+    if (index == length) {
+      add(element);
+      return;
+    }
+    // We are modifying the length just below the is-check. Without the check
+    // Array.copy could throw an exception, leaving the list in a bad state
+    // (with a length that has been increased, but without a new element).
+    if (index is! int) throw new ArgumentError(index);
+    _list.length++;
+    _list.setRange(index + 1, length, this, index);
+    if (hasObservers) {
+      _recordChange(new ListChangeRecord(index, addedCount: 1));
+    }
+    _list[index] = element;
+  }
+
+
+  E removeAt(int index) {
+    E result = this[index];
+    removeRange(index, index + 1);
+    return result;
+  }
+
+  void _rangeCheck(int start, int end) {
+    if (start < 0 || start > this.length) {
+      throw new RangeError.range(start, 0, this.length);
+    }
+    if (end < start || end > this.length) {
+      throw new RangeError.range(end, start, this.length);
+    }
+  }
+
+  void _recordChange(ListChangeRecord record) {
+    if (_records == null) {
+      _records = [];
+      queueChangeRecords(_summarizeRecords);
+    }
+    _records.add(record);
+  }
+
+  /**
+   * We need to summarize change records. Consumers of these records want to
+   * apply the batch sequentially, and ensure that they can find inserted
+   * items by looking at that position in the list. This property does not
+   * hold in our record-as-you-go records. Consider:
+   *
+   *     var model = toObservable(['a', 'b']);
+   *     model.removeAt(1);
+   *     model.insertAll(0, ['c', 'd', 'e']);
+   *     model.removeRange(1, 3);
+   *     model.insert(1, 'f');
+   *
+   * Here, we inserted some records and then removed some of them.
+   * If someone processed these records naively, they would "play back" the
+   * insert incorrectly, because those items will be shifted.
+   *
+   * We summarize changes using a straightforward technique:
+   * Simulate the moves and use the final item positions to synthesize a
+   * new list of changes records. This has the advantage of not depending
+   * on the actual *values*, so we don't need to perform N^2 edit
+   */
+  // TODO(jmesserly): there's probably something smarter here, but this
+  // algorithm is pretty simple. It has complexity equivalent to the original
+  // list modifications.
+  // One simple idea: we can simply update the index map as we do the operations
+  // to the list, then produce the records at the end.
+  void _summarizeRecords() {
+    int oldLength = length;
+    for (var r in _records) {
+      oldLength += r.removedCount - r.addedCount;
+    }
+
+    if (length != oldLength) {
+      notifyPropertyChange(_LENGTH, oldLength, length);
+    }
+
+    if (_records.length == 1) {
+      notifyChange(_records[0]);
+      _records = null;
+      return;
+    }
+
+    var items = [];
+    for (int i = 0; i < oldLength; i++) items.add(i);
+    for (var r in _records) {
+      items.removeRange(r.index, r.index + r.removedCount);

[Siggi Cherem (dart-lang), 2013/05/09 18:49:35]

I assume items.removeRange(x, x) is a noop? or would list throw an error in that
case?

[Jennifer Messerly, 2013/05/09 18:55:41]

yup! it's a no-op

+
+      // Represent inserts with -1.
+      items.insertAll(r.index, new List.filled(r.addedCount, -1));
+    }
+    assert(items.length == length);
+
+    _records = null;
+
+    int index = 0;
+    int offset = 0;
+    while (index < items.length) {
+      // Skip unchanged items.
+      while (index < items.length && items[index] == index + offset) {
+        index++;
+      }
+
+      // Find inserts
+      int startIndex = index;
+      while (index < items.length && items[index] == -1) {
+        index++;
+      }
+
+      int added = index - startIndex;
+
+      // Use the delta between our actual and expected position to determine
+      // how much was removed.
+      int actualIndex = index < items.length ? items[index] : oldLength;

[Siggi Cherem (dart-lang), 2013/05/09 18:49:35]

it took me a while to understand these two lines, but they make sense once you
draw an example on paper. 

Maybe it can help if we rename actualIndex and expectedIndex. It seems that we
have 2 concepts named 'index', the values stored in the items (which are
indices) and the meta-index represented by the index variable. So maybe we can
call them actualItem/exectedItem or actualValue/expectedValue?

[Jennifer Messerly, 2013/05/09 18:55:41]

good idea! went with *Item

+      int expectedIndex = startIndex + offset;
+
+      int removed = actualIndex - expectedIndex;
+
+      if (added > 0 || removed > 0) {
+        notifyChange(new ListChangeRecord(startIndex, addedCount: added,
+            removedCount: removed));
+      }
+
+      offset += removed - added;
+    }
+  }
+}
+
+// TODO(jmesserly): bogus type to workaround spurious VM bug with generic base
+// class and mixins.
+abstract class _ListBaseWorkaround extends ListBase<dynamic> {}