skipgammadeltagammadeltabitstreamindexreader.java

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

    state = BEFORE_COUNT;
   // 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;
		}
	*/
  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 ( 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 );
   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();
 }
}