it.unimi.dsi.mg4j.io
Class OutputBitStream

java.lang.Object
  extended byit.unimi.dsi.mg4j.io.OutputBitStream
Direct Known Subclasses:
DebugOutputBitStream

public class OutputBitStream
extends Object

Bit-level output stream.

IMPORTANT: In MG4J 0.6, this class has been completely rewritten. It is much faster, but there are also incompabilities. Mainly, unary representations are one-terminated sequences of zeroes.

This class wraps any OutputStream so that you can treat it as bit stream. Constructors and methods closely resemble those of OutputStream. Data can be added to such a stream in several ways: writing an integer or long in fixed-width, unary, γ, δ, ζ and Golomb coding, or providing a vector of bytes.

This class can also wrap a byte array; this is much more lightweight than wrapping a FastByteArrayOutputStream wrapping the array, but overflowing the array will cause an IOException.

Note that when writing using a vector of bytes bits are written in the natural way: the first bit is bit 7 of the first byte, the eightth bit is bit 0 of the first byte, the ninth bit is bit 7 of the second byte and so on. When writing integers using some coding, instead, the lower bits are considered for coding (in the fixed-width case, the given number of bits, otherwise the lower bits starting from the most significant one).

The bit stream format

The bit streams written by this class are big endian. That is, the first bit of the stream is bit 7 of the first byte, the eightth bit is bit 0 of the first byte, the ninth bit is bit 7 of the second byte and so on.

Blocks of bits (such as coded integers) are written starting from the most significant bit. In other words, if you take the first bytes of a stream and print them in binary you will see exactly the sequence of bits you have written. In particular, if you write 32-bit integers you will get a stream which is identical to the one produced by a DataOutput.

Additional features:

This class is not synchronised. If multiple threads access an instance of this class concurrently, they must be synchronised externally.

Since:
0.1
Author:
Sebastiano Vigna

Field Summary
static int DEFAULT_BUFFER_SIZE
          The default size of the byte buffer in bytes (16Ki).
 
Constructor Summary
protected OutputBitStream()
          This (non-public) constructor exists just to provide fake initialisation for classes such as DebugOutputBitStream.
  OutputBitStream(byte[] a)
          Creates a new output bit stream wrapping a given byte array.
  OutputBitStream(File file)
          Creates a new output bit stream writing to a file.
  OutputBitStream(File file, int bufSize)
          Creates a new output bit stream writing to file.
  OutputBitStream(OutputStream os)
          Creates a new output bit stream wrapping a given output stream using a buffer of size DEFAULT_BUFFER_SIZE.
  OutputBitStream(OutputStream os, int bufSize)
          Creates a new output bit stream wrapping a given output stream with a specified buffer size.
  OutputBitStream(String name)
          Creates a new output bit stream writing to a file.
  OutputBitStream(String name, int bufSize)
          Creates a new output bit stream writing to file.
 
Method Summary
 int align()
          Aligns the stream.
 void close()
          Closes the bit stream.
 void flush()
          Flushes the bit stream.
 void position(long position)
          Sets this stream bit position, if it is based on a RepositionableStream or on a FileChannel.
 int write(byte[] bits, int len)
          Writes a sequence of bits.
 int writeBit(boolean bit)
          Writes a bit.
 int writeBit(int bit)
          Writes a bit.
 int writeDelta(int x)
          Writes a natural number in δ coding.
 int writeDelta(long x)
          Deprecated. As of MG4J 0.2, replaced by writeLongDelta(long).
 int writeGamma(int x)
          Writes a natural number in γ coding.
 int writeGolomb(int x, int b)
          Writes a natural number in Golomb coding.
 int writeGolomb(int x, int b, int log2b)
          Writes a natural number in Golomb coding.
 int writeInt(int x, int len)
          Writes a fixed number of bits from an integer.
 int writeLong(long x, int len)
          Writes a fixed number of bits from a long.
 int writeLongDelta(long x)
          Writes a long natural number in δ coding.
 int writeLongGamma(long x)
          Writes a long natural number in γ coding.
 long writeLongGolomb(long x, long b)
          Writes a long natural number in Golomb coding.
 long writeLongGolomb(long x, long b, int log2b)
          Writes a long natural number in Golomb coding.
 int writeLongMinimalBinary(long x, long b)
          Writes a long natural number in a limited range using a minimal binary coding.
 int writeLongMinimalBinary(long x, long b, int log2b)
          Writes a long natural number in a limited range using a minimal binary coding.
 int writeLongNibble(long x)
          Writes a long natural number in variable-length nibble coding.
 long writeLongSkewedGolomb(long x, long b)
          Writes a long natural number in skewed Golomb coding.
 long writeLongUnary(long x)
          Writes a long natural number in unary coding.
 long writeLongZeta(long x, int k)
          Writes a long natural number in ζ coding.
 int writeMinimalBinary(int x, int b)
          Writes a natural number in a limited range using a minimal binary coding.
 int writeMinimalBinary(int x, int b, int log2b)
          Writes a natural number in a limited range using a minimal binary coding.
 int writeNibble(int x)
          Writes a natural number in variable-length nibble coding.
 int writeSkewedGolomb(int x, int b)
          Writes a natural number in skewed Golomb coding.
 int writeUnary(int x)
          Writes a natural number in unary coding.
 int writeZeta(int x, int k)
          Writes a natural number in ζ coding.
 long writtenBits()
          Returns the number of bits written to this bit stream.
 void writtenBits(long writtenBits)
          Sets the number of bits written to this bit stream.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_BUFFER_SIZE

