//-< ArrayOfBoolean.java >-------------------------------------------*--------*
// GOODS                      Version 2.02       (c) 1998  GARRET    *     ?  *
// (Generic Object Oriented Database System)                         *   /\|  *
// GOODS Persistent Class Library                                    *  /  \  *
//                          Created:      3-Nov-98    K.A. Knizhnik  * / [] \ *
//                          Last update:  3-Nov-98    K.A. Knizhnik  * GARRET *
//-------------------------------------------------------------------*--------*
// Dynamic packed array of boolean
//-------------------------------------------------------------------*--------*

package goodslib;
import  goodsjpi.*;

/**
 *  <code>ArrayOfBoolean</code> is just that, an array of booleans. For efficiency
 * they are stored in a byte[] internally.
 *
 * @author   K.A. Knizhnik
 * @version 1.0
 */
public class ArrayOfBoolean extends AnyArray { 

  /**
   *  <code>array</code> holds the booleans in a byte []
   */
    protected byte[] array;

  /**
   * Creates a new <code>ArrayOfBoolean</code> instance.
   *
   * @param size  is the initial size, (length)
   */
    public ArrayOfBoolean(int size) {
	this(size, size == 0 ? 16 : size);
    }

  /**
   * Creates a new <code>ArrayOfBoolean</code> instance. (Full of false)
   *
   * @param size, or length of the array
   * @param allocatedSize is the size it can grow to without resizing
   */
    public ArrayOfBoolean(int size, int allocatedSize) {
	Assert.that(size <= allocatedSize);
	array = new byte[(allocatedSize+7) >>>3];
	used = size;
    }
    
  /**
   * Creates a new <code>ArrayOfBoolean</code> instance, as a copy of the given 
   * boolean[]
   *
   * @param src a <code>boolean[]</code> that will be copied
   */
    public ArrayOfBoolean(boolean[] src) { 
	int length = src.length;
	array = new byte[(length + 7) >>> 3];
	used = length;
        while (--length >= 0) { 
	    if (src[length]) { 
		array[length >>> 3] |= 1 << (length & 7);
	    }
	}
    }

  /**
   * Put a boolean value at a given index
   *
   * @param index an <code>int</code> value, where the value should be set 
   * @param value the <code>boolean</code> value to be set
   */
    public synchronized void putAt(int index, boolean value) { 
        if (index < 0 || index >= used) { 
	    throw new ArrayIndexOutOfBoundsException(index);
	}
	Metaobject.modify();
	if (value) { 
	    array[index >>> 3] |= 1 << (index & 7);
	} else { 
	    array[index >>> 3] &= ~(1 << (index & 7));
	}
    }

  /**
   * Get a boolean at the specified index
   *
   * @param index of the boolean you want
   * @return a <code>boolean</code> value, at index "index"
   */
    public synchronized boolean getAt(int index) { 
        if (index < 0 || index >= used) { 
	    throw new ArrayIndexOutOfBoundsException(index);
	}
	return (array[index >>> 3] & (1 << (index & 7))) != 0;
    }
    

  /**
   * Resize the amount of space taken by the array. Either grow or shrink as 
   * neccessary. You get an IndexOutOfBoundException for negative values. <br>
   * of course the old data is copied.
   *
   * @param newSize an <code>int</code> denoting the new size.
   */
    public synchronized void changeSize(int newSize) { 
        if (newSize < 0) { 
	    throw new ArrayIndexOutOfBoundsException(newSize);
	}
	int newIntSize = (newSize + 7) >>> 3;
	int oldIntSize = (used + 7) >>> 3;
	int allocated = array.length;
	if (newIntSize > allocated) {
	    allocated = (allocated*2 > newIntSize) ? allocated*2 : newIntSize;
	    byte[] newArray = new byte[allocated];
	    System.arraycopy(array, 0, newArray, 0, oldIntSize);
	    array = newArray;
	} else { 
	    while (newIntSize < oldIntSize) { 
		array[newIntSize++] = 0;
	    }
	    if (newSize < used && (newSize & 7) != 0) {
		array[newSize >>> 3] &= (1 << (newSize & 7)) - 1;
	    }
	} 
	used = newSize;
    }


