How to interleave (merge) two Java 8 Streams?

Question

 Stream<String> a = Stream.of("one", "three", "five");
 Stream<String> b = Stream.of("two", "four", "six");

What do I need to do for the output to be the below?

// one
// two
// three
// four
// five
// six

I looked into concat but as the javadoc explains, it just appends one after the other, it does not interleave / intersperse.

Stream<String> out = Stream.concat(a, b);
out.forEach(System.out::println);

Creates a lazily concatenated stream whose elements are all the elements of the first stream followed by all the elements of the second stream.

Wrongly gives

 // one
 // three
 // five
 // two
 // four
 // six

Could do it if I collected them and iterated, but was hoping for something more Java8-y, Streamy :-)

Note

I don't want to zip the streams

“zip” operation will take an element from each collection and combine them.

the result of a zip operation would be something like this: (unwanted)

 // onetwo
 // threefour
 // fivesix

Monkhmer

zip is used to combine elements, I don't want to combine the elements, I want to keep the same total number of elements – Monkhmer

why wouldn't zip keep the same total number of elements? – Maddox

Reading the other thread, zip always takes a zipper function to combine an element from each stream to make a new element. I just want to interleave not zip – Monkhmer

I see your point and thanks for the clarification, using the zip function from the aforementioned dupe one could do Stream<String> result = zip(a, b, (e, z) -> Stream.of(e, z)).flatMap(x -> x); to get the result you want above. – Maddox

yeah thanks, thats what I've done. Just a shame that zip question is so so noisy, and doesn't come up when you google the keywords I've used here – Monkhmer

For anyone coming here in the future, here is the comments + redirected answer : gist.github.com/blundell/3f062b8ec55fd1906c68e6ec8d848683 – Monkhmer

I like the creation of the interleave method which essentially wraps the zip method to improve readability et al. I've voted to reopen, so you could post that here instead of externally... – Maddox

Answer 1

I’d use something like this:

public static <T> Stream<T> interleave(Stream<? extends T> a, Stream<? extends T> b) {
    Spliterator<? extends T> spA = a.spliterator(), spB = b.spliterator();
    long s = spA.estimateSize() + spB.estimateSize();
    if(s < 0) s = Long.MAX_VALUE;
    int ch = spA.characteristics() & spB.characteristics()
           & (Spliterator.NONNULL|Spliterator.SIZED);
    ch |= Spliterator.ORDERED;

    return StreamSupport.stream(new Spliterators.AbstractSpliterator<T>(s, ch) {
        Spliterator<? extends T> sp1 = spA, sp2 = spB;

        @Override
        public boolean tryAdvance(Consumer<? super T> action) {
            Spliterator<? extends T> sp = sp1;
            if(sp.tryAdvance(action)) {
                sp1 = sp2;
                sp2 = sp;
                return true;
            }
            return sp2.tryAdvance(action);
        }
    }, false);
}

It retains the characteristics of the input streams as far as possible, which allows certain optimizations (e.g. for count()and toArray()). Further, it adds the ORDERED even when the input streams might be unordered, to reflect the interleaving.

When one stream has more elements than the other, the remaining elements will appear at the end.

Kish

Wouldn't it be better to use Stream<? extends T> a for a much generic solution? Just asking, since I referenced this in another answer here. – Pointtopoint

@Pointtopoint of course. It's just a bit annoying having to carry the ? extends throughout the entire code. But it should be done for a good API. – Kish

Answer 2

A much dumber solution than Holger did, but may be it would fit your requirements:

private static <T> Stream<T> interleave(Stream<T> left, Stream<T> right) {
    Spliterator<T> splLeft = left.spliterator();
    Spliterator<T> splRight = right.spliterator();

    T[] single = (T[]) new Object[1];

    Stream.Builder<T> builder = Stream.builder();

    while (splRight.tryAdvance(x -> single[0] = x) && splLeft.tryAdvance(builder)) {
        builder.add(single[0]);
    }

    return builder.build();
}

Marry

This inconsistently includes all elements of left, when it has more elements than right, but will drop elements of right when it has more than left. You should decide. To included all common elements, use do {} while(splLeft.tryAdvance(builder) && spRight.tryAdvance(builder));, then decide. If you want to include all elements when the the streams have different sizes, do (splLeft.tryAdvance(builder)? splLeft: spRight).forEachRemaining(builder); after the loop. And well, Stream.Builder<T> does already implement Consumer<T>, conveniently. – Kish

