Merging two lists alternating by N elements with Stream API

Question

I need to merge two lists alternating by N elements from each list: taking first N elements from first list, after taking first N elements from second list, after that second portion of N elements from first list, second portion of N elements from second list and so on. If one list is longer than the other, then append the remaining elements from the longer list into resulting list. 

For example, first list: 1, 2, 3, 4, second list: 10, 11, 12, 13, 14, 15, 16, 17

merging result of alternating by N = 2 is 1, 2, 10, 11, 3, 4, 12, 13, 14, 15, 16, 17.

Such merging could be implemented in the following way:

List<Integer> list1 = Arrays.asList(1, 2, 3, 4);
List<Integer> list2 = Arrays.asList(10, 11, 12, 13, 14, 15, 16, 17);
int alternatingNumber = 2;
List<Integer> mergedList = alternatingMerge(list1, list2, alternatingNumber);


public static <T> List<T> alternatingMerge(List<T> list1, List<T> list2, int alternatingNumber) {
    List<T> result = new ArrayList<T>();
    int size = Math.max(list1.size(), list2.size());

    for (int outerIndex = 0; outerIndex < size; outerIndex += alternatingNumber) {
        for (int innerIndex = 0; innerIndex < alternatingNumber; innerIndex++) {
            if (outerIndex + innerIndex < list1.size()) result.add(list1.get(outerIndex + innerIndex));
        }

        for (int innerIndex = 0; innerIndex < alternatingNumber; innerIndex++) {
            if (outerIndex + innerIndex < list2.size()) result.add(list2.get(outerIndex + innerIndex));
        }
    }

    return result;
}

Similar merging algorithms for alternating by 1 element (alternatingNumber = 1) described here, but I need to implement a universal logic for any alternating number.

Is it possible to do that somehow with Stream API?

Answer 1

I have used the wrap/process/unwrap pattern to encapsulate each entry with ((entryIndex / alternateStep), entry).

The wrapped elements are comparable, so when the stream is sorted by natural order, they will be sorted by their position (entryIndex / alternateStep).

In the last step, i've collected the entires stream into a List to be returned.

import java.util.Arrays;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

class Program
{
    static <T> List<T> alternateElementsBynStep (List<? extends T> flist, List<? extends T> slist, int n)
    {
        class Wrapper implements Comparable<Wrapper>
        {
            int position;
            T value;

            Wrapper (int position, T value)
            {
                this.position = position;
                this.value = value;
            }

            T getValue ()
            {
                return value;
            }

            @Override
            public int compareTo(Wrapper o) {
                return Integer.compare(position, o.position);
            }
        }

        Function<List<? extends T>, Stream<? extends Wrapper>> wrap =
            seq ->  IntStream.range(0, seq.size())
                        .mapToObj(i -> new Wrapper(i / n, seq.get(i)))
        ;

        return Stream.concat(wrap.apply(flist), wrap.apply(slist))
            .sorted()
            .map(Wrapper::getValue)
            .collect(Collectors.toList())
        ;
    }

    public static void main(String[] args)
    {
        System.out.println(Arrays.toString(alternateElementsBynStep(Arrays.asList(1, 2, 3, 4), Arrays.asList(10, 11, 12, 13, 14, 15, 16, 17), 2).toArray()));

        // output: [1, 2, 10, 11, 3, 4, 12, 13, 14, 15, 16, 17]
    }
}

Answer 2

Guava provides a method Streams.zip which allows to process two streams element by element at once. The following code applies this method to merge two lists alternating:

public static <T> Stream<T> streamAlternatingInParts(List<T> first, List<T> second, int partSize) {
    Stream<Stream<T>> zipped = zip(partitioning(first, partSize), partitioning(second, partSize));
    Stream<T> alternating = zipped.flatMap(Function.identity());

    int lengthFirst = first.size();
    int lengthSecond = second.size();
    if (lengthFirst != lengthSecond) {
        if (lengthFirst > lengthSecond) {
            return Stream.concat(alternating, first.subList(lengthSecond, lengthFirst).stream());
        }
        return Stream.concat(alternating, second.subList(lengthFirst, lengthSecond).stream());
    }

    return alternating;
}

public static <T> Stream<Stream<T>> partitioning(List<T> list, int partSize) {
    int end = (list.size() + partSize - 1) / partSize;
    return IntStream.range(0, end)
            .mapToObj(i -> list.subList(partSize * i, Math.min(partSize * i + partSize, list.size())).stream());
}

public static <T> Stream<T> zip(Stream<T> first, Stream<T> second) {
    return zip(() -> StreamSupport.stream(first.spliterator(), false), () -> StreamSupport.stream(second.spliterator(), false));
}

public static <T> Stream<T> zip(Supplier<Stream<T>> first, Supplier<Stream<T>> second) {
    return Streams.zip(first.get(), second.get(), Stream::of).flatMap(Function.identity());
}

partioning according to this answer.
zip according to this answer.

Applied to the example given in the question:

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(1, 2, 3, 4);
    List<Integer> list2 = Arrays.asList(10, 11, 12, 13, 14, 15, 16, 17);
    List<Integer> alternatingInParts = streamAlternatingInParts(list1, list2, 2).collect(Collectors.toList());
    System.out.println(Iterables.toString(alternatingInParts));
}

The output is:

[1, 2, 10, 11, 3, 4, 12, 13, 14, 15, 16, 17]

SincestreamAlternatingInParts returns a Stream it's possible to continue the streaming.