differencedocumentiterator.java

MG4J (Managing Gigabytes for Java) is a free full-text search engine for large document collections

package it.unimi.dsi.mg4j.search;

/*		 
 * MG4J: Managing Gigabytes for Java
 *
 * Copyright (C) 2007 Sebastiano Vigna 
 *
 *  This library is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  This library is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 *  for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 */

import it.unimi.dsi.fastutil.ints.IntSet;
import it.unimi.dsi.fastutil.objects.Reference2ReferenceArrayMap;
import it.unimi.dsi.fastutil.objects.Reference2ReferenceMap;
import it.unimi.dsi.fastutil.objects.Reference2ReferenceMaps;
import it.unimi.dsi.fastutil.objects.ReferenceSet;
import it.unimi.dsi.mg4j.index.Index;
import it.unimi.dsi.mg4j.search.visitor.DocumentIteratorVisitor;
import it.unimi.dsi.util.Interval;
import it.unimi.dsi.util.Intervals;

import java.io.IOException;


/** A document iterator that computes the Brouwerian difference between two given document iterators.
 * 
 * <p>In the lattice of interval antichains, the Brouwerian difference is obtained by deleting from
 * the first operand all intervals that contain some interval of the second operand. Thus,
 * Brouwerian difference can be fruitfully employed to kill intervals containing a term or, even
 * more fruitfully, to change at query time the granularity of an index by subtracting from the
 * results of a query those length-two intervals 
 * that cross the cutpoints between the desired parts of the index.
 * 
 * <p>Additionally, this class provides <em>interval enlargment</em>&mdash;by using a suitable
 * {@linkplain #getInstance(DocumentIterator, DocumentIterator, int, int) factory method} each interval
 * returned by the subtrahend will be enlarged to the left and to the right by the given amount (e.g.,
 * if the left margin is 1 and the right margin is 2 the interval [2..3] will turn into [1..5]).
 * 
 * @author Sebastiano Vigna
 * @since 1.2
 */

public class DifferenceDocumentIterator extends AbstractDocumentIterator implements DocumentIterator {
	private static final boolean DEBUG = false;
	private final static boolean ASSERTS = false;
	
	/** The first operand. */
	final private DocumentIterator minuendIterator;
	/** The second operand. */
	final private DocumentIterator subtrahendIterator;
	/** If not <code>null</code>, the sole index involved in this iterator. */
	final private Index soleIndex;
	/** A map from indices to interval iterators. */
	final private Reference2ReferenceArrayMap<Index,IntervalIterator> intervalIterators;
	/** 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 {@link #intervalIterators}
	 * because it could be {@link IntervalIterators#TRUE} (in fact, in that case it may even
	 * happen that {@link #intervalIterators} does not contain the index). */
	final private Reference2ReferenceArrayMap<Index,IntervalIterator> currentIterators;
	/** An unmodifiable wrapper around {@link #currentIterators}. */
	final private Reference2ReferenceMap<Index,IntervalIterator> unmodifiableCurrentIterators;

	/** A margin that will be added to the left of each interval. */
	private final int leftMargin;
	/** A margin that will be added to the right of each interval. */
	private final int rightMargin;
	/** If true, for the current document we have intervals for the minuend but not for the subtrahend. */
	private boolean noSubtrahend;

	/** Creates a new difference document iterator given a minuend and a subtrahend iterator.
	 * @param minuendIterator the minuend.
	 * @param subtrahendIterator the subtrahend.
	 */
	protected DifferenceDocumentIterator( final DocumentIterator minuendIterator, final DocumentIterator subtrahendIterator, final int leftMargin, final int rightMargin ) {
		if ( leftMargin < 0 || rightMargin < 0 ) throw new IllegalArgumentException( "Illegal margins: " + leftMargin + ", " + rightMargin );
		this.minuendIterator = minuendIterator;
		this.subtrahendIterator = subtrahendIterator;
		this.leftMargin = leftMargin;
		this.rightMargin = rightMargin;
		final int n = minuendIterator.indices().size();
		soleIndex = n == 1 ? indices().iterator().next() : null;

		intervalIterators = new Reference2ReferenceArrayMap<Index,IntervalIterator>( n );
		currentIterators = new Reference2ReferenceArrayMap<Index,IntervalIterator>( n );
		unmodifiableCurrentIterators = Reference2ReferenceMaps.unmodifiable( currentIterators );
	}