@Kish indeed i wanted only common ones, but now the problem is worse, since do {} while(splLeft.tryAdvance(builder) && spRight.tryAdvance(builder)); will still take an element from left, so it's still not correct :(. the bigger problem I see now that I think about it - is that this is cheating, Stream.Builder still uses a hidden collection to gather elements... – Marry

Taking one additional element from left wouldn’t contradict the “interleaving” pattern (ababa). If you don’t want that, consider tracking the count and apply a limit to the resulting stream. That’s simpler than dealing with an additional storage operation, especially with generic arrays. The builder implies a storage, I thought you were aware of it, as that’s the main (only) disadvantage over implementing a spliterator. – Kish

@Kish I thought about a limit too, but don't know, the more I think about it, the more I like what you did – Marry

To rescue your approach, how about for(List<T> tmp = new ArrayList<>(1); splRight.tryAdvance(tmp::add) && splLeft.tryAdvance(builder); tmp.clear()) tmp.forEach(builder);? – Kish

@Kish I admit I was working into something close to that, but your solution is far more nice. thank you for the time, still your solution (as usual) must be the accepted one. – Marry

Streams may contain null, so you shouldn’t use a test against null here. On the other hand, there is no reason not to use the return value of splRight.tryAdvance(…), you can even inline the call into the if statement. It also makes the single[0] = null; obsolete. Then, transform the while(true) { if(condition) { statement; continue; } break; } to a while(condition) statement;… – Kish

Another con is that this approach is not lazy, i.e. it constructs the builder for the new interleaved stream in memory... – Purgative

@FedericoPeraltaSchaffner right, that is the exact point about the in memory collection, overall, just use whatever Holger put in place... – Marry

Answer 3

As you can see from the question comments, I gave this a go using zip:

Stream<String> a = Stream.of("one", "three", "five");
Stream<String> b = Stream.of("two", "four", "six");

Stream<String> out = interleave(a, b);


    public static <T> Stream<T> interleave(Stream<T> streamA, Stream<T> streamB) {
        return zip(streamA, streamB, (o1, o2) -> Stream.of(o1, o2)).flatMap(s -> s);
    }

    /**
    * https://mcmap.net/q/128256/-zipping-streams-using-jdk8-with-lambda-java-util-stream-streams-zip
    **/
    private static <A, B, C> Stream<C> zip(Stream<A> streamA, Stream<B> streamB, BiFunction<A, B, C> zipper) {
        final Iterator<A> iteratorA = streamA.iterator();
        final Iterator<B> iteratorB = streamB.iterator();
        final Iterator<C> iteratorC = new Iterator<C>() {
            @Override
            public boolean hasNext() {
                return iteratorA.hasNext() && iteratorB.hasNext();
            }

            @Override
            public C next() {
                return zipper.apply(iteratorA.next(), iteratorB.next());
            }
        };
        final boolean parallel = streamA.isParallel() || streamB.isParallel();
        return iteratorToFiniteStream(iteratorC, parallel);
    }

    private static <T> Stream<T> iteratorToFiniteStream(Iterator<T> iterator, boolean parallel) {
        final Iterable<T> iterable = () -> iterator;
        return StreamSupport.stream(iterable.spliterator(), parallel);
    }

Monkhmer

Answer 4

This may not be a good answer because
(1) it collects to map, which you don't want to do I guess and
(2) it is not completely stateless as it uses AtomicIntegers.

Still adding it because
(1) it is readable and
(2) community can get an idea from this and try to improve it.

Stream<String> a = Stream.of("one", "three", "five");
Stream<String> b = Stream.of("two", "four", "six");

AtomicInteger i = new AtomicInteger(0);
AtomicInteger j = new AtomicInteger(1);

Stream.of(a.collect(Collectors.toMap(o -> i.addAndGet(2), Function.identity())),
        b.collect(Collectors.toMap(o -> j.addAndGet(2), Function.identity())))
        .flatMap(m -> m.entrySet().stream())
        .sorted(Comparator.comparing(Map.Entry::getKey))
        .forEach(e -> System.out.println(e.getValue())); // or collect

