CS203
Spring 2013
April 8

Assign 3 due: Mon, April 15

• Implement a polymorphic type
• Gain experience using Java’s Generics

1. Launch Netbeans, and create a new project named assign3 under your cs203 course directory
   • make the main class Examples rather than the default
2. Add the tester.jar file to your project’s Libraries

Exercise 8.7 (p. 205) from Liskov:

Specify and implement a Bag type that can hold elements of arbitrary types. Bags are like sets except that they can contain multiple copies of an element. Your bags should have insert, remove, and size methods, implement the Iterable interface, as well as provide the following method:

/**
 * EFFECTS: Returns a count of the number of occurrences of x in this Bag.
 */
public int card (T x)

Be sure to define the rep invariant and abstraction function and to implement toString and repOK.

Finally, be sure to test your Bag implementation on at least two different types of objects (e.g., Strings and Integers).

Your Bag clients love how they can use your generic Bag collection to store different types of objects, but there have been some complaints about performance. In particular, the card method takes too long to compute for very large Bags. After careful analysis you discover the problem is with the choice of underlying data structure to store the elements of your Bag. The solution is to Refactor your Bag implementation, using a HashMap instead of an ArrayList. If you need to refresh youself on the HashMap collection class, see:
http://docs.oracle.com/javase/7/docs/api/index.html?java/util/HashMap.html

• change your field declaration for your Bag’s elements from

      private ArrayList<T> elems;

  to

      private HashMap<T, Integer> elems;

  where each entry in the HashMap associates a bag element with its number of occurrences in the bag.

• Refactor the rest of your Bag methods so they work with the new underlying data structure
• Your Examples class should continue to work unchanged from the Lab 9 version.

When you’re ready to submit the assignment:
$ submit203 assign3 <assign3-root-dir>