DataSetDiff.java

/*
The MIT License (MIT)

Copyright (c) 2016 Tigerspike

Permission is hereby granted, free of charge, to any person obtaining a copy of 
this software and associated documentation files (the "Software"), to deal in the 
Software without restriction, including without limitation the rights to use, copy, 
modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, 
and to permit persons to whom the Software is furnished to do so, subject to the 
following conditions:

The above copyright notice and this permission notice shall be included in all copies 
or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE 
FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR 
OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
DEALINGS IN THE SOFTWARE.
*/

package com.morrisons.instore.utility;

import android.support.annotation.Nullable;

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

/**
 * The ChangeDetection class will use the Model's hashCode method to calculate differences between
 * data sets.
 *
 * Make sure your class adds a hashCode implementation and it is kept up to date.
 */
public class ChangeDetection<Model> {

    private List<Integer> mPreviousDataHashes = new ArrayList<>();

    public synchronized List<Change> newData(@Nullable List<Model> data) {
        List<Integer> newDataHashes = new ArrayList<>();

        if (data!=null) {
            for (Model model : data) {
                newDataHashes.add(model.hashCode());
            }
        }

        List<Change> changeList = calculateChangeList(mPreviousDataHashes, newDataHashes);

        mPreviousDataHashes = newDataHashes;
        return changeList;
    }

    private List<Change> calculateChangeList(@Nullable List<Integer> previousDataHashes, @Nullable List<Integer> newDataHashes) {

        int newDataSize = newDataHashes != null ? newDataHashes.size() : 0;
        int previousDataSize = previousDataHashes != null ? previousDataHashes.size() : 0;

        int previousHashPosition = 0;
        int newHashPosition = 0;

        // Yes we can.
        List<Change> changes = new ArrayList<>();

        while (previousHashPosition < previousDataSize && newHashPosition < newDataSize) {
            int oldHash = previousDataHashes.get(previousHashPosition);
            int newHash = newDataHashes.get(newHashPosition);

            // Since we update them up here, we'll have to - 1 them when pointing to the right position
            // in the Change created.
            previousHashPosition++;
            newHashPosition++;

            if (oldHash == newHash) {
                // unchanged item, carry on
                continue;
            }

            boolean isNewHashNew = !previousDataHashes.contains(newHash);
            boolean isOldHashDeleted = !newDataHashes.contains(oldHash);

            if (isNewHashNew && isOldHashDeleted) {
                // Updated item
                changes.add(new Change(Change.Type.UPDATE, previousHashPosition - 1));
            }

            else if (isNewHashNew) {
                // Added an item
                changes.add(new Change(Change.Type.ADD, newHashPosition - 1));

                // Move back the previous item pointer so it is still in the
                // same position in the next loop iteration.
                previousHashPosition--;
            }
            else if (isOldHashDeleted) {
                // Old hash is a removed change.
                changes.add(new Change(Change.Type.REMOVE, previousHashPosition - 1));

                // Move back the new hash position so as to avoid updating everything.
                newHashPosition--;
            }
            else {
                // The hash is different, but the old item is not deleted, and the new item is not new.
                // Seems like a change of order. Will be treated as updated item
                changes.add(new Change(Change.Type.UPDATE, previousHashPosition - 1));
            }
        }

        while (previousHashPosition < previousDataSize) {
            // Removed items.
            changes.add(new Change(Change.Type.REMOVE, previousHashPosition));

            previousHashPosition++;
        }

        while (newHashPosition < newDataSize) {
            // Added item
            changes.add(new Change(Change.Type.ADD, newHashPosition));

            newHashPosition++;
        }

        return changes;
    }

}

// Change.java

public class Change {

    private final int mPosition;
    private final Type mType;

    public Change(Type type, int position) {
        mPosition = position;
        mType = type;
    }

    public int getPosition() {
        return mPosition;
    }

    public Type getType() {
        return mType;
    }

    public enum Type {
        ADD, REMOVE, UPDATE
    }
}

// Test

package com.morrisons.instore.utility;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import static org.hamcrest.MatcherAssert.*;
import static org.hamcrest.CoreMatchers.*;

public class ChangeDetectionTest {

    @Test
    public void changeDetectionOnEmptyListReturnsNoChanges() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(new ArrayList<Integer>());
        int changeSize = changeDetection.newData(new ArrayList<Integer>()).size();