Output

one
two
three
four
five
six

@Holger's edit

Stream.concat(a.map(o -> new AbstractMap.SimpleEntry<>(i.addAndGet(2), o)),
        b.map(o -> new AbstractMap.SimpleEntry<>(j.addAndGet(2), o)))
        .sorted(Map.Entry.comparingByKey())
        .forEach(e -> System.out.println(e.getValue())); // or collect

Neocene

You don’t need to collect into maps, as you are only interested in getting the stream of entries, so you can simply use Stream.concat( a.map(o -> new AbstractMap.SimpleEntry<>(i.addAndGet(2),o)), b.map(o -> new AbstractMap.SimpleEntry<>(j.addAndGet(2),o)) ) to get it. Then, you may chain .sorted(Map.Entry.comparingByKey()). But you’re right in that this mutable state is discouraged. Most notably, it will have problems with parallel execution. – Kish

@Kish thank you, added this to the answer. I thought about it earlier, but couldn't find an EntrySet constructor and got lazy to google search how to create an EntrySet :( – Neocene

It’s not creating an EntrySet but just a stream of Entry instances. The ready-to-use implementations are indeed not easy to find (there’s also a SimpleImmutableEntry in AbstractMap). Starting with Java 9, you can simply use Map.entry(key, value) to get an immutable Entry instance, but you have to be aware that it does not support null keys or values, so you can only use it when you can preclude null. – Kish

Answer 5

One solution with Iterator

final Iterator<String> iterA = a.iterator();
final Iterator<String> iterB = b.iterator();

final Iterator<String> iter = new Iterator<String>() {
  private final AtomicInteger idx = new AtomicInteger();
  @Override
  public boolean hasNext() { 
    return iterA.hasNext() || iterB.hasNext();
  }
  @Override
  public String next() {
    return idx.getAndIncrement() % 2 == 0 && iterA.hasNext() ? iterA.next() : iterB.next();
  }
};

 // Create target Stream with StreamEx from: https://github.com/amaembo/streamex    
 StreamEx.of(iter).forEach(System.out::println);

 // Or Streams from Google Guava
 Streams.stream(iter).forEach(System.out::println);

Or simply by the solution in abacus-common provided by me:

 AtomicInteger idx = new AtomicInteger();
 StreamEx.merge(a, b, (s1, s2) -> idx.getAndIncrement() % 2 == 0 ? Nth.FIRST : Nth.SECOND).forEach(Fn.println()); 

Stalder

Answer 6

without any external lib (using jdk11)

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class MergeUtil {

    private static <T> Stream<T> zipped(List<T> lista, List<T> listb) {
        int maxSize = Math.max(lista.size(), listb.size());
        final var listStream = IntStream
                .range(0, maxSize)
                .mapToObj(i -> {
                    List<T> result = new ArrayList<>(2);
                    if (i < lista.size()) result.add(lista.get(i));
                    if (i < listb.size()) result.add(listb.get(i));
                    return result;
                });
        return listStream.flatMap(List::stream);
    }

    public static void main(String[] args) {
        var l1 = List.of(1, 2, 3);
        var l2 = List.of(4, 5, 6, 7, 8, 9);
        final var zip = zipped(l1, l2);
        System.out.println(zip.collect(Collectors.toList()));
    }

}

listStream is a Stream<List<A>> that flatted in return.

The result is: [1, 4, 2, 5, 3, 6, 7, 8, 9]

Pincer

Answer 7

You don't need any hammer. For each element of the first stream, construct a stream with that element and an element of the second (extracted with an iterator), then flatMap:

Stream<String> a = Stream.of("one", "three", "five");
Stream<String> b = Stream.of("two", "four", "six");
Iterator<String> bi = b.iterator();
a.flatMap( x -> Stream.of(x, bi.next()) ).forEach(System.out::println);

Meekins

Answer 8

Using Guava's Streams.zip and Stream.flatMap:

Stream<String> interleaved = Streams
        .zip(a, b, (x, y) -> Stream.of(x, y))
        .flatMap(Function.identity());

---

interleaved.forEach(System.out::println);

Prints:

one
two
three
four
five
six

Florineflorio