baku-toolkit/lib/src/main/java/io/v/baku/toolkit/bind/DerivedListDeltaAccumulator.java

// Copyright 2015 The Vanadium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package io.v.baku.toolkit.bind;

import android.support.v7.widget.RecyclerView;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import java8.util.function.Function;
import lombok.RequiredArgsConstructor;
import lombok.experimental.Delegate;
import rx.Observable;

/**
 * This {@link ListDeltaAccumulator} derives its deltas from {@link ListAccumulator} snapshots.
 *
 * @param <T>
 */
@RequiredArgsConstructor
public class DerivedListDeltaAccumulator<T> implements ListDeltaAccumulator<T> {
    @RequiredArgsConstructor
    private static class DiffContext<T> {
        final NumericIdMapper ids;
        final Function<? super ImmutableList<T>, ? extends ListAccumulator<T>> stepFactory;

        final List<DerivedListDeltaAccumulator<T>> steps = new ArrayList<>();

        /**
         * Algorithm:
         *
         * 1. Notify of all removals.
         * 2. Notify of moves to reorder intersection.
         * 3. Notify of all insertions.
         *
         * This algorithm does not trigger any item change events, preferring remove/insert instead.
         * Also, it fails if any items are not unique.
         */
        DiffContext<T> diff(final ListAccumulator<T> a, final ListAccumulator<T> b) {
            if (a == null) {
                steps.add(new DerivedListDeltaAccumulator<>(ids, b));
            } else {
                final ImmutableList<T>
                        aList = a.getListSnapshot(),
                        bList = b.getListSnapshot();
                final ImmutableSet<T>
                        aItems = ImmutableSet.copyOf(aList),
                        bItems = ImmutableSet.copyOf(bList);

                final List<T> mutable = processRemovals(aList, bItems);

                final List<T> to = new ArrayList<>(bList);
                to.retainAll(aItems);
                processMoves(mutable, to);

                processInsertions(mutable, bList);
            }
            return this;
        }

        ListAccumulator<T> produceStepSnapshot(final List<T> working) {
            return stepFactory.apply(ImmutableList.copyOf(working));
        }

        /**
         * @param start the mutable ordered start state
         * @param goal  the elements in the end state
         * @return the result of retaining `goal` from `start`
         */
        List<T> processRemovals(final ImmutableList<T> start, final ImmutableSet<T> goal) {
            final List<T> working = new ArrayList<>(start);
            int removalCount = 0, i = 0;

            for (final T item : start) {
                if (goal.contains(item)) {
                    processRemovals(working, i, removalCount);
                    i++;
                    removalCount = 0;
                } else {
                    removalCount++;
                }
            }
            processRemovals(working, i, removalCount);
            return working;
        }

        /**
         * Helper to {@link #processRemovals(ImmutableList, ImmutableSet)} that performs multi-item
         * removal, single-item removal, or no-ops based on contiguous scan results.
         */
        void processRemovals(final List<T> working, final int index, final int count) {
            if (count > 0) {
                working.subList(index, index + count).clear();
                steps.add(new DerivedListDeltaAccumulator<T>(ids, produceStepSnapshot(working)) {
                    @Override
                    public void notifyDeltas(RecyclerView.Adapter<?> rva) {
                        rva.notifyItemRangeRemoved(index, count);
                    }
                });
            }
        }

