import java.util.*;

public class ArrayList implements List {

	// Each ArrayList object is an indexed list (sequence) whose elements 
	// are objects.
	
	// This list is represented as follows: its elements occupy 
	// elems[0�length-1].
	private Object[] elems;
	private int length;
	
	//////////// Constructor ////////////
	
	public ArrayList (int maxlength) {
	// Construct a list, initially empty, whose length will be bounded by 
	// maxlength.
		elems = new Object[maxlength];
		length = 0;
	}
	
	//////////// Accessors ////////////
	
	public boolean isEmpty () {
	// Return true if and only if this list is empty.
		return (length == 0);
	}
	
	public int size () {
	// Return this list's length.
		return length;
	}
	
	public Object get (int i) {
	// Return the element with index i in this list. Throw an
	// IndexOutOfBoundsException if i is out of range.
		if (i < 0 || i >= length)
			throw new IndexOutOfBoundsException();
		return elems[i];
	}
	
	public boolean equals (List that) {
	// Return true if and only if this list and that have the same length, and 
	// each element of this list equals the corresponding element of that.
		ArrayList other = (ArrayList) that;
		if (length != other.length)
			return false;
		for (int i = 0; i < length; i++) {
			if (! elems[i].equals(other.elems[i]))
				return false;
		}
		return true;
	}
	
	//////////// Transformers ////////////
	
	public void clear () {
	// Make this list empty.
		for (int i = 0; i < length; i++)
			elems[i] = null;
		length = 0;
	}
	
	public void set (int i, Object elem) {
	// Replace by elem the element at index i in this list. Throw an
	// IndexOutOfBoundsException if i is out of range.
		if (i < 0 || i >= length)
			throw new IndexOutOfBoundsException();
		elems[i] = elem;
	}
	
	public void add (int i, Object elem) {
	// Add elem as the element with index i in this list. Throw an
	// IndexOutOfBoundsException if i is out of range.
		if (i < 0 || i > length)
			throw new IndexOutOfBoundsException();
		if (length == elems.length)  expand();
		for (int j = length; j > i; j--)
			elems[j] = elems[j-1];
		elems[i] = elem;
		length++;
	}
	
	public void add (Object elem) {
	// Add elem after the last element of this list.
		if (length == elems.length)  expand();
		elems[length++] = elem;
	}
	
	public void addAll (List that) {
	// Add all the elements of that after the last element of this list.
		ArrayList other = (ArrayList) that;
		for (int i = 0; i < other.length; i++)
			add(other.elems[i]);
	}
	
	public Object remove (int i) {
	// Remove and return the element with index i in this list. Throw an
	// IndexOutOfBoundsException if i is out of range.
		if (i < 0 || i >= length)
			throw new IndexOutOfBoundsException();
		Object oldElem = elems[i];
		for (int j = i+1; j < length; j++)
			elems[j-1] = elems[j];
		length--;
		elems[length] = null;
		return oldElem;
	}
	
	//////////// Iterator ////////////
	
	public Iterator iterator () {
	// Return an iterator that will visit all elements of this list, in left-to-right 
	// order.
		return new ArrayList.LRIterator();
	}
	
	//////////// Auxiliary method ////////////
	
	private void expand () {
	// Make the elems array longer.
		Object[] newElems = new Object[2*length];
		System.arraycopy(elems, 0, newElems, 0, length);
		elems = newElems;
	}
	
	//////////// Inner class ////////////
	
	private class LRIterator implements Iterator {

		// An ArrayList.LRIterator object is a left-to-right iterator over a
 		// list represented by an ArrayList object.

		// This iterator is represented by the array index of the next element to be 
		// visited, place.
		private int place;

		private LRIterator () {
			place = 0;
		}

		public boolean hasNext () {
			return (place < length);
		}

		public Object next () {
			if (place >= length)
				throw new NoSuchElementException();
			return elems[place++];
		}

		public void remove () {
			throw new UnsupportedOperationException();
		}

	}

}