Solve the question

Question

Problem: Johnny realized that there are many developers out there who will be pleased if there is a data structure that can store paired-data of int and String (this is what they call key-value paired data).

Johnny is thinking of creating an abstract data type, called "ArrayMap", which provides the set of methods as shown below (same style of diagram as used in the class).

Give an implementation that will support these APIs, using two arrays.

Array Map:

void put(int key, String value);

String get(int key);

int[] getAllKeys();

String remove(int key);

boolean isEmpty();

int size();

void clear();

Example operation:

ArrayMap map = new ArrayMap(100); // It will hold up to 100 paired data.

map.put(107, "John");

map.put(102, "Sally"); // These data will be stored as paired.

map.put(211, "Dave");

map.put(195, "Tom");

String name = map.get(211); // will return "Dave".

int[] keys = map.getAllKeys(); // will return {107, 102, 211, 195}

System.out.println(map.remove(102)); // will remove [102, Sally] pair.

System.out.println(map.isEmpty()); // will return 'false;

System.out.println(map.size()); // will return 3.

map.clear(); // will make both arrays empty.

Answer 1

class ArrayMap

{

//*****************************************************************//

// Nested class KeyLog : KeyLog Record

class KeyLog

{

private int key;

private String data;

public KeyLog( int Key, String str)

{

this.key = Key;

this.data = new String(str);

}

public int GetKey() { return(key); }

public String GetData() { return(data); }

public KeyLog( KeyLog keylog)

{

this.key = keylog.GetKey();

this.data = new String(keylog.GetData());

}

public void UpdateData( String str) { this.data = new String(str); }

} //KeyLog

//********************************************************************//

private KeyLog [] A;

private int count;

private int maxSize;

//constructor

public ArrayMap( int N)

{

maxSize = N;

A = new KeyLog[N];

count = 0;

}

//Linear searches for the key; returns index position if found, -1 otherwise

public int LinearSearch( int key)

{

int iReturn = -1;

if (count >0)

{

for (int iLoop=0; iLoop<count; iLoop++)

{

if (A[iLoop].GetKey()==key)

{

iReturn = iLoop;

break;

}

}

}

return(iReturn);

}

//adds keylog record to end of array if not already there; otherwise updates the data;

// returns 0 on success, -1 if array is full

public int Put( int key, String str)

{

int iReturn=0;

if (count < maxSize) // if array is not full

{

int iIndexPos = this.LinearSearch(key); //looks for keylog record with specified key

//keylog record does not exist: adds it at the end

if (iIndexPos<0)

{

A[count++] = new KeyLog(key,str);

}

else //keylog record already exists: updates the data

{

A[iIndexPos].UpdateData(str); //note: count does not get updated

// because a new record was not actually added

}

}

else

{

iReturn=-1;

}

return(iReturn);

}

//returns the string associated with the key, or null if does not exist

public String Get(int key)

{

String strReturn=null;

int iIndexPos = this.LinearSearch(key);

if (iIndexPos>-1) //keylog record exists

{

strReturn = A[iIndexPos].GetData();

}

return(strReturn);

}

//returns the array of keys in the array

public int[] GetAllKeys()

{

int keys[] = new int[count];

for (int iLoop=0; iLoop<count; iLoop++)

{

keys[iLoop]=A[iLoop].GetKey();

}

return(keys);

}

//removes the keylog record with the specified key;

// returns the data of the delete key, or null if does not exist

// or list is empty

public String Remove(int key)

{

String strReturn=null;

if (count>0) //if array is not empty

{

int iIndexPos = this.LinearSearch(key); //locates the keylog record with specified key

if (iIndexPos >=0) //keylog record exists

{

strReturn = A[iIndexPos].GetData(); //records the data to be returned

//moves keylog records one position to the left, over-writing the

//keylog record to be deleted

for (int iLoop=iIndexPos; iLoop<count-1; iLoop++)

{

A[iLoop]=A[iLoop+1];

}

A[count-1]=null; //invalidates the last keylog record

count--; // and updates the count

}

}

return(strReturn);

}

public boolean IsEmpty() { return(count==0); }

public int GetCount() { return(count); }

public int Size() { return(count); }

public int GetMaxSize() { return(maxSize); }

//returns the keylog record at the specified index, or null if index is invalid

public KeyLog IndexerGetIndexAt( int iIndexPos)

{

KeyLog keylogReturn=null;

if ((iIndexPos>=0) && (iIndexPos<count))

{

keylogReturn = A[iIndexPos];

}

return(keylogReturn);

}

// clears the data and reallocates

public void Clear()

{

for (int iLoop=0; iLoop<count; iLoop++)

{

A[iLoop]=null;

}

A = new KeyLog[maxSize];

count=0;

}

public static void main (String args[])

{

ArrayMap map = new ArrayMap(100);

map.Put(107,"John");

map.Put(102,"Sally");

map.Put(211,"Dave");

map.Put(195,"Tom");

map.Put(100,"Replace me with X");

int n = map.GetCount(); System.out.println(" size = " + map.Size());

for (int iLoop=0; iLoop<n; iLoop++)

{

KeyLog curKeylogRec = map.IndexerGetIndexAt(iLoop);

System.out.println(" key = " + curKeylogRec.GetKey() + " : data = " + curKeylogRec.GetData() );

}

System.out.println(map.Get(211));

map.Put(100,"X");

System.out.println(map.Get(100));

int [] keys = map.GetAllKeys();

for (int iLoop=0; iLoop<keys.length; iLoop++)

{

System.out.println(keys[iLoop]);

}

map.Remove(102);

map.Remove(100);

n = map.GetCount(); System.out.println(" size = " + map.Size());

for (int iLoop=0; iLoop<n; iLoop++)

{

KeyLog curKeylogRec = map.IndexerGetIndexAt(iLoop);

System.out.println(" key = " + curKeylogRec.GetKey() + " : data = " + curKeylogRec.GetData() );

}

map.Clear();

System.out.println(" count = " + map.GetCount() + " : max size = " + map.GetMaxSize() );

}

}