CPSC 211 10S Term Project
Part 1: Implementing a Set

Contents

• Project Overview
• Set
• Details
• Iterator
• Testing
• Grading
• Deliverables

• a1.zip: the files with the code that is used for this part. (See below for how to import this code into Eclipse.)

Project Overview

Over the course of four assignments, you and a partner will produce a music library with functionality similar to programs such as Microsoft Windows Media Player and Apple iTunes.

Your program will allow the user to perform a variety of organizational tasks related to music collections, such as viewing and editing artist, title, album and genre data, and filtering views with a desired constraint (e.g., to see all songs in a particular album). You will also be able to play, pause, stop and seek through songs using a provided MP3 playback library.

This project presents a great opportunity to develop a commercial-quality music library application. How far you take it will be up to your creativity!

Set

The music library application requires the ability to store songs in a data structure. As it will be obvious later, the structure used to store the collection of songs will be very important for the application. In later parts of the project, you will experiment with several different data structures for the song collection. Initially, we will use a simple structure called 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. 

In part 1 of this project, you will implement a Set class and its iterator, which will be used in part 2 to hold the set of songs for a music library.

Details

An implementation of a set can be realized in more than one way. In this part of the project, you are to implement and test an ArraySet class in Java that implements the Set interface we provide in the 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. It would be inappropriate for us to implement a set that was capable of storing only song objects; although such a class would be useful for the music library application, it would not be useful  for many other applications that might need the functionality of a set. A further 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 Song has already been defined:

Set songSet = new ArraySet();

//Add a song object to the set
songSet.add( new Song() );  // no problem; a Song is a subclass of Object   (Song is-a Object)
 
// Create an array with the songs in the set:
// Song[] songs  = songSet.toArray(); 
 
// This code won't compile because an Object [] (returned by toArray())  is NOT an array of Songs.  
// Instead, we need to do the following:

Object[] songs  = songSet.toArray();
Song s = (Song) songs[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 10 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; do not try to keep track of null entries in the underlying 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 ubc.cs.cpsc211.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 songs that are stored in a song set:

Remember: Your goal in this part of the project is to build ArraySet and an iterator for it. You will not be working with Songs until the next part of the project.

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:

• 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.
• 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 a1.zip (also listed in the Resources section above) 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 will examine later in the course. To prevent confusion and possible errors we use different names than those used in the Java library.

Loading the Assignment Files

1. Save the assignment files (a1.zip) into a directory on your computer.
2. In Eclipse, create a new Java Project (File->New->Java Project). Let's assume you have named this project "AssignmentOne".
3. Right click on the AssignmentOne project in the PackageExplorer. Select Import. Expand the General category and select "Archive File". Press Next. Open up the a1.zip archive file. Click "Finish".
4. When prompted, allow the imported files to overwrite your .project and .classpath files. (This will ensure JUnit is enabled for your project.)

You should now have two packages in your project: ca.ubc.cs.cpsc211.utility and ca.ubc.cs.cpsc211.utility.test.

Testing

The assignment zip file a1.zip (listed in the Resources section above) contains a number of  JUnit tests for your ArraySet class.  In the first lab, you learned how to run JUnit tests from Eclipse. 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 tests.  

Grading

The following criteria will be used to grade this assignment:

• The correctness of your implementation. (Do your methods satisfy the invariants and postconditions? Have you taken into account any preconditions?)
• The readability of your code. (How easy will it be for someone else to read your code? Have you chosen descriptive identifiers for variables and methods? Did you use helper methods to make your code easier to read? Did you keep it simple?)
• The conciseness of your code (Did you use helper methods to avoid duplication of code? Did you keep it simple?)
• The number of the JUnit tests your code passes.

Deliverables

You should develop the assignment with your partner, but in the end only one of you will submit the final version for both of you.  Do not submit more than one copy for each group.  The person who will submit the project should do the following:

 If you have not done so, create a directory named  cs211 inside your home directory.  Inside cs211 create another directory named part1.  You should place all the files that you need to submit for this assignment in the part1 directory, before you issue the handin command, as it is stated below.

When you are ready to hand in your files, find the ArraySet.java file that you have completed and tested and copy it to the part1 directory. If you created the Eclipse project by following the instructions we gave you above,  this file should be in your workspace, in a directory that has the same name as the project you created.

Copy the cover page for this assignment in the directory part1 and fill it in. Make sure that your partner has also filled in his/her part in the cover page.

When you are ready to hand in your files, check that only the latest versions of  ArraySet.java  and the cover page  are in directory part1 and  type the following command:

handin cs211 part1

Now check that the handin process was successful with the command:

handin -c cs211 part1

You will see a list of all the files that were submitted. Check that you have submitted the necessary files and that you haven't submitted any extraneous files.

Last Updated : 21-Jun-2010 1:21 PM