bitstreamindexreader.c

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

					break;
				default:
					throw new IllegalStateException( "The required pointer coding (" + pointerCoding + ") is not supported." );
				}
#endif
			}
			else currentDocument++;
			numberOfDocumentRecord++;

#if GENERIC
			if ( hasPayloads ) 
#endif
#if GENERIC || ( PAYLOADS && #counts(NONE) )
				state = BEFORE_PAYLOAD;
#endif
#if GENERIC
			else if ( hasCounts ) 
#endif
#if GENERIC || ! #counts(NONE)
				state = BEFORE_COUNT;
			count = -1;
#endif

#if GENERIC
			if ( hasSkips && ( numberOfDocumentRecord & quantumModuloMask ) == 0 ) state = BEFORE_TOWER;
#elif SKIPS
			if ( ( numberOfDocumentRecord & quantumModuloMask ) == 0 ) state = BEFORE_TOWER;
#endif

			return currentDocument;
		}

#if GENERIC || SKIPS
		/** Reads the entire skip tower for the current position. 
		 */
		private void readTower() throws IOException {
			readTower( -1 );
		}

		/** Reads the skip tower for the current position, possibly skipping part of the tower. 
		 * 
		 * <P>Note that this method will update {@link #state} only if it reads the entire tower,
		 * otherwise the state remains {@link #BEFORE_TOWER}.
		 * 
		 * @param pointer the tower will be read up to the first entry smaller than or equal to this pointer; use
		 * -1 to guarantee that the entire tower will be read.
		 */

		private void readTower( final int pointer ) throws IOException {
			int i, j, k, cacheOffset, cache, towerLength = 0;
			long bitsAtTowerStart = 0;
			boolean truncated = false;

			if ( ASSERTS ) assert numberOfDocumentRecord % quantum == 0;
			if ( ASSERTS && state != BEFORE_TOWER ) throw new IllegalStateException( "readTower() called in state " + state );
			
			cacheOffset = ( numberOfDocumentRecord & wModuloMask );
			k = cacheOffset >> quantumDivisionShift;
			if ( ASSERTS && k == 0 ) { // Invalidate current tower data
				it.unimi.dsi.fastutil.ints.IntArrays.fill( pointerSkip, Integer.MAX_VALUE );
				it.unimi.dsi.fastutil.longs.LongArrays.fill( bitSkip, Integer.MAX_VALUE );
			}
			
			// Compute the height of the current skip tower.
			s = ( k == 0 )? height : Fast.leastSignificantBit( k );
			
			cache = frequency - w * ( numberOfDocumentRecord >> wDivisionShift );
			if ( cache < w ) {
				maxh = Fast.mostSignificantBit( ( cache >> quantumDivisionShift ) - k );
				if ( maxh < s ) {
					s = maxh;
					truncated = true;
				} else truncated = false;
			}
			else {
				cache = w;
				maxh = height;
				truncated = k == 0;
			}

			//assert w == cache || k == 0 || lastMaxh == Fast.mostSignificantBit( k ^ ( cache/quantum ) )  : lastMaxh +","+ (Fast.mostSignificantBit( k ^ ( cache/quantum ) ));
			
			i = s;

			if ( s >= 0 ) {
				if ( k == 0 ) {
					if ( quantumBitLength < 0 ) { 
						quantumBitLength = ibs.readDelta();
						entryBitLength = ibs.readDelta();
					}
					else {
						quantumBitLength += Fast.nat2int( ibs.readDelta() ); 
						entryBitLength += Fast.nat2int( ibs.readDelta() );
					}
					if ( DEBUG ) System.err.println( "{" + this + "} quantum bit length=" + quantumBitLength + " entry bit length=" + entryBitLength );
				}

				if ( DEBUG ) System.err.println( "{" + this + "} Reading tower; pointer=" + pointer + " maxh=" + maxh + " s=" + s );
				
				if ( s > 0 ) {
					towerLength = entryBitLength * ( s + 1 ) + Fast.nat2int( ibs.readDelta() );
					if ( DEBUG ) System.err.println( "{" + this + "} Tower length=" + towerLength );
				}
			
				// We store the number of bits read at the start of the tower (just after the length).
				bitsAtTowerStart = ibs.readBits();
				
				if ( truncated ) {
					if ( DEBUG ) System.err.println( "{" + this + "} Truncated--reading tops" );
					// We read the tower top.
					pointerSkip[ s ] = Fast.nat2int( ibs.readGolomb( towerTopB[ s ], towerTopLog2B[ s ] ) ) + pointerPrediction[ s ];
					bitSkip[ s ] = quantumBitLength * ( 1 << s ) + entryBitLength * ( ( 1 << s + 1 ) - s - 2 ) + Fast.nat2int( ibs.readLongDelta() );
				}
				else {
					// We copy the tower top from the lowest inherited entry suitably updated.
					pointerSkip[ s ] = pointerSkip[ s + 1 ] - ( currentDocument - pointerAtLastSkipTower );
					bitSkip[ s ] = bitSkip[ s + 1 ] - ( bitsAtTowerStart - readBitsAtLastSkipTower ) - towerLength;
				}
				
				// We read the remaining part of the tower, at least until we point after pointer.
				if ( currentDocument + pointerSkip[ i ] > pointer ) {
					for( i = s - 1; i >= 0; i-- ) {
						pointerSkip[ i ] = Fast.nat2int( ibs.readGolomb( towerLowerB[ i ], towerLowerLog2B[ i ] ) ) + pointerSkip[ i + 1 ] / 2;
						bitSkip[ i ] = ( bitSkip[ i + 1 ] - entryBitLength * ( i + 1 ) ) / 2 - Fast.nat2int( ibs.readLongDelta() );
						if ( DEBUG && currentDocument + pointerSkip[ i ] <= pointer ) System.err.println( "{" + this + "} stopping reading at i=" + i + " as currentDocument (" + currentDocument + ") plus pointer skip (" + pointerSkip[ i ] + ") is smaller than or equal target (" + pointer +")" );
						if ( currentDocument + pointerSkip[ i ] <= pointer ) break;
					}
				}
			}

			/* If we did not read the entire tower, we need to fix the skips we read (as they
			 * are offsets from the *end* of the tower) and moreover we must make unusable the
			 * rest of the tower (for asserts). */
			if ( i > 0 ) {
				final long fix = ibs.readBits() -  bitsAtTowerStart;
				for( j = s; j >= i; j-- ) bitSkip[ j ] += towerLength - fix;
				if ( ASSERTS ) for( ; j >= 0; j-- ) pointerSkip[ j ] = Integer.MAX_VALUE;
			}
			else 
#if GENERIC			
				state = hasPayloads ? BEFORE_PAYLOAD : hasCounts ? BEFORE_COUNT : BEFORE_POINTER;
#elif PAYLOADS
				state = BEFORE_PAYLOAD;
#elif ! #counts(NONE)
				state = BEFORE_COUNT;
#else
				state = BEFORE_POINTER;
#endif

			// We update the inherited tower.
			final long deltaBits = ibs.readBits() - readBitsAtLastSkipTower;
			final int deltaPointers = currentDocument - pointerAtLastSkipTower;

			for( j = Fast.mostSignificantBit( k ^ ( cache >> quantumDivisionShift ) ); j >= s + 1; j-- ) {
				bitSkip[ j ] -= deltaBits;
				pointerSkip[ j ] -= deltaPointers;
			}
			
			readBitsAtLastSkipTower = ibs.readBits();
			pointerAtLastSkipTower = currentDocument;
			
			lowest = i < 0 ? 0 : i;

			if ( DEBUG ) {
				System.err.println( "{" + this + "} " + "Computed skip tower (lowest: " + lowest + ") for document record number " + numberOfDocumentRecord + " (pointer " + currentDocument + ") from " + Math.max( i , 0 ) + ": " );
				System.err.print( "% " );
				for( j = 0; j <= s; j++ ) System.err.print( pointerSkip[ j ] + ":" + bitSkip[ j ] + " " );
				System.err.print( " [" );
				for( ; j <= height; j++ ) System.err.print( pointerSkip[ j ] + ":" + bitSkip[ j ] + " " );
				System.err.print( "]" );
				System.err.println();
			}
		}

		/*
		public int skip( final int n ) throws IOException {
			int i, k, cacheOffset, start = numberOfDocumentRecord, skip = 0;

			if ( DEBUG ) System.err.println( "{" + this + "} " + "Going to enter linear skip code with lastDoc=" + currentDocument + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", n=" + n + ", endOfList()=" + endOfList() );
			if ( n < 0 ) throw new IllegalArgumentException();
			if ( n == 0 ) return 0;
			
			// If we are just at the start of a list, let us read the first pointer.
			if ( numberOfDocumentRecord == -1 ) readDocumentPointer();
			if ( state == BEFORE_TOWER ) readTower( -1 ); 

			if ( DEBUG ) System.err.println( "{" + this + "} " + "Entering skip code with lastDoc=" + currentDocument + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", n=" + n + ", endOfList()=" + endOfList() );

			for(;;) {
				if ( DEBUG ) System.err.println( "{" + this + "} " + "In for loop, lastDoc=" + currentDocument + ", maxh=" + maxh + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", n=" + n );

				cacheOffset = ( numberOfDocumentRecord & wModuloMask );
				k = cacheOffset >> quantumDivisionShift;

				if ( maxh < 0 ) break; // Defective quantum--no tower.

				for( i = Fast.mostSignificantBit( k ^ ( Math.min( w, frequency - numberOfDocumentRecord + cacheOffset ) >> quantumDivisionShift ) ); i >= 0; i-- )
					if ( ( skip = ( ( k & - ( 1 << i ) ) + ( 1 << i ) ) * quantum - cacheOffset ) <= n ) break;
				
				if ( i >= 0 ) {
					ibs.skip( bitSkip[ i ] - ( ibs.readBits() - readBitsAtLastSkipTower ) );
					state = BEFORE_TOWER;
					currentDocument = pointerSkip[ i ] + pointerAtLastSkipTower;
					numberOfDocumentRecord += skip;
					// If we skipped beyond the end of the list, we invalidate the current document.
					if ( numberOfDocumentRecord == frequency ) currentDocument = -1;
					readTower( -1 );
					count = -1; // We must invalidate count as readDocumentPointer() would do.
					if ( endOfList() ) return numberOfDocumentRecord - start;
				}
				else break;
			}

			if ( DEBUG ) System.err.println( "{" + this + "} " + "Completing sequentially, lastDoc=" + currentDocument + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", n=" + n );

			while( numberOfDocumentRecord - start < n ) {
				if ( endOfList() ) break;
				readDocumentPointer();
			}
			return numberOfDocumentRecord - start;
		}
	*/	
		

