@ Override public ListMultimap < Iterator < T > , T > next ( ) { ListMultimap < Iterator < T > , T > results = ArrayListMultimap . create ( ) ; while ( true ) { HeapEntry heapEntry = heap . poll ( ) ; if ( heapEntry == null ) { break ; // heap is empty } results . put ( iterators . get ( heapEntry . fromIterator ) , heapEntry . item ) ; // The heap must contain one entry for each iterator that has >= 1 item remaining. // Replace the one we just popped with a new one from the source iterator. Iterator < T > sourceIterator = iterators . get ( heapEntry . fromIterator ) ; if ( hasNextWrapper ( sourceIterator ) ) { HeapEntry newEntry = new HeapEntry ( nextWrapper ( sourceIterator ) , heapEntry . fromIterator ) ; // Any new heap items should compare >= popped items if input iterators are sorted assert heap . comparator ( ) . compare ( newEntry , heapEntry ) >= 0 ; heap . add ( newEntry ) ; } // Iterate again if and only if the next item on the heap should be returned with this one // (that is, they compare equal by the given comparator). HeapEntry peekHeap = heap . peek ( ) ; if ( peekHeap == null || heap . comparator ( ) . compare ( heapEntry , heap . peek ( ) ) != 0 ) { break ; } } if ( results . size ( ) == 0 ) { throw new NoSuchElementException ( ) ; // Input iterators are empty } return results ; }
Get the next group of results that compare equal .