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?

Streams are not good at changing their length. So you probably should start with a stream that is long enough to hold the resulting list and somehow merge your elements into there via some kind of logic to get the correct index in the input streams based on the index in the output stream. — luk2302
– luk2302, Commented Aug 3, 2017 at 20:25
I you have to think too much how to do it with the Stream API, just do it with a classic loop — Felix
– Felix, Commented Aug 3, 2017 at 20:36
If you are worried about performance the stream api isn't going to magically make this better. — icirellik
– icirellik, Commented Aug 3, 2017 at 20:40
@rollback, I just curious is it possible to do that in a more smart way with Stream API. If not, I will stay with implementation like above. — Vasyl Sarzhynskyi
– Vasyl Sarzhynskyi, Commented Aug 3, 2017 at 20:41
"is it possible to do [...] with Stream API"? Yes, write your own Spliterator. --- "in a more smart way"? In my opinion, no. — Andreas
– Andreas, Commented Aug 3, 2017 at 20:45

marsouf · Accepted Answer · 2017-08-03 22:06:07Z

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]
    }
}

LuCio · Accepted Answer · 2018-07-17 09:53:40Z

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.

Collectives™ on Stack Overflow

Merging two lists alternating by N elements with Stream API

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related