#endif
		
		public int skipTo( final int p ) throws IOException {
			if ( DEBUG ) System.err.println( this + ".skipTo(" + p + ") [currentDocument=" + currentDocument + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", endOfList()=" + endOfList() );
			
			// If we are just at the start of a list, let us read the first pointer.
			if ( numberOfDocumentRecord == -1 ) nextDocument(); // TODO: shouldn't we just read the tower?
			
			if ( currentDocument >= p ) {
				if ( DEBUG ) System.err.println( this + ": No skip necessary, returning " + currentDocument );
				return currentDocument; 
			}

#if GENERIC
			if ( hasSkips ) {
#endif
#if GENERIC || SKIPS

				if ( state == BEFORE_TOWER ) readTower( p );

				final int[] pointerSkip = this.pointerSkip;

				for(;;) {
					if ( ASSERTS ) assert maxh < 0 || lowest > 0 || pointerSkip[ 0 ] != Integer.MAX_VALUE;

					// If on a defective quantum (no tower) or p is inside the current quantum (no need to scan the tower) we bail out. 
					if ( maxh < 0 || lowest == 0 && pointerAtLastSkipTower + pointerSkip[ 0 ] > p ) break;

					if ( DEBUG ) System.err.println( this + ": In for loop, currentDocument=" + currentDocument + ", maxh=" + maxh + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", p=" + p );

					final int cacheOffset = ( numberOfDocumentRecord & wModuloMask );
					final int k = cacheOffset >> quantumDivisionShift;
					final int top = Fast.mostSignificantBit( k ^ ( Math.min( w, frequency - numberOfDocumentRecord + cacheOffset ) >> quantumDivisionShift ) );

					int i;

					for( i = lowest; i <= top; i++ ) {
						if ( ASSERTS && ( k & 1 << i ) != 0 ) assert pointerSkip[ i ] == pointerSkip[ i + 1 ];
						if ( ASSERTS ) assert pointerSkip[ i ] != Integer.MAX_VALUE : "Invalid pointer skip " + i + " (lowest=" + lowest + ", top=" + top + ")";
						if ( pointerAtLastSkipTower + pointerSkip[ i ] > p ) break;
					}

					if ( --i < 0 ) break;

					if ( ASSERTS ) assert i >= lowest : i + " < " + lowest;

					if ( DEBUG ) System.err.println( this + ": Safely after for with i=" + i + ", P[i]=" + pointerSkip[i] + ", A[i]=" + bitSkip[i] );
					if ( DEBUG ) System.err.println( this + ": [" + ibs.readBits() + "] Skipping " + ( bitSkip[ i ] - ( ibs.readBits() - readBitsAtLastSkipTower ) ) + " bits (" + ( ( ( k & - ( 1 << i ) ) + ( 1 << i ) ) * quantum - cacheOffset ) + " records) to get to document pointer " + ( currentDocument + pointerSkip[ i ] ) );

					ibs.skip( bitSkip[ i ] - ( ibs.readBits() - readBitsAtLastSkipTower ) );
					state = BEFORE_TOWER;
					currentDocument = pointerSkip[ i ] + pointerAtLastSkipTower;
					numberOfDocumentRecord += ( ( k & - ( 1 << i ) ) + ( 1 << i ) ) * quantum - cacheOffset;
					// If we skipped beyond the end of the list, we invalidate the current document.
					if ( numberOfDocumentRecord == frequency ) {
						currentDocument = Integer.MAX_VALUE;
						state = BEFORE_POINTER; // We are actually before a frequency, but we must avoid that calls to nextDocument() read anything
					}
					else readTower( p ); // Note that if we are exactly on the destination pointer, we will read the entire tower.
					count = -1; // We must invalidate count as readDocumentPointer() would do.
					if ( endOfList() ) {
						if ( DEBUG ) System.err.println( this + ".toSkip(): end-of-list, returning " + currentDocument );
						// Note that if p == Integer.MAX_VALUE, we are certainly beyond end-of-list
						return p == Integer.MAX_VALUE ? Integer.MAX_VALUE : currentDocument;
					}
				}

				if ( DEBUG ) System.err.println( this + ": Completing sequentially, currentDocument=" + currentDocument + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", p=" + p );
#endif
#if GENERIC
			}
#endif

			while( currentDocument < p ) {
				if ( DEBUG ) System.err.println( this + ": Skipping sequentially (second), currentDocument=" + currentDocument + ", numberOfDocumentRecord=" + numberOfDocumentRecord + ", p=" + p );

				if ( nextDocument() == -1 ) {
					if ( DEBUG ) System.err.println( this + ": end-of-list, returning MAX_VALUE" );
					return Integer.MAX_VALUE;
				}
			}

			if ( DEBUG ) System.err.println( this + ".toSkip(): Returning " + currentDocument );
			return currentDocument;
		}

		public void dispose() throws IOException {
			parent.close();
		}

		public boolean hasNext() {
			return ! endOfList();
		}
		
		public int nextInt() {
			if ( ! hasNext() ) throw new NoSuchElementException();
			try {
				return nextDocument();
			}
			catch ( IOException e ) {
				throw new RuntimeException( e );
			}
		}
		
		public String toString() {
			return index + " [" + currentTerm + "]";
		}

		/** An interval iterator returning the positions of the current document as singleton intervals. */
		private final class IndexIntervalIterator extends AbstractObjectIterator<Interval> implements IntervalIterator {
			int pos = -1;			

			public void reset() throws IOException {
				pos = -1;
				if ( state <= BEFORE_POSITIONS ) updatePositionCache(); // This guarantees the position cache is ok 
			}

			public void intervalTerms( final IntSet terms ) {
				terms.add( BitStreamIndexReaderIndexIterator.this.currentTerm );
			}

			public boolean hasNext() {
				return pos < count - 1;
			}
			
			public Interval next() {
				if ( ! hasNext() ) throw new NoSuchElementException();
				return Interval.valueOf( positionCache[ ++pos ] );
			}
			
			public Interval nextInterval() {
				return pos < count - 1 ? Interval.valueOf( positionCache[ ++pos ] ) : null; 
			}
			
			public int extent() {
				return 1;
			}
			
			public String toString() {
				return index + ": " + term + "[doc=" + currentDocument + ", count=" + count + ", pos=" + pos + "]";
			}
		};

		public Reference2ReferenceMap<Index,IntervalIterator> intervalIterators() throws IOException {
			intervalIterator();
			return singletonIntervalIterator;
		}

		public IntervalIterator intervalIterator() throws IOException {
			return intervalIterator( keyIndex );
		}

		public IntervalIterator intervalIterator( final Index index ) throws IOException {
			if ( ASSERTS ) ensureCurrentDocument();
			// TODO: this was if ( index != keyIndex || hasPayloads ) 
			if ( index != keyIndex ) return IntervalIterators.TRUE;
			if ( ASSERTS ) assert intervalIterator != null;
			intervalIterator.reset();
			return intervalIterator;
		}
		
		public ReferenceSet<Index> indices() {
			return index.singletonSet;
		}
	}
	
	private IndexIterator documents( final CharSequence term, final int termNumber ) throws IOException {
		indexIterator.term( term );
		indexIterator.position( termNumber );
		return indexIterator;
	} 
	
	public IndexIterator documents( final int term ) throws IOException {
		return documents( null, term );
	}
	
	public IndexIterator documents( final CharSequence term ) throws IOException {
		if ( closed ) throw new IllegalStateException( "This " + getClass().getSimpleName() + " has been closed" );
		if ( index.termMap != null ) {
			final int termIndex = (int)index.termMap.getLong( term );
			if ( termIndex == -1 ) return index.emptyIndexIterator;
			return documents( term, termIndex );
		}
		
		throw new UnsupportedOperationException( "Index " + index + " has no term map" );
	}

 	@Override
 	public IndexIterator nextIterator() throws IOException {
 		return indexIterator.advance();
 	}
 
	public String toString() {
		return getClass().getSimpleName() + "[" + index + "]";
	}
	
	public void close() throws IOException {
		super.close();
		indexIterator.ibs.close();
	}
	
}

#else
"Mismatch in specified directives. First of all, you must define CLASSNAME."
"Then, you must either just define GENERIC, or the full range of assertions"
"(#frequencies, #pointers, #counts, #positions); optionally, you can define"
"SKIPS and PAYLOADS."
#endif