Java Programming Project

Java Programming Project

Implementing a Set

A set is a collection of items without duplicates and in no particular order (i.e., unordered). A user may add items to a set, remove items from a set and check whether an item is in a particular set. Occasionally, the elements in the set must be accessed one at a time; for instance, this is necessary to list the set elements to the standard output. An Iterator object supports accessing each element of a set, one at a time.

Details

An implementation of a set can be realized in more than one way. You are required to implement and test an ArraySet class in Java that implements the Set interface we provide in the attached code. You must implement the set by using an array whose elements are of type Object. Note that such an array is capable of storing objects of any type, so the ArraySet class will be useful in many different contexts. A consequence of using an array of Objects to store the items in the set becomes apparent when code is written to use the toArray method of the set, as illustrated in the following code snippet, where it is assumed that a class Player has already been defined:

Set playerSet = new ArraySet();

//Add a player object to the set

playerSet.add( new Player() );

// no problem a Player is a subclass of Object (Player is-a Object)

// Create an array with the players in the set:
// Player[] players = playerSet.toArray();

// This code won't compile because an Object [] (returned by toArray()) is NOT an array of Player`s.
// Instead, we need to do the following:

Object[] players = playerSet.toArray();

Player p = (Player) players[i];

// we have to cast each individual object to the appropriate type when we use it

Your implementation of the ArraySet class must support initially holding ten items. If there is an attempt to add one more item than the current size allows, the size of the set must double. One way to do this is to create a new array that is twice the size of the current array and add all of the data from the current array to the new array.

When an item is added to the set, you should add the item to the end of the array. When an item is removed from the set, another item in the set must be moved into the recently vacated slot (you should determine which item to move). In the case of removal, your implementation must not move more than one element to remain efficient.

Your implementation of the ArraySet class must implement the interface provided by the Set class in the source files provided. You must strictly adhere to the specification in this document. Be sure to use helper methods to keep all of the methods that you implement concise and readable. The array expansion operation should be coded in a helper method.

Your ArraySet class is to be implemented in a package named utility.

Iterator

As stated earlier, to allow the the items of a set to be accessed, an iterator is used. An iterator for a set s is an object that implements the MyIterator interface and can access the items of s. At any given time, the iterator \"refers to\" an item in s. The iterator interface allows the user to access the set item that the iterator points to, advance the iterator to the next item in the set, and check whether there are more items in the set that have not yet been accessed by the iterator. The iterator's interface is defined by the interface MyIterator that is also provided in the source code for the assignment.

The only object that knows how to set up an iterator for a set is the set itself. For this reason, the Set interface extends the MyIterable interface, which contains a single method called iterator() that returns an iterator for that set. Therefore, the ArraySet you implement has to include its own iterator that can be returned when its method iterator() is called. The following code snippet illustrates how a client can use an iterator to print out the players that are stored in a player set:

Set playerSet = new ArraySet();
MyIterator itr = playerSet.iterator();

// get an iterator over the set playerSet

Player nextPlayer;
while( itr.hasNext() ){ // while there is a next element in the set
nextPlayer = (Player) itr.next(); // get the next element (note the cast from Object)
System.out.println( nextPlayer.toString() ); // print it out
}

The best way to define an iterator for an ArraySet is to do the following:

1. Define a private class inside the ArraySet class named SetIterator that implements the MyIterator interface. Such a class is called an inner class. There are several advantages to implementing the SetIterator as an inner class of the ArraySet class:
o The client of an ArraySet won't know that it exists. This is a good thing. All the client needs to know is that when they call the iterator() method they get back something (they don't care exactly what) that implements the MyIterator interface.
o It has direct access to the private members of the enclosing class. In other words, your SetIterator can access the private members of your ArraySet class. This is really useful as the SetIterator will need to extract data from the ArraySet.

2. Your SetIterator will have a single data member that stores the index of the next item to be returned by the iterator.

The zip file attached contains all of the interfaces as well as the the ArraySet.java file that contains a skeleton for the ArraySet and SetIterator classes. You just need to fill in the components of these classes in these files.

NOTE: The interfaces MyIterable and MyIterator are similar to ones defined in the Java library (Iterable and Iterator) that we have examined during the course. To prevent confusion and possible errors we use different names than those used in the Java library.

The \"sting in the tail\"

Now modify the classes to use Java Generics.

Testing

The assignment zip file contains a number of JUnit tests for your ArraySet class. Use the tests we provide to help assess your implementation. The mark for this part will be largely determined by how well your class passes these (and additional) tests. (We haven't included the generic versions of these tests; that is down to you.)