Class RangeIntersectionIterator.BounceIntersectionIterator<K extends java.lang.Comparable<K>,​D extends CombinedValue<K>>

  • Type Parameters:
    K - The type used to sort ranges.
    D - The container type which is going to be returned by Iterator.next().
    All Implemented Interfaces:
    com.google.common.collect.PeekingIterator<D>, java.io.Closeable, java.lang.AutoCloseable, java.util.Iterator<D>
    Enclosing class:
    RangeIntersectionIterator

    protected static class RangeIntersectionIterator.BounceIntersectionIterator<K extends java.lang.Comparable<K>,​D extends CombinedValue<K>>
    extends RangeIterator<K,​D>
    Iterator which performs intersection of multiple ranges by using bouncing (merge-join) technique to identify common elements in the given ranges. Aforementioned "bounce" works as follows: range queue is poll'ed for the range with the smallest current token (main loop), that token is used to RangeIterator.skipTo(Comparable) other ranges, if token produced by RangeIterator.skipTo(Comparable) is equal to current "candidate" token, both get merged together and the same operation is repeated for next range from the queue, if returned token is not equal than candidate, candidate's range gets put back into the queue and the main loop gets repeated until next intersection token is found or at least one iterator runs out of tokens. This technique is every efficient to jump over gaps in the ranges.
    • Method Detail

      • computeNext

        protected D computeNext()
        Description copied from class: AbstractIterator
        Returns the next element. Note: the implementation must call AbstractIterator.endOfData() when there are no elements left in the iteration. Failure to do so could result in an infinite loop.

        The initial invocation of AbstractIterator.hasNext() or AbstractIterator.next() calls this method, as does the first invocation of hasNext or next following each successful call to next. Once the implementation either invokes endOfData or throws an exception, computeNext is guaranteed to never be called again.

        If this method throws an exception, it will propagate outward to the hasNext or next invocation that invoked this method. Any further attempts to use the iterator will result in an IllegalStateException.

        The implementation of this method may not invoke the hasNext, next, or AbstractIterator.peek() methods on this instance; if it does, an IllegalStateException will result.

        Specified by:
        computeNext in class AbstractIterator<D extends CombinedValue<K>>
        Returns:
        the next element if there was one. If endOfData was called during execution, the return value will be ignored.