        assertThat(0, is(equalTo(changeSize)));
    }

    // ADD

    @Test
    public void addToEmptyList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(new ArrayList<Integer>());
        List<Change> changes = changeDetection.newData(Arrays.asList(1, 2, 3));
        int changeSize = changes.size();

        assertThat(3, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.ADD, 0);
    }

    @Test
    public void addToEndOfNonEmptyList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(0,1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(0, 1, 2, 3, 4, 5, 6));
        int changeSize = changes.size();

        assertThat(3, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.ADD, 4);
    }

    @Test
    public void addToStartOfNonEmptyList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(3, 4, 5, 6));
        List<Change> changes = changeDetection.newData(Arrays.asList(0, 1, 2, 3, 4, 5, 6));
        int changeSize = changes.size();

        assertThat(3, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.ADD, 0);
    }

    @Test
    public void addMiddleOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(0, 1, 2, 3));
        List<Change> changes = changeDetection.newData(Arrays.asList(0, 1, 5, 2, 3));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        assertThat(Change.Type.ADD, is(equalTo(changes.get(0).getType())));
        assertThat(2, is(equalTo(changes.get(0).getPosition())));
    }

    // Updates

    @Test
    public void updateAllList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(4, 5, 6));
        int changeSize = changes.size();

        assertThat(3, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.UPDATE, 0);
    }

    @Test
    public void updateStartOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(5, 2, 3));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.UPDATE, 0);
    }

    @Test
    public void updateEndOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(1, 2, 5));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.UPDATE, 2);
    }

    @Test
    public void updateMiddleOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(1,4,3));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(), is(equalTo(Change.Type.UPDATE)));
        assertThat(changes.get(0).getPosition(), is(equalTo(1)));
    }

    // Remove

    @Test
    public void removeAllList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(new ArrayList<Integer>());
        int changeSize = changes.size();

        assertThat(3, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.REMOVE, 0);
    }

    @Test
    public void removeStartOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(2,3));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.REMOVE, 0);
    }

    @Test
    public void removeEndOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(1,2));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.REMOVE, 2);
    }

    @Test
    public void removeMiddleOfList() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(1,3));
        int changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        iterateChangesCheckingPositionAndType(changes, Change.Type.REMOVE, 1);
    }

    // Add and remove

    @Test
    public void addAndRemoveWithItemsInTheMiddleInTheEnd() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(1,3,4));
        int changeSize = changes.size();

        assertThat(2, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(), is(equalTo(Change.Type.REMOVE)));
        assertThat(changes.get(0).getPosition(), is(equalTo(1)));
        assertThat(changes.get(1).getType(), is(equalTo(Change.Type.ADD)));
        assertThat(changes.get(1).getPosition(), is(equalTo(2)));
    }

    @Test
    public void addAndRemoveWithItemsInTheMiddleInTheStart() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2,3));
        List<Change> changes = changeDetection.newData(Arrays.asList(4,1,3));
        int changeSize = changes.size();

        assertThat(2, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(), is(equalTo(Change.Type.ADD)));
        assertThat(changes.get(0).getPosition(), is(equalTo(0)));
        assertThat(changes.get(1).getType(), is(equalTo(Change.Type.REMOVE)));
        assertThat(changes.get(1).getPosition(), is(equalTo(1)));
    }

    // Complex

    @Test
    public void nonTrivialChangeDetectionTest() {
        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();

        changeDetection.newData(Arrays.asList(1,2));
        List<Change> changes = changeDetection.newData(Arrays.asList(4, 3));
        int changeSize = changes.size();

        assertThat(2, is(equalTo(changeSize)));

        changes = changeDetection.newData(Collections.singletonList(4));
        changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(),is(equalTo(Change.Type.REMOVE)));

        changes = changeDetection.newData(Collections.singletonList(5));
        changeSize = changes.size();

        assertThat(1, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(),is(equalTo(Change.Type.UPDATE)));

        changes = changeDetection.newData(Arrays.asList(1,2,5));
        changeSize = changes.size();

        assertThat(2, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(),is(equalTo(Change.Type.ADD)));
        assertThat(changes.get(1).getType(),is(equalTo(Change.Type.ADD)));

        changes = changeDetection.newData(Arrays.asList(1,5,2));
        changeSize = changes.size();

        assertThat(2, is(equalTo(changeSize)));
        assertThat(changes.get(0).getType(),is(equalTo(Change.Type.UPDATE)));
        assertThat(changes.get(1).getType(),is(equalTo(Change.Type.UPDATE)));


        changes = changeDetection.newData(Arrays.asList(1,5,2));
        changeSize = changes.size();

        assertThat(0, is(equalTo(changeSize)));
    }

    // Performance

//    @Test
//    public void performanceTestWorstCaseScenario() {
//        ChangeDetection<Integer> changeDetection = new ChangeDetection<>();
//        ArrayList<Integer> initialData = new ArrayList<>(Collections.nCopies(1000, 1));
//        ArrayList<Integer> finalData = new ArrayList<>(Collections.nCopies(1000, 1));
//        changeDetection.newData(initialData);
//
//        long millis = System.currentTimeMillis();
//        changeDetection.newData(finalData);
//        long finalMillis = System.currentTimeMillis();
//
//        long elapsed = finalMillis - millis;
//
//        assertThat(elapsed < 100, is(equalTo(true)));
//    }

    // Helpers

    private void iterateChangesCheckingPositionAndType(List<Change> changes, Change.Type type, int initialPosition) {
        int position = initialPosition;
        for (Change change : changes) {
            assertThat(position, is(equalTo(change.getPosition())));
            assertThat(type, is(equalTo(change.getType())));
            position++;
        }
    }

}