StrictMergeIterator.java

import com.google.common.collect.Iterators;
import com.google.common.collect.PeekingIterator;

import java.util.*;

import static java.util.stream.Collectors.toList;

public final class StrictMergeIterator {

    private StrictMergeIterator(){}

    public static <T> PeekingIterator<T> mergeSortingIteratorWithStableSort(List<Iterator<T>> iterators, Comparator<? super T> comparator) {
        //The difference between my implementation here and the Guava implementation is that in the case where the comparator finds the inputs to be equal
        //my implementation will return the inputs in the order that they came in.
        
        //This matters for non-transitive operations: merge(), leftStrictAdd(), ...
        //For transitive operations this doesn't matter: add(), mult(), lenientAdd(),...

        //The way this works is to attach an index to the inputs - so for the case where the inputs are equal we then go on to compare the index to determine which comes first

        List<Iterator<ThingWithIndex<T>>> withIndex = new ArrayList<>();
        int idx = 0;
        for (Iterator<T> it: iterators) {
            Iterator<ThingWithIndex<T>> withIndexIterator = buildIteratorWtihIndex(it, idx);
            withIndex.add(withIndexIterator);
            idx++;
        }



        return Iterators.peekingIterator(
                buildReducingIterator(Iterators.mergeSorted(withIndex, buildComparator(comparator)))
        );
    }

    private static class ThingWithIndex<T> {
        private final T thing;
        private final int index;

        public ThingWithIndex(T thing, int index) {
            this.thing = thing;
            this.index = index;
        }
    }

    private static <T> Comparator<ThingWithIndex<T>> buildComparator(Comparator<? super T> underlying) {
        return new Comparator<ThingWithIndex<T>>() {
            @Override
            public int compare(ThingWithIndex<T> o1, ThingWithIndex<T> o2) {
                var c = underlying.compare(o1.thing, o2.thing);
                if(c==0) {
                    return Integer.compare(o1.index, o2.index);
                }
                return c;
            }
        };
    }

    private static <T> Iterator<ThingWithIndex<T>> buildIteratorWtihIndex(Iterator<T> it, int idx) {
        return new Iterator<ThingWithIndex<T>>() {
            @Override
            public boolean hasNext() {
                return it.hasNext();
            }

            @Override
            public ThingWithIndex<T> next() {
                return new ThingWithIndex<>(it.next(), idx);
            }
        };
    }

    private static <T> Iterator<T> buildReducingIterator(Iterator<ThingWithIndex<T>> withIndexIterator) {
        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return withIndexIterator.hasNext();
            }

            @Override
            public T next() {
                return withIndexIterator.next().thing;
            }
        };
    }
}