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(); } } }