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

import exceptions.EmptyCollectionException;

public abstract class AArrayList implements ListADT { protected static final int FRONT = 0; // The front position (always 0) protected static final int DEFAULT_SIZE = 10; // Default size protected T listArray[]; // Array holding list elements protected int listSize; // Current # of list items, indicates next open // location in array protected int modifiedCount; // Count how many times list has been modified // (add or remove)

// Constructors // Create a new list object with maximum size "size" @SuppressWarnings("unchecked") // Generic array allocation AArrayList(int size) { // maxSize = size; listSize = modifiedCount = 0; listArray = (T[]) new Object[size]; // Create listArray }

// Create a list with the default capacity AArrayList() { this(DEFAULT_SIZE); // Just call the other constructor }

// Reset the list -- note that we could also iterate the array and null all // values public void clear() { // Reinitialize the list listSize = modifiedCount = 0; // Simply reinitialize values }

@Override // the add method will be different for each subclass public abstract boolean add(T element);

// Increase the size of the array when it becomes full protected void growList() { // create a larger array newList // copy all elements of list into newList array // update the list reference to point to newList

T[] newList = (T[]) (new Object[size() + DEFAULT_SIZE]);

for (int i = 0; i

listArray = newList;

}

@Override public T remove(T element) throws NoSuchElementException { // Remove element from the list // This method may also throw the EmptyCollectionException - depending on // how you code it return null; }

@Override public T removeFirst() { // Remove first element from the list T retElement; if (isEmpty()) throw new EmptyCollectionException("list");

retElement = listArray[FRONT];

// shift elements for (int i = 0; i

listArray[listSize] = null; // null where the last element used to be listSize--; modifiedCount++;

return retElement; }

@Override public T removeLast() throws NoSuchElementException { // Remove the last element from the list // This method may also throw the EmptyCollectionException - depending on // how you code it

return null; }

@Override public int size() { return listSize; // Return list size }

// Tell if the list is empty or not public boolean isEmpty() { return listSize == 0; }

protected boolean isFull() { return (listSize == listArray.length); }

@Override public T first() { // TODO Auto-generated method stub return null; }

@Override public T last() { if (isEmpty()) throw new EmptyCollectionException("list"); return listArray[listSize - 1]; }

@Override public boolean contains(T element) { // TODO Auto-generated method stub return false; }

@Override public int indexOf(T element) { // TODO Auto-generated method stub return 0; }

@Override public void toArray(T[] anArray) { // TODO Auto-generated method stub

}

@Override public String toString() { String retString = "[";

for (int i = 0; i

// You may use this method to shift elements and open an index location to add protected void shiftElements(int insertingIndex) { // shift elements so that the index location at // starting index is open for the new element

for (int i = size(); i > insertingIndex; i--) { listArray[i] = listArray[i - 1]; } listArray[insertingIndex] = null; }

@Override public Iterator iterator() { // Return an iterator for this list return new ArrayListIterator(); }

// private iterator class

private class ArrayListIterator implements Iterator {

int currentPos; int currentModCount;

public ArrayListIterator() { currentPos = 0; currentModCount = modifiedCount;

}

@Override public boolean hasNext() { // Indicate if there are elements left to iterate if (currentModCount != modifiedCount) { throw new ConcurrentModificationException(); } return (currentPos

@Override public T next() { // Return the next element in the list // First time calling next returns the first element in the list

if (hasNext()) { currentPos++; return listArray[currentPos - 1]; } else { throw new NoSuchElementException(); } }

} }

ListADT Code:

import java.util.NoSuchElementException;

public interface ListADT extends Iterable { public void clear();

// Append "it" at the end of the list for unordered lists // Add at appropriate position for ordered lists // The list must ensure that the list's capacity is not exceeded public boolean add(T it);

// Remove and return the current element public T remove(T element) throws NoSuchElementException;

// Remove and return the first element public T removeFirst() throws NoSuchElementException;

// Remove and return the last element public T removeLast() throws NoSuchElementException;

// Return the number of elements in the list public int size();

// Tell if the list is empty or not public boolean isEmpty();

// Return the first element in the list public T first();

// Return the last element in the list public T last();

// Tell if the element exists in the list public boolean contains(T element);

// Return the index of the specified element public int indexOf(T element);

// Copies the elements of the list onto the parameter array public void toArray(T[] anArray);

/* * Unused methods below * * // Insert "it" at the current location // The list must ensure that the * list's capacity is not exceeded public boolean addAtCurrent(T it); * * // Remove and return the current element public T removeCurrent() throws * NoSuchElementException; * * // Return the position of the current element public int currPos(); * * // Set the current position to "pos" public boolean moveToPos(int pos); * * // Return true if current position is at end of the list public boolean * isAtEnd(); * * // Return the current element public T getCurrentValue() throws * NoSuchElementException; * * // Set the current position to the start of the list public void * moveToStart(); * * // Set the current position to the end of the list public void moveToEnd(); * * // Move the current position one step left, no change if already at * beginning public void prev(); * * // Move the current position one step right, no change if already at end * public void next(); * * End of unused methods */

}

NOTES: The AArrayList implements the ListADT; it is an abstract list with implementations for methods that are common to all of our lists. The UArrayList extenda the AArrayList and implements the UnorderedListADT; it includes the implementation of the methods that apply to an unordered/indexed list. Complete the AArrayList Use the provided class and complete the required methods 1. + remove(t element) remove the element from the list, throw NoSuchElementException if the element does not exist in the list 2. + removeLast(T element) remove the last element from the list, throw NoSuchElementException if the element does not exist in the list