sclass OrderedMultiIterator<A extends Comparable<A>> extends ItIt<A> {
  srecord noeq Stream<A extends Comparable<A>>(Iterator<A> iterator, A element) is Comparable<Stream<A>> {
    public int compareTo(Stream<A> stream) {
      ret element.compareTo(stream.element);
    }
    
    bool advance() {
      if (!iterator.hasNext()) false;
      element = iterator.next();
      true;
    }
  }
  
  new ArrayList<Stream<A>> streams;
  bool sorted;
  
  void add(Iterable<A> it) {
    add(iteratorOrNull(it));
  }
  
  void add(Iterator<A> iterator) {
    if (iterator == null || !iterator.hasNext()) ret;
    A element = iterator.next();
    streams.add(new Stream<A>(iterator, element));
    sorted = false;
  }
  
  void addAll(Iterable<? extends Iterator<A>> iterators) {
    fOr (it : iterators) add(it);
  }
  
  public bool hasNext() {
    ret nempty(streams);
  }
  
  public A next() {
    if (!sorted) {
      sortInPlace(streams);
      set sorted;
    }
    
    var stream = first(streams);
    A element = stream.element;
    
    if (!stream.advance())
      streams.remove(0);
    else {
      // put stream in the right place
      
      int i = 0, n = streams.size()-1;
      Stream<A> stream2;
      while (i < n && stream.compareTo(stream2 = streams.get(i+1)) >= 0)
        streams.set(i++, stream2);
      streams.set(i, stream);
    }
      
    ret element;
  }
}