introduce ObservableList.listChanges to keep list changes separate from property changes

pkg/template_binding/lib/src/list_diff.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.
-
-library template_binding.src.list_diff;
-
-import 'dart:math' as math;
-import 'package:observe/observe.dart' show ListChangeRecord;
-
-/**
- * A summary of an individual change to a [List].
- *
- * Each delta represents that at the [index], [removed] sequence of items were
- * removed, and counting forward from [index], [addedCount] items were added.
- *
- * See also: [summarizeListChanges].
- */
-class ListChangeDelta implements ListChangeRecord {
-  /** The index of the change. */
-  final int index;
-
-  List _removed;
-
-  // Note: conceptually final, but for convenience we increment it as we build
-  // the object. It will be "frozen" by the time it is returned the the user.
-  int _addedCount = 0;
-
-  ListChangeDelta(this.index, {List removed, int addedCount: 0})
-      : _removed = removed != null ? removed : [],
-        _addedCount = addedCount;
-
-  // TODO(jmesserly): freeze remove list before handing it out?
-  /** The items removed, if any. Otherwise this will be an empty list. */
-  List get removed => _removed;
-
-  /** The number of items added. */
-  int get addedCount => _addedCount;
-
-  int get removedCount => _removed.length;
-
-  /** Returns true if the provided index was changed by this operation. */
-  bool indexChanged(key) {
-    // If key isn't an int, or before the index, then it wasn't changed.
-    if (key is! int || key < index) return false;
-
-    // If this was a shift operation, anything after index is changed.
-    if (addedCount != removedCount) return true;
-
-    // Otherwise, anything in the update range was changed.
-    return key < index + addedCount;
-  }
-
-  String toString() => '#<$runtimeType index: $index, '
-      'removed: $removed, addedCount: $addedCount>';
-}
-
-// Note: This function is *based* on the computation of the Levenshtein
-// "edit" distance. The one change is that "updates" are treated as two
-// edits - not one. With List splices, an update is really a delete
-// followed by an add. By retaining this, we optimize for "keeping" the
-// maximum array items in the original array. For example:
-//
-//   'xxxx123' -> '123yyyy'
-//
-// With 1-edit updates, the shortest path would be just to update all seven
-// characters. With 2-edit updates, we delete 4, leave 3, and add 4. This
-// leaves the substring '123' intact.
-List<List<int>> _calcEditDistances(List current, int currentStart,
-    int currentEnd, List old, int oldStart, int oldEnd) {
-  // "Deletion" columns
-  var rowCount = oldEnd - oldStart + 1;
-  var columnCount = currentEnd - currentStart + 1;
-  var distances = new List(rowCount);
-
-  // "Addition" rows. Initialize null column.
-  for (var i = 0; i < rowCount; i++) {
-    distances[i] = new List(columnCount);
-    distances[i][0] = i;
-  }
-
-  // Initialize null row
-  for (var j = 0; j < columnCount; j++) {
-    distances[0][j] = j;
-  }
-
-  for (var i = 1; i < rowCount; i++) {
-    for (var j = 1; j < columnCount; j++) {
-      if (identical(old[oldStart + i - 1], current[currentStart + j - 1])) {
-        distances[i][j] = distances[i - 1][j - 1];
-      } else {
-        var north = distances[i - 1][j] + 1;
-        var west = distances[i][j - 1] + 1;
-        distances[i][j] = math.min(north, west);
-      }
-    }
-  }
-
-  return distances;
-}
-
-const _EDIT_LEAVE = 0;
-const _EDIT_UPDATE = 1;
-const _EDIT_ADD = 2;
-const _EDIT_DELETE = 3;
-
-// This starts at the final weight, and walks "backward" by finding
-// the minimum previous weight recursively until the origin of the weight
-// matrix.
-List<int> _spliceOperationsFromEditDistances(List<List<int>> distances) {
-  var i = distances.length - 1;
-  var j = distances[0].length - 1;
-  var current = distances[i][j];
-  var edits = [];
-  while (i > 0 || j > 0) {
-    if (i == 0) {
-      edits.add(_EDIT_ADD);
-      j--;
-      continue;
-    }
-    if (j == 0) {
-      edits.add(_EDIT_DELETE);
-      i--;
-      continue;
-    }
-    var northWest = distances[i - 1][j - 1];
-    var west = distances[i - 1][j];
-    var north = distances[i][j - 1];
-
-    var min = math.min(math.min(west, north), northWest);
-
-    if (min == northWest) {
-      if (northWest == current) {
-        edits.add(_EDIT_LEAVE);
-      } else {
-        edits.add(_EDIT_UPDATE);
-        current = northWest;
-      }
-      i--;
-      j--;
-    } else if (min == west) {
-      edits.add(_EDIT_DELETE);
-      i--;
-      current = west;
-    } else {
-      edits.add(_EDIT_ADD);
-      j--;
-      current = north;
-    }
-  }
-
-  return edits.reversed.toList();
-}
-
-int _sharedPrefix(List arr1, List arr2, int searchLength) {
-  for (var i = 0; i < searchLength; i++) {
-    if (!identical(arr1[i], arr2[i])) {
-      return i;
-    }
-  }
-  return searchLength;
-}
-
-int _sharedSuffix(List arr1, List arr2, int searchLength) {
-  var index1 = arr1.length;
-  var index2 = arr2.length;
-  var count = 0;
-  while (count < searchLength && identical(arr1[--index1], arr2[--index2])) {
-    count++;
-  }
-  return count;
-}
-
-/**
- * Lacking individual splice mutation information, the minimal set of
- * splices can be synthesized given the previous state and final state of an
- * array. The basic approach is to calculate the edit distance matrix and
- * choose the shortest path through it.
- *
- * Complexity: O(l * p)
- *   l: The length of the current array
- *   p: The length of the old array
- */
-List<ListChangeDelta> calculateSplices(List current, List previous) =>
-    _calcSplices(current, 0, current.length, previous, 0, previous.length);
-
-List<ListChangeDelta> _calcSplices(List current, int currentStart,
-    int currentEnd, List old, int oldStart, int oldEnd) {
-
-  var prefixCount = 0;
-  var suffixCount = 0;
-
-  var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart);
-  if (currentStart == 0 && oldStart == 0) {
-    prefixCount = _sharedPrefix(current, old, minLength);
-  }
-
-  if (currentEnd == current.length && oldEnd == old.length) {
-    suffixCount = _sharedSuffix(current, old, minLength - prefixCount);
-  }
-
-  currentStart += prefixCount;
-  oldStart += prefixCount;
-  currentEnd -= suffixCount;
-  oldEnd -= suffixCount;
-
-  if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) {
-    return const [];
-  }
-
-  if (currentStart == currentEnd) {
-    var splice = new ListChangeDelta(currentStart);
-    while (oldStart < oldEnd) {
-      splice.removed.add(old[oldStart++]);
-    }
-
-    return [splice ];
-  } else if (oldStart == oldEnd)
-    return [new ListChangeDelta(currentStart,
-        addedCount: currentEnd - currentStart)];
-
-  var ops = _spliceOperationsFromEditDistances(
-      _calcEditDistances(current, currentStart, currentEnd, old, oldStart,
-          oldEnd));
-
-  ListChangeDelta splice = null;
-  var splices = <ListChangeDelta>[];
-  var index = currentStart;
-  var oldIndex = oldStart;
-  for (var i = 0; i < ops.length; i++) {
-    switch(ops[i]) {
-      case _EDIT_LEAVE:
-        if (splice != null) {
-          splices.add(splice);
-          splice = null;
-        }
-
-        index++;
-        oldIndex++;
-        break;
-      case _EDIT_UPDATE:
-        if (splice == null) splice = new ListChangeDelta(index);
-
-        splice._addedCount++;
-        index++;
-
-        splice.removed.add(old[oldIndex]);
-        oldIndex++;
-        break;
-      case _EDIT_ADD:
-        if (splice == null) splice = new ListChangeDelta(index);
-
-        splice._addedCount++;
-        index++;
-        break;
-      case _EDIT_DELETE:
-        if (splice == null) splice = new ListChangeDelta(index);
-
-        splice.removed.add(old[oldIndex]);
-        oldIndex++;
-        break;
-    }
-  }
-
-  if (splice != null) {
-    splices.add(splice);
-  }
-  return splices;
-}