lib/src/differs/list_differ.dart - observable - Git at Google

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