Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Merged Iterator. Uses Guava
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import com.google.common.collect.Iterators;
import com.google.common.collect.PeekingIterator;
public class MergedIterator<T> implements Iterator<T> {
private final Comparator<? super T> comparator;
private final PeekingIterator<T> first;
private final PeekingIterator<T> second;
private MergedIterator(Comparator<? super T> comparator, Iterator<T> first, Iterator<T> second) {
this.comparator = comparator;
this.first = Iterators.peekingIterator(first);
this.second = Iterators.peekingIterator(second);
}
@SafeVarargs
public static <T> Iterator<T> merge(Comparator<? super T> ordering, Iterator<T>... iterators) {
return merge(ordering, iterators, 0, iterators.length);
}
private static <T> Iterator<T> merge(Comparator<? super T> ordering, Iterator<T>[] iterators, int offset, int length) {
if (length == 0) {
return Collections.emptyIterator();
}
if (length == 1) {
return iterators[offset];
}
return new MergedIterator<>(ordering,
merge(ordering, iterators, offset, length / 2),
merge(ordering, iterators, offset + length / 2, length - (length / 2)));
}
@Override
public boolean hasNext() {
return first.hasNext() || second.hasNext();
}
@Override
public T next() {
if (!first.hasNext()) {
if (!second.hasNext()) {
throw new NoSuchElementException();
}
return second.next();
}
return !second.hasNext() || (comparator.compare(first.peek(), second.peek()) <= 0) ? first.next() : second.next();
}
}
import static org.assertj.core.api.Assertions.assertThat;
import java.util.Iterator;
import org.junit.Test;
import com.google.common.collect.Iterators;
import com.google.common.collect.Lists;
import com.google.common.collect.Ordering;
public class MergedIteratorTest {
@Test
public void merge() {
Iterator<Integer> stream1 = Iterators.forArray(4, 6);
Iterator<Integer> stream3 = Iterators.forArray(1, 3, 5, 7, 9, 11);
Iterator<Integer> stream2 = Iterators.forArray(2, 8, 10);
Iterator<Integer> merged = MergedIterator.merge(Ordering.natural(), stream1, stream2, stream3);
assertThat(Lists.newArrayList(merged)).hasSize(11).isSorted();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.