import java.io.*;

/**
 This class is a buffered output stream that allows for users to easily write
 bits and bytes to the underlying stream.  All methods use computer arithmetic
 to maipulate the bits, and have a default buffer of 64 bits (long).

 <pre>
 Usage: Identical to the BufferedOutputStream.
 	ie.  BitOutputStream out = new BitOutputStream(new FileOutputStream(file));
 </pre>

 @version		0.1, 11/09/04
 @author 		Winson Chung
 */
public class BitOutputStream extends OutputStream {

	/** The output stream to write to. */
	private BufferedOutputStream out;
	/** The 'long' buffer that stores the bits. */
	protected long buf;
	/** A 'long' is represented by 64 bits, thus the length of the buffer is 64 bits. */
	protected int bufLength = 64;
	/** The current location in the buffer. */
	protected int count;
	/** The reduce arrays used to reduce large values. */
	protected long[] byteLReduce, outReduce;

	/** Initialize all variables needed for this stream.
	 	@param os the OutputStream to write to. */
	public BitOutputStream(OutputStream os) {
		// init vars
		buf 	= 0L;
		count 	= 0;
		out 	= new BufferedOutputStream(os);

		// build other reduce arrays (used for overflow handling)
		byteLReduce = lReduce(8, 0);

		// build the array to reduce output
		//  	ie. 0xFF0000..0, 0x00FF000..0, ...
		outReduce = new long[8];
		for (int i = 0; i < 8; i++)
			outReduce[i] = (long) ((long)255 << (i*8));
	}

	/** Creates an array of left-aligned reduce int values.  From 'start' to
	 	'end', including 'end'.  'start' MUST be > 'end'.
	  		ie. 10000000, 11000000, 11100000, ... , 11111111
	  	@param length the length of the array to be made. */
	private long[] lReduce(int start, int end) {
		if (start <= end)
			return new long[0];

		long[] red = new long[start-end];
		for (int i = (start-1); i >= end; i--) {
			red[start-(i+1)] |= ((long)1 << i);
			if (i > end)
				red[start-(i)] = red[start-(i+1)];
		}
		return red;
	}

	/** Closes this output stream and releases any system resources associated
	 	with this stream. */
	public void close() throws IOException {
		this.flush();
		out.flush();
		out.close();
	}

	/** Flushes this output stream and forces any buffered output bytes to be
	 	written out. */
	public void flush() throws IOException {
		this.writeBufferOut();
	}

	/** Writes the buffer to the output stream specified. */
	private void writeBufferOut() throws IOException {
		byte len 		= (byte) Math.ceil(count/8.0);
		byte[] bytesOut = new byte[len];

		for (byte i = 0; i < len; i++)
			bytesOut[i] = (byte) ((buf & outReduce[8-i-1]) >> ((8-i-1) * 8));

		out.write(bytesOut, 0, len);
		buf   		= 0L;
		count 		= 0;
	}

	/** Writes b.length bytes from the specified byte array to this output
	 	stream.

	 	@param b the byte array to be written. */
	public void write(byte[] b) throws IOException {
		this.writeBytes(b, 0, b.length);
	}


	/** Writes the specified byte to this output stream.

	 	@param b the byte to be written. */
	public void write(int b) throws IOException {
		this.writeByte((byte) b);
	}

    /** Writes len bytes from the specified byte array starting at offset off to
        this output stream.

	 	@param b the byte array to be written.
		@param off the offset from the beginning of the array.
	 	@param len the number of bytes of the array to be written. */
	public void write(byte[] b, int off, int len) throws IOException {
		this.writeBytes(b, off, len);
	}

	/** Writes len bytes from the specified byte array starting at offset off
	 	to this output stream.

	 	@param b the byte array to be written.
		@param off the offset from the beginning of the array.
	 	@param len the number of bytes of the array to be written. */
	public void writeBytes(byte[] b, int off, int len) throws IOException {
		if (b == null)
			throw new NullPointerException();
		if ((off + len > b.length) || (off < 0) || (len < 0))
			throw new IndexOutOfBoundsException();
		for (int i = off; i < len; i++)
			this.writeByte(b[i]);
	}

