CODEWITHSUNDEEP
javacollections
FlorianT
FlorianT

Reputation: 1227

Java - how to obtain an interleaved iterator/collection

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.

Upvotes: 1

Views: 599

Answers (4)

Ivan Balashov
Ivan Balashov

Reputation: 1953

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

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 520878

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.

Upvotes: 2

Kirill Boyarintsev
Kirill Boyarintsev

Reputation: 1

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.

Upvotes: 0

Mark Peters
Mark Peters

Reputation: 81054

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.

Upvotes: 0

Related Questions