calculateDiff<T> function

DiffResult<T> calculateDiff<T>(DiffDelegate cb, { bool detectMoves = false, })

Calculates the list of update operations that can covert one list into the other one.

If your old and new lists are sorted by the same constraint and items never move (swap positions), you can disable move detection which takes O(N^2) time where N is the number of added, moved, removed items.

@param cb The callback that acts as a gateway to the backing list data @param detectMoves True if DiffUtil should try to detect moved items, false otherwise.

@return A DiffResult that contains the information about the edit sequence to convert the old list into the new list.

Implementation

DiffResult<T> calculateDiff<T>(DiffDelegate cb, {bool detectMoves = false}) {
  final oldSize = cb.getOldListSize();
  final newSize = cb.getNewListSize();
  final diagonals = <_Diagonal>[];
  // instead of a recursive implementation, we keep our own stack to avoid potential stack
  // overflow exceptions
  final stack = <_Range>[];
  stack.add(_Range(
      oldListStart: 0,
      oldListEnd: oldSize,
      newListStart: 0,
      newListEnd: newSize));
  final max = (oldSize + newSize + 1) ~/ 2;
  // allocate forward and backward k-lines. K lines are diagonal lines in the matrix. (see the
  // paper for details)
  // These arrays lines keep the max reachable position for each k-line.
  final forward = _CenteredArray(max * 2 + 1);
  final backward = _CenteredArray(max * 2 + 1);
  // We pool the ranges to avoid allocations for each recursive call.
  final rangePool = <_Range>[];
  while (stack.isNotEmpty) {
    final range = stack.removeLast();
    final snake = midPoint(range, cb, forward, backward);

    if (snake != null) {
      // if it has a diagonal, save it
      if (snake.diagonalSize() > 0) {
        diagonals.add(snake.toDiagonal());
      }

      // add new ranges for left and right
      final _Range left = rangePool.isEmpty
          ? _Range.empty()
          : rangePool.removeAt(rangePool.length - 1);
      left.oldListStart = range.oldListStart;
      left.newListStart = range.newListStart;
      left.oldListEnd = snake.startX;
      left.newListEnd = snake.startY;

      stack.add(left);

      // re-use range for right
      //noinspection UnnecessaryLocalVariable
      final _Range right = range;
      right.oldListEnd = range.oldListEnd;
      right.newListEnd = range.newListEnd;
      right.oldListStart = snake.endX;
      right.newListStart = snake.endY;
      stack.add(right);
    } else {
      rangePool.add(range);
    }
  }
  diagonals.sort(_diagonalComparator);

  return DiffResult._(cb, diagonals, forward.data, backward.data, detectMoves);
}