getUpdatesWithData - change return type from Iterable to List

[Robbendebiene]

Thanks for this really handy library!

I wonder if there is any reason getUpdatesWithData returns the changes in reverse order? At least I didn't expect that maybe you could add a little hint in the documentation.

Since I need the values in their "original" order I'm calling diffResult.getUpdatesWithData().toList().reversed. However I've noticed that internally you are already constructing a List so I wonder why you decided to return an Iterable instead. I guess returning an Iterable would make sense if the construction was lazy but in this case returning the already existing List seems more appropriate.

[knaeckeKami]

Thanks for your feedback!

I wonder if there is any reason getUpdatesWithData returns the changes in reverse order? At least I didn't expect that maybe you could add a little hint in the documentation.

What do you mean with reversed order? I know that the order of operations can look weird, but the algorithm just calculates the shortest amount of edit-operations to transform one list into another.

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:

List: [], Insert item "a" at position 0, result ["a"] List: ["a"], Insert item "b" at position 1, result ["a", "b"] List: ["a", "b"], Insert item "c" at position 2, result ["a", "b", "c"] However, this is another way to do that:

List: [], Insert item "c" at position 0, result ["c"] List: ["c"], Insert item "b" at position 0, result ["b", "c"] List: ["b", "c"], Insert item "a" at position 0, result ["a", "b", "c"]

Both ways have the same amount of operations, so both are valid. The algorithm just happens to pick the second one. I don't know of a way to make it pick the more "human" way to construct the result.

But you should be careful when you call reverse() at the result because the positions will be wrong then.

Or if the positions are still correct, then I have a terrible bug and I would love to see an example to reproduce that.

Since I need the values in their "original" order I'm calling diffResult.getUpdatesWithData().toList().reversed. However I've noticed that internally you are already constructing a List so I wonder why you decided to return an Iterable instead. I guess returning an Iterable would make sense if the construction was lazy but in this case returning the already existing List seems more appropriate.

I decided to return an Iterable in order to be free to make optimizations in the future (like using another List implementation). But yeah, that's unlikely to happen, so I will just tighten the return type to List in a Future update.

[Robbendebiene]

What do you mean with reversed order? I know that the order of operations can look weird, but the algorithm just calculates the shortest amount of edit-operations to transform one list into another.

Good point I should have explained my self better. When I remove all items from a list the returned Iterable starts at the highest index instead of zero.

final diffResult = calculateListDiff<String>(
  ["a", "b", "c", "d"], [],
  detectMoves: false
);
for (final update in diffResult.getUpdatesWithData()) {
  update.when(
    insert: (index, data) {},
    remove: (index, data) {
      print(index);
    },
    change: (index, oldData, newData) {},
    move: (from, to, data) {},
  );
}

Outputs: 3 2 1 0 while I expected 0 1 2 3

From a first glance changing line https://github.com/knaeckeKami/diffutil.dart/blob/master/lib/src/diffutil_impl.dart#L331 to start iterating from 0 should still work. I know that iterating a List in reverse is save when it comes to removing elements from the list, but in this case it seems like you aren't removing any elements. However my understanding of your library is very limited so I might as well overlook a lot of things :)

But you should be careful when you call reverse() at the result because the positions will be wrong then.

True, in my particular case it should be fine though.

[knaeckeKami]

Outputs: 3 2 1 0 while I expected 0 1 2 3

Actually, 0 1 2 3 would be a wrong result. Note that the result is a list of operations that would turn the old list into the new one, when applied in the returned order. The result is not order-independent.

An alternative, equally valid result would be: 0 0 0 0.

Here's why 0 1 2 3 would not work:

List: [a,b,c,d], remove at position 0, result [b,c,d] List: [b,c,d], remove at position 1, result [b,d] List: [b,d] remove at position 2, crash of an index out of bounds exception

I don't know what your use case is, but if you just need the removed Items from the old list, you might get there for example with the help of https://api.flutter.dev/flutter/dart-core/Set/difference.html

Regarding the order of the result: I am not sure if changing the iteration order would be safe. I would need to take a deep dive into https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ again to understand it ;)

[Robbendebiene]

@knaeckeKami Thanks for your clarification, this perspective actually makes sense!

I don't know what your use case is, but if you just need the removed Items from the old list, you might get there for example with the help of https://api.flutter.dev/flutter/dart-core/Set/difference.html

I was using this approach before, but since I needed to detect whether elements were added or removed it felt not very optimized to use multiple of these boolean operations.

Feel free to close the issue :)

[knaeckeKami]

ok, hope I could at least help a bit :)