lib/src/list_diff.dart

// Copyright (c) 2016, 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 observable.src.list_diff;

import 'dart:collection' show UnmodifiableListView;
import 'dart:math' as math;

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 /* TODO(tvolkert): remove */ 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, List 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 [ref] index was changed by this operation.
  bool indexChanged(int ref) {
    // If ref is before the index, then it wasn't changed.
    if (ref < 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 ref < 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
  int rowCount = oldEnd - oldStart + 1;
  int columnCount = currentEnd - currentStart + 1;
  List<List<int>> distances = new List<List<int>>(rowCount);

  // "Addition" rows. Initialize null column.
  for (int i = 0; i < rowCount; i++) {
    distances[i] = new List(columnCount);
    distances[i][0] = i;
  }

  // Initialize null row
  for (int j = 0; j < columnCount; j++) {
    distances[0][j] = j;
  }

  for (int i = 1; i < rowCount; i++) {
    for (int j = 1; j < columnCount; j++) {
      if (old[oldStart + i - 1] == current[currentStart + j - 1]) {
        distances[i][j] = distances[i - 1][j - 1];
      } else {
        int north = distances[i - 1][j] + 1;
        int west = distances[i][j - 1] + 1;
        distances[i][j] = math.min(north, west);
      }
    }
  }

  return distances;
}

const _kEditLeave = 0;
const _kEditUpdate = 1;
const _kEditAdd = 2;
const _kEditDelete = 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) {
  int i = distances.length - 1;
  int j = distances[0].length - 1;
  int current = distances[i][j];
  List<int> edits = <int>[];
  while (i > 0 || j > 0) {
    if (i == 0) {
      edits.add(_kEditAdd);
      j--;
      continue;
    }
    if (j == 0) {
      edits.add(_kEditDelete);
      i--;
      continue;
    }
    int northWest = distances[i - 1][j - 1];
    int west = distances[i - 1][j];
    int north = distances[i][j - 1];

    int min = math.min(math.min(west, north), northWest);

    if (min == northWest) {
      if (northWest == current) {
        edits.add(_kEditLeave);
      } else {
        edits.add(_kEditUpdate);
        current = northWest;
      }
      i--;
      j--;
    } else if (min == west) {
      edits.add(_kEditDelete);
      i--;
      current = west;
    } else {
      edits.add(_kEditAdd);
      j--;
      current = north;
    }
  }

  return edits.reversed.toList();
}

int _sharedPrefix(List arr1, List arr2, int searchLength) {
  for (int i = 0; i < searchLength; i++) {
    if (arr1[i] != arr2[i]) {
      return i;
    }
  }
  return searchLength;
}

int _sharedSuffix(List arr1, List arr2, int searchLength) {
  int index1 = arr1.length;
  int index2 = arr2.length;
  int 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) {
  int prefixCount = 0;
  int suffixCount = 0;

  int 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) {
    ListChangeRecord 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)
    ];
  }

  List<int> ops = _spliceOperationsFromEditDistances(_calcEditDistances(
      current, currentStart, currentEnd, old, oldStart, oldEnd));

  ListChangeRecord splice;
  List<ListChangeRecord> splices = <ListChangeRecord>[];
  int index = currentStart;
  int oldIndex = oldStart;
  for (int i = 0; i < ops.length; i++) {
    switch (ops[i]) {
      case _kEditLeave:
        if (splice != null) {
          splices.add(splice);
          splice = null;
        }

        index++;
        oldIndex++;
        break;
      case _kEditUpdate:
        if (splice == null) splice = new ListChangeRecord(current, index);

        splice._addedCount++;
        index++;

        splice._removed.add(old[oldIndex]);
        oldIndex++;
        break;
      case _kEditAdd:
        if (splice == null) splice = new ListChangeRecord(current, index);

        splice._addedCount++;
        index++;
        break;
      case _kEditDelete:
        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) {
  ListChangeRecord splice = new ListChangeRecord(record.object, record.index,
      removed: record._removed.toList(), addedCount: record.addedCount);

  bool inserted = false;
  int 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 (int i = 0; i < splices.length; i++) {
    final ListChangeRecord current = splices[i];
    current._index += insertionOffset;

    if (inserted) continue;

    int 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;
      int deleteCount =
          splice.removed.length + current.removed.length - intersectCount;

      if (splice.addedCount == 0 && deleteCount == 0) {
        // merged splice is a noop. discard.
        inserted = true;
      } else {
        List 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++;

      int 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) {
  List<ListChangeRecord> splices = [];
  for (ListChangeRecord 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<Object> list, List<ListChangeRecord> records) {
  if (records.length <= 1) return records;

  List<ListChangeRecord> splices = <ListChangeRecord>[];
  for (ListChangeRecord 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;
}