class BitStream {

    public BitStream () {

	_array = new int[1];

    }

    public BitStream (int[] array) {

	_array = copyArray(array);

	// Assume all bits in the array are meaningful.
	_currentWriteIndex = _array.length * _bitsPerInt;

    }

    protected static int[] copyArray (int[] original) {

	int[] duplicate = new int[original.length];
	for (int i = 0; i < original.length; i++) {
	    duplicate[i] = original[i];
	}

	return duplicate;

    }

    // Expand the array.
    protected void expandArray () {

	int[] newArray = new int[_array.length + 1];
	for (int index = 0; index < _array.length; index++) {

	    newArray[index] = _array[index];

	}

	_array = newArray;

    }

    // Add a single bit to the stream.
    protected void addBit (int bitValue) {

	// Expand the array if needed.
	if ((_currentWriteIndex % _bitsPerInt) == 0) {
	    expandArray();
	}

	// Calculate the index of the current int in the array.
	int arrayIndex = _currentWriteIndex / _bitsPerInt;

	// Calculate the index of the current bit within that int.
	int bitIndex = _currentWriteIndex % _bitsPerInt;

	// Set the bit.
	_array[arrayIndex] = (bitValue << bitIndex) | _array[arrayIndex];

	_currentWriteIndex++;

    }

    // Add a sequence of bits to the end of the stream.
    public void addBits (int bitValues, int numberOfBits) {

	if ((numberOfBits < 0) || (numberOfBits > 32)) {

	    System.out.println("Invalid number of bits to add: " +
			       numberOfBits);
	    System.exit(1);

	}

	// Loop through the bits to be added.
	for (int currentBitIndex = numberOfBits - 1;
	     currentBitIndex >= 0;
	     currentBitIndex--) {

	    // Grab the bit.
	    int currentBit = (bitValues >>> currentBitIndex) & 1;

	    // Add it.
	    addBit(currentBit);

	}

    }

    // Read the next bit from the stream.
    protected int readBit () {

	// If we've gone beyond the end, abort.
	if (_currentReadIndex == _currentWriteIndex) {

	    System.out.println("Bit stream ended.");
	    System.exit(1);

	}

	// Calculate the index of the current int in the array.
	int arrayIndex = _currentReadIndex / _bitsPerInt;

	// Calculate the index of the current bit within that int.
	int bitIndex = _currentReadIndex % _bitsPerInt;

	// Read the bit.
	int returnBit = (_array[arrayIndex] >>> bitIndex) & 1;

	_currentReadIndex++;
	return returnBit;

    }

    // Read a sequence of bits from the stream.
    public int readBits (int numberOfBits) {

	if ((numberOfBits < 0) || (numberOfBits > 32)) {

	    System.out.println("Invalid number of bits to read: " +
			       numberOfBits);
	    System.exit(1);

	}

	// Loop through the bits to be read.
	int returnBits = 0;
	for (int currentBitIndex = 0;
	     currentBitIndex < numberOfBits;
	     currentBitIndex++) {

	    // Add the next bit.
	    returnBits = (returnBits << 1) | readBit();

	}

	return returnBits;

    }

    public void resetReadIndex () {

	_currentReadIndex = 0;

    }

    public int[] toIntArray () {

	return copyArray(_array);

    }

    protected int[] _array;
    protected int _currentWriteIndex;
    protected int _currentReadIndex;
    protected final static int _bitsPerInt = 32;

}