package cop3530; public interface Set<AnyType> extends Iterable<AnyType> { boolean isEmpty( ); int getSize( ); boolean add( AnyType x ); boolean remove( AnyType x ); boolean contains( AnyType x ); java.util.Iterator<AnyType> iterator( ); }In interface Set, observe the following:
Here is the rough outline of the implementation:
package cop3530; import java.util.Comparator; import java.util.NoSuchElementException; public class SortedArraySet<AnyType> implements Set<AnyType> { public SortedArraySet( ) { /* Implementation not shown */ } public SortedArraySet( Comparator<? super AnyType> c ) { /* Implementation not shown */ } public boolean isEmpty( ) { /* Implementation not shown */ } public int getSize( ) { /* Implementation not shown */ } public boolean add( AnyType x ) { /* Implementation not shown */ } public boolean remove( AnyType x ) { /* Implementation not shown */ } public boolean contains( AnyType x ) { /* Implementation not shown */ } private class LocalIterator implements java.util.Iterator<AnyType> { public boolean hasNext( ) { /* Implementation not shown */ } public AnyType next( ) { /* Implementation not shown */ } public void remove( ) { if( !okToRemove ) throw new IllegalStateException( ); okToRemove = false; SortedArraySet.this.remove( items[ --current ] ); } private int current = 0; private boolean okToRemove = false; } public java.util.Iterator<AnyType> iterator( ) { /* Implementation not shown */ } public String toString( ) { /* Implementation not shown */ } private void doubleArray( ) { /* Implementation not shown */ } private int compare( AnyType lhs, AnyType rhs ) { if( cmp != null ) return cmp.compare( lhs, rhs ); else return ((Comparable)lhs).compareTo( rhs ); } private AnyType [ ] items; private int theSize; private Comparator<? super AnyType> cmp; }
A SortedArraySet object is created by supplying a java.util.Comparator function object that determines the sorted order; if none is given, it is assumed that the items all implement the java.lang.Comparable interface and can be compared by calling compareTo. This logic is implemented for you in the private helper method compare. The cmp private data member should be initialized by the constructor(s).
In implementing the SortedArraySet you must use a sorted array of AnyTypes as the private data (shown as items), along with a theSize field. You should not need to throw any runtime exceptions. The array items initially starts with length 5, and is doubled in the add routine when capacity is reached. You may not replace this with any of the java.util.List implementations. Also, note that duplicates are not allowed. An item is already seen if the comparator says so (specifically, DO NOT use equals to make the determination).
Your implementation will almost certainly want to add some private methods to perform some of the repetitive tedious work.
Finally, the implementation of SortedArraySet requires that you implement the LocalIterator class, which itself implements the Iterator interface. This one is fairly tricky to code. You are not required to detect ConcurrentModificationExceptions (i.e. changes to the Set made by others outside of the iterator). But you should throw a NoSuchElementException if the call to next is out-of-bounds. I have provided an implementation of the trickiest part of LocalIterator; you have to fill in the rest. The implementation shows that it is ok to call remove only if the last call to next has not already had a call to remove made.
For this assignment only, it is important that you provide Javadoc comments for both the Set interface and the SortedArraySet class.