4.5 MULTISETS

This section under major construction.

Multisets. Multiset = unorder collection of elements, duplicates allowed. Sometimes referred to as a bag. Program LinkedMultiSet.java Implement a multiset using a linked list. It includes an add method for inserting an element and an iterator for traversing the elements. Program MultiSetDemo.java is a toy client. We use the encapsulating class LinkedMultiList for several reasons. First, we wish to hide the internal representation from the client. Second, we want it to work for empty lists. Third, we can store auxilliary information, e.g., the length of the list, instead of computing it from scratch each time. We use a private nested class for the data type Node. This hides the node data type from the outside world. We do not need to make the instance variables of the node data type private to maintain encapsulation. This enables us the convenience of being able to directly access the instance variables of the node data type, without breaking encapsulation.

A sample client. Read in a database consisting of the name of a song, followed by the name of one of three possible genre (rock, classical, or hip-hop). Create a multiset for each genre and put the song name in the appropriate set. After reading in all of the data, print out all of the songs, ordered by genre. If we knew ahead of time how many songs were in the database (or an upper bound on that quantity), we could store them in an array. Since we don't, a multiset is a natural data type to store an unbounded number of items.

Iterators. Sometimes the client needs to access all of the elements of a list, one at a time, without deleting them. We will need this kind of access when we implement graphs in Section XYZ. To maintain encapsulation, we cannot reveal the internal representation of the list (array or linked list) to the client. We solve this design challenge by introducing an Iterator interface. Any object that implements the Iterator interface promises to implement two methods: hasNext and next. The client uses these methods to access the list elements one a time using the following idiom.

Iterator i = s.iterator();
while (i.hasNext()) {
   Object x = i.next();
   // do something with x
}

To implement a list iterator, we create a subclass ListIterator in List.java....

Enhanced for loop.

ArayList<Integer> list = new ArrayList<Integer>();
for (Integer i : list) { ... }

Lessons

Q + A.

Q. Are generics solely for auto-casting?

A. No, but this will be the only thing we use them for. Here is a generics tutorial.

Exercises

Add a method Object[] toArray() to MultiSet that returns all N elements on the queue as an array of length N.

Creative Exercises

Copy a multiset. Create a new constructor so that MultiSet y = new MultiSet(x) makes r reference a new and independent multiset.
Array implementation of an iterator. Add iterator capabilities to MultiSetArray.
Set of integers. Create a data type that represents a set of integers (no duplicates) between 0 and N-1. Support add(i), exists(i), remove(i), size(), intersect, difference, symmetricDifference, union, isSubset, isSuperSet, and isDisjointFrom.
Multiset of letters. For anagrams, text twist.
TwoWayIterator. Define an interface TwoWayIterator that supports four methods: hasNext, hasPrevious, next, and previous. Implement a list that supports a TwoWayIterator. Hint: implement the list using an array or doubly linked list.

Adding a list to itself. What is the result of the following code fragment?

List list1 = new ArrayList();
List list2 = new ArrayList();
list1.add(list2);
list2.add(list1);
System.out.println(list1.equals(list2));

List list = new ArrayList();
list.add(list);
System.out.println(list.hashCode());

Answer: stack overflow. The Java documents says that "while it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a list."