// 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.

part of observable.src.differs;

/// Determines differences between two lists, returning [ListChangeRecord]s.
///
/// While [ListChangeRecord] has more information and can be replayed they carry
/// a more significant cost to calculate and create and should only be used when
/// the details in the record will actually be used.
///
/// See also [EqualityDiffer] for a simpler comparison.
class ListDiffer<E> implements Differ<List<E>> {
  final Equality<E> _equality;

  const ListDiffer([this._equality = const DefaultEquality()]);

  @override
  List<ListChangeRecord<E>> diff(List<E> e1, List<E> e2) {
    return _calcSplices<E>(
      e2,
      _equality,
      0,
      e2.length,
      e1,
      0,
      e1.length,
    );
  }
}

enum _Edit {
  leave,
  update,
  add,
  delete,
}

// 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>> _calcEditDistance<E>(
  List<E> current,
  int currentStart,
  int currentEnd,
  List<E> old,
  int oldStart,
  int oldEnd,
) {
  // 'Deletion' columns.
  final rowCount = oldEnd - oldStart + 1;
  final columnCount = currentEnd - currentStart + 1;
  final distances = new List<List<int>>(rowCount);

  // 'Addition' rows. Initialize null column.
  for (var i = 0; i < rowCount; i++) {
    distances[i] = new List<int>(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 {
        final north = distances[i - 1][j] + 1;
        final west = distances[i][j - 1] + 1;
        distances[i][j] = math.min(north, west);
      }
    }
  }

  return distances;
}

