Multiset Project

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.

For this project we are providing the following basic Multiset implementation:

Multiset.java

It will be your responsibility to make a series of modifications to improve the usability and efficiency of this collection. Make sure you understand the provided code before moving on with the rest of the project.

Part 1 - Generics

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.

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

There is nothing to submit for Part 1.

Part 2 - Interfaces (DUE 9 / 12)

Congratulations! Your Multiset collection is now type-safe. Unfortunately, your improved implementation still violates the central design commandment of this course:

THOU SHALT SEPARATE INTERFACE FROM IMPLEMENTATION

The Java Collections Framework provides some nice examples of putting this principle into action. 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.

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. You should not change the implementation of any of the existing methods.

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.

The optional methods removeAll and retainAll must return an UnsupportedOperationException.

You may use the following implementation of the hashCode method:

      /**
       * The role of the hashCode method will be addressed later in the semester.
       *
       * @return 1, always 1.
       */
      @Override
      public int hashCode() {
        return 1;
      }

All other Collection methods must be implemented, including those that are described as optional. Note that the java.util.AbstractCollection class provides default implementations for some of these methods. You are free to take advantage of that fact.

Note that you will need to make slight modifications to some method signatures in ArrayListMultiset. For example, the add method required by Collection must return a boolean value. For some collection types, this would be used to indicate whether the add operation actually changed the contents of the collection. For Multiset this can always return true.

You may use the following JUnit tests to confirm that your code matches the specification. Submit your completed files through Web-CAT.

• MultisetTest.java - This abstract class defines testing methods for each of the methods included in the Multiset interface. Any correct implementation should pass these tests.
• ArrayListMultisetTest.java - Subclass of MultisetTest that can be used to test your ArrayListMultiset implementation.

Part 3 - Building a Better Data Structure (DUE 9 / 19)

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 store Pair objects representing counters. The resulting class hierarchy should match the following UML:

(Again, You are encouraged to insert abstract superclasses if they simplify your implementation.)

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

• CounterMultisetTest.java - Subclass of MultisetTest.

Part 4 Demonstration Workload (DUE 9 / 19)

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.

WorkloadDriver.java

Submission and Grading

Submit all of your completed Multiset files along with WorkloadDriver.java through Web-CAT. The project will be graded as follows:

Web-CAT Funcionality Tests for Part 2	10%
Web-CAT Functionality Tests for Parts 3 and 4	50%
Web-CAT Style Checks for Parts 3 and 4	20%
Web-CAT Instructor Style Points for Parts 3 and 4	20%

Looking Ahead

The counter-based Multiset that you developed is, in general, much more efficient than the terrible implementation we provided. This raises the question of whether it is possible to develop an even more efficient implementation. It is. We’ll see several data structures later in the semester that could be used to create much better implementations of this ADT.

Acknowledgments

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