Move detection doesn't work as I expected

[MHQB]

The first test case in the following snippet works correctly but not the second one. Am I doing something wrong?

import 'package:collection/collection.dart';
import 'package:diffutil_dart/diffutil.dart';

main() {
  final firstCaseInit = [1, 2, 3];
  final firstCaseExpected = [3, 2, 1];

  final secondCaseInit = [1, 2, 3, 4, 5, 6];
  final secondCaseExpected = [1, 4, 2, 5, 6, 3];

  final firstCaseDiffs =
      calculateListDiff(firstCaseInit, firstCaseExpected, detectMoves: true)
          .getUpdatesWithData();
  print(firstCaseDiffs); 
  // prints [Move{from: 1, to: 2, data: 2}, Move{from: 0, to: 2, data: 1}]
  // this is good

  final secondCaseDiffs =
      calculateListDiff(secondCaseInit, secondCaseExpected, detectMoves: true)
          .getUpdatesWithData();
  print(secondCaseDiffs);
  // prints [Move{from: 2, to: 5, data: 3}, Move{from: 1, to: 3, data: 2}]
  // this doesn't make sense

  final firstCaseResult = applyDiffs(firstCaseInit, firstCaseDiffs);
  final secondCaseResult = applyDiffs(secondCaseInit, secondCaseDiffs);

  print(firstCaseResult.equals(firstCaseExpected)); // prints true
  print(secondCaseResult.equals(secondCaseExpected)); // prints false, the result is [1 ,4 ,5 ,2 ,6 ,3]
}

List<T> applyDiffs<T>(List<T> init, Iterable<DataDiffUpdate<T>> diffs) =>
    diffs.fold(
        init,
        (state, diff) => switch (diff) {
              DataInsert(:final position, :final data) => state.toList()
                ..insert(position, data),
              DataRemove(:final position) => state.toList()..removeAt(position),
              DataMove(:final from, :final to, :final data) => state.toList()
                ..removeAt(from)
                ..insert(to, data),
              DataChange(:final position, :final newData) => state.toList()
                ..replaceRange(position, position + 1, [newData]),
            });

[MHQB]

i'm on the master branch btw, since i encountered the endless loop issue in 4.0.0.

[knaeckeKami]

thanks! you can try out the potential fix in #22

[MHQB]

That solved the issue, thanks. btw the following snippet suggests a property-based testing method that can generate a large number of random list of ints to make sure that the end result of the diff algorithm is correct. It could be useful for you to add some test units like this:

import 'package:collection/collection.dart';
import 'package:diffutil_dart/diffutil.dart';
import 'package:fpdart/fpdart.dart';

main() {
  List<int> randomIntList(int maxLength) => List.generate(
      randomInt(0, maxLength).run(), (_) => randomInt(0, 10000).run());

  ({List<int> init, List<int> expected}) randomIntListPair() =>
      (init: randomIntList(100), expected: randomIntList(200));

  final tenThousandTestCases = List.generate(10000, (_) => randomIntListPair());

  // ensuring property: b.equals(applyDiffs(a, diff(a, b)))
  final result = tenThousandTestCases
      .map((t) => t.expected.equals(applyDiffs(
            t.init,
            calculateListDiff(t.init, t.expected, detectMoves: true)
                .getUpdatesWithData(),
          )))
      .fold(
          (success: 0, failure: 0),
          (state, testUnit) => switch (testUnit) {
                true => (success: state.success + 1, failure: state.failure),
                false => (success: state.success, failure: state.failure + 1),
              });

  print(result); // prints (failure: 0, success: 10000), it's all good now :)
}
   applyDiffs(...)...

[knaeckeKami]

Thanks! I'll add something like that when I have time!

I published 4.0.1 with the fix from #22