Package org.apache.cassandra.index.sasi.utils

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

java.lang.Object
org.apache.cassandra.utils.AbstractGuavaIterator<T>
org.apache.cassandra.index.sasi.utils.RangeIterator<K,D>
org.apache.cassandra.index.sasi.utils.RangeIntersectionIterator.BounceIntersectionIterator<K,D>
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>, Closeable, AutoCloseable, Iterator<D>
Enclosing class:
RangeIntersectionIterator
protected static class RangeIntersectionIterator.BounceIntersectionIterator<K extends 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.