package key.util;

import java.io.*;

public final class Bits
	implements Cloneable,
	java.io.Serializable
{
    private final static int BITS_PER_UNIT = 6;
    private final static int MASK = (1<<BITS_PER_UNIT)-1;
    private long bits[];
	
	private int lowestSet;
	
    /**
     * Convert bitIndex to a subscript into the bits[] array.
     */
    private static int subscript(int bitIndex)
	{
		return bitIndex >> BITS_PER_UNIT;
    }
	
    /**
     * Convert a subscript into the bits[] array to a (maximum) bitIndex.
     */
    private static int bitIndex(int subscript)
	{
		return (subscript << BITS_PER_UNIT) + MASK;
    }
	
    /**
     * Creates an empty set.
     */
    public Bits()
	{
		this(1 << BITS_PER_UNIT);
    }

    /**
     * Creates an empty set with the specified size.
     * @param nbits the size of the set
     */
    public Bits(int nbits)
	{
		/* nbits can't be negative; size 0 is OK */
		if (nbits < 0)
		{
			throw new NegativeArraySizeException(Integer.toString(nbits));
		}
		
		/* On wraparound, truncate size; almost certain to o-flo memory. */
		if (nbits + MASK < 0)
		{
			nbits = Integer.MAX_VALUE - MASK;
		}
		
		/* subscript(nbits + MASK) is the length of the array needed to hold nbits */
		bits = new long[subscript(nbits + MASK)];
		
		lowestSet = Integer.MAX_VALUE;
    }

    /**
     * Ensures that the Bits can hold at least an nth bit.
     * This cannot leave the bits array at length 0.
     * @param	nth	the 0-origin number of the bit to ensure is there.
     */
    private void ensureCapacity(int nth)
	{
		/* Doesn't need to be synchronized because it's an internal method. */
		int required = subscript(nth) + 1;	/* +1 to get length, not index */
		if (required > bits.length)
		{
			/* Ask for larger of doubled size or required size */
			int request = Math.max(2 * bits.length, required);
			long newBits[] = new long[request];
			System.arraycopy(bits, 0, newBits, 0, bits.length);
			bits = newBits;
		}
    }

    /**
     * Sets a bit.
     * @param bit the bit to be set
     */
    public void set(int bit)
	{
		if (bit < 0)
		{
			throw new IndexOutOfBoundsException(Integer.toString(bit));
		}
		
		synchronized (this)
		{
			ensureCapacity(bit);
			bits[subscript(bit)] |= (1L << (bit & MASK));
			
			if( bit < lowestSet )
				lowestSet = bit;
		}
    }

    /**
     * Clears a bit.
     * @param bit the bit to be cleared
     */
    public void clear(int bit)
	{
		if( bit < 0 )
			throw new IndexOutOfBoundsException( Integer.toString(bit) );
		
		if( subscript(bit) >= bits.length )
			return;
		
		synchronized( this )
		{
			ensureCapacity(bit);
			bits[subscript(bit)] &= ~(1L << (bit & MASK));

			if( bit == lowestSet )
			{
				lowestSet = Integer.MAX_VALUE;
			}
		}
    }
	
	public int firstSet()
	{
		if( lowestSet == Integer.MAX_VALUE )
		{
			int bitsLength = bits.length;
			int i;
			
			for( i = 0; i < bitsLength; i++ )
			{
				if( bits[i] != 0 )
				{
					long bi = bits[i];
					long j;
					int added = i*64;
					
					int c = 32;
					
					do
					{
						j = (bi << c);
						
						if( (bi << c) == 0 )
							added += c;
						else
							bi = j;
						
						c >>= 1;
					} while( c != 0 );
					
					return( added );
					//lowestSet = added;
					//break;
				}
			}
			
			lowestSet = Integer.MAX_VALUE;
		}
		
		return( lowestSet );
	}
	
    /**
     * Gets a bit.
     * @param bit the bit to be gotten
     */
    public boolean get(int bit)
	{
		if (bit < 0)
		{
			throw new IndexOutOfBoundsException(Integer.toString(bit));
		}
		boolean result = false;
		synchronized (this)
		{
			int n = subscript(bit);		/* always positive */
			if (n < bits.length)
			{
				result = ((bits[n] & (1L << (bit & MASK))) != 0);
			}
		}
		return result;
    }

    /**
     * Logically ANDs this bit set with the specified set of bits.
     * @param set the bit set to be ANDed with
     */
    public void and(Bits set) {
	/*
	 * Need to synchronize  both this and set.
	 * This might lead to deadlock if one thread grabs them in one order
	 * while another thread grabs them the other order.
	 * Use a trick from Doug Lea's book on concurrency,
	 * somewhat complicated because Bits overrides hashCode().
	 */
	if (this == set) {
	    return;
	}
	Bits first = this;
	Bits second = set;
	if (System.identityHashCode(first) > System.identityHashCode(second)) {
	    first = set;
	    second = this;
	}
	synchronized (first) {
	    synchronized (second) {
		int bitsLength = bits.length;
		int setLength = set.bits.length;
		int n = Math.min(bitsLength, setLength);
		for (int i = n ; i-- > 0 ; ) {
		    bits[i] &= set.bits[i];
		}
		for (; n < bitsLength ; n++) {
		    bits[n] = 0;
		}
	    }
	}
    }

    /**
     * Logically ORs this bit set with the specified set of bits.
     * @param set the bit set to be ORed with
     */
    public void or(Bits set) {
	if (this == set) {
	    return;
	}
	/* See the note about synchronization in and(), above. */
	Bits first = this;
	Bits second = set;
	if (System.identityHashCode(first) > System.identityHashCode(second)) {
	    first = set;
	    second = this;
	}
	synchronized (first) {
	    synchronized (second) {
		int setLength = set.bits.length;
		if (setLength > 0) {
		    ensureCapacity(bitIndex(setLength-1));
		}
		for (int i = setLength; i-- > 0 ;) {
		    bits[i] |= set.bits[i];
		}
	    }
	}
    }

    /**
     * Logically XORs this bit set with the specified set of bits.
     * @param set the bit set to be XORed with
     */
    public void xor(Bits set) {
	/* See the note about synchronization in and(), above. */
	Bits first = this;
	Bits second = set;
	if (System.identityHashCode(first) > System.identityHashCode(second)) {
	    first = set;
	    second = this;
	}
	synchronized (first) {
	    synchronized (second) {
		int setLength = set.bits.length;
		if (setLength > 0) {
		    ensureCapacity(bitIndex(setLength-1));
		}
		for (int i = setLength; i-- > 0 ;) {
		    bits[i] ^= set.bits[i];
		}
	    }
	}
    }

    /**
     * Gets the hashcode.
     */
    public int hashCode() {
	long h = 1234;
	synchronized (this) {
	    for (int i = bits.length; --i >= 0; ) {
		h ^= bits[i] * (i + 1);
	    }
	}
	return (int)((h >> 32) ^ h);
    }
    
    /**
     * Calculates and returns the set's size in bits.
     * The maximum element in the set is the size - 1st element.
     */
    public int size() {
	/* This doesn't need to be synchronized, since it just reads a field. */
	return bits.length << BITS_PER_UNIT;
    }

    /**
     * Compares this object against the specified object.
     * @param obj the object to compare with
     * @return true if the objects are the same; false otherwise.
     */
    public boolean equals(Object obj) {
	if ((obj != null) && (obj instanceof Bits)) {
	    if (this == obj) {
		return true;
	    }
	    Bits set = (Bits) obj;
	    /* See the note about synchronization in and(), above. */
	    Bits first = this;
	    Bits second = set;
	    if (System.identityHashCode(first) > System.identityHashCode(second)) {
		first = set;
		second = this;
	    }
	    synchronized (first) {
		synchronized (second) {
		    int bitsLength = bits.length;
		    int setLength = set.bits.length;
		    int n = Math.min(bitsLength, setLength);
		    for (int i = n ; i-- > 0 ;) {
			if (bits[i] != set.bits[i]) {
			    return false;
			}
		    }
		    if (bitsLength > n) {
			for (int i = bitsLength ; i-- > n ;) {
			    if (bits[i] != 0) {
				return false;
			    }
			}
		    } else if (setLength > n) {
			for (int i = setLength ; i-- > n ;) {
			    if (set.bits[i] != 0) {
				return false;
			    }
			}
		    }
		}
	    }
	    return true;
	}
	return false;
    }

    /**
     * Clones the Bits.
     */
    public Object clone() {
	Bits result = null;
	synchronized (this) {
	    try {
		result = (Bits) super.clone();
	    } catch (CloneNotSupportedException e) {
		// this shouldn't happen, since we are Cloneable
		throw new InternalError();
	    }
	    result.bits = new long[bits.length];
	    System.arraycopy(bits, 0, result.bits, 0, result.bits.length);
	}
	return result;
    }

    /**
     * Converts the Bits to a String.
     */
    public String toString() {
	StringBuffer buffer = new StringBuffer();
	boolean needSeparator = false;
	buffer.append('{');
	synchronized (this) {
	    int limit = size();
	    for (int i = 0 ; i < limit ; i++) {
		if (get(i)) {
		    if (needSeparator) {
			buffer.append(", ");
		    } else {
			needSeparator = true;
		    }
		    buffer.append(i);
		}
	    }
	}
	buffer.append('}');
	return buffer.toString();
    }

	/*
	public static void main( String args[] )
	{
		Bits bits = new Bits();
		int r = 0;
		DataInputStream dis = new DataInputStream( System.in );
		
		System.out.println( "bitting program" );
		
		do
		{
			System.out.print( "enter bit, or '?': " );
			
			try
			{
				String s = dis.readLine();
				
				if( s.charAt(0) == '?' )
				{
					System.out.println( bits.toString() );
					continue;
				}
				
				r = Integer.parseInt( s );
			}
			catch( Exception e )
			{
				System.out.println( e.toString() );
				continue;
			}
			
			if( bits.get( r ) )
			{
				bits.clear( r );
				System.out.println( "Cleared bit " + r );
			}
			else
			{
				bits.set( r );
				System.out.println( "Set bit " + r );
			}
			
			System.out.println( "First bit set is " + bits.firstSet() );
		} while( r >= 0 );
	}
	*/
}