public static final int DEFAULT_BUFFER_SIZE
The default size of the byte buffer in bytes (16Ki).

See Also:
Constant Field Values
Constructor Detail

OutputBitStream

protected OutputBitStream()
This (non-public) constructor exists just to provide fake initialisation for classes such as DebugOutputBitStream.


OutputBitStream

public OutputBitStream(OutputStream os)
Creates a new output bit stream wrapping a given output stream using a buffer of size DEFAULT_BUFFER_SIZE.

Parameters:
os - the output stream to wrap.

OutputBitStream

public OutputBitStream(OutputStream os,
                       int bufSize)
Creates a new output bit stream wrapping a given output stream with a specified buffer size.

Parameters:
os - the output stream to wrap.
bufSize - the size in byte of the buffer; it may be 0, denoting no buffering.

OutputBitStream

public OutputBitStream(byte[] a)
Creates a new output bit stream wrapping a given byte array.

Parameters:
a - the byte array to wrap.

OutputBitStream

public OutputBitStream(String name,
                       int bufSize)
                throws FileNotFoundException
Creates a new output bit stream writing to file.

Parameters:
name - the name of the file.
bufSize - the size in byte of the buffer; it may be 0, denoting no buffering.

OutputBitStream

public OutputBitStream(String name)
                throws FileNotFoundException
Creates a new output bit stream writing to a file.

Parameters:
name - the name of the file.

OutputBitStream

public OutputBitStream(File file,
                       int bufSize)
                throws FileNotFoundException
Creates a new output bit stream writing to file.

Parameters:
file - the file.
bufSize - the size in byte of the buffer; it may be 0, denoting no buffering.

OutputBitStream

public OutputBitStream(File file)
                throws FileNotFoundException
Creates a new output bit stream writing to a file.

Parameters:
file - the file.
Method Detail

flush

public void flush()
           throws IOException
Flushes the bit stream.

This method will align the stream, write the bit buffer, empty the byte buffer and delegate to the OutputStream.flush() method of the underlying output stream.

This method is provided so that users of this class can easily wrap repositionable streams (for instance, file-based streams, which can be repositioned using the underlying FileChannel).

It is guaranteed that after calling this method the underlying stream can be repositioned, and that the next write to the underlying output stream will start with the content of the first write method called afterwards.

Throws:
IOException

close

public void close()
           throws IOException
Closes the bit stream. All resources associated to the stream are released.

Throws:
IOException

writtenBits

public long writtenBits()
Returns the number of bits written to this bit stream.

Returns:
the number of bits written so far.

writtenBits

public void writtenBits(long writtenBits)
Sets the number of bits written to this bit stream.

This method is provided so that, for instance, the user can reset via writtenBits(0) the written-bits count after a flush().

Returns:
writtenBits the new value for the number of bits written so far.

align

public int align()
          throws IOException
Aligns the stream. After a call to this function, the stream is byte aligned. Zeroes are used to pad it if necessary.

Returns:
the number of padding bits.
Throws:
IOException

position

public void position(long position)
              throws IOException
Sets this stream bit position, if it is based on a RepositionableStream or on a FileChannel.

Given an underlying stream that implements RepositionableStream or that can provide a FileChannel via the getChannel() method, a call to this method has the same semantics of a flush(), followed by a call to position(position / 8) on the byte stream. Currently there is no clean, working way of supporting out-of-byte-boundary positioning.