        /**
         * Transitions from {@code working} to {@code goal} by moving one item at a time. Moves are
         * performed in clusters of like deltas, moving smaller clusters first in the hopes that
         * larger clusters will fall into place as a result of the smaller moves. While this usually
         * results in optimal plans, there are cases where it can result in terrible plan, e.g.
         * <p>
         * 3 4 2 1 -> 3 2 4 1 -> 2 4 3 1 -> 4 2 3 1 -> 2 3 1 4 -> 1 2 3 4
         * <p>
         * I believe we can prevent this pitfall by rejecting moves that would break clusters:
         * <p>
         * 3 4 2 1 -> 1 3 4 2 -> 1 2 3 4
         * <p>
         * TODO(rosswang): Do this (and add a test).
         */
        void processMoves(final List<T> working, final List<T> goal) {
            final HashMap<T, Integer> goalIndices = new HashMap<>(goal.size());
            for (int i = 0; i < goal.size(); i++) {
                goalIndices.put(goal.get(i), i);
            }

            class MoveProcessor {
                int start, end, clusterStart, clusterDelta,
                        minClusterStart, minClusterEnd, minClusterDelta;

                boolean hasMovingCluster() {
                    return minClusterDelta != 0;
                }

                void startCluster(final int index, final int delta) {
                    clusterStart = index;
                    clusterDelta = delta;
                }

                void endCluster(final int indexAfter) {
                    if (clusterDelta == 0) {
                        if (!hasMovingCluster()) {
                            start = indexAfter;
                        } else if (indexAfter == end) {
                            end = clusterStart;
                        }
                    } else if (!hasMovingCluster() ||
                            indexAfter - clusterStart < minClusterEnd - minClusterStart) {
                        // smallest cluster; keep it as a prime candidate for moving
                        minClusterStart = clusterStart;
                        minClusterEnd = indexAfter;
                        minClusterDelta = clusterDelta;
                    }
                }

                MoveProcessor() {
                    this(0, working.size());
                }

                MoveProcessor(final int start, final int end) {
                    this.start = start;
                    this.end = end;
                    for (int i = start; i < end; i++) {
                        final int delta = goalIndices.get(working.get(i)) - i;
                        if (delta != clusterDelta) {
                            endCluster(i);
                            startCluster(i, delta);
                        }
                    }
                    endCluster(end);
                }

                DerivedListDeltaAccumulator<T> step(final int from, final int to) {
                    working.add(to, working.remove(from));
                    return new DerivedListDeltaAccumulator<T>(ids, produceStepSnapshot(working)) {
                        @Override
                        public void notifyDeltas(RecyclerView.Adapter<?> rva) {
                            rva.notifyItemMoved(from, to);
                        }
                    };
                }

                void addMinClusterSteps() {
                    if (minClusterDelta < 0) {
                        for (int i = minClusterStart; i < minClusterEnd; i++) {
                            steps.add(step(i, i + minClusterDelta));
                        }
                    } else {
                        for (int i = minClusterEnd - 1; i >= minClusterStart; i--) {
                            steps.add(step(i, i + minClusterDelta));
                        }
                    }
                }
            }

            for (MoveProcessor mp = new MoveProcessor(); mp.hasMovingCluster();
                 mp = new MoveProcessor(mp.start, mp.end)) {
                mp.addMinClusterSteps();
            }
        }

        /**
         * @param working the mutable ordered (intermediate) start state
         * @param goal    the ordered end state
         */
        void processInsertions(final List<T> working, final ImmutableList<T> goal) {
            final List<T> insert = new ArrayList<>();

            for (int i = 0; i < goal.size(); i++) {
                final T item = goal.get(i);
                final int insertAt = i - insert.size();
                if (insertAt < working.size() && item.equals(working.get(insertAt))) {
                    processInsertions(working, insertAt, insert);
                    insert.clear();
                } else {
                    insert.add(item);
                }
            }
            if (!insert.isEmpty()) {
                // Capture these ints so that we're not holding onto instances of the working lists
                // and opening us to errors if they're modified.
                final int count = insert.size(), index = goal.size() - count;
                steps.add(new DerivedListDeltaAccumulator<T>(ids, stepFactory.apply(goal)) {
                    @Override
                    public void notifyDeltas(RecyclerView.Adapter<?> rva) {
                        rva.notifyItemRangeInserted(index, count);
                    }
                });
            }
        }

        /**
         * Helper to {@link #processInsertions(List, ImmutableList)} that performs multi-item
         * insertion, single-item insertion, or no-ops based on contiguous scan results.
         */
        void processInsertions(final List<T> working, final int index, final List<T> insert) {
            if (!insert.isEmpty()) {
                working.addAll(index, insert);
                // Capture count so that we're not holding onto an instance of insert and opening us
                // to errors if (and when) it's modified.
                final int count = insert.size();
                steps.add(new DerivedListDeltaAccumulator<T>(ids, produceStepSnapshot(working)) {
                    @Override
                    public void notifyDeltas(RecyclerView.Adapter<?> rva) {
                        rva.notifyItemRangeInserted(index, count);
                    }
                });
            }
        }
    }

    private final NumericIdMapper mIds;
    @Delegate
    private final ListAccumulator<T> mSnapshot;

    public static <T> Observable<DerivedListDeltaAccumulator<T>> scanFrom(
            final Observable<? extends ListAccumulator<T>> snapshots,
            final Function<? super ImmutableList<T>, ? extends ListAccumulator<T>> stepFactory) {
        final NumericIdMapper ids = new NumericIdMapper();
        return Observable.concat(Observable.zip(
                // need to wrap null as an Observable (or Iterable) to capture generic wildcard
                // without overload ambiguity
                snapshots.startWith(Observable.just(null)),
                snapshots,
                (previous, next) -> Observable.from(new DiffContext<>(ids, stepFactory)
                        .diff(previous, next).steps)));
    }

    /**
     * The default implementation simply calls
     * {@link android.support.v7.widget.RecyclerView.Adapter#notifyDataSetChanged()}.
     * However, it is fully expected that subclasses, such as the anonymous subclasses generated
     * within {@link #scanFrom(Observable, Function)}, override this for more specific
     * notifications.
     */
    @Override
    public void notifyDeltas(final RecyclerView.Adapter<?> rva) {
        rva.notifyDataSetChanged();
    }

    @Override
    public long getItemId(final int position) {
        return mIds.assignNumericId(getRowAt(position));
    }
}