import java.util.NoSuchElementException;


/**
 * LABSection #1: Building an Iterator
 * @version 1.0,  29 August 2005
 * 
 *
 */
public class GenericWrapper {
	private Object[] data;
	private int size;
	
	/** constructor: allocate an array of Objects 
	 * @param length of Array of Objects
     */
	public GenericWrapper(int length){
		data = new Object[length];
		size = 0;
	}

	/** adds an element to this Array of Objects 
	 * @param Object to be added
	 */
	public void add(Comparable x){
		int pos = findPos(x); // find position of x in array
		if (pos >= size){ // x is not in the array of objects
			pos = pos%(size+1);
			if (size >= data.length) doubleDataLength();
			// open up gap for x
			for (int i=size; i>pos;i--)
				data[i] = data[i-1];
			// place x in array
			data[pos] = x;
			size++;
		}
	}
	
	/** checks wheter an Object x belongs to this Array of Objects
	 * @param  Object to be checked
	 * @return if the Object is in the array return true*/
	public boolean contains(Comparable x){
		return(findPos(x) < size);
	}
	
	/** removes an element from this Array of Objects 
	 * @param object to be removed*/
	public void remove(Comparable x){
		int pos = findPos(x); // find position of x in array
		if (pos < size) { // x is currently in the set
			// delete x
			for (int i=pos+1; i < size;i++)
				data[i-1] = data[i];
			size--;
		}
	}
	
	/** checks wheter this Array of Objects is empty
	 * @return  if the array is empty return true*/
	public boolean isEmpty(){
		return(size==0);
	}
	
	/** Finds and returns position of x in data array. If x is not 
	  * present, a position >= size is returned; in this case the return value modulo
	  * (size+1) is the position x should be inserted
	  * @return the position p, of x in data
	  * if 0 <= p < size then x is present in the array
	  * otherwise p%(size+1) is the insertion position for x
	  */
	  private int findPos(Comparable x) {
	  	// uses binary search to find position of x
	  	int l = -1,r = size,m;
	  	while (l < r-1){
	  		m = (l+r)/2;
	  		if (x.compareTo(data[m]) < 0)
				r = m;
			else
				l = m;
	  	}
	  	if (l<0) return(size+1); // x not present and should go in data[0]
	    if (x.equals(data[l])) return(l);
	    else return(l+size+2); // x not present and should go in data[l+1]
	  }
	
	  /** doubles the size of the array data */
	  private void doubleDataLength(){
	  	Object[] newData = new Object[2*data.length];
	  	for (int i=0; i < data.length; i++)
	  		newData[i] = data[i];
	  	data = newData;
	  }
}