blah.java

import com.google.common.base.Joiner;
import com.google.common.collect.Lists;

import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;

public class Incr2 {
    static class Datum {
        final int id;
        final String name;

        Datum(int id, String name) {
            this.id = id;
            this.name = name;
        }

        @Override
        public String toString() {
            return "Datum{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
        }
    }

    static class DatumComparator implements Comparator<Datum> {
        @Override
        public int compare(Datum obj1, Datum obj2) {
            return Integer.compare(obj1.id, obj2.id);
        }
    }

    static final DatumComparator C = new DatumComparator();

    public static void main(String[] args) throws Exception {
        List<Datum> sync = Lists.newArrayList(new Datum(1, "a"), new Datum(3, "c"), new Datum(4, "d"), new Datum(100, "Z"));
        List<Datum> del = Lists.newArrayList(new Datum(4, "d"));
        List<Datum> ups = Lists.newArrayList(new Datum(0, "z"), new Datum(2, "b"), new Datum(3, "x"), new Datum(1000, "*"));

        System.out.println("Sync");
        System.out.println(Joiner.on(", ").join(sync));
        System.out.println();

        applyDeletes(sync, del, C);

        System.out.println("After deletes");
        System.out.println(Joiner.on(", ").join(sync));
        System.out.println();

        applyUpdates(sync, ups, C);

        System.out.println("After updates");
        System.out.println(Joiner.on(", ").join(sync));
        System.out.println();
    }

    private static <T> void applyUpdates(List<T> sync, List<T> ups, Comparator<T> c) {
        int syncCursor = 0;

        for (T d : ups) {
            // catch up sync's cursor to the next element equal to or greater than d
            int result = 1;
            while ((syncCursor < sync.size()) && ((result = c.compare(sync.get(syncCursor), d)) < 0)) {
                syncCursor++;
                result = 1;
            }

            if (result == 0) {
                sync.set(syncCursor, d);
            } else if (result > 0) {
                sync.add(syncCursor, d);
            } else {
                throw new IllegalStateException("can't happen");
            }
        }
    }

    private static <T> void applyDeletes(List<T> sync, List<T> del, Comparator<T> c) {
        final ListIterator<T> is = sync.listIterator();

        for (T d : del) {
            T next = catchUp(is, d, c);
            if (next == null) {
                return;
            }

            int comp = c.compare(next, d);
            if (comp == 0) {
                is.remove();
            }
        }
    }

    private static <T> T catchUp(ListIterator<T> is, T d, Comparator<T> c) {
        T next;
        do {
            if (!is.hasNext()) {
                return null;
            }
            next = is.next();
        } while (c.compare(next, d) < 0);
        return next;
    }
}