Lab 06: A Set Collection Due: date-time

Lab 06: A Set Collection

Learning Objectives

  • Explore another collection interface.
  • Develop a Java 5 generic implementation for a collection.
  • Work with raw arrays for internally representing a collection.
  • Develop test cases for collection methods.

Overview

In this lab you will complete the implementation of a collection called a set. After examining its interface, you will complete an implementation that uses formal Java 5 generics. In lab last week, you used an ArrayList object as the underlying implementation mechanism for the bag collection. This week, you'll implement a set using an actual array.

Part I: A Set Collection

A set is a collection of objects that contains no duplicates. Adding an element to a set has no effect if an equal element is already contained in the set. Like the bag collection from last week's lab, a set has no inherent order, so there is no notion of position.

  1. First, determine with your partner who will initially play the roles of driver and navigator. Review the principles of pair programming if necessary.

  2. Download and unzip the files provided for this lab (lab06files.zip). Create a new project for this lab in Eclipse and add all files to its source directory. Don't forget to include CS2114-Support.

  3. The file Set.java contains an interface that describes a set collection. This is a subset of the java.util.Set interface defined in the Java API (the java.util.Set interface is a bit too long to implement in lab). Do not make changes to this interface.

    1. Discuss the interface methods with your partner, noting the use of the parameterized type Item.

    2. Note also the @precondition and @postcondition tags in the javadoc comments. A collection could be defined so that it allows null elements. In this case, null elements are not allowed.

  4. The ArraySet.java file contains a partial implementation of the ArraySet class, which implements the Set interface. Your task is to complete this class. Create exhaustive test cases for each method of ArraySet AS YOU GO. An ArraySetTest class has been provided for you as a starting point, but note that most of its tests are not yet written, and in many cases, you will want to have multiple test cases for each ArraySet method to check all possible behaviors. Don't wait until you've completed the implementation to perform unit testing. For this lab, it is sufficient to use String objects as elements of the set in your tests.

    1. Examine the implementation of the ArraySet constructor, which uses an initial capacity of 10 (using the declared constant, of course). Remember (from the implementation of the KWArrayList class) that you can't instantiate an array of the generic type -- you have to create an array of Object and cast it into an array of the generic type. Examine carefully how it creates the array.

    2. You have been given the implementations of size(), isEmpty(), and toString(), and you have also been given corresponding test cases for them (of course, the tests won't pass until you implement add(), later). Briefly examine these methods so that you understand how they work, and then move on to the next step.

    3. By thinking carefully for a moment about the add(), remove(), and contains() methods for a set, you can find common behavior and improve the design of your implementation. You only add a new element if it isn't already in the set. And to remove an element, you first must find it. The contains() method is used to determine if an element is in the set, returning a boolean result. So while add() could make use of contains(), both contains() and remove() could benefit from a private helper method that returns the index of the found element.

    4. Write test cases for the contains() method (some test cases might use add(), so they may not pass until you have implemented it as well--but not every test for contains() should require add()). Write a private helper method that takes an item and returns its index in the array, or -1 if it was not found. Then complete the implementation of the contains() method.

    5. Now write test cases for the add() method. Remember, do not attempt to write test cases that violate a method's preconditions.

    6. Complete the implementation of the add() method, which first asserts the precondition, then checks to see if the capacity of the array has been reached and expands it if necessary. Be sure to run the test cases you have, to make sure that your work so far behaves as you expect. And note that since there is no concept of position, you can always add a new element to the next empty position in your array.

    7. The expandCapacity() private helper method doesn't really change the capacity of an existing array (you can't change the size of an array once it is created). Instead, it creates a new array twice as big as the old one, then copies over the existing contents to the new array. Complete this method. Note that you won't write test cases for it directly, since it is private--instead, it will be tested by your test cases for add(). Note that expandCapacity() won't be covered unless you write a test case that causes the set to fill up beyond its capacity; use the set2 variable given in the test class that has an initial capacity of 1 to make testing this easier.

Part II: Finishing the Set Implementation

  1. Switch roles with your partner at this point. The driver will now be the navigator and vice versa. As always, respect these roles.

  2. Now implement the clear() and write the corresponding test for it. When implementing clear(), avoid the temptation to write a loop or call remove()--think of a simpler, faster way (discuss with your partner on how to do this, or ask for help if neither of you can think of a way).

  3. Submit your code to Web-CAT. Fix any problems, and resubmit as necessary. Maximize your score now.

  4. Write test cases for the remove() method and then complete its implementation. When you remove an item from the set, you don't want to leave a "hole" in the array where the removed item was. Instead, you need to shift the items after the one that was removed back one position. Think carefully about how you would write a for-loop to do this -- be cautious of off-by-one errors. Page 75 of the textbook has an example of this in their implementation of remove() for the KWArrayList.

  5. Write test cases for the equals() method and then complete its implementation. Remember that this equals() method determines if one set is equal to another. Two sets are equal if they contain the same elements. But the elements need not be in the same order in the arrays of the two sets. So to determine if two sets are equal, see if each element in one set is contained in the other, and that there are no "extra" elements in either set (that both sets are the same size).

  6. Write test cases for the removeAny() method and then complete its implementation. Note that, unlike last week, this implementation is not set up to select an item at random to remove. Instead, since clients of this class cannot count on any particular item being removed, we can select any one. Why not pick the item that is easiest to remove? Think of which is easiest, and use that choice in implementing removeAny() (here's a hint: the easiest element to remove can be removed without modifying the contents of the array at all). Also, avoid calling remove() within removeAny() (if you're not sure why, discuss it with your partner).

Part III: Final Submission to Web-CAT

  1. Continue to submit your code to Web-CAT.

  2. Examine the results, fix any problems, and resubmit as necessary.

  3. Each partner should keep a local copy of the submission.