  /**
   *  <code>insert</code> a "count" amount of values  at a given index. Throws an 
   * IndexOutOfBoundsException for too small (<0) or too big (>length) count or index.
   *
   * @param index , where to start inserting value(s)
   * @param count , how many values to insert
   * @param value a <code>boolean</code> value to insert
   */
    public synchronized void insert(int index, int count, boolean value) { 
	if (count < 0) { 
	    throw new ArrayIndexOutOfBoundsException(count);
	} else if (index < 0 || index > used) { 
	    throw new ArrayIndexOutOfBoundsException(index);
	}
	int len = used;
	changeSize(used+count);
	for (int i = len; --i >= index;) {
	    if ((array[i >>> 3] & (1 << (i & 7))) != 0) { 
		array[(i+count) >>> 3] |= 1 << ((i + count) & 7);
	    } else { 
		array[(i+count) >>> 3] &= ~(1 << ((i + count) & 7));
	    }
	}
	if (value) { 
	    while (--count >= 0) { 
		array[index >>> 3] |= 1 << (index & 7);
		index += 1;
	    }
	} else { 
	    while (--count >= 0) { 
		array[index >>> 3] &= ~(1 << (index & 7));
		index += 1;
	    }
	}
    }

  /**
   * <code>remove</code> a number of values. The array shrinks in it's length, but no
   * resizing is done. Get an IndexOutOfBoundsException for inappropriate index or
   * count values.
   *
   * @param index , where to start removing
   * @param count , how many values to remove
   */
    public synchronized void remove(int index, int count) {
	if (count < 0) { 
	    throw new ArrayIndexOutOfBoundsException(count);
	} else if (index < 0) { 
	    throw new ArrayIndexOutOfBoundsException(index);
	} else if (index+count > used) { 
	    throw new ArrayIndexOutOfBoundsException(index+count);
	}
	used -= count;
	for (int i = index; i < used; i++) { 
	    int bit = (1 << ((i + count) & 7)); 
	    if ((array[(i + count) >>> 3] & bit) != 0) { 
		array[(i + count) >>> 3] -= bit;
		array[i >>> 3] |= 1 << (i & 7);
	    } else { 
		array[i >>> 3] &= ~(1 << (i & 7));
	    }
	}
    }


  /**
   *  Use the array as a stack with the <code>push</code> method.
   *
   * @param value , a <code>boolean</code> to push to the stack
   */
    public synchronized void push(boolean value) { 
	changeSize(used+1);
	if (value) { 
	    array[(used-1) >>> 3] |= 1 << ((used-1) & 7);
	}
    }

  /**
   * Use the array as a stack and <code>pop</code> a value. (Value is removed)
   * IndexOutOfBoundsExceptions comes when array has hit 0 length.
   *
   * @return the top most <code>boolean</code> value
   */
    public synchronized boolean pop() { 
	if (used == 0) { 
	    throw new ArrayIndexOutOfBoundsException(0);
	}
	used -= 1;
	int value = array[used >>> 3] & (1 << (used & 7));
	array[used >>> 3] &= ~value;
	return value != 0;
    }

  /**
   * Check the top boollean with the <code>top</code> method. This returns what 
   * <code>pop</code> returns, just it doesn't remove the value. In other stack
   * implementations it may be called peek()
   *
   * @return a <code>boolean</code> value
   */
    public synchronized boolean top() { 
	if (used == 0) { 
	    throw new ArrayIndexOutOfBoundsException(0);
	}
	return (array[(used-1) >>> 3] & (1 << ((used-1) & 7))) != 0;
    }

