import java.util.*;
import java.io.*;

/**
 * A bit vector, that is, a data structure that represents an
 * arbitrarily long sequence of bits. This is a class with very
 * limited operations (basically only appending to the bit vector
 * and serializing it), designed with the needs of Huffman
 * encoding in mind.
 * 
 * @author David Matuszek 
 * @version 1
 */
public class BitVector implements Serializable {

    protected Vector vector =  new Vector(1000);
    protected long bitCount = 0;
    
    private static final boolean DEBUG = true;
    protected static int arraySize = 1000;
    private int array[];
    private int arrayIndex = 0;
    private int bitIndex = 0;
    
    /**
     * Adds a single bit, represented as a boolean, to this BitVector.
     */
    public void add(boolean bit) {
        
        // Create new array if needed, and put it in the vector
        if (arrayIndex == 0 && bitIndex == 0) {
            array = new int[arraySize];
            vector.add(array);
        }
        
        // Insert bit
        if (bit) array[arrayIndex] |= (1 << (31 - bitIndex));
        bitCount++;
        
        // Find location for next bit
        if (++bitIndex == 32) {
            bitIndex = 0;
            if (++arrayIndex == arraySize) {
                arrayIndex = 0;
            }
        }
    }
    
    /**
     * Adds a single bit, represented as a '0' or '1' character,
     * to this BitVector.
     */
    public void add(char ch) {
        if (ch == '0') add(false);
        else if (ch == '1') add(true);
        else throw new IllegalArgumentException("Not a binary digit: " + ch);
    }
    
    /**
     * Adds a String of bits to this BitVector, where the characters '0'
     * and '1' represent the bits 0 and 1, respectively.
     */
    public void add(String string) {
        for (int i = 0; i < string.length(); i++) {
            add(string.charAt(i));
        }
    }
    
    /**
     * Adds a full word to this BitVector. This method assumes that all
     * bits in the previous word have been filled, and that adding a word
     * will not fill or overflow the array, hence it is unsafe for
     * public use.
     */
    private void add(int word) {
        if (bitIndex != 0 || arrayIndex == arraySize - 1) {
            System.out.println("add(int) called with arrayIndex = " + arrayIndex +
                               ", bitIndex = " + bitIndex);
        }
        else {
            array[arrayIndex++] = word;
        }
    }
        
    /**
     * Returns the number of bits in this BitVector.
     */
    public long computeSize() {
        return bitCount;
    }
    
    /**
     * Writes this BitVector to a file.
     */
    public void writeBitVector(ObjectOutputStream out) throws IOException {
    
        long extraBits = bitCount % (32 * arraySize);
        if (extraBits == 0) {
            out.writeObject(this);
        }
        else {
            // Create appreviated version of last array in vector
            int wordsUsed = ((int)(extraBits + 31) / 32);
            int smallerArray[] = new int[wordsUsed];
            for (int i = 0; i < wordsUsed; i++) {
                smallerArray[i] = array[i];
            }
            // Replace vector's last array with abbreviated array
            // and trim it to the minimum size
            int tempArray[] = array;
            int lastVectorIndex = vector.size() - 1;
            vector.setElementAt(smallerArray, lastVectorIndex);
            vector.trimToSize();
            array = null;
            
            // Write the vector
            out.writeObject(this);

            // Restore the last array (no need to restore capacity)
            array = tempArray;
            vector.setElementAt(array, lastVectorIndex);
        }            
    }
    
    /**
     * Reads a BitVector from a file.
     */
    public static BitVector readBitVector(ObjectInputStream in)
            throws IOException, ClassNotFoundException {
            
        // Read the bit vector as saved on the file
        BitVector bitVector = (BitVector)in.readObject();
        
        // Expand last array in bit vector (if it was abbreviated)
        Vector newVector = (Vector)bitVector.vector;
        int lastVectorIndex = newVector.size() - 1;
        int lastArray[] = (int[])newVector.elementAt(lastVectorIndex);
        if (lastArray.length != arraySize) {
            int newArray[] = new int[arraySize];
            for (int i = 0; i < lastArray.length; i++) {
                newArray[i] = lastArray[i];
            }
            newVector.setElementAt(newArray, lastVectorIndex);
            bitVector.array = newArray;
        }
        if (DEBUG) {
            System.out.println("Read bitCount = " + bitVector.bitCount +
                               ", arrayIndex = " + bitVector.arrayIndex +
                               ", bitIndex = " + bitVector.bitIndex);
        }
        return bitVector;
    }
    
    /**
     * Tests for equality (mostly for testing purposes).
     */
    public boolean equals(BitVector that) {
        if (this.bitCount != that.bitCount) return false;
        for (int i = 0; i < this.vector.size() - 1; i++) {
            if (! Arrays.equals((int[])this.vector.elementAt(i),
                                (int[])that.vector.elementAt(i))) {
                return false;
            }
        }
        if (bitCount % (32 * arraySize) == 0) return true;
        int thisArray[] = (int[])this.vector.elementAt(arrayIndex);
        int thatArray[] = (int[])that.vector.elementAt(arrayIndex);
        int size = Math.min(thisArray.length, thatArray.length);
        for (int i = 0; i < size; i++) {
            if (thisArray[i] != thatArray[i]) return false;
        }
        return true;
    }
    
    /**
     * Prints up to 75 bits of this BitVector. If there are more than
     * 75 bits, the result will end in "...". This method is really
     * only intended for debugging.
     */
    public void print() {
        BitIterator iter = new BitIterator(this);
        StringBuffer buffer = new StringBuffer(80);
        int count = 0;
        while (iter.hasNext() && count++ < 75) {
            buffer.append(iter.next() ? '1' : '0');
        }
        if (iter.hasNext()) buffer.append("...");
        System.out.println("BitVector: " + buffer);
    }            

// -----------------------------------------------------------------------------

    /**
     * Performs unit testing (with arraySize set much smaller!).
     */
    public static void main(String args[]) throws Exception {
        Random random = new Random();
        arraySize = 3;
        test(1);
        test(14);
        test(31);
        test(32);
        test(33);
        test(32 * arraySize - 1);
        test(32 * arraySize);
        test(32 * arraySize + 1);
        test(3 * 32 * arraySize - 1);
        test(3 * 32 * arraySize);
        test(3 * 32 * arraySize + 1);
        for (int i = 0; i < 5; i++) {
            test(1 + random.nextInt(1000));
        }
        BitVector goingOut = test(321);
        BitVector comingIn = testIO(goingOut);
        BitVector comingInAgain = testIO(comingIn);
    }
    
    /**
     * Tests whether the given bit vector can be written out and
     * then read back in successfully.
     */
    public static BitVector testIO(BitVector goingOut) throws Exception {
        ObjectOutputStream objectOut =
            new ObjectOutputStream(
                new BufferedOutputStream(
                    new FileOutputStream("foo.huf")));
        goingOut.writeBitVector(objectOut);
        objectOut.close( );
        
        BitVector comingIn;
        ObjectInputStream objectIn =
            new ObjectInputStream(
                new BufferedInputStream(
                    new FileInputStream("foo.huf")));
        comingIn = readBitVector(objectIn);
        objectIn.close( );
        
        System.out.println("Are they equal?  " + goingOut.equals(comingIn));
        return comingIn;
    }
    
    /**
     * Performs unit testing.
     */
     private static BitVector test(int bufferSize) {
        System.out.println("\nTesting with bufferSize = " + bufferSize +
                           ", arraySize = " + arraySize +
                           " (" + 32 * arraySize + " bits)");
        
       // Make up fake data, saving it in a StringBuffer
        Random random = new Random();
        StringBuffer buffer = new StringBuffer(bufferSize);
        for (int i = 0; i < bufferSize; i++) {
            buffer = buffer.append(random.nextBoolean() ? '1' : '0');
        }
        // Create a bit vector and add fake data to it
        BitVector bitVector = new BitVector();
        bitVector.add(buffer.toString());
        
        // Print values so far
        if (bufferSize < 60) {
            System.out.println("Original data: " + buffer.toString());
            System.out.print("Reloaded data: ");
        }
        // Create iterator and see if BitVector contents agree with saved data
        BitIterator iter = new BitIterator(bitVector);
        if (!iter.hasNext()) {
            System.out.println("Nothing in bit vector!");
        }
        int count = 0;
        while (iter.hasNext()) {
            boolean bit = iter.next();
            char ch = (bit ? '1' : '0');
            if (bufferSize < 60) System.out.print(ch);
            if (ch == buffer.charAt(count)) count++;
            else {
                System.out.println();
                System.out.print("\n*** Disagreement at bit " + count);
                System.exit(0);
            }
        }
        if (bufferSize < 60) System.out.println();
        System.out.println("Checked " + count + " bits.");
        // Try to throw exception
        try {
            iter.next();
            System.out.println("*** Should have thrown exception.");
        }
        catch (NoSuchElementException e) {}
        
        return bitVector;
    }
}