observe/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 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;
}