This week's giveaway is in the Spring forum.
We're giving away four copies of REST with Spring (video course) and have Eugen Paraschiv on-line!
See this thread for details.
The moose likes Java in General and the fly likes Implement a data structure that support a sorted Map. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of REST with Spring (video course) this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Implement a data structure that support a sorted Map." Watch "Implement a data structure that support a sorted Map." New topic

Implement a data structure that support a sorted Map.

Eghe Urhos

Joined: Sep 03, 2003
Posts: 5
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;
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) ) ).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) );
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) );
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) );
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.

Ernest Friedman-Hill
author and iconoclast

Joined: Jul 08, 2003
Posts: 24195

I like to do my development "test first". This means that you write a test, then write only the code to make the test pass. Then you repeat the process, until there are no more tests to write; then you're done. Many people use JUnit to do this; it's worth the effort to learn it. But if you don't want to, you could just write your tests as tiny Java programs.
Your first goal should probably be to get SortedArrayMap skeleton class to compile. All you'll have to do is add "return null" and "return 0", etc, until the class compiles.
Then, write a test. Let's test that "size" returns 0 when the map is empty:

Compile this and run it -- it should pass!
Now, another test: size should return 1 after you've added one item.

This test will fail, so you have to start working on the code. How about using an array of Pair objects, plus a number to keep count of how many items are in the array?

Now Test1 and Test2 will pass. Of course, there are many other tests you could write that will fail. You can base many of your tests on the requirements in the problem statement. When you can't think of any more tests to write, try running Assign1.
Good luck - you can ask more questions here if you need to.

[Jess in Action][AskingGoodQuestions]
I agree. Here's the link:
subject: Implement a data structure that support a sorted Map.
It's not a secret anymore!