interface Pair
{
    /* See Apr03.java */
}

interface IntMap
{
    /* See Apr03.java */
}

// 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
{
    /* See Apr03.java */
}


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

class ListIntMap implements IntMap
{
    public ListIntMap( )
      { first = null; theSize = 0; }
    
    // This implementation does not maintain key-sorted order
    public void put( int k, int v )
    {
        for( Node p = first; p != null; p = p.next )
            if( p.key == k )
            {
                p.value = v;
                return;
            }
        
        // k not already in map
        first = new Node( k, v, first );
        theSize++;
    }
    
    public boolean containsKey( int key )
    {
        /* Implementation not shown */
    }
    
    public int get( int k )   // throws exception if k not found
    {
        for( Node p = first; p != null; p = p.next )
            if( p.key == k )
                return p.value;
        
        throw new IllegalArgumentException( );
    }

    public boolean remove( int k )
    {
        /* Implementation not shown */
    }
    
    public int [ ] allKeys( )
    {
        int [ ] result = new int[ size( ) ];
        int idx = 0;
        
        for( Node p = first; p != null; p = p.next )
            result[ idx++ ] = p.key;
        
        return result;
    }

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

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

    public int size( )
      { return theSize; }
    
    public boolean isEmpty( )
      { return size( ) == 0; }

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


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

        System.out.println( "Pairs: " );
        Pair [ ] items = squares.allPairs( );
        for( Pair p : items )
            System.out.println( p );
    }
}