This lab consists of four parts. The first three parts are compulsory, while the last part is optional (and will not be graded).
A multiset is a set that allows repetition of individual elements. Thus, adding an element always increases the cardinality by one, regardless of whether the element is already present. In this lab, you will implement a multiset of char.
Write a class that implements the MultiSetOfChar interface:
interface MultiSetOfChar {
int getCardinality();
int getElementCount(char target);
Set<Character> getElementSet();
void add(char item);
boolean remove(char target);
char randomUniformChoose();
}
As far as semantics (behavior) of these methods, your implementation should do the following:
getCardinality getElementCount getElementSet add remove randomUniformChoose Your implementation should be called DenseMultiSetOfChar and should make use of the Collections Framework. In addition, you should obtimize your implementation for containing many repetitions of relatively few distinct characters. That is, a DenseMultiSetOfChar should not use significantly (any?) more memory if it contains 100,000 repetitions of 'a' vs just one.
For your convenience, the test program TestDenseMultiSetOfCharSimple.java is provided. Your DenseMultiSetOfChar class should compile with this test program. This test program documents the expected behavior so it should help you ensure you have implemented the correct method behaviors as well as signatures.
How many characters are in the text of "Alice in Wonderland"? How many times does the character 'A' appear? In this part of the lab, you will implement a class that could be used to keep track of this information for every book in a library.
Write a class that implements the FrequencyLibrary interface:
interface FrequencyLibrary {
int size();
boolean contains(String target);
MultiSetOfChar getFrequencies(String target);
void add(String name, char element);
boolean remove(String name, char element);
char randomUniformChoose(String name);
}
As far as semantics (behavior) of these methods, your implementation should do the following:
size contains getFrequencies add remove randomUniformChoose Your implementation should be called DenseFrequencyLibrary and should make use of your solution to part 1 as well as the Collections Framework.
For your convenience, the test program TestDenseFrequencyLibrarySimple.java is provided. Your DenseFrequencyLibrary class should compile with this test program. This test program documents the expected behavior so it should help you ensure you have implemented the correct method behaviors as well as signatures.
Compare the run-time performance of your DenseMultiSetOfChar using two different choices for collection on which it is built. For example, if you wrote DenseMultiSetOfChar to use a HashSet, compare it with using a TreeSet instead. (I am not suggesting or advising you to use a HashSet for your solution! This is just an illustrative example.)
Note: you should be able to change between two implementations (such as HashSet and TreeSet) by changing a single line of code in your implementation.
For your convenience, a basic timing program Profiler.java is provided. Expand and modify this program until you have gathered enough performance data to observe the impact that choice of collection implementation makes on your code. For example, you might want to look at the performance of different methods under different circumstances (e.g., small/large cardinality or few/many repetitions). Include a text file in your submission that describes your findings. (Only a brief discussion is needed: a single paragraph.)
Note: This part of the lab is optional. It will not be graded, so you do not have to complete it in order to get full credit for the lab.
Modify the multiset interface provided as part of this lab to use generics. Modify your implementation of this interface accordingly.