Parameters:
position - the new position expressed as a bit offset; it must be byte-aligned.
Throws:
IllegalArgumentException - when trying to position outside of byte boundaries.
UnsupportedOperationException - if the underlying byte stream does not implement RepositionableStream and if the channel it returns is not a FileChannel.
IOException
See Also:
FileChannel.position(long)

write

public int write(byte[] bits,
                 int len)
          throws IOException
Writes a sequence of bits. Bits will be written in the natural way: the first bit is bit 7 of the first byte, the eightth bit is bit 0 of the first byte, the ninth bit is bit 7 of the second byte and so on.

Parameters:
bits - a vector containing the bits to be written.
len - a bit length.
Returns:
the number of bits written (len).
Throws:
IOException

writeBit

public int writeBit(boolean bit)
             throws IOException
Writes a bit.

Parameters:
bit - a bit.
Returns:
the number of bits written.
Throws:
IOException

writeBit

public int writeBit(int bit)
             throws IOException
Writes a bit.

Parameters:
bit - a bit.
Returns:
the number of bits written.
Throws:
IOException

writeInt

public int writeInt(int x,
                    int len)
             throws IOException
Writes a fixed number of bits from an integer.

Parameters:
x - an integer.
len - a bit length; this many lower bits of the first argument will be written (the most significant bit first).
Returns:
the number of bits written (len).
Throws:
IOException

writeLong

public int writeLong(long x,
                     int len)
              throws IOException
Writes a fixed number of bits from a long.

Parameters:
x - a long.
len - a bit length; this many lower bits of the first argument will be written (the most significant bit first).
Returns:
the number of bits written (len).
Throws:
IOException

writeUnary

public int writeUnary(int x)
               throws IOException
Writes a natural number in unary coding. Note that by unary coding we mean that 1 encodes 0, 01 encodes 1 and so on.

Parameters:
x - a natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number.
IOException

writeLongUnary

public long writeLongUnary(long x)
                    throws IOException
Writes a long natural number in unary coding.

Parameters:
x - a long natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you write to write a negative number.
IOException
See Also:
writeUnary(int)

writeGamma

public int writeGamma(int x)
               throws IOException
Writes a natural number in γ coding. The γ coding of a positive number of k bits is obtained writing k-1 in unary, followed by the lower k-1 bits of the number. The coding of a natural number is obtained by adding one and coding.

Parameters:
x - a natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you write to write a negative number.
IOException

writeLongGamma

public int writeLongGamma(long x)
                   throws IOException
Writes a long natural number in γ coding.

Parameters:
x - a long natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you write to write a negative number.
IOException
See Also:
writeGamma(int)

writeDelta

public int writeDelta(int x)
               throws IOException
Writes a natural number in δ coding. The δ coding of a positive number of k bits is obtained writing k-1 in γ coding, followed by the lower k-1 bits of the number. The coding of a natural number is obtained by adding one and coding.

Parameters:
x - a natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you write to write a negative number.
IOException

writeDelta

public int writeDelta(long x)
               throws IOException
Deprecated. As of MG4J 0.2, replaced by writeLongDelta(long).

Writes a long natural number in δ coding.

Parameters:
x - a long natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you write to write a negative number.
IOException
See Also:
writeDelta(int)

writeLongDelta

public int writeLongDelta(long x)
                   throws IOException
Writes a long natural number in δ coding.

Parameters:
x - a long natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you write to write a negative number.
IOException
See Also:
writeDelta(int)

writeMinimalBinary

public int writeMinimalBinary(int x,
                              int b)
                       throws IOException
Writes a natural number in a limited range using a minimal binary coding.

Parameters:
x - a natural number.
b - a strict upper bound for x.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a nonpositive base.
IOException

writeMinimalBinary

public int writeMinimalBinary(int x,
                              int b,
                              int log2b)
                       throws IOException
Writes a natural number in a limited range using a minimal binary coding. This method is faster than writeMinimalBinary(int,int) because it does not have to compute log2b.

Parameters:
x - a natural number.
b - a strict upper bound for x.
log2b - the floor of the base-2 logarithm of the bound.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a nonpositive base.
IOException

writeLongMinimalBinary

public int writeLongMinimalBinary(long x,
                                  long b)
                           throws IOException
Writes a long natural number in a limited range using a minimal binary coding.

