Different result with batched parameter when one list is empty

[pawelsa]

When performing diff between two lists where the compared list is empty results with different results depending on the batched parameter. To simplify the problem I've created a sample code so that it can be easily tested.

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

void main() {

  test("empty -> [...6 items] should have 6 inserts operations with consecutive positions and count 1 when not batched", () {
    final apiList = [
      SimpleClass("1", "Content 1"),
      SimpleClass("2", "Content 2"),
      SimpleClass("3", "Content 3"),
      SimpleClass("4", "Content 4"),
      SimpleClass("5", "Content 5"),
      SimpleClass("6", "Content 6"),
    ];
    final dbList = <SimpleClass>[];

    final diff = calculateDiff(
      SimpleClassDiffDelegate(dbList, apiList),
      detectMoves: true,
    ).getUpdates(batch: false).toList();
    expect(diff, const [
      Insert(position: 0, count: 1),
      Insert(position: 1, count: 1),
      Insert(position: 2, count: 1),
      Insert(position: 3, count: 1),
      Insert(position: 4, count: 1),
      Insert(position: 5, count: 1),
    ]);
  });

  test("empty -> [...6 items] should have 1 insert operation with count 6 on position 0 when batched", () {
    final apiList = [
      SimpleClass("1", "Content 1"),
      SimpleClass("2", "Content 2"),
      SimpleClass("3", "Content 3"),
      SimpleClass("4", "Content 4"),
      SimpleClass("5", "Content 5"),
      SimpleClass("6", "Content 6"),
    ];
    final dbList = <SimpleClass>[];

    final diff = calculateDiff(
      SimpleClassDiffDelegate(dbList, apiList),
      detectMoves: true,
    ).getUpdates(batch: true).toList();
    expect(diff, const [
      Insert(position: 0, count: 6),
    ]);
  });

  test("[...6 items] -> empty list should have 6 remove operations with 6 consecutive positions and count 1 when not batched", () {
    final apiList = <SimpleClass>[];
    final dbList = [
      SimpleClass("1", "Content 1"),
      SimpleClass("2", "Content 2"),
      SimpleClass("3", "Content 3"),
      SimpleClass("4", "Content 4"),
      SimpleClass("5", "Content 5"),
      SimpleClass("6", "Content 6"),
    ];

    final diff = calculateDiff(
      SimpleClassDiffDelegate(dbList, apiList),
      detectMoves: true,
    ).getUpdates(batch: false).toList();
    expect(diff, const [
      Remove(position: 5, count: 1),
      Remove(position: 4, count: 1),
      Remove(position: 3, count: 1),
      Remove(position: 2, count: 1),
      Remove(position: 1, count: 1),
      Remove(position: 0, count: 1),
    ]);
  });

  test("[...6 items] -> empty list should have 1 remove operation with position 0 and count 6 when batched", () {
    final apiList = <SimpleClass>[];
    final dbList = [
      SimpleClass("1", "Content 1"),
      SimpleClass("2", "Content 2"),
      SimpleClass("3", "Content 3"),
      SimpleClass("4", "Content 4"),
      SimpleClass("5", "Content 5"),
      SimpleClass("6", "Content 6"),
    ];

    final diff = calculateDiff(
      SimpleClassDiffDelegate(dbList, apiList),
      detectMoves: true,
    ).getUpdates(batch: true).toList();
    expect(diff, const [
      Remove(position: 0, count: 6),
    ]);
  });
}

class SimpleClass {
  final String id;
  final String content;

  SimpleClass(this.id, this.content);

  @override
  bool operator ==(Object other) =>
      identical(this, other) ||
      other is SimpleClass &&
          runtimeType == other.runtimeType &&
          id == other.id &&
          content == other.content;

  @override
  int get hashCode => id.hashCode ^ content.hashCode;
}

class SimpleClassDiffDelegate implements DiffDelegate {
  final List<SimpleClass> _oldList;
  final List<SimpleClass> _newList;

  SimpleClassDiffDelegate(this._oldList, this._newList);

  @override
  bool areContentsTheSame(int oldItemPosition, int newItemPosition) => _oldList[oldItemPosition] == _newList[newItemPosition];

  @override
  bool areItemsTheSame(int oldItemPosition, int newItemPosition) => _oldList[oldItemPosition].id == _newList[newItemPosition].id;

  @override
  Object getChangePayload(int oldItemPosition, int newItemPosition) => _newList[newItemPosition];

  @override
  int getNewListSize() => _newList.length;

