Question: A Multi Set, as described in Exercise is like a Set, but allows duplicates. Exercise suggested an implementation that uses a Map, in which the value represents a count of the number of duplicates. However, that implementation loses information. For instance if we add a Big Decimal representing 4.0 and another Big Decimal representing 4.000 (note that for these two objects, compare To yields 0, but equals yields false), the first occurrence will be inserted with a count of 2, and to String will necessarily lose information about 4.000 being in the multiset. Consequently, an alternative implementation would be to use a Map, in which the value represents a list of all additional instances of the key. Write a complete implementation of the Multi Set, and test it by adding several logically equal Big Decimals.
Exercise: A Multi Set is like a Set, but allows duplicates. Consider the following interface for a Multi Set:
public interface MultiSet
{
void add( AnyType x );
boolean contains( AnyType x );
int count( AnyType x );
boolean removeOne( AnyType x );
boolean removeAll( AnyType x );
void toArray( AnyType [] arr );
}
There are many ways to implement the Multi Set interface. A Tree Multi Set stores items in sorted order. The data representation can be a Tree Map, in which the key is an item that is in the multiset, and the value represents the number of times the item is stored. Implement the Tree Multi Set, and make sure to String is provided.