====== Assignment 3 ======

~~NOTOC~~

** CS203 ** \\
** Spring 2013 ** \\
** April 8 **

//**Assign 3 due:**// //Mon, April 15//

===== Goals =====

  * Implement a polymorphic type
  * Gain experience using Java's Generics


===== Part 1 =====

  - Launch Netbeans, and create a new project named **//assign3//** under your ''cs203'' course directory
    * make the main class ''Examples'' rather than the default
  - 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:

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

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).





===== Part 2 =====

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 <code java> 
    private ArrayList<T> elems;
</code> to <code java>
    private HashMap<T, Integer> elems;
</code> 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.
  

===== Submission Details =====

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