import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;

import cop3530.Map;
import cop3530.Map.Entry;
import cop3530.SortedArrayMap;

public class Assign1
{
    private static void printFactors( int [] m )
    {
        System.out.print( m[ 0 ] );
        for( int i = 1; i < m.length; i++ )
            System.out.print(  " " + m[ i ] );
        System.out.println( );
    }

    // Return int[] containing the prime factorization of n.
    // Precondition: n > 1.
    private static int [] getFactors( int n )
    {
        List result = new ArrayList( );

        for( int i = 2; i * i <= n; )
        {
            if( n % i == 0 )
            {
                result.add( new Integer( i ) );
                n /= i;
            }
            else
                i++;
        }

        if( n > 1 )
            result.add( new Integer( n ) );

        int [] returnVal = new int[ result.size( ) ];
        Iterator itr = result.iterator( );
        
        for( int i = 0; itr.hasNext( ); i++ )
            returnVal[ i ] =  ((Integer) itr.next( ) ).intValue( );
        return returnVal;
    }

    // Print factorizations of number in Map m that have
    // at least threshold factors.
    private static void printLargeFactorizations( Map m, int threshold )
    {
    
        Iterator itr = m.getIterator( );
        
        while( itr.hasNext( ) )
        {
            Map.Entry entry = (Map.Entry) itr.next( );
            int [] factors = (int[]) entry.getValue( );
            if( factors.length >= threshold )
            {
                System.out.print( entry.getKey( ) + ": " );
                printFactors( factors );
            }
        }    
    }

    // Remove all primes from the map.
    private static void removePrimes( Map m )
    {
        Iterator itr = m.getIterator( );
        
        while( itr.hasNext( ) )
        {
            Map.Entry entry = (Map.Entry) itr.next( );
            int [] factors = (int[]) entry.getValue( );
            
            if( factors.length == 1 )
                itr.remove( );
        }    
    }

    public static void main( String [ ] args )
    {
        Map m = new SortedArrayMap( );
        final int n = 100;

        System.out.println( "*********TEST #1*********" );
        for( int i = 2; i <= n; i++ )
        {
            int [ ] factorization = getFactors( i );
            if( factorization.length >= 1 )
                m.put( new Integer( i ), factorization );
        }

        removePrimes( m );

        System.out.println( "Number of nonprimes less or equal to than " + n
             + " is " + m.size( ) );

        printLargeFactorizations( m, 4 );
    
    
        class MyComparator implements java.util.Comparator
        {
            public int compare( Object lhs, Object rhs )
            {
                int left = Integer.parseInt( (String) lhs);
                int right = Integer.parseInt( (String) rhs);
                
                return left - right;
            }
        }
        
        System.out.println( "*********TEST #2*********" );
        
        m = new SortedArrayMap( new MyComparator( ) );    
        m.put( "12", "144" );
        m.put( "6", "36" );
        m.put( "100", "10000" );
        
        Iterator itr = m.getIterator( );
        while( itr.hasNext( ) )
        {
            Map.Entry entry = (Map.Entry) itr.next( );
            System.out.println( entry.getKey( ) + " " + entry.getValue( ) );
        }
    }
}