calculateDiff<Item> function

Future<List<Operation<Item>>> calculateDiff<Item>(List<Item> oldList, List<Item> newList, bool areEqual(Item a, Item b))

Calculates the difference between two lists.

This algorithm works by filling out a table with the two lists at the axes, where a cell at position (x,y) represents the number of operations needed to get from the first x items of the first list to the first y items of the second one.

For example, let's say, the old list is [a, b] and the new one is [a, c]. The following table is created:

| a b --+------ | 0 1 2 a | 1 0 1 c | 2 1 2

As you see, the first row and column are just a sequence of numbers. That's because for each new character, it takes one more deletion to get to the empty list and one more insertion to get from the empty list to the new one.

All the other cells are filled out using these rules:

• If the item at index x in the old list and the item at index y in the new list are equal, no operation is needed. That means, the value of the cell left above the current one can just be copied. (If it takes N operations to get from oldList to newList, it takes the same N operations to get from [...oldList, item] to [...newList, item]).
• Otherwise, we can either insert an item coming from the cell above or delete an item coming from the cell on the left. That translates in aking either the cell above or on the left and adding one operation. The smaller one of those both should be chosen for the shortest possible sequence of operations.

Implementation details:

• For storage efficiency, only the active row of the table is actually saved. Then, the new row is calculated and the original row is replaced with the new one.
• Instead of storing just the number of moves, we store the _Sequence of operations so that we can later retrace the path we took.

Implementation

Future<List<Operation<Item>>> calculateDiff<Item>(
  List<Item> oldList,
  List<Item> newList,
  bool Function(Item a, Item b) areEqual,
) async {
  var row = _getInitialRow(oldList);

  for (var y = 0; y < newList.length; y++) {
    final nextRow = <_Sequence<Item>>[];

    for (var x = 0; x <= oldList.length; x++) {
      if (x == 0) {
        nextRow.add(_Sequence.insert(row[0], newList[y]));
      } else if (await _doItemsMatch(newList[y], oldList[x - 1], areEqual)) {
        nextRow.add(_Sequence.unchanged(row[x - 1]));
      } else if (row[x].isShorterThan(nextRow[x - 1])) {
        nextRow.add(_Sequence.insert(row[x], newList[y]));
      } else {
        nextRow.add(_Sequence.delete(nextRow[x - 1], oldList[x - 1]));
      }
    }

    row = nextRow;
  }

  return row.last.toOperations();
}