A09

Due Date: Thursday, March 26
File(s) to be submitted: TreeMapBag.java
Sample Output: SampleOutput.html
Starter Files:

• Bag.java
• TestBag.java

TreeMapBag (Implementing Bag Using a java.util Class

Summary

In this assignment you will implement the Bag interface using a java.util.TreeMap.

NOTE: this is not the TreeBag class from the notes, tho' you may find some of the methods from that class helpful for your implementation.

Your implementation does not need to include iterator, but should include the containsAll, addAll, removeAll and retainAll methods.

Details

The ArrayBag and LinkedBag classes that we created earlier in the course went "back to basics" in order to help you understand how the ArrayList and LinkedList classes are implemented, and also to get a feel for why some data structures are good at some operations and worse at others.

But in general it is better to use the tools that Java provides to produce the results you need.

In this assignment you are going to use Java's TreeMap class to implement the Bag interface.

In the notes you will see a partial implementation of a TreeBag class. Your TreeMapBag class will operate in much the same way, but will use java.util's built in type to avoid some of the complicated programming necessary for making a balanced binary search tree.

In particular:

• The elements of the Bag will be the keys of the TreeMap.
• The value associated with each key/bag item will be its frequency in the Bag. So if "be" is in the Bag twice, then map.get("be") will return 2.
• Adding/removing items in the Bag is accomplished by adding/subtracting 1 to/from the associated value.
• Keys will be removed from the TreeMap when (and only when) their value drops to zero.

Your TreeMapBag class must have two constructors:

• TreeMapBag() which uses the natural order of the base type.
• TreeMapBag(Comparator<? super E>) which uses the given comparator to sort the elements.

To help you along, here are some notes on TreeMaps:

• The TreeMap class has (among others) constructors corresponding to the ones the TreeMapBag needs:
  • TreeMap() which uses the natural order of the base type.
  • TreeMap(Comparator<? super E>) which uses the given comparator to sort the elements.

  To implement your TreeMapBag constructors, you should call the corresponding constructors from the TreeMap class. (Do not use the this(...) call in either constructor.) That way, you will not have to worry at all about the way that the Bag elements are ordered.

• TreeBag has no add method. Instead you add a key to the TreeMap using the put method. For example,
  map.put("be", 1);
  will put "be" into map with an associated value of 1.
• The get method returns the value associated with the key given to it. For example,
  map.get("be")
  will return the value associated with "be", whether that be 1 or 2 (or whatever).
• The remove method removes the given key from the TreeMap. For example,
  map.remove("be")
  will remove the node associated with the key "be", including the value it has.
• There is no contains method. Instead use the containsKey method to determine whether a given key is in the map.
• TreeMap has a method called keySet that returns a Set containing all its keys. This Set can be used when you want to iterate thru the nodes of the tree.
• None of the ___All methods from the Collection interface are in TreeMap. You must write all of them yourself.

  removeAll and retainAll can be done a bit more efficiently using a TreeMap than they in ArrayBag and LinkedBag. All of the repeated elements are together in the structure.

  Beware of the dreaded ConcurrentModificationException! Why might you get one? How can you avoid it?

• TreeMap has a clear method.
• TreeMap has a size method, but it only tells you how many keys are in the TreeMap. That's not necessarily the same size as the Bag.