Java: zipping sorted collections

Let’s say we need to combine two sorted lists of numbers into a list of pairs, where a pair contains numbers that are equal.

If there is a number missing in one of the two lists, than we create a pair with the number and a ZERO element.

Example:


list_1 = [1, 3, 4, 6, 10]

list_2 = [1, 2, 3, 4, 5, 7, 10]

zippedList = [ (1, 1), (0, 2), (3, 3), (4, 4), (0, 5), (6, 0), (0, 7), (10, 10) ]

 

We can achive it with following implementation:

 

import io.vavr.Tuple;
import io.vavr.Tuple2;

import java.util.Iterator;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public class ZippedIterator implements Iterator<Tuple2> {

    private final Iterator iter1;
    private final Iterator iter2;
    private final T zeroElement;

    private T lastElement1 = null;
    private T lastElement2 = null;

    public static  Iterator<Tuple2>
    zipAllIterators(Iterator iter1, Iterator iter2, T zeroElement) {
        if (!iter1.hasNext() && !iter2.hasNext()) {
            return Stream.<Tuple2>empty().iterator();
        } else {
            return new ZippedIterator(iter1, iter2, zeroElement);
        }
    }

    public static  Stream<Tuple2>
    zipAll(Stream stream1, Stream stream2, T zeroElement, boolean parallel) {
        Iterator<Tuple2> tuple2Iterator =
            zipAllIterators(stream1.iterator(), stream2.iterator(), zeroElement);
        Iterable<Tuple2> iterable = () -> tuple2Iterator;
        return StreamSupport.stream(iterable.spliterator(), parallel);
    }

    public ZippedIterator(Iterator iter1, Iterator iter2, T zeroElement) {
        this.iter1 = iter1;
        this.iter2 = iter2;
        this.zeroElement = zeroElement;
    }

    @Override
    public boolean hasNext() {
        return hasNext1() || hasNext2();
    }

    @Override
    public Tuple2 next() {
        T e1 = next1();
        T e2 = next2();
        if (e1 != null && e2 != null) {
            int r = e1.compareTo(e2);
            if (r == 0) {
                lastElement1 = null;
                lastElement2 = null;
                return Tuple.of(e1, e2);
            } else if (r  0
                lastElement2 = null;
                return Tuple.of(zeroElement, e2);
            }
        }
        if (e1 == null) {
            lastElement2 = null;
            return Tuple.of(zeroElement, e2);
        }
        lastElement1 = null;
        return Tuple.of(e1, zeroElement);
    }

    private boolean hasNext1() {
        return lastElement1 != null || iter1.hasNext();
    }

    private boolean hasNext2() {
        return lastElement2 != null || iter2.hasNext();
    }

    private T next1() {
        return lastElement1 != null ? lastElement1 : (!iter1.hasNext() ? null : (lastElement1 = iter1.next()));
    }

    private T next2() {
        return lastElement2 != null ? lastElement2 : (!iter2.hasNext() ? null : (lastElement2 = iter2.next()));
    }

} 

 

We can check this implementation with a few tests:

 

import static io.vavr.Tuple.of;
import static org.hamcrest.Matchers.contains;
import static org.junit.Assert.assertThat;

import io.vavr.Tuple2;
import org.junit.Test;

import java.util.stream.Collectors;
import java.util.stream.Stream;

public class ZippedIteratorTest {

    private Integer zero = 0;

    @Test
    public void testZipper() throws Exception {
        Stream s1 = Stream.of(4, 5, 10, 11);
        Stream s2 = Stream.of(1, 2, 4, 6, 8, 10, 15);

        Stream<Tuple2> zipped = zipper(s1, s2, zero);

        assertThat(zipped.collect(Collectors.toList()), contains(
            of(zero, 1),
            of(zero, 2),
            of(4, 4),
            of(5, zero),
            of(zero, 6),
            of(zero, 8),
            of(10, 10),
            of(11, zero),
            of(zero, 15)
        ));
    }

    @Test
    public void testZipperRigthEmpty() throws Exception {
        Stream s1 = Stream.of(4, 5, 10, 11);
        Stream s2 = Stream.empty();

        Stream<Tuple2> zipped = zipper(s1, s2, zero);

        assertThat(zipped.collect(Collectors.toList()), contains(
            of(4, zero),
            of(5, zero),
            of(10, zero),
            of(11, zero)
        ));
    }

    @Test
    public void testZipperLeftEmpty() throws Exception {
        Stream s1 = Stream.empty();
        Stream s2 = Stream.of(4, 5, 10, 11);

        Stream<Tuple2> zipped = zipper(s1, s2, zero);

        assertThat(zipped.collect(Collectors.toList()), contains(
            of(zero, 4),
            of(zero, 5),
            of(zero, 10),
            of(zero, 11)
        ));
    }

    private Stream<Tuple2> zipper(Stream s1, Stream s2,
                                                    Integer nullObject) {
        return zipAll(s1, s2, nullObject, false);
    }
}
Advertisements