Program #6: Collections classes and recursion

Program outline

The program consists of two parts. First, you will provide two implementations of an IntMultiSet class. An IntMultiSet stores a collection of integers, in which duplicates are allowed. One implementation will use a "bucket" array. The second implementation will use a singly-linked list. You will need to write code to test your implementations. The second part will ask you to write a routine that given as input an array of integers, returns a IntMultiSet containing all possible sums consisting of two or more elements in the array.

The IntMultiSet

The IntMultiSet and its implementations should all be in package cop3337 Here is the interface that describes the IntMultiSet: 
package cop3337;

public interface IntMultiSet
{
    public void add( int x );
    public boolean contains( int x );
    public int howMany( int x );   // Returns number of occurrences of x
    public boolean removeOne( int x ); // Returns true if remove succeeds
    public int removeAll( int x );  // Returns number of items removed
    public int mode( );   // The most common value (any of the most if there is a tie)
    
    public int [ ] toArray ( );
    
    public int size( );   // Total number of items (each duplicate is a separate item)
    public boolean isEmpty( );
}
Note that although it is not explicitly listed, implementations of IntMultiSet should provide a toString method. The Implementations will be BoundedIntMultiSet and ListIntMultiSet. In a BoundedIntMultiSet, the constructor will specify the largest permissible value that can be added. Here is a sample test program, which is not part of the cop3337 package: 
import cop3337.IntMultiSet;
import cop3337.BoundedIntMultiSet;

public class Assign6
{    
    public static void main( String [ ] args )
    {
        int N = 6;
        
        IntMultiSet ms = new BoundedIntMultiSet( N*N * 2 );
        
        for( int i = 0; i < N; i++ )
            for( int j = i; j < N; j++ )
                ms.add( i*i + j*j );
        
        System.out.println( "Size: " + ms.size( ) );
        System.out.println( "After all adds: " + ms );


        int [ ] sub = ms.toArray( );
        System.out.println( "After dumping into an array: ");
        for( int k : sub )
            System.out.print( k + " " );
        System.out.println( );
        
        for( int i = 0; i < N*N * 2; i++ )
            ms.removeOne( i );
        
        System.out.println( "After removing one of everything: " );
        System.out.println( "Size: " + ms.size( ) );
        System.out.println( "Items: " + ms );     
    }
}
The output of the test program should be the following (please note the format of toString, in which the values are sorted and multiple occurrences are specified in parentheses): 
Size: 21
After all adds: [ 0 1 2 4 5 8 9 10 13 16 17 18 20 25(2) 26 29 32 34 41 50 ]
After dumping into an array: 
0 1 2 4 5 8 9 10 13 16 17 18 20 25 25 26 29 32 34 41 50 
After removing one of everything: 
Size: 1
Items: [ 25 ]

BoundedIntMultiSet Implementation

This implementation maintains an array count, in which count[x] represents the number of occurrences of x in the multiset, (zero if x is not found at all). Because this array must be created with a fixed size, the constructor must be invoked with a parameter representing the largest value allowed in the multiset. (The length of the count array will be this largest value plus 1.) If any method attempts to add, remove, or search for a value that is larger than the specified maximum, or smaller than zero, you should make sure that an IllegalArgumentException is thrown rather than simply allowing the misleading ArrayIndexOutOfBoundsException to be thrown. Here is a sketch of this class (you may wish to add additional private methods): 
package cop3337;

public class BoundedIntMultiSet implements IntMultiSet
{
    public BoundedIntMultiSet( int max )
       { /* Implementation not shown */ }
    
    public void add( int x )
       { /* Implementation not shown */ }
    
    public boolean contains( int x )
       { /* Implementation not shown */ }
    
    public int howMany( int x )
       { /* Implementation not shown */ }

    public boolean removeOne( int x )
       { /* Implementation not shown */ }
    
    public int removeAll( int x )
       { /* Implementation not shown */ }

    public int mode( )
       { /* Implementation not shown */ }
    
    public int [ ] toArray( )
       { /* Implementation not shown */ }

    public int size( )
       { /* Implementation not shown */ }
    
    public boolean isEmpty( )
       { /* Implementation not shown */ }

    public String toString( )
       { /* Implementation not shown */ }
    
    private int [ ] count;
    private int theSize = 0;
}

ListIntMultiSet Implementation

This implementation maintains a sorted singly linked list, in which each node maintains a value and the number of occurrences of the value in the multiset, (the number of occurrences is always at least one; if a remove causes the number of occurrence to drop to zero then the node must be removed). There are no maximum or minimum value restrictions. Here is a sketch of this class (you may wish to add additional private methods): 
package cop3337;

class Node
{
    public Node( int d, int c, Node n )
       { /* Implementation not shown */ }
    
    int data;
    int count;
    Node next;
}

public class ListIntMultiSet implements IntMultiSet
{
    public ListIntMultiSet( )
       { /* Implementation not shown */ }
    
    public void add( int x )
       { /* Implementation not shown */ }
    
    public boolean contains( int x )
       { /* Implementation not shown */ }
    
    public int howMany( int x )
       { /* Implementation not shown */ }

    public boolean removeOne( int x )
       { /* Implementation not shown */ }
    
    public int removeAll( int x )
       { /* Implementation not shown */ }

    public int mode( )
       { /* Implementation not shown */ }
    
    public int [ ] toArray( )
       { /* Implementation not shown */ }

    public int size( )
       { /* Implementation not shown */ }
    
    public boolean isEmpty( )
       { /* Implementation not shown */ }

    public String toString( )
       { /* Implementation not shown */ }
    
    private Node first;  // or header, if more convenient for you
    private int theSize = 0;
}

Recursive Routine

The public routine generateSums takes as parameter an array of integers and returns an IntMultiSet consisting of all possible sums using two or more elements of the array. This routine can be placed in class Assign6 and is not part of the cop3337 package. The easiest way to implement this routine is to write a private recursive routine that is invoked from the public routine. The private recursive routine can find all possible sums using zero or more elements of the array, and the driver can remove the sums that were formed from zero and one array element. Here is a sketch of those routines: 
 
    // Returns an IntMultiSet containing all possible sums using two or more elements in arr
    public static IntMultiSet generateSums( int [ ] arr )
    {
        // Hint: invoke the recursive routine and then remove sums that consist
        //       of zero or one item
    }

    // Returns an IntMultiSet containing all possible sums
    // using zero or more elements in arr[ low..high]
    private static void generateSums( int [ ] arr, int low, int high, BoundedIntMultiSet result )
    {
        // Hint: this is less than 10 lines of code   
    }
If the public version of generateSums is called with the following array: { 1, 2, 3, 5 }, then the result is [ 3 4 5 6(2) 7 8(2) 9 10 11 ].

Commenting

Please provide appropriate comments and Javadoc your multiset interface and implementations.

Testing

At a later date, I may provide a test program that you can work with. However, you must make sure that your multiset implementations work completely before you try to use it in the recursive generateSums or you could find yourself debugging recursion when the problem is the multiset. It is your responsibility to completely test and debug your multiset implementations. If everything is correctly written, you should definitely be able to write code to answer the following question: