Skip to content

PA 1: Multiset

Introduction

The Java collections framework provides interfaces corresponding to some of the most commonly used abstract data types: List, Map, Set, etc. One abstract data type that is not included is the Multiset.

The Multiset ADT is a generalization of the Set ADT that allows duplicate elements. Multisets are useful in cases where we don't care about the order of the elements but we do need to maintain a count of how many times each element appears. For example, in a document analysis domain we may need to count the number of occurrences of each word in the document. Such distributions of word frequencies can be useful for problems like authorship detection and topic classification.

The project stages below should be completed in order. Each part builds on the work completed in the earlier stages.

Starter Code

For this project, you will be making several modifications to the following Multiset implementation.

These modifications will improve the usability and efficiency of this collection. Make sure you understand the provided code before attempting to implement the rest of the project.

Note

The provided start code related to this PA have the package declaration package pas.multiset;. This means that the files should be placed in a directory named multiset inside a directory named pas inside your source/project directory.

You can reference the setup guide for a refresher on how to setup your projects and packages.

Part A: Getting Acquainted with Multiset

(10% of the final grade)

The goal of Part A is to understand the provided Multiset class and learn how to use it.

This part is designed as a combined review of CS159 coding concepts and generics. The majority of the work is in Part B.

Need Help?

If you're struggling with Part A, we recommend reviewing the basics of coding in Java and generics:

Follow the steps below to complete Part A:

1. Make Multiset Generic

Your first task is to modify the provided Multiset class so that it makes appropriate use of generics. The functionality should be unchanged, except that your improved class should accept a type parameter specifying an element type.

Once this phase of the project it complete, code like the following should compile and execute:

    Multiset<Character> chars = new Multiset<>();

    chars.add('a');
    chars.add('b', 3);
    chars.add('a');

    System.out.println(chars); // prints "[a x 2, b x 3]"

You should test your updated class by creating a test driver or some simple JUnit tests.

2. Complete the Roller Application

For this part of the project you will build a simple utility class that makes use of your generic multiset. Complete the following dice rolling class so that the methods conform to the provided Javadoc comments:

You will need to implement the multiRoll and plotRolls methods. You will also need to modify roll to throw the appropriate exceptions.

The following example illustrates the required format for the output of the plotRolls method. This code:

Roller roller = new Roller(10);
roller.plotRolls(1000, 3, 6, 10);

would result in:

Rolling 3d6 1000 times
3  :
4  :#
5  :###
6  :####
7  :#######
8  :########
9  :############
10 :############
11 :#############
12 :###########
13 :#########
14 :#######
15 :####
16 :##
17 :#
18 :
Note how the output is formatted. You have each possible sum, left-aligned with a width of 2, followed by a space and a colon. Then, you have a number of # characters representing the number of times that sum was rolled.

In the example, because the scale argument is set to 10, each # represents 10 outcomes, rounding down. So there were between 10-19 rolls with a sum of 4, since there is one # character.

You may want to review the String.format() and printf() methods to help with formatting the output.

Part A Submission

Submit Roller.java and your updated Multiset.java to Gradescope.

You must pass all style checks for the autograder to run.

Part B: Improving the Multiset Implementation

(60% of the final grade)

At this point, your Multiset collection is type-safe, but it violates the principle of separating implementation from interface. The Java Collections Framework provides some nice examples of putting this principle into action.

Learn more: ADT vs. Data Structure

The UML below shows a small subset of the classes and interfaces included in the collections framework. In this diagram the List interface expresses the methods that are associated with the List ADT. LinkedList and ArrayList are concrete classes that implement the List interface, each using a different underlying data structure. The various abstract classes provide default implementations for some methods to simplify the implementation of the concrete classes.

classDiagram
direction BT

class `java.lang.Iterable&lt;E&gt;` {
    <<Interface>>
}

class `java.util.Collection&lt;E&gt;` {
    <<Interface>>
}

class `java.util.List&lt;E&gt;` {
    <<Interface>>
}

