List Abstractions and Iterators -- ArrayIntList
// written originally by Stuart Reges (some formatting by GY)
Interface IntListIterator.java
------------------------------
// Interface IntListIterator provides tools for iterating through the
// list first to last, potentially removing values when encountered
public interface IntListIterator { public boolean hasNext();
public int next();
public void remove();
}
Interface IntList.java
----------------------
// The IntList interface defines a set of operations for an ordered
// collection (sequence) of integers.
public interface IntList { public int size();
public int get(int index);
public int indexOf(int value);
public boolean isEmpty();
public boolean contains(int value);
public void add(int value);
public void add(int index, int value);
public void addAll(IntList other);
public void remove(int index);
public void removeAll(IntList other);
public void set(int index, int value);
public void clear();
public void ensureCapacity(int capacity);
public IntListIterator iterator();
}
Class AbstractIntList.java
--------------------------
// AbstractIntList provides a skeletal implementation of IntList
// Many operations defined in terms of the list iterator. Subclasses
// must define size(),get(int index),add(int value),add(index, value),
// remove(index), set(index, value), clear() and ensureCapacity().
public abstract class AbstractIntList implements IntList { // post: returns a comma-separated, bracketed version of the list
public String toString() { IntListIterator i = iterator();
String result = "[";
if (i.hasNext()) { result += i.next();
while (i.hasNext())
result += ", " + i.next();
}
result += "]";
return result;
}
// post : returns the position of the first occurrence of the given
// value (-1 if not found)
public int indexOf(int value) { IntListIterator i = iterator();
int index = 0;
while (i.hasNext()) { if (i.next() == value)
return index;
index++;
}
return -1;
}
// post: returns true if list is empty, false otherwise
public boolean isEmpty() { return !iterator().hasNext();
}
// post: returns true if the given value is contained in the list,
// false otherwise
public boolean contains(int value) { return this.indexOf(value) != -1;
}
// post: appends all values from given list to the end of this list
public void addAll(IntList other) { IntListIterator i = other.iterator();
while (i.hasNext())
this.add(i.next());
}
// post: removes all occurrences of the values in the given list
// from this list
public void removeAll(IntList other) { IntListIterator i = iterator();
while (i.hasNext())
if (other.contains(i.next()))
i.remove();
}
// post: throws an exception if the given index is out of range
protected void checkIndex(int index) { if (index < 0 || index >= size())
throw new IndexOutOfBoundsException("illegal index"); }
}
Class ArrayIntList.java
-----------------------
// ArrayIntList provides an implementation of the IntList interface
// backed by an array. This will provide O(1) performance for methods
// like get and set that access a particular element of the array. The
// underlying array will be doubled in size if necessary to accommodate
// add operations. The appending add has O(1) performance (amortized // for doubling when full). The iterator's remove method has O(n)
// performance as do adding at a particular index and removing at a
// particular index.
import java.util.*;
public class ArrayIntList extends AbstractIntList { private int[] elementData; // list of integers
private int size; // current number of elements in list
public static final int DEFAULT_CAPACITY = 100;
// post: constructs an empty list of default capacity
public ArrayIntList() { this(DEFAULT_CAPACITY);
}
// pre : capacity >= 0
// post: constructs an empty list with the given capacity
public ArrayIntList(int capacity) { if (capacity < 0)
throw new IllegalArgumentException("negative capacity"); elementData = new int[capacity];
size = 0;
}
// post: returns the current number of elements in the list
public int size() { return size;
}
// pre : 0 <= index < size()
// post: returns the integer at the given index in the list
public int get(int index) { checkIndex(index);
return elementData[index];
}
// post: appends the given value to the end of the list
public void add(int value) { ensureCapacity(size + 1);
elementData[size] = value;
size++;
}
// pre: 0 <= index <= size()
// post: inserts the given value at the given index, shifting
// subsequent values right
public void add(int index, int value) { if (index < 0 || index > size)
throw new IndexOutOfBoundsException("illegal index"); ensureCapacity(size + 1);
for (int i = size; i > index; i--)
elementData[i] = elementData[i - 1];
elementData[index] = value;
size++;
}
// pre : 0 <= index < size()
// post: removes value at the given index, shifting subsequent
// values left
public void remove(int index) { checkIndex(index);
for (int i = index; i < size - 1; i++)
elementData[i] = elementData[i + 1];
size--;
}
// pre : 0 <= index < size()
// post: replaces the integer at given index with given value
public void set(int index, int value) { checkIndex(index);
elementData[index] = value;
}
// post: list is empty
public void clear() { size = 0;
}
// post: ensures that the underlying array has the given capacity;
// if not, the size is doubled (or more if given capacity is even
// larger)
public void ensureCapacity(int capacity) { if (capacity > elementData.length) { int newCapacity = elementData.length * 2 + 1;
if (capacity > newCapacity)
newCapacity = capacity;
int[] newList = new int[newCapacity];
for (int i = 0; i < size; i++)
newList[i] = elementData[i];
elementData = newList;
}
}
// post: returns an iterator for this list
public IntListIterator iterator() { return new ArrayIterator();
}
private class ArrayIterator implements IntListIterator { private int position; // current position within the list
private boolean removeOK; // whether it's okay to remove now
// post: constructs an iterator for the given list
public ArrayIterator() { position = 0;
removeOK = false;
}
// post: returns true if more elements left, false otherwise
public boolean hasNext() { return position < size();
}
// pre : hasNext()
// post: returns the next element in the iteration
public int next() { if (!hasNext())
throw new NoSuchElementException();
int result = get(position);
position++;
removeOK = true;
return result;
}
// pre : next() has been called without a call on remove (i.e.,
// at most one call per call on next)
// post: removes the last element returned by the iterator
public void remove() { if (!removeOK)
throw new IllegalStateException();
ArrayIntList.this.remove(position - 1);
position--;
removeOK = false;
}
}
}