inputbitstream.java

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

	/** Reads a natural number in a limited range using a minimal binary coding.
	 *
	 * @param b a strict upper bound.
	 * @return the next minimally binary encoded natural number.
	 * @throws IllegalArgumentException if you try to read a negative number or use a nonpositive base.
	 * @see OutputBitStream#writeMinimalBinary(int, int)
	 */

	public int readMinimalBinary( final int b ) throws IOException {
		return readMinimalBinary( b, Fast.mostSignificantBit( b ) );
	}

	/** Reads a natural number in a limited range using a minimal binary coding.
	 *
	 * This method is faster than {@link #readMinimalBinary(int)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * @param b a strict upper bound.
	 * @param log2b the floor of the base-2 logarithm of the bound.
	 * @return the next minimally binary encoded natural number.
	 * @throws IllegalArgumentException if you try to read a negative number or use a nonpositive base.
	 * @see OutputBitStream#writeMinimalBinary(int, int)
	 */

	public int readMinimalBinary( final int b, final int log2b ) throws IOException {
		if ( b < 1 ) throw new IllegalArgumentException( "The bound " + b + " is not positive" );

		final int m = ( 1 << log2b + 1 ) - b; 
		final int x = readInt( log2b );

		if ( x < m ) return x;
		else return ( ( x << 1 ) + readBit() - m );
	}

	/** Reads a long natural number in a limited range using a minimal binary coding.
	 *
	 * @param b a strict upper bound.
	 * @return the next minimally binary encoded long natural number.
	 * @throws IllegalArgumentException if you try to read a negative number or use a nonpositive base.
	 * @see OutputBitStream#writeMinimalBinary(int, int)
	 */

	public long readLongMinimalBinary( final long b ) throws IOException {
		return readLongMinimalBinary( b, Fast.mostSignificantBit( b ) );
	}


	/** Reads a long natural number in a limited range using a minimal binary coding.
	 *
	 * This method is faster than {@link #readLongMinimalBinary(long)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * @param b a strict upper bound.
	 * @param log2b the floor of the base-2 logarithm of the bound.
	 * @return the next minimally binary encoded long natural number.
	 * @throws IllegalArgumentException if you try to read a negative number or use a nonpositive base.
	 * @see OutputBitStream#writeMinimalBinary(int, int)
	 */

	public long readLongMinimalBinary( final long b, final int log2b ) throws IOException {
		if ( b < 1 ) throw new IllegalArgumentException( "The bound " + b + " is not positive" );

		final long m = ( 1L << log2b + 1 ) - b; 
		final long x = readLong( log2b );

		if ( x < m ) return x;
		else return ( ( x << 1 ) + readBit() - m );
	}

	/** Reads a natural number in Golomb coding.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * nothing will be read, and 0 will be returned. 
	 *
	 * @param b the modulus for the coding.
	 * @return the next Golomb-encoded natural number.
	 * @throws IllegalArgumentException if you use a nonpositive modulus.
	 * @see OutputBitStream#writeGolomb(int, int)
	 */

	public int readGolomb( final int b ) throws IOException {
		return readGolomb( b, Fast.mostSignificantBit( b ) );
	}

	/** Reads a natural number in Golomb coding.
	 *
	 * This method is faster than {@link #readGolomb(int)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * nothing will be read, and 0 will be returned. 
	 *
	 * @param b the modulus for the coding.
	 * @param log2b the floor of the base-2 logarithm of the coding modulus.
	 * @return the next Golomb-encoded natural number.
	 * @throws IllegalArgumentException if you use a nonpositive modulus.
	 * @see OutputBitStream#writeGolomb(int, int)
	 */

	public int readGolomb( final int b, final int log2b ) throws IOException {
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) return 0;

		return readUnary() * b + readMinimalBinary( b, log2b );
	}



	/** Reads a long natural number in Golomb coding.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * nothing will be read, and 0 will be returned. 
	 *
	 * @param b the modulus for the coding.
	 * @return the next Golomb-encoded long natural number.
	 * @throws IllegalArgumentException if you use a nonpositive modulus.
	 * @see OutputBitStream#writeGolomb(int, int)
	 */

	public long readLongGolomb( final long b ) throws IOException {
		return readLongGolomb( b, Fast.mostSignificantBit( b ) );
	}

	/** Reads a long natural number in Golomb coding.
	 *
	 * This method is faster than {@link #readLongGolomb(long)} because it does not
	 * have to compute <code>log2b</code>.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * nothing will be read, and 0 will be returned. 
	 *
	 * @param b the modulus for the coding.
	 * @param log2b the floor of the base-2 logarithm of the coding modulus.
	 * @return the next Golomb-encoded long natural number.
	 * @throws IllegalArgumentException if you use a nonpositive modulus.
	 * @see OutputBitStream#writeGolomb(int, int)
	 */

	public long readLongGolomb( final long b, final int log2b ) throws IOException {
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) return 0;

		return readUnary() * b + readLongMinimalBinary( b, log2b );
	}

	/** Reads a natural number in skewed Golomb coding.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * nothing will be read, and 0 will be returned. 
	 *
	 * @param b the modulus for the coding.
	 * @return the next skewed Golomb-encoded natural number.
	 * @throws IllegalArgumentException if you use a negative modulus.
	 * @see OutputBitStream#writeSkewedGolomb(int, int)
	 */

	public int readSkewedGolomb( final int b ) throws IOException {
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) return 0;

		final int M = ( ( 1 << readUnary() + 1 ) - 1 ) * b;
		final int m = ( M / ( 2 * b ) ) * b;
		return m + readMinimalBinary( M - m );
	}


	/** Reads a long natural number in skewed Golomb coding.
	 *
	 * <P>This method implements also the case in which <code>b</code> is 0: in this case,
	 * nothing will be read, and 0 will be returned. 
	 *
	 * @param b the modulus for the coding.
	 * @return the next skewed Golomb-encoded long natural number.
	 * @throws IllegalArgumentException if you use a negative modulus.
	 * @see OutputBitStream#writeSkewedGolomb(int, int)
	 */

	public long readLongSkewedGolomb( final long b ) throws IOException {
		if ( b < 0 ) throw new IllegalArgumentException( "The modulus " + b + " is negative" );
		if ( b == 0 ) return 0;

		final long M = ( ( 1 << readUnary() + 1 ) - 1 ) * b;
		final long m = ( M / ( 2 * b ) ) * b;
		return m + readLongMinimalBinary( M - m );
	}


	/** Reads a natural number in &zeta; coding.
	 *
	 * @param k the shrinking factor.
	 * @return the next &zeta;-encoded natural number.
	 * @throws IllegalArgumentException if you use a nonpositive shrinking factor.
	 * @see OutputBitStream#writeZeta(int, int)
	 */

	public int readZeta( final int k ) throws IOException {
		if ( k < 1 ) throw new IllegalArgumentException( "The shrinking factor " + k + " is not positive" );

		if ( k == 3 ) {
			int preComp;
			if ( ( fill >= 16 || refill() >= 16 ) && ( preComp = ZETA_3[ current >> ( fill - 16 ) & 0xFFFF ] ) != 0 ) {
				readBits += preComp >> 16;
				fill -= preComp >> 16;
				return preComp & 0xFFFF;
			}
		}

		final int h = readUnary();
		final int left = 1 << h * k;
		final int m = readInt( h * k + k - 1 );
		if ( m < left ) return m + left - 1;
		return ( m << 1 ) + readBit() - 1;
	}

	/** Reads a long natural number in &zeta; coding.
	 *
	 * @param k the shrinking factor.
	 * @return the next &zeta;-encoded long natural number.
	 * @throws IllegalArgumentException if you use a nonpositive shrinking factor.
	 * @see OutputBitStream#writeZeta(int, int)
	 */

	public long readLongZeta( final int k ) throws IOException {
		if ( k < 1 ) throw new IllegalArgumentException( "The shrinking factor " + k + " is not positive" );

		if ( k == 3 ) {
			int preComp;
			if ( ( fill >= 16 || refill() >= 16 ) && ( preComp = ZETA_3[ current >> ( fill - 16 ) & 0xFFFF ] ) != 0 ) {
				readBits += preComp >> 16;
				fill -= preComp >> 16;
				return preComp & 0xFFFF;
			}
		}

		final int h = readUnary();
		final long left = 1L << h * k;
		final long m = readLong( h * k + k - 1 );
		if ( m < left ) return m + left - 1;
		return ( m << 1 ) + readBit() - 1;
	}


	/** Skips a given number of &zeta;-coded integers.
	 *
	 * <p>This method should be significantly quicker than iterating <code>n</code> times on
	 * {@link #readZeta(int)} or {@link #readLongZeta(int)}, as precomputed tables are used directly,
	 * so the number of method calls is greatly reduced, and the result is discarded, so
	 * {@link #skip(long)} can be invoked instead of more specific decoding methods.
	 * 
	 * 
	 * @param k the shrinking factor.
	 * @param n the number of &zeta;-coded integers to be skipped.
	 * @see #readZeta(int)
	 */

	public void skipZetas( final int k, int n ) throws IOException {
		int h, preComp;

		while( n-- != 0) {
			if ( k == 3 && ( fill >= 16 || refill() >= 16 ) && ( preComp = ZETA_3[ current >> ( fill - 16 ) & 0xFFFF ] >> 16 ) != 0 ) {
				readBits += preComp;
				fill -= preComp;
				continue;
			}

			h = readUnary();
			if ( readInt( h * k + k - 1 ) >= 1 << h * k ) skip( 1L );
		}
	}

	/** Reads a given number of &gamma;-coded integers.
	 * 
	 * <p>This method should be significantly quicker than iterating <code>n</code> times on
	 * {@link #readGamma()}, as precomputed tables are used directly,
	 * so the number of method calls is greatly reduced.
	 *
	 * @param k the shrinking factor.
	 * @param a an array of at least <code>count</code> integers where the result
	 * wil be written starting at the first position. 
	 * @param count the number of &zeta;-coded integers to be read.
	 * @see #readGamma()
	 */

	public void readZetas( final int k, final int[] a, final int count ) throws IOException {
		int h, left, m;
		int preComp;
		
		for( int i = 0; i < count; i++ ) {
			if ( k == 3 && ( fill >= 16 || refill() >= 16 ) && ( preComp = ZETA_3[ current >> ( fill - 16 ) & 0xFFFF ] ) != 0 ) {
				readBits += preComp >> 16;
				fill -= preComp >> 16;
				a[ i ] = preComp & 0xFFFF;
				continue;
			}

			h = readUnary();
			left = 1 << h * k;
			m = readInt( h * k + k - 1 );
			a[ i ] = m < left ? m + left - 1 : ( m << 1 ) + readBit() - 1;
		}
	}

	/** Reads a natural number in variable-length nibble coding.
	 *
	 * @return the next variable-length nibble-encoded natural number.
	 * @see OutputBitStream#writeNibble(int)
	 */

	public int readNibble() throws IOException {
		int b;
		int x = 0;

		do {
			x <<= 3;
			b = readBit();
			x |= readInt( 3 );
		} while( b == 0 );
		
		return x;
	}
	
	/** Reads a long natural number in variable-length nibble coding.
	 *
	 * @return the next variable-length nibble-encoded long natural number.
	 * @see OutputBitStream#writeNibble(int)
	 */

	public long readLongNibble() throws IOException {
		int b;
		long x = 0;

		do {
			x <<= 3;
			b = readBit();
			x |= readInt( 3 );
		} while( b == 0 );
		
		return x;
	}

	public boolean hasNext() {
		return true;
	}
	
	public boolean nextBoolean() {
		try {
			return readBit() != 0;
		}
		catch ( IOException e ) {
			throw new RuntimeException( e );
		}
	}
	
	/** Skips over the given number of bits.
	 * 
	 * @param n the number of bits to skip.
	 * @return the number of bits actually skipped.
	 * @deprecated This method is simply an expensive, try/catch-surrounded version
	 * of {@link #skip(long)} that is made necessary by the interface
	 * by {@link BooleanIterator}. 
	 */
	@Deprecated
	public int skip( final int n ) {
		try {
			return (int)skip( (long)n );
		}
		catch ( IOException e ) {
			throw new RuntimeException( e );
		}
	}
}