Parameters:
x - a natural number.
b - a strict upper bound for x.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a nonpositive base.
IOException

writeLongMinimalBinary

public int writeLongMinimalBinary(long x,
                                  long b,
                                  int log2b)
                           throws IOException
Writes a long natural number in a limited range using a minimal binary coding. This method is faster than writeLongMinimalBinary(long,long) because it does not have to compute log2b.

Parameters:
x - a long natural number.
b - a strict upper bound for x.
log2b - the floor of the base-2 logarithm of the bound.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a nonpositive base.
IOException

writeGolomb

public int writeGolomb(int x,
                       int b)
                throws IOException
Writes a natural number in Golomb coding.

This method implements also the case in which b is 0: in this case, the argument x may only be zero, and nothing will be written.

Parameters:
x - a natural number.
b - the modulus for the coding.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a negative modulus.
IOException

writeGolomb

public int writeGolomb(int x,
                       int b,
                       int log2b)
                throws IOException
Writes a natural number in Golomb coding. This method is faster than writeGolomb(int,int) because it does not have to compute log2b.

This method implements also the case in which b is 0: in this case, the argument x may only be zero, and nothing will be written.

Parameters:
x - a natural number.
b - the modulus for the coding.
log2b - the floor of the base-2 logarithm of the coding modulus (it is irrelevant when b is zero).
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a negative modulus.
IOException

writeLongGolomb

public long writeLongGolomb(long x,
                            long b)
                     throws IOException
Writes a long natural number in Golomb coding.

This method implements also the case in which b is 0: in this case, the argument x may only be zero, and nothing will be written.

Parameters:
x - a long natural number.
b - the modulus for the coding.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a negative modulus.
IOException

writeLongGolomb

public long writeLongGolomb(long x,
                            long b,
                            int log2b)
                     throws IOException
Writes a long natural number in Golomb coding. This method is faster than writeLongGolomb(long,long) because it does not have to compute log2b.

This method implements also the case in which b is 0: in this case, the argument x may only be zero, and nothing will be written.

Parameters:
x - a long natural number.
b - the modulus for the coding.
log2b - the floor of the base-2 logarithm of the coding modulus (it is irrelevant when b is zero).
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a negative modulus.
IOException

writeSkewedGolomb

public int writeSkewedGolomb(int x,
                             int b)
                      throws IOException
Writes a natural number in skewed Golomb coding.

This method implements also the case in which b is 0: in this case, the argument x may only be zero, and nothing will be written.

Parameters:
x - a natural number.
b - the modulus for the coding.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a negative modulus.
IOException

writeLongSkewedGolomb

public long writeLongSkewedGolomb(long x,
                                  long b)
                           throws IOException
Writes a long natural number in skewed Golomb coding.

This method implements also the case in which b is 0: in this case, the argument x may only be zero, and nothing will be written.

Parameters:
x - a long natural number.
b - the modulus for the coding.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a negative modulus.
IOException

writeZeta

public int writeZeta(int x,
                     int k)
              throws IOException
Writes a natural number in ζ coding.

ζ coding (with modulo k) records positive numbers in the intervals [1,2k-1],[2k,2k+1-1],…,[2hk,2(h+1)k-1] by coding h in unary, followed by a minimal binary coding of the offset in the interval. The coding of a natural number is obtained by adding one and coding.

A detailed analysis of ζ codes is given in

Paolo Boldi and Sebastiano Vigna, The WebGraph Framework II: Codes for the World-Wide Web.

Parameters:
x - a natural number.
k - the shrinking factor.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a nonpositive shrinking factor.
IOException

writeLongZeta

public long writeLongZeta(long x,
                          int k)
                   throws IOException
Writes a long natural number in ζ coding.

Parameters:
x - a long natural number.
k - the shrinking factor.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number or use a nonpositive shrinking factor.
IOException

writeNibble

public int writeNibble(int x)
                throws IOException
Writes a natural number in variable-length nibble coding.

Variable-length nibble coding records a natural number by padding its binary representation to the left using zeroes, until its length is a multiple of three. Then, the resulting string is broken in blocks of 3 bits, and each block is prefixed with a bit, which is zero for all blocks except for the last one.

Parameters:
x - a natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number.
IOException

writeLongNibble

public int writeLongNibble(long x)
                    throws IOException
Writes a long natural number in variable-length nibble coding.

Parameters:
x - a long natural number.
Returns:
the number of bits written.
Throws:
IllegalArgumentException - if you try to write a negative number.
IOException