it.unimi.dsi.mg4j.search
Class AbstractIntersectionDocumentIterator

java.lang.Object
  extended by it.unimi.dsi.fastutil.ints.AbstractIntIterator
      extended by it.unimi.dsi.mg4j.search.AbstractDocumentIterator
          extended by it.unimi.dsi.mg4j.search.AbstractCompositeDocumentIterator
              extended by it.unimi.dsi.mg4j.search.AbstractIntersectionDocumentIterator
All Implemented Interfaces:
IntIterator, DocumentIterator, Iterable<Interval>, Iterator<Integer>
Direct Known Subclasses:
AbstractOrderedIntervalDocumentIterator, AndDocumentIterator

public abstract class AbstractIntersectionDocumentIterator
extends AbstractCompositeDocumentIterator

An abstract iterator on documents, generating the intersection of the documents returned by a number of document iterators.

To be usable, this class must be subclassed so to provide also an iterator on intervals. Such iterators must be instantiable using getComposedIntervalIterator(Index). The latter is an example of a non-static factory method, that is, a factory method which depends on the enclosing instance. This pattern allows to easily specialise this class to iterators that do different things, such as AndDocumentIterator and ConsecutiveDocumentIterator, but that have a similar semantics at the document level (the semantics may in fact be slightly different: for instance, not all document belonging to all components will actually appear in a consecutive iterator, as there may be documents filtered at the interval level).

The important invariant is that only after a call to nextDocument(), a call to intervalIterator(Index) will return an interval iterator over the document just returned, and that for at least one index in AbstractCompositeDocumentIterator.indices() the iterator will not be empty or TRUE.

The intersection algorithm

Since MG4J 1.1, this class implements a new intersection algorithm that should be significantly faster than the previous one. The main idea is that of letting sparser iterator interact as much as possible to obtain a candidate common document, and then trying to align the others. At construction time, the component iterators are sorted so that index iterators are separated, and sorted by frequency. Then, each time we have to align the iterators we align them greedily starting from the index iterators, in frequency order. This has the effect of skipping very quickly (and usually by large jumps, which are handled nicely by indices with skips), as the main interaction happens between low-frequency index iterators.

Moreover, this class treats in a special way index iterators coming from payload-based indices. Such iterators are checked at the end of the alignment process, after all standard index iterators (and general document iterators) are aligned. At that point, the special method PayloadPredicateDocumentIterator.skipUnconditionallyTo(int) is used to position unconditionally such iterators and check whether the payload predicate is satisfied. If this doesn't happen, the current candidate (obtained by alignment of standard iterators) is increased and the whole process is restarted. This procedure guarantees that we will never search exhaustively in a payload-based index a document record satisfying the predicate (unless, of course, we have a query containing just PayloadPredicateDocumentIterators), which is very efficient if the payload-based index uses skipping.


Nested Class Summary
 
Nested classes/interfaces inherited from class it.unimi.dsi.mg4j.search.AbstractCompositeDocumentIterator
AbstractCompositeDocumentIterator.AbstractCompositeIndexIntervalIterator, AbstractCompositeDocumentIterator.AbstractCompositeIntervalIterator
 
Nested classes/interfaces inherited from class it.unimi.dsi.mg4j.search.AbstractDocumentIterator
AbstractDocumentIterator.AbstractIntervalIterator
 
Field Summary
protected  Reference2ReferenceArrayMap<Index,IntervalIterator> currentIterators
          A map from indices to the iterators returned for the current document.
protected  Reference2ReferenceArrayMap<Index,IntervalIterator> intervalIterators
          A map from indices to interval iterators.
protected  Reference2ReferenceMap<Index,IntervalIterator> unmodifiableCurrentIterators
          An unmodifiable wrapper around currentIterators.
 
Fields inherited from class it.unimi.dsi.mg4j.search.AbstractCompositeDocumentIterator
documentIterator, indexIterator, indices, n, soleIndex
 
Fields inherited from class it.unimi.dsi.mg4j.search.AbstractDocumentIterator
last, next
 
Constructor Summary
protected AbstractIntersectionDocumentIterator(DocumentIterator[] documentIterator)
          Creates a new intersection iterator using a given array of iterators.
protected AbstractIntersectionDocumentIterator(Index index, DocumentIterator[] documentIterator)
          Creates a new intersection iterator using a given array of iterators and a given index.
 
Method Summary
protected abstract  IntervalIterator getComposedIntervalIterator(Index index)
           
 IntervalIterator intervalIterator(Index index)
          Returns the interval iterator of this document iterator for the given index.
 Reference2ReferenceMap<Index,IntervalIterator> intervalIterators()
          Returns an unmodifiable map from indices to interval iterators.
 int nextDocument()
          Returns the next document provided by this document iterator, or -1 if no more documents are available.
 int skipTo(int n)
          Skips all documents smaller than n.
 
Methods inherited from class it.unimi.dsi.mg4j.search.AbstractCompositeDocumentIterator
accept, acceptOnTruePaths, dispose, indices, intervalIterator, toString
 
Methods inherited from class it.unimi.dsi.mg4j.search.AbstractDocumentIterator
document, hasNext, iterator, nextInt
 
