import java.util.Arrays;

public class MyList<E> implements MyListInterface<E> {

 // The list data structure 
   private E[] theData; // has an array to store elements
   private int size; // the number of elements it currently holds
   private int capacity; // the maximum elements it can hold
   
   // Constructors
   public MyList() {
   capacity = 1;
   size = 0;
   theData = (E[]) new Object[capacity];
   }
   
   public MyList(int cap) {
   capacity = cap;
   size = 0;
   theData = (E[]) new Object[capacity];
   }

 // Operations from MyListInterface
   public void clear() {
   // Set it to an empty list
   size = 0;
   }

 public int size() {
   // Returns the size of the list
   return size;
   }
   
   public boolean isEmpty() {
   // Returns true is list if empty, false o/w
   return (size == 0);
   }
   
   public boolean add(E item) {
   // Inserts item at end of list. Returns true if successful, false o/w
   if (size == capacity) {
   reallocate();
   }
   theData[size] = item;
   size++;
   return true;
   }
   
   public boolean add(int index, E item) {
   // Insert item at idex-th position in list. Returns true if successful, false o/w
   if (index < 0 || index > size) {
   throw new ArrayIndexOutOfBoundsException(index);
   }
   
   if (size == capacity) {
   reallocate();
   }
   
   // shift items back by one to make room at index for item
   for (int i=size; i > index; i--) {
   theData[i] = theData[i-1];
   }
   theData[index] = item;
   size++;
   return true;
   }
   
   public E set(int index, E item) {
   // Sets the index-th element to item, Returns the old item at index
   if (index < 0 || index > size-1) {
   throw new ArrayIndexOutOfBoundsException(index);
   }
   
   E oldItem = theData[index];
   theData[index] = item;
   return oldItem;
   }
   
   public E get(int index) {
   // Returns the item at index-th location in list
   if (index < 0 || index > size-1) {
   throw new ArrayIndexOutOfBoundsException(index);
   }
   return theData[index];
   }
   
   public E remove(int index) {
   // Removes the index-th element from list, and returns it
   if (index < 0 || index > size-1) {
   throw new ArrayIndexOutOfBoundsException(index);
   }
   E item = theData[index];
   
   for (int i=index+1; i < size; i++) {
   theData[i-1] = theData[i];
   }
   size--;
   return item;
   }
   
   public boolean contains(E item) {
   // Returns true if list conatins item, false o/w
   for (int i=0; i < size; i++) {
   if (theData[i].equals(item)) {
   return true;
   }
   }
   return false;
   }
   
   private void reallocate() {
   E[] oldData = theData;
   capacity *= 2;
   theData = (E[]) new Object[capacity];
   
   // copy all elements from oldData to theData
   for (int i=0; i < size; i++) {
   theData[i] = oldData[i];
   }
   //Below is an alternative/better way that uses Java's built-in copy
   // function for arrays...
   //theData = Arrays.copyOf(theData, capacity);
   }
   
   } // class MyList