Description
The purpose of this project is for you to learn how to implement the Abstract Data Type (ADT)
called frequency bag. You will have to understand the behavior of the ADT frequency bag and
implement it using linked list.
The ADT Frequency Bag
The ADT frequency bag is an unusual ADT to store collection of data. Instead of storing each
item individually in this bag, we will store the frequency of each item added into the bag. For this
frequency bag, we will only store frequencies of various type of compatible objects. Thus, you must
develop this ADT using generic type. The following are behavior of our frequency bag:
• Users are only allowed to add entries into the bag but not remove.
• Users can check the number of items inside the bag.
• Users can empty the bag.
• Users can check the number of occurrence (frequency) of a specific item inside the bag.
• Users can check the maximum frequency of items inside the bag.
• Users can check the probability of a specific item inside the bag.
• There is no rule about how items are organized inside the bag.
For example, suppose a user create an empty frequency bag of class wrapper Integer named fb
and adds the following integer into the bag (in that order):
3, 6, 7, 1, 5, 2, 3, 7, 4, 7, 9, 5, 3, 7, 6, 4, 7, 4, 2, 5, and 3
The table below shows the frequency of data added into the bag:
Data Frequency
1 1
2 2
3 4
4 3
5 3
6 2
7 5
8 0
9 1
1
The following are returns values of some methods of this frequency bag:
1. fb.size() should return 21.
2. fb.getFrequencyOf(4) should return 3.
3. fb.getFrequencyOf(8) should return 0.
4. fb.getMaxFrequency() should return 5 since 7 has the maximum number of occurrences
which is 5.
5. fb.getProbabilityOf(6) should return 0.095238095 since 2/21 = 0.095238095.
What to Do?
For this project, you must develop two classes, FrequencyBag.java and CharacterFrequency.java.
Details about each class are as follows:
Part 1: FrequencyBag.java
For this project, you are going to create a class named FrequencyBag which is an implementation
of ADT frequency bag. Your class MUST use a linked list to store frequencies of data. Start
with the starter file named FrequencyBag which can be found in our CourseWeb under this project.
Do not change signatures of any methods.
Note that for this project, you must use linked list. As we discussed in class, linked list has a
drawback. Imagine if you develop your class using linked list to store items from the example in
previous page, you will end up with a linked list consisting of 21 nodes. Each node for each item.
Now, if you need to return the frequency of 3 (getFrequencyOf(3)), you need to traverse the linked
chain from the first node to the last node and count how many 3 are there. Same situation with
the method getProbabilityOf(). Imagine if you have to use this frequency bag to store 100,000
or more items. Any applications that use a lot of getFrequencyOf() and getProbabilityOf()
methods will suffer a huge performance lost.
Suppose you store data as a pair of data and frequency (e.g., (1,1), (2,2), (3,4), (4,3), . . .).
In doing so, the number of nodes in your linked chain to store the same set of data (shown in
the example on the previous page) is now only 8. Obviously the methods getFrequencyOf() and
getProbabilityOf() should run a little bit faster. For this project, you must implement
your frequencyBag this way because our test class will call methods getFrequencyOf()
and getProbabilityOf() very often.
Constructor
There will be only one constructor to construct an empty frequency bag as follows:
public FrequencyBag()
{
// TO DO
}
2
Methods
The following are methods from your starter code (FrequencyBag.java) that you must implement:
public class FrequencyBag
