Please I need someone to assits me with how to go about the attached assign. I'm really having a hard time figuring out what to do and how to do it. I would really appreciate any assistance from anybody. Below are the details of what this program is supported to accomplish. A
test program - Assign1 is also provide to test the sortedArrayMap class.
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( ) );
}
}
}
A program is provide to test the the implementation of a data structure that support a sortd Map. The sorted Map implements the Map interface.
The Map interface is a package named Edos.
package Edos;
public interface Map
{
boolean isEmpty( );
void makeEmpty( );
int size( );
Object put( Object key, Object value );
Object get( Object key );
void remove( Object key );
java.util.Iterator getIterator( ); //non standard
public interface Entry
{
Object getKey( );
Object getValue( );
void setValue( Object value );
}
}
In interface Map, observe the following:
isEmpty: returns true if there are no elements in the map.
makeEmpty: clears the map, by setting the number of elements to zero.
size: returns the number of elements in the map.
put: adds a key and the associated value into the map, returning the value previously associated with the key, or null if the key is new.
get: returns the value associated with the key, or null if the key is not in the map.
remove: removes the key (and associated value) from the map if it was present, and does nothing otherwise.
getIterator: returns an object that implements the standard java.util.Iterator interface. getIterator is not a method that you would find in the standard java.util.Map interface.
Entry: is a public nested interface, so its type is Map.Entry. This object stores a key/value pair, allowing access to either the key or value, and allowing changes to the value. The Iterator that is returned by getIterator views Map.Entry objects.
Here is the rough outline of the implementation:
package Edos;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class SortedArrayMap implements Map
{
public SortedArrayMap( )
{ /* Implementation not shown */ }
public SortedArrayMap( Comparator c )
{ /* Implementation not shown */ }
public boolean isEmpty( )
{ /* Implementation not shown */ }
public void makeEmpty( )
{ /* Implementation not shown */ }
public int size( )
{ /* Implementation not shown */ }
public Object put( Object key, Object value )
{ /* Implementation not shown */ }
public Object get( Object key )
{ /* Implementation not shown */ }
public void remove( Object key )
{ /* Implementation not shown */ }
public java.util.Iterator getIterator( )
{ return new LocalIterator( ); }
private class LocalIterator implements java.util.Iterator
{
/* next and hasNext not shown */
public void remove( )
{
if( !okToRemove )
throw new
IllegalStateException( );
okToRemove = false; // two removes in a row not allowed
SortedArrayMap.this.remove( entries[ --current ].getKey( ) );
}
private int current = 0;
private boolean okToRemove = false; // set to true in next
}
private static class Pair implements Map.Entry
{ /* Implementation not shown */ }
private Pair [] entries;
private int theSize;
private Comparator cmp;
}
A SortedArrayMap object is created by supplying a java.util.Comparator function object that determines the sorted order; if none is given, it is assumed that the keys all implement the java.lang.Comparable interface and can be compared by calling compareTo. The cmp private data member should be initialized by the constructor(s). For the zero parameter constructor, initialize cmp to an instance of a default Comparator, as discussed in class.
In implementing the SortedArrayMap you must use a sorted array of Pairs as the private data (shown as entries), along with a theSize field.
You should not need to throw any runtime exceptions. The array entries initially starts with length 5, and is doubled in the put routine when capacity is reached. You may not replace this with any of the java.util.List implementations. Also, note that duplicate keys are not allowed, and put overrides the existing value for a key with the new value if an attempt is made to put an already seen key. A key is already seen if the comparator says so (specifically, DO NOT use equals to make the determination.
Your implementation will almost certainly want to add some private methods to perform some of the repetitive tedious work.
The Map interface defines a nested interface Entry, and the implementation class defines a private class called Pair that implements Map.Entry. This implementation should be relatively trivial: it stores a key and value (both as Object), implements the three Map.Entry public methods in one line each, and provides a public two parameter constructor.
The implementation of SortedArrayMap requires that implementing the LocalIterator class, which itself implements the Iterator interface. This one is fairly tricky to code. You are not required to detect ConcurrentModificationExceptions (i.e. changes to the Map made by others outside of the iterator). But you should throw a NoSuchElementException if the call to next is out-of-bounds. I have provided an implementation of the trickiest part of LocalIterator; you have to fill in the rest. The implementation shows that it is ok to call remove only if the last call to next has not already had a call to remove made.
Provide Javadoc comments for both the Map interface and the SortedArrayMap class.
