Skip to content

Instantly share code, notes, and snippets.

@ibalashov
Created May 8, 2018 13:57
Show Gist options
  • Save ibalashov/7dd9fc16102b93e18387dce30d05c2e4 to your computer and use it in GitHub Desktop.
Save ibalashov/7dd9fc16102b93e18387dce30d05c2e4 to your computer and use it in GitHub Desktop.
Interleaved iterator with multiple backing iterators support
package com.outbrain.utils;
import com.google.common.collect.Lists;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class InterleavedIteratorMany<T> implements Iterator<T> {
static class Node<K> {
Node<K> next;
Node<K> prev;
final K value;
Node(K value) {
this.value = value;
}
public void setNext(Node<K> next) {
this.next = next;
}
public void setPrev(Node<K> prev) {
this.prev = prev;
}
}
private Node<Iterator<T>> node;
public InterleavedIteratorMany(Collection<Iterator<T>> iterators) {
Node<Iterator<T>> prev = null;
for (Iterator<T> iterator : iterators) {
if (!iterator.hasNext()) {
continue;
}
Node<Iterator<T>> current = new Node<>(iterator);
if (prev != null) {
prev.setNext(current);
current.setPrev(prev);
} else {
node = current;
}
prev = current;
}
if (prev != null) {
prev.setNext(node);
node.setPrev(prev);
}
}
@Override
public boolean hasNext() {
return node.value.hasNext();
}
@Override
public T next() {
T res = node.value.next();
updateNode();
return res;
}
private void updateNode() {
Node<Iterator<T>> nextNode = node.next;
if (node.value.hasNext()) {
node = nextNode;
} else if (node != nextNode) {
node.prev.next = nextNode;
nextNode.prev = node.prev;
node = nextNode;
}
}
public static void main(String[] args) {
display(Lists.newArrayList(numIt(0, 1), numIt(10, 12)));
display(Lists.newArrayList(numIt(0, 5), numIt(10, 12), numIt(20, 26)));
}
private static void display(ArrayList<Iterator<Integer>> iterators) {
System.out.println(toList(new InterleavedIteratorMany<>(iterators)));
}
private static List<Integer> toList(InterleavedIteratorMany<Integer> it) {
List<Integer> list = Lists.newArrayList();
it.forEachRemaining(list::add);
return list;
}
private static Iterator<Integer> numIt(int start, int end) {
return IntStream.range(start, end + 1).boxed().collect(Collectors.toList()).iterator();
}
}
@ibalashov
Copy link
Author

range(0, 1) + range(10, 12) -> [0, 10, 1, 11, 12]
range(0, 5) + range(10, 12) + range(20, 26) -> [0, 10, 20, 1, 11, 21, 2, 12, 22, 3, 23, 4, 24, 5, 25, 26]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment