import java.util.*;
/**
 * An iterator for the objects of the BitVector class. Does not
 * implement the Iterator interface because we want next() to
 * return a boolean.
 * 
 * @author David Matuszek 
 * @version 2
 */
public class BitIterator {

    BitVector bitVector = null;
    long originalSize;
    int vectorIndex, arrayIndex, bitIndex;
    long bitsReturned;

    /**
     * Creates a bitIterator for the given bitVector.
     *
     * @param bitVector the bitVector that needs an iterator.
     * @throws IllegalArgumentException if given a null argument.
     */
    public BitIterator(BitVector bitVector) {
        // Check for illegal argument
        if (bitVector == null) throw new IllegalArgumentException();
        
        // If the bitVector is empty, don't do anything
        originalSize = bitVector.computeSize();
        if (originalSize == 0) return;
        
        // Set position of first bit to be gotten
        this.bitVector = bitVector;
        int vectorIndex = 0, arrayIndex = 0, bitIndex = 0;
        bitsReturned = 0;
    }
    
    /**
     * Returns true if there are more elements to be gotten from
     * the bitVector.
     */
    public boolean hasNext() {
        return bitVector != null;
    }
    
    /**
     * Returns the next bit from the bitVector.
     */
    public boolean next() {
        // Ensure that there is another bit in the bitVector.
        if (bitVector == null) {
            throw new NoSuchElementException();
        }
        // Ensure that the bitVector hasn't changed during the iteration.
        if (bitVector.computeSize() != originalSize) {
            throw new ConcurrentModificationException();
        }
        // Find the next bit
        int [] array = (int[])(bitVector.vector.elementAt(vectorIndex));
        int word = array[arrayIndex];
        boolean bit = (((word >> (31 - bitIndex)) & 1) == 1);
        
        // If at last bit, unset bitVector and return last bit
        if (++bitsReturned == originalSize) {
            bitVector = null;
        }
        // If not at last bit, prepare to return another bit next time
        else {
            if (++bitIndex == 32) {
                bitIndex = 0;
                if (++arrayIndex == BitVector.arraySize) {
                    arrayIndex = 0;
                    vectorIndex++;
                }
            }
        }
        // Finally, return this bit
        return bit;
    }    
}