CIS 211
Lab Assignment 3
Winter, 2005

120 Points, Due: Monday 31 Jan
Multisets are an interesting domain for exploring basic aspects of algorithm design and analysis.
MultiSets hold arbitrary groups of Objects, including multiple instances of the same Objects.
Sameness in Java will be determined by the equals method.
Thus, MultiSets differ from Sets, as Sets hold only one instance of any element.
An element is a distinct value of instance in a MultiSet.
The cardinality of a MultiSet is equal to the number of instances in it;
the diversity of a MultiSet is equal to the number of elements in it.
For example, the following MultiSet {5, 5, 4, 3, 4, 3, 2} has cardinality 7 and diversity 4.

We define the basic methods for MultiSets by the following Java interface. 

//
//

public interface MultiSetI{

  public int cardinality();	// number of instances in the MultiSet

  public int diversity();	// number of elements in the MultiSet
  
  public boolean isEmpty();	// true if cardinality is 0, false otherwise

  public void addInstance(Object o);	// add instance of Object o to the MultiSet

  public void removeInstance(Object o);	// remove one instance of Object o

  public void removeElement(Object o); // remove all instances of Object o
 
  public boolean isMember(Object o);	// true if an instance of Object o is in the MultiSet

  public int count(Object o);	// number of instances of Object o in the MultiSet

  public Object [] elements();	// an array of the distinct elements in the MultSet (its length is diversity)

  public Object [] instances(); // an array of the instances in the MultiSet (its length is cardinality)
							
  public String toString();  
		// returns string of form: "[" followed by
		// the toString of each element followed by " : " 
		// followed by the count for that element followed by ";  "
		// ended by "]"

 }

Part I: Implementation -- 80 Points

In this lab, we use an array of ElementNode , each of which holds an object and a count of its occurrences in the MultiSet.
We also maintain a variable numElements, which is the number of elements in the MultiSet, i.e, the diversity. 
public class MultiSetB implements MultiSetI{

   // inner class

private class ElementNode
{ public Object el;
  public int count;

       //create a node for a new element

 public ElementNode(Object e)
   {el = e;
    count = 1;
   }
}

   // encapsulated data elements

private ElementNode[] theElements;
private int numElements;


    // invariants
       //  numElements is the number of distinct elements in the MultiSet
       //  theElements.length >= numElements
       //  ElementNodes occur in locations 0 to numElements-1 of the array
       //  distinct is determined by use of equals method

  // constructors


//  the following constructor creates an empty MultiSetB with
//  array space allocated to hold 4 nodes

public MultiSetB()
    { 
    }

//  The following constructor acts as a "copy constructor",
//  creating a MultiSetB with same contents as given argument.
//  One can not assume the other is a MultiSetB object.

public MultiSetB(MultiSetI other)
    { 
    }


// methods implementing the MultiSetI interface

  
}
Complete an implementation of class MultiSetB by providing methods for the constructors
and the methods from the MultiSetI interface. Implement the interface
methods based upon the algorithm design ideas discussed in class:
employing iterative decomposition and using existing methods to implement other methods, where appropriate.

Note: The method for addInstance expands theElements array when necessary,
making it twice as long (e.g. if 4 elements in length, it becomes 8 elements long).

You will hand in printouts of file MultiSetB.java.
Your comments should argue for correctness of your methods.
In your comments, indicate the Big-O complexity of each method
in terms of cardinality c and diversity d .>
For example, a method may have complexity O(cd) .
Code:60; comments: 20.

Part II: Testing -- 40 Points

You will test your implementation of MultiSets by writing a class TestMultiSet with a main method
that exercises the methods. Comment your test driver to argue that it does an adequate job testing
conditions in the methods you have implemented for the class.

You will hand in the code for the test driver in TestMultiSet.java, as well as the output of the tests.