/** *
An implementation of the SimpleUSet
interface using
* an array to store the elements in the set.
the default capacity of the array storing the set's contents
*/ public static final int DEFAULT_CAPACITY = 16; private int size = 0; private int capacity; private Object[] contents; /** *Create a new ArraySimpleUSet with initial capacity
* DEFAULT_CAPACITY
.
Create a new ArraySimpleUSet with a given initial capacity.
* * @param capacity the desired initial capacity > 0 */ public ArraySimpleUSet(int capacity) { this.capacity = capacity; contents = new Object[capacity]; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean add(E x) { // check if x is already in the set for (int i = 0; i < this.size; ++i) { if (x.equals(contents[i])) return false; } // x is not in the set, so it must be added // check if we need to increase the capacity if (size == capacity) increaseCapacity(); // add x to the contents and increment the size contents[size] = x; ++size; return true; } @Override @SuppressWarnings("unchecked") public E remove(E x) { for (int i = 0; i < size; ++i) { if (x.equals(contents[i])) { Object y = contents[i]; removeAtIndex(i); return (E) y; } } return null; } @Override @SuppressWarnings("unchecked") public E find(E x) { for (int i = 0; i < size; ++i) { if (x.equals(contents[i])) { return (E) contents[i]; } } return null; } private void removeAtIndex(int j) { for (int i = j; i < size - 1; ++i) { contents[i] = contents[i+1]; } --size; } private void increaseCapacity() { Object[] bigContents = new Object[2 * capacity]; for(int i = 0; i < capacity; ++i) { bigContents[i] = contents[i]; } contents = bigContents; capacity = 2 * capacity; } }