import java.util.Iterator;
import java.util.NoSuchElementException;

/**Realization of a set by means of a SORTED extendible array
*/
public class ArraySet2<E extends Comparable<E>> implements Set<E> {
	private E[] A; //array storing the elements of the set
	private int capacity=16; //initial length of array A
	private int size=0; //number of elements stored in the list
	
	
	
	/**Creates the list with initial capacity 16. */
	public ArraySet2(){
		A= (E[]) new Comparable[capacity];//Compiler may warn, but ok
	}
	
	
	
	
	
	public int size() {
       return size;
	}
	
	

	/**Adds the specified element to this set if not already present */
	//adds element in sorted order using binary search
	public boolean add(E e) {
		if(isEmpty()) addBefore(0,e);
		else{
		  
		  int L=0;
		  int H=size()-1;
		  int mid=0;
		  while(L<=H){
			  //System.out.println("H is " + H + " and L is " +L);
			  mid=(H+L)/2;
			  if (A[mid].compareTo(e)==0) return false;
			  else{
				  if (A[mid].compareTo(e)<0) L=mid+1;
				  else H=mid-1;
					
				  }
			  }
		  addBefore (L,e);
		}
		  return true;
		
		
		  
	}
	
	//helper method
	/**add new element e at position i
	 * and move other elements up*/
	public void addBefore(int j, E e){
		//System.out.println("Adding " + e + " to position " + j);
		if(size==capacity){
		      capacity *=2;
		      E[] B=(E[]) new Comparable[capacity];
		      for (int i=0;i<size;i++)
			    B[i]=A[i];
		      A=B;
	        }
		if (j==size()) A[size]=e;
		else{
		  for(int k=size;k>j;k--) A[k]=A[k-1];
		  A[j]=e;
		}
		size++;
		//System.out.println("added " + e + " to set");
		//System.out.println("set is now " + this);
	}
	
	/**Removes all of the elements from this set*/
	public void clear(){
		for(int i=0;i<size();i++) A[i]=null;
		size=0;
	}
	
	/**Returns true if this collection contains the specified element*/
	public boolean contains(E e){
		if(isEmpty()) return false;
		else{
		  
		  int L=0;
		  int H=size()-1;
		  int mid=0;
		  while(L<=H){
			  mid=(H+L)/2;
			  if (A[mid].compareTo(e)==0) return true;
			  else{
				  if (A[mid].compareTo(e)<0) L=mid+1;
				  else H=mid-1;
					
				  }
			  }
		}
		  return false;
		
		
		  
	}
	
	
	
	
	
	/**Removes the specified element from this set, if it is present*/
	public boolean remove(E e){
		int i=0;
		boolean found=false;
		while((i<size()-1)&&(found==false)){
			if(A[i].equals(e)){
				A[i]=null;
				for(int j=i;j<size()-1;j++) A[j]=A[j+1];
				i=size()-1;
				size--;
			}
		}
		return found;
			
			
		
	}

	
	/**Returns true if the set contains no elements*/
	public boolean isEmpty() {
		return size==0;
	}
	
	
	
	public Iterator<E> iterator()
	{ArraySetIterator tempIterator=new ArraySetIterator();
	 return (Iterator<E>) tempIterator;}
	
	private class ArraySetIterator implements Iterator<E>{
		private int current=0;
		
		/**Returns true if the iteration has more elements*/
		public boolean hasNext()
		{return current<size();}
		
		public E next(){
			if(!hasNext())
				throw new NoSuchElementException();
			return A[current++];
		}
		
		/**Removes from the underlying collection the last element returned by the iterator*/
		public void remove(){};
			// not implemented
		}
		
	
	
	public String toString(){
		String s="";
		int count=0;
		for(E sTemp:this) {s+=" "+sTemp;
		count++;
		if (count==20){s+="\n";count=0;}//to add line breaks
		}
		return s;
		 }

}