import java.util.Iterator; import java.util.ListIterator; /** * An array (expanding as needed) implementation of the SimpleList interface * Also implements an iterator so it can be used in a for-each loop * * @author Tim Pierson, Dartmouth CS10, Winter 2024, based on prior terms GrowingArray */ public class GrowingArray implements SimpleList, Iterable { private T[] array; private int size; // how much of the array is actually filled up so far private static final int initCap = 10; // how big the array should be initially public GrowingArray() { array = (T[]) new Object[initCap]; // java generics oddness -- create an array of objects and typecast to array of T size = 0; } /** * Return the number of elements in the List (they are indexed 0..size-1) * @return number of elements */ public int size() { return size; } /** * Returns true if there are no elements in the List, false otherwise * @return true or false */ public boolean isEmpty() { return size == 0; } /** * Add item at index idx, move other items to make a hole for this new item * @param idx index to add * @param item item to add * @throws Exception invalid index */ public void add(int idx, T item) throws Exception { if (idx > size || idx < 0) throw new Exception("invalid index"); if (size == array.length) { // Double the size of the array, to leave more space T[] copy = (T[]) new Object[size*2]; // Copy it over for (int i=0; i=idx; i--) array[i+1] = array[i]; array[idx] = item; size++; } /** * Add item at end of List * @param item - item to add to List * @throws Exception */ public void add(T item) throws Exception { add(size,item); } /** * Remove and return the item at index idx. Move items left to fill hole. * @param idx index of item to remove * @return the value previously at index idx * @throws Exception invalid index */ public T remove(int idx) throws Exception { if (idx > size-1 || idx < 0) throw new Exception("invalid index"); T data = array[idx]; // Shift left to cover it over for (int i=idx; i= 0 && idx < size) return array[idx]; else throw new Exception("invalid index"); } /** * Overwrite item at index idx with item parameter * @param idx index of item to get * @param item overwrite existing item at index idx with this item * @throws Exception invalid index */ public void set(int idx, T item) throws Exception { if (idx >= 0 && idx < size) array[idx] = item; else throw new Exception("invalid index"); } public String toString() { String result = "["; for (int i = 0; i < size-1; i++) { result += array[i] + ", "; } if (size > 0) { result += array[size - 1]; } result += "]"; return result; } /** * Returns an iterator over the elements in this List. * @return iterator */ public Iterator iterator() { //satisfy iterator requirement in SimpleSet interface return new ListIterator(); } /** * Iterator class that implements the required functionality to use this List in a for each loop */ private class ListIterator implements Iterator { // Use curr to point to next item in List int curr; public ListIterator() { curr = 0; } /** * Does iterator have more items? * * @return true if more items, false otherwise */ public boolean hasNext() { return curr < size; } /** * Return the next item in the iterator, advance to next item in list * * @return item stored at curr position in the list */ public T next() { if (curr >= size) { throw new IndexOutOfBoundsException(); } curr++; return array[curr-1]; } } }