calculateDiff<Item> function
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
tonewList
, 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();
}