  /**
   *  <code>append</code> add the given values to the end of the array
   *
   * @param tail a <code>boolean[]</code> that will be appended
   */
    public synchronized void append(boolean[] tail) { 
        int size = used;
        changeSize(size + tail.length);
	copy(size, tail, 0, tail.length);
    }

  /**
   *  <code>toArray</code> makes a Java boolean[] out of the values. Internally they
   *  are stored in a byte[] for space efficiency
   *
   * @return the array as a <code>boolean[]</code> 
   */
    public synchronized boolean[] toArray() { 
        boolean[] arr = new boolean[used];
	for (int i = used; --i >= 0;) {
	    arr[i] = (array[i >>> 3] & (1 << (i & 7))) != 0;
	}
        return arr;
    }
  
  /**
   *  <code>copy</code> into this array from a destination, a given amount of values.
   * Get a IndexOutOfBounds if the src or count don't fit
   *
   * @param dstIndex , the index (of this array) where to copy to
   * @param src a <code>boolean[]</code> , where to copy from
   * @param srcIndex an <code>int</code> , where to start copying from
   * @param count an <code>int</code> , how many values to copy
   */
    public synchronized void copy(int dstIndex, boolean[] src, int srcIndex, 
				  int count) 
    { 
        if (dstIndex < 0) { 
	    throw new ArrayIndexOutOfBoundsException(dstIndex);
	} else if (dstIndex+count > used) { 
	    throw new ArrayIndexOutOfBoundsException(dstIndex+count);
	} 
	Metaobject.modify();
        while (--count >= 0) { 
	    if (src[srcIndex++]) { 
		array[dstIndex >>> 3] |= 1 << (dstIndex & 7);
	    } else { 
		array[dstIndex >>> 3] &= ~(1 << (dstIndex & 7));
	    }
	    dstIndex += 1;
	}
    }

  /**
   *  <code>indexOf</code> returns the first occurrence of val
   *
   * @param val a <code>boolean</code> to be looked for
   * @return an <code>int</code>, where the value was found, or -1
   */
    public synchronized int indexOf(boolean val) { 
        int i, last = used >>> 3;
	if (val) { 
	    for (i = 0; i < last; i++) { 
		if (array[i] != 0) { 
		    return (i << 3)  + firstSetBit[array[i] & 0xFF];
		}
	    }
	    if ((used & 7) != 0 && array[last] != 0) {  
		return (last << 3) + firstSetBit[array[last] & 0xFF];
	    }
	} else { 
	    for (i = 0; i < last; i++) { 
		if (array[i] != -1) { 
		    return (i << 3) + firstSetBit[~array[i] & 0xFF];
		}
	    }
	    if ((used & 7) != 0) { 
		return firstSetBit[~((-1 << (used & 7)) | array[last])];
	    }
	}	    
	return -1;
    }

  /**
   * Find the <code>lastIndexOf</code> a given value
   *
   * @param val a <code>boolean</code> value to be found (from the back)
   * @return an <code>int</code> , where the value was found, or -1
   */
    public synchronized int lastIndexOf(boolean val) { 
        int i, last = used >>> 3;
	if (val) { 
	    if ((used & 7) != 0 && array[last] != 0) { 
		return (last << 3) + lastSetBit[array[last] & 0xFF];
	    }
	    for (i = last; --i >= 0;) { 
		if (array[i] != 0) { 
		    return (i << 3) + lastSetBit[array[i] & 0xFF];
		}
	    }
	} else { 
	    if ((used & 7) != 0 && array[last] != (1 << (used & 7)) - 1) {
		return (last << 3) + lastSetBit[~array[last] & 0xFF];
	    }
	    for (i = last; --i >= 0;) { 
		if (array[i] != -1) { 
		    return (i << 3) + lastSetBit[~array[i] & 0xFF];
		}
	    }
	}	    
	return -1;
    }

    static final byte firstSetBit[] = {
	-1,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
	5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
    };
    static final byte lastSetBit[] = {
	-1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
	5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
	7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
    };
}