• Multiset. In a prior assignment, you implemented a Multiset274 class. You will repeat that exercise here but using generics and a Map to represent the multiset: MapMultiset274. This class will use a Java Map to represent the frequency counts. For example, if the following items were added to the MapMultiset274: A, A, B, B, C, D the underlying map would look like:

Key	Value
A	2
B	2
C	1
D	1

If two Bs were deleted, the map would now look like:

Key	Value
A	2
C	1
D	1

You will need to ensure that the keys are present only if their corresponding frequency count is > 0.

import java.util.HashMap;

public class MapMultiset274 implements Multiset274 { // We will assume that T is a class that has a hashCode and equals // methods defined. // These are the only data members that you can use. protected HashMap counts; protected int numItems; @Override public int size() { // TODO Auto-generated method stub return 0; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return false; } @Override public void add(T item) { // TODO Auto-generated method stub } @Override public boolean remove(T item) { // TODO Auto-generated method stub return false; } @Override public int removeAll(T item) { // TODO Auto-generated method stub return 0; } @Override public void clear() { // TODO Auto-generated method stub } @Override public int frequency(T item) { // TODO Auto-generated method stub return 0; } @Override public Object[] toArray() { // TODO Auto-generated method stub return null; } }

/* * A multiset is an unordered collection class that allows duplicates. * As a collection class, it supports add and remove operations. In addition, * the typical methods - size, isEmpty, clear, toArray - are also present. * One of the key features of a multiset, is a method named frequency, * which returns the number of copies of an item present in the collection. */

public interface Multiset274 { /** * Returns the number of elements in this multiset (its cardinality). * * @return the number of elements in this multiset (its cardinality) */ public int size();

/** * Returns true if this multiset contains no elements. * * @return true if this multiset contains no elements */ public boolean isEmpty();

/** * Adds the specified element to this multiset. * * @param item element to be added to this multiset */ public void add(T item);

/** * Removes one occurrence of the specified element from this multiset. * * @param item The item to be removed. * @return true if this multiset contained the specified element */ public boolean remove(T item);

/** * Removes all occurrences of the specified element from this multiset. * * @param item The item to be removed. * @return the number of items removed */ public int removeAll(T item);

/* * Removes all of the elements from this multiset. The multiset will * be empty after this call returns. */ public void clear();

/** * Returns The number of occurrences of the specified element. * * @param item element whose presence in this multiset is to be tested. * @return number of occurrences the specified element */ public int frequency(T item);

/** * Returns an array containing all of the elements in this multiset. * * @return an array containing all the elements in this multiset */ public Object[] toArray(); }

public class MultisetDriver { public static void demoStrings(Multiset274 ms) {

// The following should display: 0 0 0 0 System.out.printf("%d %d %d %d%n", ms.size(), ms.frequency("A"), ms.frequency("B"), ms.frequency("C")); ms.add("A"); ms.add("A"); ms.add("B"); ms.add("A"); ms.add("B"); // The following should display: A A B A B (but in no particular order) Object [] strings = ms.toArray(); for (Object obj : strings) { String str = (String)obj; // The multiset contains only strings, so can cast System.out.print(str + " "); } System.out.println(); // The following should display: 5 3 2 0 System.out.printf("%d %d %d %d%n", ms.size(), ms.frequency("A"), ms.frequency("B"), ms.frequency("C")); // The following should display: true true false System.out.printf("%s %s %s%n", ms.remove("A"), ms.remove("B"), ms.remove("C")); // The following should display: 3 2 1 0 System.out.printf("%d %d %d %d%n", ms.size(), ms.frequency("A"), ms.frequency("B"), ms.frequency("C")); // The following should display: 2 System.out.println(ms.removeAll("A")); // The following should display: 1 0 1 0 System.out.printf("%d %d %d %d%n", ms.size(), ms.frequency("A"), ms.frequency("B"), ms.frequency("C")); ms.clear(); // The following should display: 0 0 0 0 System.out.printf("%d %d %d %d%n", ms.size(), ms.frequency("A"), ms.frequency("B"), ms.frequency("C")); } public static void main(String [] args) { demoStrings(new MapMultiset274()); }

}