	/** Returns new difference document iterator given a minuend and a subtrahend iterator.
	 * @param minuendIterator the minuend.
	 * @param subtrahendIterator the subtrahend.
	 */
	public static DocumentIterator getInstance( final DocumentIterator minuendIterator, final DocumentIterator subtrahendIterator ) {
		return getInstance( minuendIterator, subtrahendIterator, 0, 0 );
	}

	/** Returns new difference document iterator given a minuend and a subtrahend iterator.
	 * @param minuendIterator the minuend.
	 * @param subtrahendIterator the subtrahend.
	 * @param leftMargin a margin that will be added to the left of each interval.
	 * @param rightMargin a margin that will be added to the right of each interval.
	 */
	public static DocumentIterator getInstance( final DocumentIterator minuendIterator, final DocumentIterator subtrahendIterator, final int leftMargin, final int rightMargin ) {
		// If the subtrahend is empty, the result is equal to the minuend.
		if ( ! subtrahendIterator.hasNext() ) return minuendIterator;
		return new DifferenceDocumentIterator( minuendIterator, subtrahendIterator, leftMargin, rightMargin );
	}

	public ReferenceSet<Index> indices() {
		return minuendIterator.indices();
	}

	public int nextDocument() throws IOException {
		if ( next >= 0 ) {
			last = next;
			next = -1;
			return last;
		}
		
		do currentIterators.clear(); while( ( last = minuendIterator.nextDocument() ) != -1 && ! isValid() );
		return last;
	}
	
	public int skipTo( final int n ) throws IOException {
		// The easy case.
		if ( last >= n ) return last;
		if ( next >= n ) return nextDocument();
		
		next = -1;
		currentIterators.clear();
		// We first try to get a candidate document.
		last = minuendIterator.skipTo( n );
		// If this doesn't work, be bail out.
		if ( last == Integer.MAX_VALUE ) {
			last = -1;
			return Integer.MAX_VALUE;
		}

		// Otherwise, we must manually check that we are on a valid document
		if ( isValid() ) return last;
		// If not, we invalidate and check whether there is another possible document.
		return nextDocument() != -1 ? last : Integer.MAX_VALUE;
	}

	private boolean isValid() throws IOException {
		// An easy optimisation for the case in which the subtrahend does not include the current document.
		if ( noSubtrahend = ( subtrahendIterator.skipTo( last ) != last ) ) return true;
		
		/* The policy here is that a difference iterator is valid is at least one of the underlying
		 * interval iterators would return at least one interval. */
		if ( soleIndex != null ) return intervalIterator( soleIndex ).hasNext();
		
		for( Index index: indices() ) if ( intervalIterator( index ).hasNext() ) return true;
		return false;
	}

	public Reference2ReferenceMap<Index,IntervalIterator> intervalIterators() throws IOException {
		if ( last == -1 ) throw new IllegalStateException();
		for( Index index : indices() ) intervalIterator( index );
		return unmodifiableCurrentIterators;
	}

	public IntervalIterator intervalIterator() throws IOException {
		if ( soleIndex == null ) throw new IllegalStateException();
		return intervalIterator( soleIndex );
	}

	public IntervalIterator intervalIterator( final Index index ) throws IOException {
		if ( last == -1 ) throw new IllegalStateException();
		if ( DEBUG ) System.err.println( this + ".intervalIterator(" + index + ")" );
		if ( ! minuendIterator.indices().contains( index ) ) return IntervalIterators.TRUE;

		IntervalIterator intervalIterator, subtrahendIntervalIterator;

		// If the iterator has been created and it's ready, we just return it.		
		if ( ( intervalIterator = currentIterators.get( index ) ) != null ) return intervalIterator;
		intervalIterator = minuendIterator.intervalIterator( index );

		if ( ! noSubtrahend && subtrahendIterator.document() == minuendIterator.document() && intervalIterator.hasNext() &&
				( subtrahendIntervalIterator = subtrahendIterator.intervalIterator( index ) ).hasNext() ) {
			if ( subtrahendIntervalIterator == IntervalIterators.TRUE ) intervalIterator = IntervalIterators.FALSE;
			else if ( intervalIterator != IntervalIterators.TRUE ) { 
				intervalIterator = intervalIterators.get( index );
				if ( intervalIterator == null ) intervalIterators.put( index, intervalIterator = new DifferenceIntervalIterator( index ) );
				intervalIterator.reset();
			}
		}

		currentIterators.put( index, intervalIterator );
		
		if ( DEBUG ) System.err.println( "Returning interval iterator " + intervalIterator );
		return intervalIterator;
	}

