Add observatory_pub_packages snapshot to third_party

observatory_pub_packages/observe/src/list_diff.dart

Index: observatory_pub_packages/observe/src/list_diff.dart
===================================================================
--- observatory_pub_packages/observe/src/list_diff.dart	(revision 0)
+++ observatory_pub_packages/observe/src/list_diff.dart	(working copy)
@@ -0,0 +1,392 @@
+// 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 observe.src.list_diff;
+
+import 'dart:math' as math;
+import 'dart:collection' show UnmodifiableListView;
+import 'change_record.dart' show ChangeRecord;
+
+/// 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.
+class ListChangeRecord extends ChangeRecord {
+  /// The list that changed.
+  final List object;
+
+  /// The index of the change.
+  int get index => _index;
+
+  /// The items removed, if any. Otherwise this will be an empty list.
+  List get removed => _unmodifiableRemoved;
+  UnmodifiableListView _unmodifiableRemoved;
+
+  /// Mutable version of [removed], used during the algorithms as they are
+  /// constructing the object.
+  List _removed;
+
+  /// The number of items added.
+  int get addedCount => _addedCount;
+
+  // Note: conceptually these are 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 _index, _addedCount;
+
+  ListChangeRecord._(this.object, this._index, removed, this._addedCount)
+      : _removed = removed,
+        _unmodifiableRemoved = new UnmodifiableListView(removed);
+
+  factory ListChangeRecord(List object, int index,
+      {List removed, int addedCount}) {
+
+    if (removed == null) removed = [];
+    if (addedCount == null) addedCount = 0;
+    return new ListChangeRecord._(object, index, removed, addedCount);
+  }
+
+  /// 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 != removed.length) return true;
+
+    // Otherwise, anything in the update range was changed.
+    return key < index + addedCount;
+  }
+
+  String toString() => '#<ListChangeRecord 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 (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 (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 && 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<ListChangeRecord> 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 ListChangeRecord(current, currentStart);
+    while (oldStart < oldEnd) {
+      splice._removed.add(old[oldStart++]);
+    }
+
+    return [splice ];
+  } else if (oldStart == oldEnd)
+    return [new ListChangeRecord(current, currentStart,
+        addedCount: currentEnd - currentStart)];
+
+  var ops = _spliceOperationsFromEditDistances(
+      _calcEditDistances(current, currentStart, currentEnd, old, oldStart,
+          oldEnd));
+
+  ListChangeRecord splice = null;
+  var splices = <ListChangeRecord>[];
+  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 ListChangeRecord(current, index);
+
+        splice._addedCount++;
+        index++;
+
+        splice._removed.add(old[oldIndex]);
+        oldIndex++;
+        break;
+      case _EDIT_ADD:
+        if (splice == null) splice = new ListChangeRecord(current, index);
+
+        splice._addedCount++;
+        index++;
+        break;
+      case _EDIT_DELETE:
+        if (splice == null) splice = new ListChangeRecord(current, index);
+
+        splice._removed.add(old[oldIndex]);
+        oldIndex++;
+        break;
+    }
+  }
+
+  if (splice != null) splices.add(splice);
+  return splices;
+}
+
+int _intersect(int start1, int end1, int start2, int end2) =>
+    math.min(end1, end2) - math.max(start1, start2);
+
+void _mergeSplice(List<ListChangeRecord> splices, ListChangeRecord record) {
+  var splice = new ListChangeRecord(record.object, record.index,
+      removed: record._removed.toList(), addedCount: record.addedCount);
+
+  var inserted = false;
+  var insertionOffset = 0;
+
+  // I think the way this works is:
+  // - the loop finds where the merge should happen
+  // - it applies the merge in a particular splice
+  // - then continues and updates the subsequent splices with any offset diff.
+  for (var i = 0; i < splices.length; i++) {
+    final current = splices[i];
+    current._index += insertionOffset;
+
+    if (inserted) continue;
+
+    var intersectCount = _intersect(
+        splice.index, splice.index + splice.removed.length,
+        current.index, current.index + current.addedCount);
+
+    if (intersectCount >= 0) {
+      // Merge the two splices
+
+      splices.removeAt(i);
+      i--;
+
+      insertionOffset -= current.addedCount - current.removed.length;
+
+      splice._addedCount += current.addedCount - intersectCount;
+      var deleteCount = splice.removed.length +
+                        current.removed.length - intersectCount;
+
+      if (splice.addedCount == 0 && deleteCount == 0) {
+        // merged splice is a noop. discard.
+        inserted = true;
+      } else {
+        var removed = current._removed;
+
+        if (splice.index < current.index) {
+          // some prefix of splice.removed is prepended to current.removed.
+          removed.insertAll(0,
+              splice.removed.getRange(0, current.index - splice.index));
+        }
+
+        if (splice.index + splice.removed.length >
+            current.index + current.addedCount) {
+          // some suffix of splice.removed is appended to current.removed.
+          removed.addAll(splice.removed.getRange(
+              current.index + current.addedCount - splice.index,
+              splice.removed.length));
+        }
+
+        splice._removed = removed;
+        splice._unmodifiableRemoved = current._unmodifiableRemoved;
+        if (current.index < splice.index) {
+          splice._index = current.index;
+        }
+      }
+    } else if (splice.index < current.index) {
+      // Insert splice here.
+
+      inserted = true;
+
+      splices.insert(i, splice);
+      i++;
+
+      var offset = splice.addedCount - splice.removed.length;
+      current._index += offset;
+      insertionOffset += offset;
+    }
+  }
+
+  if (!inserted) splices.add(splice);
+}
+
+List<ListChangeRecord> _createInitialSplices(List<Object> list,
+    List<ListChangeRecord> records) {
+
+  var splices = <ListChangeRecord>[];
+  for (var record in records) {
+    _mergeSplice(splices, record);
+  }
+  return splices;
+}
+
+/// 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.
+List<ListChangeRecord> projectListSplices(List list,
+    List<ListChangeRecord> records) {
+  if (records.length <= 1) return records;
+
+  var splices = [];
+  for (var splice in _createInitialSplices(list, records)) {
+    if (splice.addedCount == 1 && splice.removed.length == 1) {
+      if (splice.removed[0] != list[splice.index]) splices.add(splice);
+      continue;
+    }
+
+    splices.addAll(calcSplices(list, splice.index,
+        splice.index + splice.addedCount, splice._removed, 0,
+        splice.removed.length));
+  }
+
+  return splices;
+}