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

/**Realization of a list by means of an array, which is doubled
 *when the size of the list exceeds the capacity of the array
*/
public class MyArrayList<E> implements List<E> {
	private E[] a; //array storing the elements of the list
	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 MyArrayList(){
		a= (E[]) new Object[capacity];//Compiler may warn, but ok
	}
	
	
	
	/**checks whether an index r is in the range [0,n-1]*/
	public void checkIndex(int i, int n) throws IndexOutOfBoundsException{
		if(i<0 || i>=n) throw new IndexOutOfBoundsException("index out of bounds");
	}
	
	public int size() {
       return size;
	}
	
	/**Returns whether the list is empty*/
	public boolean isEmpty() {
		return size==0;
	}

	/**Inserts an element at the given index. */
	public void add(int i, E e) throws IndexOutOfBoundsException {
	  checkIndex(i,size+1);
	  if(size==capacity){
		  capacity *=2;
		  E[] b=(E[]) new Object[capacity];
		  for (int j=0;j<size;j++)
			  b[j]=a[i];
		  a=b;
	  }
	  for (int j=size-1;j>=i;j--) //shift elements up
		  a[j+1]=a[j];
	  a[i]=e;
	  size++;

	}
	
	/**Add an element to the end of the list */
	public void add(E e) throws IndexOutOfBoundsException {
		add(size,e);
	}

	/**Returns the element at index i, without removing it*/
	public E get(int i) throws IndexOutOfBoundsException {
		checkIndex(i,size);
		return a[i];
	}

	

	/**Removes and returns the element at index i, shifting the elements after this. */
	public E remove(int i) throws IndexOutOfBoundsException {
		checkIndex(i,size);
		E temp=a[i];
		for(int j=i;j<size()-1;j++) a[j]=a[j+1];
		a[size-1]=null;
		size--;
		return temp;
	}
   
	/**
	 * Replaces the element at index i with e, returning the previous element at i
	 */
	public E set(int i, E e) throws IndexOutOfBoundsException {
		checkIndex(i,size());
		E temp=a[i];
		a[i]=e;
		return temp;
	}
	
	
	public Iterator<E> iterator()
	{ArrayListIterator tempIterator=new ArrayListIterator();
	 return (Iterator<E>) tempIterator;}
	
	private class ArrayListIterator 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(){MyArrayList.this.remove(--current);}
			
		}
		
	
	
	
	//use this version if not implementing Iterable interface
	//public String toString(){
	//	String s="";
	 //   Iterator<E> it =iterator();
	 //   while(it.hasNext()) s=s+it.next()+" ";
	    
	//	return s;
	//}
	
	public String toString(){
		String s="";
		for(E sTemp:this) s+=" "+sTemp;
		return s;
		 }

}