class `java.util.AbstractCollection&lt;E&gt;` {
    <<Abstract>>
}

class `java.util.AbstractList&lt;E&gt;` {
    <<Abstract>>
}

class `java.util.AbstractSequentialList&lt;E&gt;` {
    <<Abstract>>
}


`java.util.Collection&lt;E&gt;` --|> `java.lang.Iterable&lt;E&gt;`
`java.util.List&lt;E&gt;` --|> `java.util.Collection&lt;E&gt;`
`java.util.AbstractList&lt;E&gt;` ..|> `java.util.List&lt;E&gt;`
`java.util.AbstractCollection&lt;E&gt;` ..|> `java.util.Collection&lt;E&gt;`
`java.util.AbstractList&lt;E&gt;` --|> `java.util.AbstractCollection&lt;E&gt;`
`java.util.ArrayList&lt;E&gt;` --|> `java.util.AbstractList&lt;E&gt;`
`java.util.LinkedList&lt;E&gt;` --|> `java.util.AbstractSequentialList&lt;E&gt;`
`java.util.AbstractSequentialList&lt;E&gt;` --|> `java.util.AbstractList&lt;E&gt;`

1. Create Multiset Interface

Your goal for this stage of the project is to split the existing Multiset class into an interface named Multiset and a concrete implementation named ArrayListMultiset.

Your finished code should conform to the UML diagram below. Classes in gray and with a dashed line are built-in and should not be implemented or modified.

classDiagram
direction BT

class Iterable["java.lang.Iterable&lt;E&gt;"] {
    <<Interface>>
}

class Collection["java.util.Collection&lt;E&gt;"] {
    <<Interface>>
}

class Multiset["Multiset&lt;E&gt;"] {
    <<Interface>>
}


Collection --|> Iterable
Multiset --|> Collection
`ArrayListMultiset&lt;E&gt;` ..|> Multiset

style Iterable fill:#eeea,stroke:#f66,stroke-width:2px,color:#000,stroke-dasharray: 5 5
style Collection fill:#eeea,stroke:#f66,stroke-width:2px,color:#000,stroke-dasharray: 5 5
Notice that your completed Multiset interface must extend the java.util.Collection interface. The advantage of this is that any method anywhere that expects a Collection object will now work correctly when passed a Multiset. The challenge is that the Collection interface requires several methods that are not included in the provided Multiset class.

You should start by renaming the existing Multiset class to ArrayListMultiset and then create a new interface named Multiset.

The UML of the Multiset interface is below for your reference: 

classDiagram
class Multiset["Multiset&lt;E&gt;"] {
    <<Interface>>
    +add(item: E) boolean
    +add(item: E, occurances: int) int
    +clear()
    +contains(item: Object) boolean
    +getCount(item: Object) int
    +equals(other: Object) boolean
    +iterator() Iterator&lt;E&gt;
    +remove(item: Object) boolean
    +size() int
    +toString() String
}

You can move the Javadoc comments from the ArrayListMultiset class to the Multiset interface.

2. Implementing the ArrayListMultiset

The ArrayListMultiset class should implement the Multiset interface.

Make sure you use @Override annotations in the ArrayListMultiset class to ensure that you are correctly overriding the methods from the Multiset interface. This also means that you don't need to provide Javadoc comments for any overridden methods.

In ArrayListMultiset, you must also implement any other required Collection methods, including those that are described as optional, with the exception of (Updated 2/3):

  • removeAll
  • retainAll
  • toArray (both versions)

These must return an UnsupportedOperationException instead.

You may use the following JUnit tests to confirm that your code matches the specification.

3. Creating a Better Multiset Implementation

The modifications so far have improved the usability of our original Multiset class, but they have not improved the efficiency. The current implementation is terribly inefficient in terms of both space and time.

Consider the following code snippet: 

    Multiset<String> set = new ArrayListMultiset<>();
    for (int i = 0; i < 10000; i) {
       set.add("Harrisonburg");
    }

