Program #6: Collections classes and recursion

Program outline

The program consists of two parts. First, you will provide two implementations of an IntMap class. An IntMap stores a collection of key-value pairs, in which duplicate keys are not allowed. In an IntMap a search for a key returns the corresponding value. One implementation will use a sorted array. The second implementation will use a sorted singly-linked list. You will need to write code to test your implementations. The second part will ask you to write a recursive routine to compute Fibonacci numbers, but which uses the IntMap to avoid redundant calls.

The IntMap

The IntMap and its implementations should all be in package cop3337. Here is the interface that describes the IntMap and also a Pair (that represents key-value pairs):
package cop3337;

public interface Pair
{
    public int getKey( );          // Returns key component
    public int getValue( );        // Returns value component
    public String toString( );
}

package cop3337;

public interface IntMap
{
    public void put( int k, int v );  // If k already in map, override value
    public boolean containsKey( int k );
    public int get( int k );   // Returns value corresponding to key k
    public boolean remove( int k ); // Remove k/v pair; returns true if remove succeeds
    
    public int [ ] allKeys( );     // Returns all keys
    public int [ ] allValues( );   // Returns all values
    public Pair [ ] allPairs( );   // Returns all key-value pairs
    
    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 IntMap should provide a toString method. The implementations will be BoundedArrayIntMap and ListIntMap. In a BoundedArrayIntMap, the constructor will specify the largest permissible size of the map. Here is a sample test program, which is not part of the cop3337 package:
import cop3337.IntMap;
import cop3337.BoundedArrayIntMap;
import cop3337.Pair;

public class Assign6
{    
    public static void main( String [ ] args )
    {
        int N = 6;
        
        IntMap squares = new BoundedArrayIntMap( N );
        
        for( int i = 0; i < N; i++ )
            squares.put( i, i * i );
        
        System.out.println( "Size: " + ms.size( ) );
        System.out.println( "Items: " + ms );     

        System.out.println( "Pairs: " );
        Pair [ ] items = squares.allPairs( );
        for( Pair p : items )
            System.out.println( p );
    }
}
The output of the test program should be the following (please note that in the format of toString, keys MUST BE sorted):
Size: 6
Items: [ 0=0 1=1 2=4 3=9 4=16 5=25 ]
Pairs:
0=0
1=1
2=4
3=9
4=16
5=25

BoundedArrayIntMap Implementation

This implementation maintains an array of Pairs. Because this array must be created with a fixed size, the constructor must be invoked with a parameter representing the maximum size of the BoundedArrayIntMap. Also, note the calls to get that fail must throw an IllegalArgumentException. Here is a sketch of this class (you may wish to add additional private methods):
package cop3337;

// MyPair class, constructor, and data all package visible only
// BoundedArrayIntMap constructor requires line of code such as
//    items = new MyPair[ max ];
// Used also by ListIntMap in allPairs
class MyPair implements Pair
{
    MyPair( int k, int v )
      { key = k; value = v; }

    // getKey, getValue, toString are all omitted

    int key;
    int value;
}

public class BoundedArrayIntMap implements IntMap
{
    public BoundedArrayIntMap( int max )
      { /* Implementation not shown */ }
    
    public void put( int k, int v )
      { /* Implementation not shown */ }
    
    public boolean containsKey( int key )
      { /* Implementation not shown */ }
    
    public int get( int k )   // throws exception if k not found
      { /* Implementation not shown */ }

    public boolean remove( int k )
      { /* Implementation not shown */ }
    
    public int [ ] allKeys( )
      { /* Implementation not shown */ }

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

    public Pair [ ] allPairs( )
      { /* Implementation not shown */ }

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

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

ListIntMap Implementation

This implementation maintains a sorted singly linked list, in which each node maintains a key and corresponding value. There are no size restrictions. Here is a sketch of this class (you may wish to add additional private methods):
package cop3337;

class Node
{
    public Node( int k, int v, Node n )
      { /* Implementation not shown */ }
    
    int key;
    int value;
    Node next;
}

public class ListIntMap implements IntMap
{
    public ListIntMap( )
      { /* Implementation not shown */ }
    
    public void put( int k, int v )
      { /* Implementation not shown */ }
    
    public boolean containsKey( int key )
      { /* Implementation not shown */ }
    
    public int get( int k )   // throws exception if k not found
      { /* Implementation not shown */ }

    public boolean remove( int k )
      { /* Implementation not shown */ }
    
    public int [ ] allKeys( )
      { /* Implementation not shown */ }

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

    public Pair [ ] allPairs( )
      { /* 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

A normal recursive fibonacci number routine looks like the following:
 
    public static int fib( int n )
    {
         if( n <= 1 )
             return 1;
         else
             return fib( n - 1 ) + fib( n - 2 );
    }
First, run this code to compute the first 40 Fibonacci numbers, and observe the running time. Of course, you could write this without recursion, but it is not always possible to improve recursive programs by avoid recursion altogether. Instead, you will maintain an IntMap that will record any Fibonacci number results as they are computed. Then your recursive routine can check the IntMap before making subsequent recursive calls. You should fill in the sketch shown below, and then write a test program that computes the first 44 Fibonacci numbers.
 
    // Public driver; create an appropriate IntMap, pass it to the recursive routine
    public static int fib( int n )
    {

    }

    // Private recursive routine; check priorResult on entry; update on exit
    private static int fib( int n, IntMap priorResults )
    {
         // You must implement
    }

Commenting

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

Testing

At a later date, I may provide a test program that you can work with to test your IntMap implementations. However, it is your responsibility to completely test and debug your multiset implementations.