	/** Writes a UNSIGNED byte to the buffer.  If the buffer is full,
	 	then it will be	written to the specified output stream.
	 	@param a the byte to be written. */
	public void writeByte(byte a) throws IOException {
		long b	 		= a & 0xFF;
		byte byteLength = 8,
			 start 		= (byte) (bufLength - count - 1),
			 end 		= (byte) (bufLength - (count + byteLength)),
			 total 		= (byte) (count + byteLength);
		if (total <= bufLength) {
			long byteVal = (b << end);
			buf   |= byteVal;
			count += byteLength;
			if (count == bufLength)
				this.writeBufferOut();
		}else if (total > bufLength) {
			// toZero -> # of bits before zero
			// zeroTo -> # of bits after zero
			byte toZero = (byte) (bufLength - count),
				 zeroTo = (byte) (byteLength - toZero);
			long toZeroHigh = (((b & byteLReduce[toZero-1]) >> zeroTo)),
				 zeroToLow 	= (b & (byteLReduce[toZero-1] ^ 0xFF));
			buf 	|= toZeroHigh;
			this.writeBufferOut();
			buf		= (b << (bufLength - zeroTo));
			count 	= zeroTo;
		}
	}

	/** Writes a specified bit to the buffer, and if needed, the output stream
	 	specified.  If boolean 'b' is true, 1 is written, 0 otherwise.
	 	@param b the bit to be written. */
	public void writeBit(boolean b) throws IOException {
		// only do shift arithmetic if '1' bit.
		if (b) {
			byte shift 	= (byte) (bufLength - count - 1);
			buf 	  	|= ((long)1 << shift);
		}
		count++;
		if (count >= bufLength)
			this.writeBufferOut();
	}

	/** Writes a specified bit to the buffer, and if needed, the output stream
	 	specified.  If byte 'b' is == 0, bit -> 0, If byte 'b' is != 0, bit -> 1.
	 	@param b the byte that represents the bit to be written.  See method description. */
	public void writeBit(byte b) throws IOException {
		if (b == 0)
			this.writeBit(false);
		else
			this.writeBit(true);
	}

	/** Writes a series of bits to the buffer, and if needed, the output stream
		specified.

		@param b the boolean array representing the bits from left to right.
		@param off the offset from the beginning of the array.
	 	@param len the number of bits of the array to be written. */
	public void writeBits(boolean[] b, int off, int len) throws IOException {
		if (b == null)
			throw new NullPointerException();
		if ((off + len > b.length) || (off < 0) || (len < 0))
			throw new IndexOutOfBoundsException();
		for (int i = off; i < len; i++)
			this.writeBit(b[i]);
	}

	/** Writes a series of bits to the buffer, and if needed, the output stream
		specified.  This method ONLY accepts String representations of bits.
	 		ie. "010010111"
	 	To write a general String, use the writeString() method.

	 	@param str the String to be written.
	 	@param off the offset from the beginning of the String.
	 	@param len the number of characters of the String to be written. */
	public void writeBits(String str, int off, int len) throws IOException {
		if (str == null)
			throw new NullPointerException();
		if ((off + len > str.length()) || (off < 0) || (len < 0))
			throw new IndexOutOfBoundsException();
		for (int i = off; i < len; i++) {
			char cur = str.charAt(i);
			if (cur == '1')
				this.writeBit(true);
			else if (cur == '0')
				this.writeBit(false);
			else
				throw new IOException ("Malformed binary string.");
		}
	}

	/** Writes an int to the buffer, and if needed, the output stream specified.
	 	@param i the int to be written. */
	public void writeInt(int i) throws Exception {
		byte val 	= (byte) ((i & (0xFF000000)) >> 24);
		this.writeByte(val);
		val 		= (byte) ((i & (0x00FF0000)) >> 16);
		this.writeByte(val);
		val 		= (byte) ((i & (0x0000FF00)) >> 8);
		this.writeByte(val);
		val 		= (byte) ((i & (0x000000FF)));
		this.writeByte(val);
	}

	/** Writes a long to the buffer and/or output stream.
	 	@param l the long to be written. */
	public void writeLong(long l) throws Exception {
		byte val = 0;
		for (int i = 7; i >= 0; i--) {
			val = (byte) ((l & outReduce[i]) >> (8*i));
			this.writeByte(val);
		}
	}

	/** Writes a String to the buffer, in char form.
	 	@param str the String to be written.
	 	@param off the offset from the beginning of the String.
	 	@param len the number of characters of the String to be written. */
	public void writeString(String str, int off, int len) throws Exception {
		if (str == null)
			throw new NullPointerException();
		if ((off + len > str.length()) || (off < 0) || (len < 0))
			throw new IndexOutOfBoundsException();
		for (int i = off; i < len; i++)
			this.writeByte((byte) str.charAt(i));
	}

	/** Returns a String representation of the state of the current buffer in
	 	binary form, as well as any variables associated with the buffer. */
	public String toString() {
		String lval = Long.toBinaryString(buf);
		for (int i = lval.length(); i < bufLength; i++)
			lval = '0' + lval;
		lval = lval.substring(0, count) + "^" + lval.substring(count);
		return ("Buffer (" + bufLength + "): " + lval + "\n\tCount: " + count);
	}
}