Methods inherited from class it.unimi.dsi.fastutil.ints.AbstractIntIterator
next, remove, skip
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface it.unimi.dsi.mg4j.search.DocumentIterator
document, iterator, nextInt
 
Methods inherited from interface it.unimi.dsi.fastutil.ints.IntIterator
skip
 
Methods inherited from interface java.util.Iterator
hasNext, next, remove
 

Field Detail

intervalIterators

protected final Reference2ReferenceArrayMap<Index,IntervalIterator> intervalIterators
A map from indices to interval iterators.


currentIterators

protected final Reference2ReferenceArrayMap<Index,IntervalIterator> currentIterators
A map from indices to the iterators returned for the current document. The key set may not contain an index because the related iterator has never been requested. Moreover, the iterator in this map for a given index may differ from the one in intervalIterators because it could be TRUE (in fact, in that case it may even happen that intervalIterators does not contain the index).


unmodifiableCurrentIterators

protected final Reference2ReferenceMap<Index,IntervalIterator> unmodifiableCurrentIterators
An unmodifiable wrapper around currentIterators.

Constructor Detail

AbstractIntersectionDocumentIterator

protected AbstractIntersectionDocumentIterator(Index index,
                                               DocumentIterator[] documentIterator)
                                        throws IOException
Creates a new intersection iterator using a given array of iterators and a given index.

Parameters:
index - an index that will be passed to AbstractCompositeDocumentIterator.AbstractCompositeDocumentIterator(Index, DocumentIterator...).
documentIterator - the iterators to be insersected (at least one).
Throws:
IOException

AbstractIntersectionDocumentIterator

protected AbstractIntersectionDocumentIterator(DocumentIterator[] documentIterator)
                                        throws IOException
Creates a new intersection iterator using a given array of iterators.

Parameters:
documentIterator - the iterators to be insersected (at least one).
Throws:
IOException
Method Detail

skipTo

public int skipTo(int n)
           throws IOException
Description copied from interface: DocumentIterator
Skips all documents smaller than n.

Define the current document k associated with this document iterator as follows:

If k is larger than or equal to n, then this method does nothing and returns k. Otherwise, a call to this method is equivalent to

 while( ( k = nextDocument() ) < n && k != -1 );
 return k == -1 ? Integer.MAX_VALUE : k;
 

Thus, when a result kInteger.MAX_VALUE is returned, the state of this iterator will be exactly the same as after a call to DocumentIterator.nextDocument() that returned k. In particular, the first document larger than or equal to n (when returned by this method) will not be returned by the next call to DocumentIterator.nextDocument().

Parameters:
n - a document pointer.
Returns:
a document pointer larger than or equal to n if available, Integer.MAX_VALUE otherwise.
Throws:
IOException

nextDocument

public int nextDocument()
                 throws IOException
Description copied from interface: DocumentIterator
Returns the next document provided by this document iterator, or -1 if no more documents are available.

Warning: the specification of this method has significantly changed as of MG4J 1.2. The special return value -1 is used to mark the end of iteration (a NoSuchElementException would have been thrown before in that case, so ho harm should be caused by this change). The reason for this change is providing fully lazy iteration over documents. Fully lazy iteration does not provide an hasNext() method—you have to actually ask for the next element and check the return value. Fully lazy iteration is much lighter on method calls (half) and in most (if not all) MG4J classes leads to a much simpler logic. Moreover, DocumentIterator.nextDocument() can be specified as throwing an IOException, which avoids the pernicious proliferation of try/catch blocks in very short, low-level methods (it was having a detectable impact on performance).

Returns:
the next document, or -1 if no more documents are available.
Throws:
IOException

intervalIterators

public Reference2ReferenceMap<Index,IntervalIterator> intervalIterators()
                                                                 throws IOException
Description copied from interface: DocumentIterator
Returns an unmodifiable map from indices to interval iterators.

After a call to DocumentIterator.nextDocument(), this map can be used to retrieve the intervals in the current document. An invocation of Map.get(java.lang.Object) on this map with argument index yields the same result as intervalIterator(index).

Returns:
a map from indices to interval iterators over the current document.
Throws:
IOException
See Also:
DocumentIterator.intervalIterator(Index)

intervalIterator

public IntervalIterator intervalIterator(Index index)
                                  throws IOException
Description copied from interface: DocumentIterator
Returns the interval iterator of this document iterator for the given index.

After a call to DocumentIterator.nextDocument(), this iterator can be used to retrieve the intervals in the current document (the one returned by DocumentIterator.nextDocument()) for the index index.

Note that if all indices have positions, it is guaranteed that at least one index will return an interval. However, for disjunctive queries it cannot be guaranteed that all indices will return an interval.

Indices without positions always return IntervalIterators.TRUE. Thus, in presence of indices without positions it is possible that no intervals at all are available.

Parameters:
index - an index (must be one over which the query was built).
Returns:
an interval iterator over the current document in index.
Throws:
IOException

getComposedIntervalIterator

protected abstract IntervalIterator getComposedIntervalIterator(Index index)