Java - how to obtain an interleaved iterator/collection

Question

Let's say we receive strings from 3 producers asynchronously. Once a certain amount of these objects have been received I want to iterate over them in an interleaved manner, that is, if receiving the following strings:

"a1" received from A,
"a2" received from A,
"c1" received from C,
"a3" received from A,
"b1" received from B,
"b2" received from B,

I'd like the "interleaved" iterator to return the strings as if we were iterating over the following list:

List<String> interleavedList = {"a1", "b1", "c1", "a2", "c2", "a3"},

So far I've created one List<String> for each producer, and then I'm "iterating" over all the strings by working with the 3 list iterators (with a List<Iterator<String>>). This works fine but I think there is a simpler way... Maybe by directly constructing the interleaved list while receiving the strings? but I don't see which Collection or which Comparator to use...

Note that I'm not so much interested in creating one list for each producer and then merging the 3 lists in a 4th interleaved list, as this will probably not be time-efficient.

Can you tell us more about efficiency? E.g. with a [CyclicBarrier](https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/CyclicBarrier.html) you can achieve this, however, that would slow down the producers. On the other hand, using the lists as you mentioned is totally time-efficient. It uses up some memory instead. — Tamas Rev, Aug 17 '16 at 14:54
You could subclass java.util.Iterator to achieve this. Also see following http://stackoverflow.com/questions/3610261/is-it-possible-to-merge-iterators-in-java — Ashwinee K Jha, Aug 17 '16 at 14:55
if using java 8,have you tried interleave strings in stream ? — Amir-Mousavi, Aug 17 '16 at 14:58
Do the producers finish they job sometime? Can you wait to iterate the final results? — cesarse, Aug 17 '16 at 14:59

Tim Biegeleisen · Answer 1 · 2016-08-17T15:26:37.413

It appears that you want the list to be sorted, with the number determining the sort first and the letter second. Java does not have a sorted list, because the nature of lists is that they are not sorted. However, you could use a sorted set with a custom comparator:

SortedSet<String> sortedset = new TreeSet<String>(
        new Comparator<String>() {
            @Override
            public int compare(String e1, String e2) {
                int num1 = Integer.parseInt(e1.replaceAll("[^\\d.]", ""));
                int num2 = Integer.parseInt(e2.replaceAll("[^\\d.]", ""));
                if (num1 > num2) {
                    return 1;
                }
                else if (num1 < num2) {
                    return -1;
                }
                else {
                    String let1 = e1.replaceAll("[0-9]", "");
                    String let2 = e2.replaceAll("[0-9]", "");
                    return let1.compareTo(let2);
                }
            }
        });

When you iterate over this set, you will get the ordering you described in your question.

score 0 · Answer 2 · answered Aug 17 '16 at 15:08

One option would be to dump all objects into a PriorityBlockingQueue based on the producer-specific index in which they arrive:

class Message {
   String data;
   long index;
}

PriorityBlockingQueue<Message> queue = new PriorityBlockingQueue<Message>(
  10,
  Comparator.comparing(m -> m.index)
); 

List<String> batch = new ArrayList<>(BATCH_SIZE);
for (;;) {
   for (int i = 0; i < BATCH_SIZE; i++) {
      batch.add(queue.take().data);
   }
   handleBatch(batch);
   batch.clear();
}

Note this assumes an infinite queue; if the queue is non-infinite you would have to add some logic to handle the final batch.

score 0 · Answer 3 · edited May 23 '17 at 10:28

0

You can add your strings to PriorityQueue<String> with a custom Comparator. In this case your elements will be automatically sorted when you add them. Here is a useful example.

edited May 23 '17 at 10:28

Community

1
1

answered Aug 17 '16 at 15:11

Kirill Boyarintsev

1
2

score 0 · Answer 4 · answered May 08 '18 at 14:20

I ran into similar problem recently, here is what I came up with (just take from each iterator in turns until all them drain, no sorting):

import java.util.Collection;
import java.util.Iterator;

public class InterleavedIterator<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 InterleavedIterator(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;
    }
  }
}

Java - how to obtain an interleaved iterator/collection

4 Answers4