After this code executes the ArrayList inside set will contain 10,000 copies of the string "Harrisonburg".

It would be much more efficient to store a single copy of "Harrisonburg" along with a counter. Subsequent calls to add would then increment the counter without actually increasing the number of objects stored in the ArrayList.

For this stage of the project you will create a new implementation of the Multiset interface named CounterMultiset. Instead of storing duplicate objects, this class should maintain a single copy of each object but paired with a count of the number of occurrences.

The resulting class hierarchy should align with the provided UML diagram:

classDiagram
direction BT

class Iterable["java.lang.Iterable&lt;E&gt;"] {
    <<Interface>>
}

class Collection["java.util.Collection&lt;E&gt;"] {
    <<Interface>>
}

class Multiset["Multiset&lt;E&gt;"] {
    <<Interface>>
}


Collection --|> Iterable
Multiset --|> Collection
`ArrayListMultiset&lt;E&gt;` ..|> Multiset
`CounterMultiset&lt;E&gt;` ..|> Multiset

style Iterable fill:#eeea,stroke:#f66,stroke-width:2px,color:#000,stroke-dasharray: 5 5
style Collection fill:#eeea,stroke:#f66,stroke-width:2px,color:#000,stroke-dasharray: 5 5

Implementation Tips

Read carefully:

  1. Don't be fooled by the fact that most of the methods in ArrayListMultiset.java are simple one-liners. This will not be the case for CounterMultiset.java. For example, you will need to create a custom Iterator class for CounterMultiset. You won't be able to use the existing iterator of the ArrayList class.
  2. Use the @Override annotation where appropriate! This has several benefits. It will prevent you from making some sneaky coding errors (overloading/duplicating methods instead of overriding them). It will also allow you to avoid writing Javadoc comments for overridden methods: it is generally not necessary to provide Javadoc comments for overridden methods, as long as the description in the superclass or interface provides an adequate description of the methods behavior.
  3. Instead of storing duplicate objects, this class must use a member from Java Collections Framework to maintain a single copy of each object along with a counter to track its occurrences. You need to determine the most appropriate Java Collection to effectively associate each unique object with its count (like the Collections lab).
  4. (Updated 2/3) For the CounterMultiset iterator, remember, remove() removes the previously returned item from the collection. (See the Java documentation)
    • You should keep track of the "current" element you are on AND the last element that next() returned.
    • For example, if your iterator has returned: a, a, b and you call remove(), the last element returned was b, so you should remove one b from the collection.
    • For an example of how to write an iterator (and remove method), see the PairList.java and Pair.java classes.
    • Don't forget to throw an IllegalStateException if remove() is called before next() or if remove() is called twice in a row!

You may test your finished implementation using the following JUnit tests:

Ignoring the advice above will negatively impact your grade, even if your code passes all of the submission tests.

Part C: Workload Analysis

(10% of the final grade)

It was claimed above that the counter implementation is much more efficient than the ArrayList implementation for the Multiset ADT. Strictly speaking, this claim depends on the actual sequence of operations performed.

Take a few minutes to think about scenarios where the CounterMultiset will have an advantage and scenarios where it will not, then complete the following driver class so that it conforms to the Javadoc comments.

For example, in counterFriendlyOperations, you need to set up a scenario where the CounterMultiset will be more efficient than the ArrayListMultiset. Gradescope will run the method with both implementations and compare the time taken to complete the operation.

Part B & C Submission

Submit Multiset.java, ArrayListMultiset.java, CounterMultiset.java, and WorkloadDriver.java to Gradescope.

Submission and Grading

The project will be graded as follows:

Gradescope Functionality Tests for Part A10%
Gradescope Functionality Tests for Part B60%
Gradescope Style Checks for Part B10%
Gradescope Timing Tests for Part C10%
Gradescope Instructor Style Points10%

Acknowledgments

The Multiset interface used for this project is based on a similar interface included with the the Guava Google Java libraries.