Assignment #1: Java Generics

Covers

Basic programming techniques in Java. Generics in Java 1.5.

Basic Assignment

Implement a data structure that supports a sorted set. Later in the course we'll discuss how to implement a sorted set efficiently; for this assignment your code needs to be reasonable, but you do not have to go out of your way to make it very efficient.

Testing the Class

I will provide a program to test your implementation. Compile the program, and give me the output. Warning: you should probably write another program to make sure everything works. Notice that this code is not in any package. You have to leave it that way. Your data structures will be in package cop3530. Recall that this means you have to place those classes in a subdirectory named cop3530.

Requirements

Here is the class interface for cop3530.Set. You will implement your class as cop3530.SortedArraySet. You may not change the interface in any way whatsoever (except to add comments). You may not change the test program in any way; specifically, you may not move it into package cop3530. You should not add any new public methods to your implementation, but you can add private methods as needed to avoid replication of code.
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.

Grading

This is a relatively easy assignment; the coding is basically at the level of COP-3337 and the tricky generic stuff has basically been filled in for you already. So it is expected that your code will work, and if it doesn't the grade will be very low. I will also be carefully reading your code and deducting for bad style. I advise you to look at Fall 2002 Assignment #1 and the accompanying grading sheet to see the kinds of things that are certain to get deductions.

Submission Procedure

Submit all your source code, the results of running Javadoc, and the results of running the test program Assign1.java. Your source code should include a signed disclaimer that states the work is your own. Your submission must be stapled or otherwise bound together. Failure to follow these instructions will adversely affect your grade for the assignment.

System Things

Make sure you have a Java 1.5 compiler.

Collaboration Rules

This project is an individual project. Everyone should submit their own work. If I determine that two or more students have collaborated, then those students will all suffer identical consequences, regardless of who copied from whom.

Quiz

There will be a quiz at the start of class on the due date. You will be asked to write an interface and/or implementation for a similar data structure.

Relationship to Course Outcomes