// This starts at the final weight, and walks "backward" by finding
// the minimum previous weight recursively until the origin of the weight
// matrix.
Iterable<_Edit> _spliceOperationsFromEditDistances(List<List<int>> distances) {
  var i = distances.length - 1;
  var j = distances[0].length - 1;
  var current = distances[i][j];
  final edits = <_Edit>[];
  while (i > 0 || j > 0) {
    if (i == 0) {
      edits.add(_Edit.add);
      j--;
      continue;
    }
    if (j == 0) {
      edits.add(_Edit.delete);
      i--;
      continue;
    }
    final northWest = distances[i - 1][j - 1];
    final west = distances[i - 1][j];
    final north = distances[i][j - 1];

    final 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;
}

int _sharedPrefix<E>(
  Equality<E> equality,
  List<E> e1,
  List<E> e2,
  int searchLength,
) {
  for (var i = 0; i < searchLength; i++) {
    if (!equality.equals(e1[i], e2[i])) {
      return i;
    }
  }
  return searchLength;
}

int _sharedSuffix<E>(
  Equality<E> equality,
  List<E> e1,
  List<E> e2,
  int searchLength,
) {
  var index1 = e1.length;
  var index2 = e2.length;
  var count = 0;
  while (count < searchLength && equality.equals(e1[--index1], e2[--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<E>> _calcSplices<E>(
  List<E> current,
  Equality<E> equality,
  int currentStart,
  int currentEnd,
  List<E> old,
  int oldStart,
  int oldEnd,
) {
  var prefixCount = 0;
  var suffixCount = 0;
  final minLength = math.min(currentEnd - currentStart, oldEnd - oldStart);
  if (currentStart == 0 && oldStart == 0) {
    prefixCount = _sharedPrefix(
      equality,
      current,
      old,
      minLength,
    );
  }
  if (currentEnd == current.length && oldEnd == old.length) {
    suffixCount = _sharedSuffix(
      equality,
      current,
      old,
      minLength - prefixCount,
    );
  }

  currentStart += prefixCount;
  oldStart += prefixCount;
  currentEnd -= suffixCount;
  oldEnd -= suffixCount;

  if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) {
    return ListChangeRecord.NONE;
  }

  if (currentStart == currentEnd) {
    final spliceRemoved = old.sublist(oldStart, oldEnd);
    return [
      new ListChangeRecord<E>.remove(
        current,
        currentStart,
        spliceRemoved,
      ),
    ];
  }
  if (oldStart == oldEnd) {
    return [
      new ListChangeRecord<E>.add(
        current,
        currentStart,
        currentEnd - currentStart,
      ),
    ];
  }

  final ops = _spliceOperationsFromEditDistances(
    _calcEditDistance(
      current,
      currentStart,
      currentEnd,
      old,
      oldStart,
      oldEnd,
    ),
  );

  var spliceIndex = -1;
  var spliceRemovals = <E>[];
  var spliceAddedCount = 0;

  bool hasSplice() => spliceIndex != -1;
  void resetSplice() {
    spliceIndex = -1;
    spliceRemovals = <E>[];
    spliceAddedCount = 0;
  }

  var splices = <ListChangeRecord<E>>[];

  var index = currentStart;
  var oldIndex = oldStart;
  for (final op in ops) {
    switch (op) {
      case _Edit.leave:
        if (hasSplice()) {
          splices.add(new ListChangeRecord<E>(
            current,
            spliceIndex,
            removed: spliceRemovals,
            addedCount: spliceAddedCount,
          ));
          resetSplice();
        }
        index++;
        oldIndex++;
        break;
      case _Edit.update:
        if (!hasSplice()) {
          spliceIndex = index;
        }
        spliceAddedCount++;
        index++;
        spliceRemovals.add(old[oldIndex]);
        oldIndex++;
        break;
      case _Edit.add:
        if (!hasSplice()) {
          spliceIndex = index;
        }
        spliceAddedCount++;
        index++;
        break;
      case _Edit.delete:
        if (!hasSplice()) {
          spliceIndex = index;
        }
        spliceRemovals.add(old[oldIndex]);
        oldIndex++;
        break;
    }
  }
  if (hasSplice()) {
    splices.add(new ListChangeRecord<E>(
      current,
      spliceIndex,
      removed: spliceRemovals,
      addedCount: spliceAddedCount,
    ));
  }
  assert(() {
    splices = new List<ListChangeRecord<E>>.unmodifiable(splices);
    return true;
  });
  return splices;
}

int _intersect(int start1, int end1, int start2, int end2) {
  return math.min(end1, end2) - math.max(start1, start2);
}

void _mergeSplices<E>(
  List<ListChangeRecord<E>> splices,
  ListChangeRecord<E> record,
) {
  var spliceIndex = record.index;
  var spliceRemoved = record.removed;
  var spliceAdded = 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++) {
    var current = splices[i];
    current = splices[i] = new ListChangeRecord<E>(
      current.object,
      current.index + insertionOffset,
      removed: current.removed,
      addedCount: current.addedCount,
    );

    if (inserted) continue;

    var intersectCount = _intersect(
      spliceIndex,
      spliceIndex + spliceRemoved.length,
      current.index,
      current.index + current.addedCount,
    );
    if (intersectCount >= 0) {
      // Merge the two splices.
      splices.removeAt(i);
      i--;

      insertionOffset -= current.addedCount - current.removed.length;
      spliceAdded += current.addedCount - intersectCount;

      final deleteCount =
          spliceRemoved.length + current.removed.length - intersectCount;
      if (spliceAdded == 0 && deleteCount == 0) {
        // Merged splice is a no-op, discard.
        inserted = true;
      } else {
        final removed = current.removed.toList();
        if (spliceIndex < current.index) {
          // Some prefix of splice.removed is prepended to current.removed.
          removed.insertAll(
            0,
            spliceRemoved.getRange(0, current.index - spliceIndex),
          );
        }
        if (spliceIndex + spliceRemoved.length >
            current.index + current.addedCount) {
          // Some suffix of splice.removed is appended to current.removed.
          removed.addAll(spliceRemoved.getRange(
            current.index + current.addedCount - spliceIndex,
            spliceRemoved.length,
          ));
        }
        spliceRemoved = removed;
        if (current.index < spliceIndex) {
          spliceIndex = current.index;
        }
      }
    } else if (spliceIndex < current.index) {
      // Insert splice here.
      inserted = true;
      splices.insert(
        i,
        new ListChangeRecord<E>(
          record.object,
          spliceIndex,
          removed: spliceRemoved,
          addedCount: spliceAdded,
        ),
      );
      i++;
      final offset = spliceAdded - spliceRemoved.length;
      current = splices[i] = new ListChangeRecord<E>(
        current.object,
        current.index + offset,
        removed: current.removed,
        addedCount: current.addedCount,
      );
      insertionOffset += offset;
    }
  }
  if (!inserted) {
    splices.add(new ListChangeRecord<E>(
      record.object,
      spliceIndex,
      removed: spliceRemoved,
      addedCount: spliceAdded,
    ));
  }
}

List<ListChangeRecord<E>> _createInitialSplices<E>(
  List<E> list,
  List<ListChangeRecord<E>> records,
) {
  final splices = <ListChangeRecord<E>>[];
  for (var i = 0; i < records.length; i++) {
    _mergeSplices(splices, records[i]);
  }
  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<E>> projectListSplices<E>(
  List<E> list,
  List<ListChangeRecord<E>> records, [
  Equality<E> equality = const DefaultEquality(),
]) {
  if (records.length <= 1) return records;
  final splices = <ListChangeRecord<E>>[];
  final initialSplices = _createInitialSplices(list, records);
  for (final splice in initialSplices) {
    if (splice.addedCount == 1 && splice.removed.length == 1) {
      if (splice.removed[0] != list[splice.index]) {
        splices.add(splice);
      }
      continue;
    }
    splices.addAll(
      _calcSplices(
        list,
        equality,
        splice.index,
        splice.index + splice.addedCount,
        splice.removed,
        0,
        splice.removed.length,
      ),
    );
  }
  return splices;
}