  @override
  int getOldListSize() => _oldList.length;
}

In the first test the result is:

Expected: [
            Insert:Insert{position: 0, count: 1},
            Insert:Insert{position: 1, count: 1},
            Insert:Insert{position: 2, count: 1},
            Insert:Insert{position: 3, count: 1},
            Insert:Insert{position: 4, count: 1},
            Insert:Insert{position: 5, count: 1}
          ]
  Actual: [
            Insert:Insert{position: 0, count: 1},
            Insert:Insert{position: 0, count: 1},
            Insert:Insert{position: 0, count: 1},
            Insert:Insert{position: 0, count: 1},
            Insert:Insert{position: 0, count: 1},
            Insert:Insert{position: 0, count: 1}
          ]
   Which: at location [1] is Insert:<Insert{position: 0, count: 1}> instead of Insert:<Insert{position: 1, count: 1}>

I think that we should obtain the result as in the test case, so that we can easily create a list of all items added.

[knaeckeKami]

Hi, thanks for the detailed feedback!

Unfortunately, this is not easy to implement.
The algorithm returns a list of operations to transform one list to another, and this list is correct.
It's just that there are many ways to do that and the calculated list of operations might not be how a human would do that.

For example, if you have a an empty list [] and want to transform it to a list of ["a","b","c"], this is probably what you would expect:

1. List: [], Insert item "a" at position 0, result ["a"]
2. List: ["a"], Insert item "b" at position 1, result ["a", "b"]
3. List: ["a", "b"], Insert item "c" at position 2, result ["a", "b", "c"]

However, this is another way to do that:

1. List: [], Insert item "c" at position 0, result ["c"]
2. List: ["c"], Insert item "b" at position 0, result ["b", "c"]
3. List: ["b", "c"], Insert item "a" at position 0, result ["a", "b", "c"]

For removals, it's the same. Deleting the item at position 0 6 times is the same as deleting the item at position 5,4,3,2,1,0.

But maybe there's another way to get what you want, check out my branch "data_inserts".
Is has a proof of concept feature that adds the data that was added to each Insert() object. I could also do that with Removals.
It's implemented in a hacky way and only works with the calculateListDiff function at the moment, not with the calculateDiff that you used because of that.

But if this is what you want, I can implement it cleanly and make it work also with removals.

This test passes with in this branch.

test("empty -> [...6 items] should have 6 inserts operations with consecutive positions and count 1 when not batched", () {
    final apiList = [
      SimpleClass("1", "Content 1"),
      SimpleClass("2", "Content 2"),
      SimpleClass("3", "Content 3"),
      SimpleClass("4", "Content 4"),
      SimpleClass("5", "Content 5"),
      SimpleClass("6", "Content 6"),
    ];
    final dbList = <SimpleClass>[];

    final diff = calculateListDiff(
      dbList, apiList,
      detectMoves: true,
    ).getUpdates(batch: false).toList();
    expect(diff,  [
      Insert(position: 0, count: 1, data: SimpleClass("6", "Content 6")),
      Insert(position: 0, count: 1, data: SimpleClass("5", "Content 5")),
      Insert(position: 0, count: 1, data: SimpleClass("4", "Content 4")),
      Insert(position: 0, count: 1, data: SimpleClass("3", "Content 3")),
      Insert(position: 0, count: 1, data: SimpleClass("2", "Content 2")),
      Insert(position: 0, count: 1, data: SimpleClass("1", "Content 1")),
    ]);
  });

}


class SimpleClass {
  final String id;
  final String content;

  SimpleClass(this.id, this.content);

  @override
  bool operator ==(Object other) =>
      identical(this, other) ||
          other is SimpleClass &&
              runtimeType == other.runtimeType &&
              id == other.id &&
              content == other.content;

  @override
  int get hashCode => id.hashCode ^ content.hashCode;

  @override
  String toString() {
    return 'SimpleClass{id: $id, content: $content}';
  }
}

[knaeckeKami]

I implemented this in a cleaner way and merged it on master.
Please check it out.

On how to use it, see https://github.com/knaeckeKami/diffutil.dart#updates-with-data

[pawelsa]

Sorry that I have not tested this earlier. Now it is working as I wanted to. All the tests that I provided in this issue and #8 are passing now. One thing you could change is to expose IndexableItemDiffDelegate, so making totally custom delegate would be easier.

[knaeckeKami]

Ah yeah, I forgot to export that class. I fixed it on master.
I will publish a new release soon.