	public void dispose() throws IOException {
		minuendIterator.dispose();
		subtrahendIterator.dispose();
	}
	
	public boolean accept( final DocumentIteratorVisitor visitor ) throws IOException {
		return visitor.visitPre( this ) && minuendIterator.accept( visitor ) && subtrahendIterator.accept( visitor ) && visitor.visitPost( this );
	}

	public boolean acceptOnTruePaths( final DocumentIteratorVisitor visitor ) throws IOException {
		return visitor.visitPre( this ) && minuendIterator.acceptOnTruePaths( visitor ) && visitor.visitPost( this );
	}
	
	public String toString() {
		return getClass().getSimpleName() + "(" + minuendIterator + ( leftMargin == 0 && rightMargin == 0 ? " - " : " -[" + leftMargin + "," + rightMargin + "] " ) + subtrahendIterator + ")";
	}
	
	/** An interval iterator returning just the interval shorter than {@link #threshold}. */
	
	private class DifferenceIntervalIterator extends AbstractIntervalIterator implements IntervalIterator {
		/** The index of this iterator. */
		final Index index;
		/** The underlying minuend interal iterator. */
		private IntervalIterator minuendIntervalIterator;
		/** The underlying minuend interal iterator. */
		private IntervalIterator subtrahendIntervalIterator;
		/** The last interval returned by {@link #subtrahendIntervalIterator}. */
		private Interval subtrahendInterval;
		
		public DifferenceIntervalIterator( final Index index ) {
			this.index = index;
		}

		public void reset( ) throws IOException {
			next = null;
			subtrahendInterval = Intervals.MINUS_INFINITY;
			minuendIntervalIterator = minuendIterator.intervalIterator( index );
			subtrahendIntervalIterator = subtrahendIterator.intervalIterator( index );
			if ( ASSERTS ) assert minuendIntervalIterator != IntervalIterators.TRUE;
			if ( ASSERTS ) assert minuendIntervalIterator != IntervalIterators.FALSE;
			if ( ASSERTS ) assert minuendIntervalIterator.hasNext();
			if ( ASSERTS ) assert subtrahendIntervalIterator != IntervalIterators.TRUE;
			if ( ASSERTS ) assert subtrahendIntervalIterator != IntervalIterators.FALSE;
			if ( ASSERTS ) assert subtrahendIntervalIterator.hasNext();
		}

		public void intervalTerms( final IntSet terms ) {
			// Just delegate to minuend
			minuendIntervalIterator.intervalTerms( terms );
		}
		
		public Interval nextInterval() throws IOException {
			if ( next != null ) {
				final Interval result = next;
				next = null; 
				return result;
			}
			
			if ( subtrahendInterval == Intervals.MINUS_INFINITY ) subtrahendInterval = subtrahendIntervalIterator.nextInterval();
			
			Interval minuendInterval;
			while( ( minuendInterval = minuendIntervalIterator.nextInterval() ) != null ) {
					while(	subtrahendInterval != null && 
							subtrahendInterval.left - leftMargin < minuendInterval.left &&
							subtrahendInterval.right + rightMargin < minuendInterval.right ) 
						subtrahendInterval = subtrahendIntervalIterator.nextInterval();
				if ( subtrahendInterval == null || 
						subtrahendInterval.left - leftMargin < minuendInterval.left ||
						subtrahendInterval.right + rightMargin > minuendInterval.right ) return minuendInterval;
			}
            
			return null;
		}
		
		public int extent() {
			return minuendIntervalIterator.extent(); // TODO: check this
		}
		
		public String toString() {
		   return getClass().getSimpleName() + "(" + minuendIntervalIterator + ( leftMargin == 0 && rightMargin == 0 ? " - " : " -[" + leftMargin + "," + rightMargin + "] " ) + subtrahendIntervalIterator + ")";
		}
	}
}