<![CDATA[
// Stuart Reges handout #5
// 4/1/05
//
// Class IntList can be used to store a list of integers. It has several
// methods that involve indexing the list. As with Java arrays and Strings,
// index values start with 0. This variation of the IntList will expand if
// necessary to a larger capacity. Class IntList has the following public
// methods:
//
// public IntList()
// constructs an integer list of default capacity
// public IntList(int capacity)
// constructs an integer list with given capacity
//
// public int size()
// returns the current number of elements in the list
// public int get(int index)
// returns the integer at the given index
// public String toString()
// returns a String representation of the list
// public int indexOf(int value)
// returns the index of the given value in the list, -1 if not found
// public boolean isEmpty()
// returns true if the list is empty, false otherwise
// public boolean contains(int value)
// returns true if the list contains the given value, false otherwise
//
// public void add(int number)
// appends the given number to the end of the list
// public void add(int index, int number)
// inserts the given number at the given index, shifting subsequent values
// right
// public void addAll(IntList other)
// appends all values in the given list to the end of this list
// public void remove(int index)
// removes the value at the given index, shifting subsequent elements left
// public void removeAll(IntList other)
// removes all occurrences of the values in the given list from this list
// public void set(int index, int number)
// replaces the value at the given index with the given value
// public void clear()
// removes all elements from the list making it empty
// public void ensureCapacity(int capacity)
// potentially increases capacity so list can grow to given capacity
// public IntListIterator iterator()
// returns an iterator for this list
public class IntList {
private int[] elementData; // list of integers
private int size; // current number of elements in the list
public static final int DEFAULT_CAPACITY = 100;
// post: constructs an empty list of default capacity
public IntList() {
this(DEFAULT_CAPACITY);
}
// pre : capacity >= 0
// post: constructs an empty list with the given capacity
public IntList(int capacity) {
if (capacity < 0)
throw new IllegalArgumentException("negative capacity");
this.elementData = new int[capacity];
this.size = 0;
}
// post: returns the current number of elements in the list
public int size() {
return this.size;
}
// pre : 0 <= index < size()
// post: returns the integer at the given index in the list
public int get(int index) {
checkIndex(index);
return this.elementData[index];
}
// post: creates a comma-separated, bracketed version of the list
public String toString() {
String result = "[";
if (this.size > 0) {
result += this.elementData[0];
for (int i = 1; i < this.size; i++)
result += ", " + this.elementData[i];
}
result += "]";
return result;
}
// post : returns the position of the first occurence of the given
// value (-1 if not found)
public int indexOf(int value) {
for(int i = 0; i < this.size; i++)
if (this.elementData[i] == value)
return i;
return -1;
}
// post: returns true if list is empty, false otherwise
public boolean isEmpty() {
return this.size == 0;
}
// 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 the given value to the end of the list
public void add(int value) {
ensureCapacity(this.size + 1);
this.elementData[this.size] = value;
this.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 > this.size)
throw new IndexOutOfBoundsException("illegal index");
ensureCapacity(this.size + 1);
for (int i = this.size; i > index; i--)
this.elementData[i] = this.elementData[i - 1];
this.elementData[index] = value;
this.size++;
}
// post: appends all values in the given list to the end of this list
public void addAll(IntList other) {
for (int i = 0; i < other.size; i++)
this.add(other.elementData[i]);
}
// 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 < this.size - 1; i++)
this.elementData[i] = this.elementData[i + 1];
this.size--;
}
// post: removes all occurrences of the values in the given list from
// this list
public void removeAll(IntList other) {
int newSize = 0;
for (int i = 0; i < this.size; i++)
if (!other.contains(this.elementData[i])) {
this.elementData[newSize] = this.elementData[i];
newSize++;
}
this.size = newSize;
}
// pre : 0 <= index < size()
// post: replaces the integer at the given index with the given value
public void set(int index, int value) {
checkIndex(index);
this.elementData[index] = value;
}
// post: list is empty
public void clear() {
this.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 > this.elementData.length) {
int newCapacity = this.elementData.length * 2 + 1;
if (capacity > newCapacity)
newCapacity = capacity;
int[] newList = new int[newCapacity];
for (int i = 0; i < this.size; i++)
newList[i] = this.elementData[i];
this.elementData = newList;
}
}
// post: returns an iterator for this list
public IntListIterator iterator() {
return new IntListIterator(this);
}
// post: throws an exception if the given index is out of range
private void checkIndex(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException("illegal index");
}
}
]]>
<![CDATA[
// Stuart Reges
// 4/4/05
//
// The IntListIterator class provides a set of utilities for iterating over
// an IntList and possibly removing values from the list.
public class IntListIterator {
private IntList list; // list to iterate over
private int position; // current position within the list
private boolean removeOK; // whether it's okay to remove now
// pre : list != null
// post: constructs an iterator for the given list
public IntListIterator(IntList list) {
this.list = list;
this.position = 0;
this.removeOK = false;
}
// post: returns true if there are more elements left, false otherwise
public boolean hasNext() {
return this.position < this.list.size();
}
// pre : hasNext()
// post: returns the next element in the iteration
public int next() {
if (!this.hasNext())
throw new NoSuchElementException();
int result = this.list.get(this.position);
this.position++;
this.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 (!this.removeOK)
throw new IllegalStateException();
this.list.remove(this.position - 1);
this.position--;
this.removeOK = false;
}
}
]]>