Insertion order with getUpdatesWithData

[narcodico]

I'm using you library with an animated list and I'm also aiming to animate the initial items rendering.

I noticed that when using getUpdatesWithData and comparing an initial empty list with some incoming data, e.g.: [] with [Model1(), Model2()], the insertion order will be: Model2 at 0, Model1 at 0.
This is obviously bad in terms of UI, since the logic way of seeing items appearing on the screen would start with first and end with the last one.

What's your take on this and have you planned on addressing this @knaeckeKami ?

[knaeckeKami]

I understand your problem, unfortunately, I don't have a solution as of yet.

You could maybe do a post-processing stuff on the Iterable<DataDiffUpdate> to reorder the result while maintaining the correct positions (adjusted for the reordering)?

[narcodico]

That's exactly what I currently do, but I feel this package would be even more valuable than already is if it would handle this internally.

[knaeckeKami]

Yes. I don't know how to define the "best" update order for any list diff, though.

[narcodico]

I feel there's no such thing as best but rather useful.

[knaeckeKami]

Yes, I also don't know how to define the usefulness of the diff result.
Can you show me the algorithm to reorder the result to make it work for you?

[narcodico]

final currentItemsCount = oldItems.length;
        _changes = List<diffutil.DataInsert<Item>>.from(changes)
            .reversed
            .mapIndexed((index, change) => diffutil.DataInsert<Item>(
                  position: index + currentItemsCount,
                  data: change.data,
                ));

In my particular case I do this only when I have multiple inserts that I need to handle, for obvious reasons(order of UI inserts).
changes are the ones computed by your diffutil. oldItems are used with calculateDiff.
So with this approach I get initial inserts with order of 0 1 2...
Say we already have 10 items in the list, then the insertion would look like 10 11 12...

I feel this works well when there are multiple consecutive inserts. This would get a bit more complex when dealing with deletes too.

[knaeckeKami]

Thanks. It might be possible to get your expected insertion order by tweaking the iteration order of the algorithm, especially reversing the iteration order of these loop:
https://github.com/knaeckeKami/diffutil.dart/blob/master/lib/src/diffutil_impl.dart#L683
https://github.com/knaeckeKami/diffutil.dart/blob/master/lib/src/diffutil_impl.dart#L720

However, when reversing the iteration order, the body of the loops needs to be tweaked as well.

[knaeckeKami]

Another way to go would be to implement some sort of Batching (like when you call getUpdates (batch:true)) on diffs with data.
So you would not have a [DataInsert(position: 0, data: "b"), DataInsert(position: 0, data : "a")] but rather something like
[BatchedDataInsert(position: 0, data: ["a", "b"])] .

This would be easier to implement.
Would this help?

[narcodico]

That's not gonna work well because you can't obtained the right order by doing inserts at the same position, no matter where that position is. You basically need [DataInsert(position: 0, data: "a"), DataInsert(position: 1, data : "b")], so the batch approach doesn't play well with this unless you're just grouping together the aforementioned models into a batch model which would have to look different, because like I mentioned earlier, you won't obtain the needed result by using the same position.

[knaeckeKami]

Something like this?

import 'package:diffutil_dart/src/model/diffupdate_with_data.dart';

extension Sort<T> on Iterable<DataDiffUpdate<T>> {
  Iterable<DataDiffUpdate<T>> reorder() sync* {
    DataDiffUpdate<T>? lastUpdate;
    final List<DataDiffUpdate<T>> _batchedUpdates = [];
    for (final update in this) {
      if (lastUpdate.runtimeType != update.runtimeType) {
        if (_batchedUpdates.isNotEmpty) {
          // end of consecutive updates of the same type
          yield* _yieldResult(_batchedUpdates);
          _batchedUpdates.clear();
          yield update;
        } else {
          // first new update
          _batchedUpdates.add(update);
        }
        lastUpdate = update;
      } else {
        // moves and changes cannot be batched
        if (lastUpdate is DataMove<T> || lastUpdate is DataChange<T>) {
          yield lastUpdate!;
          lastUpdate = update;
        } else if (update is DataInsert<T>) {
          // handle consecutive inserts
          final lastInsert = lastUpdate as DataInsert<T>;
          if (update.position == lastInsert.position) {
            _batchedUpdates.add(update);
          } else {
            yield* _yieldResult(_batchedUpdates);
            _batchedUpdates.clear();
            yield update;
            lastUpdate = update;
          }
        } else {
          // handle consecutive deletes
          final remove = update as DataRemove<T>;
          final lastRemove = lastUpdate as DataRemove<T>;
          if (remove.position == lastRemove.position) {
            _batchedUpdates.add(update);
          } else {
            yield* _yieldResult(_batchedUpdates);
            _batchedUpdates.clear();
            yield update;
            lastUpdate = update;
          }
        }
      }
    }
    // yield last items
    yield* _yieldResult(_batchedUpdates);
  }

  Iterable<DataDiffUpdate<T>> _yieldResult(List<DataDiffUpdate<T>> updates) sync* {
    if (updates.isEmpty) {
      return;
    }
    int correction = updates.first is DataInsert<T> ? 0 : updates.length - 1;
    for (final correctedUpdate in updates.reversed) {
      yield correctedUpdate.when(
          insert: (pos, data) => DataDiffUpdate.insert(position: pos + correction++, data: data),
          remove: (pos, data) => DataDiffUpdate.remove(position: pos + correction--, data: data),
          change: (_, __, ___) => throw AssertionError("unreachable"),
          move: (_, __, ___) => throw AssertionError("unreachable"));
    }
  }
}

(note: proof of concept, this is untested and may be buggy)

[narcodico]

Looks like a promising starting point. And yeah, writing some tests would help solidify it.