Question: I need help with the following Java code. Implement all missing methods of SortedArrayDictionary.java . For SortedArrayDictionary.java you need reimplement the locateIndex method using a
I need help with the following Java code.
Implement all missing methods of SortedArrayDictionary.java . For SortedArrayDictionary.java you need reimplement the locateIndex method using a binary search. You are allowed to throw UnsupportedOperationException from remove methods of both iterators.
/**
*An interface for a dictionary with distinct search keys.
*/
import java.util.Iterator;
public interface DictionaryInterface
{
/**
* Adds a new entry to this dictionary. If the given search key already exists
* in the dictionary, replaces the corresponding value.
*
* @param key
* An object search key of the new entry.
* @param value
* An object associated with the search key.
* @return Either null if the new entry was added to the dictionary or the
* value that was associated with key if that value was replaced.
*/
public V add(K key, V value);
/**
* Removes a specific entry from this dictionary.
*
* @param key
* An object search key of the entry to be removed.
* @return Either the value that was associated with the search key or null if
* no such object exists.
*/
public V remove(K key);
/**
* Retrieves from this dictionary the value associated with a given search key.
*
* @param key
* An object search key of the entry to be retrieved.
* @return Either the value that is associated with the search key or null if
* no such object exists.
*/
public V getValue(K key);
/**
* Sees whether a specific entry is in this dictionary.
*
* @param key
* An object search key of the desired entry.
* @return True if key is associated with an entry in the dictionary.
*/
public boolean contains(K key);
/**
* Creates an iterator that traverses all search keys in this dictionary.
*
* @return An iterator that provides sequential access to the search keys in
* the dictionary.
*/
public Iterator
/**
* Creates an iterator that traverses all values in this dictionary.
*
* @return An iterator that provides sequential access to the values in this
* dictionary.
*/
public Iterator
/**
* Sees whether this dictionary is empty.
*
* @return True if the dictionary is empty.
*/
public boolean isEmpty();
/**
* Gets the size of this dictionary.
*
* @return The number of entries (key-value pairs) currently in the dictionary.
*/
public int getSize();
/** Removes all entries from this dictionary. */
public void clear();
} // end DictionaryInterface
/**
* A class that implements the ADT dictionary by using a resizable sorted array.
* The dictionary has distinct search keys.
*
* @author Frank M. Carrano
* @author Timothy M. Henry
* @version 4.0
*/
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class SortedArrayDictionary
{
private Entry
private int numberOfEntries;
private boolean initialized = false;
private final static int DEFAULT_CAPACITY = 25;
private static final int MAX_CAPACITY = 10000;
/*
* < Constructors analogous to ones presented in ArrayDictionary >
*/
/** Precondition: key and value are not null. */
public V add(K key, V value)
{
checkInitialization();
if ((key == null) || (value == null))
throw new IllegalArgumentException("Cannot add null to a dictionary.");
else
{
V result = null;
int keyIndex = locateIndex(key);
if ((keyIndex < numberOfEntries) && key.equals(dictionary[keyIndex].getKey()))
{
// Key found, return and replace entry's value
result = dictionary[keyIndex].getValue(); // Old value
dictionary[keyIndex].setValue(value); // Replace value
} else // Key not found; add new entry to dictionary
{
makeRoom(keyIndex); // Make room for new entry
dictionary[keyIndex] = new Entry<>(key, value); // Insert new entry in array
numberOfEntries++;
ensureCapacity(); // Ensure enough room for next add
} // end if
return result;
} // end if
} // end add
/*
* < Implementations of other methods in DictionaryInterface. > . . .
*/
// Returns the index of either the entry that contains key or
// the location that should contain key, if no such entry exists.
private int locateIndex(K key)
{
// Search until you either find an entry containing key or
// pass the point where it should be
int index = 0;
while ((index < numberOfEntries) && key.compareTo(dictionary[index].getKey()) > 0)
{
index++;
} // end while
return index;
} // end locateIndex
// Makes room for a new entry at a given index by shifting
// array entries towards the end of the array.
// Precondition: keyIndex is valid; list length is old length.
private void makeRoom(int keyIndex)
{
// . . . To be implemented
} // end makeRoom
// Removes an entry at a given index by shifting array
// entries toward the entry to be removed.
private void removeArrayEntry(int keyIndex)
{
// . . . To be implemented
} // end removeArrayEntry
private class Entry
{
private S key;
private T value;
private Entry(S searchKey, T dataValue)
{
key = searchKey;
value = dataValue;
} // end constructor
private S getKey()
{
return key;
} // end getKey
private T getValue()
{
return value;
} // end getValue
private void setValue(T dataValue)
{
value = dataValue;
} // end setValue
} // end Entry
} // end SortedArrayDictionary
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help