I need help with the following Java code. Implement all missing methods of Sorte
ID: 3907383 • Letter: I
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 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<K, V>
{
/**
* 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<K> getKeyIterator();
/**
* 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<V> getValueIterator();
/**
* 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<K extends Comparable<? super K>, V> implements DictionaryInterface<K, V>
{
private Entry<K, V>[] dictionary; // Array of entries sorted by search key
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<S, T>
{
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
Explanation / Answer
Given below is the code for the question.
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
Please do rate the answer if it was helpful. Thank you
/**
* 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<K extends Comparable<? super K>, V> implements DictionaryInterface<K, V>
{
private Entry<K, V>[] dictionary; // Array of entries sorted by search key
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
private void ensureCapacity() {
if(numberOfEntries < dictionary.length)
{
int cap = 2 * dictionary.length;
Entry[] temp = new Entry[cap];
for(int i = 0; i < numberOfEntries; i++)
temp[i] = dictionary[i];
dictionary = temp;
}
}
// 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)
{
if(isEmpty())
return 0;
int start = 0, end = numberOfEntries - 1;
int mid = (start + end) / 2;
while(start <= end){
mid = (start + end) / 2;
if(dictionary[mid].getKey().compareTo(key)==0)
return mid;
else if(key.compareTo(dictionary[mid].getKey()) < 0)
end = mid- 1;
else
start = mid + 1;
}
return mid;
} // 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)
{
if(keyIndex >= 0 && keyIndex < numberOfEntries)
{
for(int i = numberOfEntries-1; i >= keyIndex; i--)
dictionary[i+1] = dictionary[i];
}
} // end makeRoom
// Removes an entry at a given index by shifting array
// entries toward the entry to be removed.
private void removeArrayEntry(int keyIndex)
{
for(int i = keyIndex + 1; i < numberOfEntries; i++)
dictionary[i-1] = dictionary[i];
numberOfEntries--;
} // end removeArrayEntry
private void checkInitialization() {
if(!initialized)
{
dictionary = new Entry[DEFAULT_CAPACITY];
initialized = true;
numberOfEntries = 0;
}
}
private class Entry<S, T>
{
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
public class KeyIterator implements Iterator<K>
{
private int currentIndex;
private KeyIterator() { currentIndex = 0; } // end default constructor
public boolean hasNext() { return currentIndex < numberOfEntries; } // end hasNext
public K next()
{
K result;
if (hasNext())
{
result = dictionary[currentIndex].getKey();
currentIndex++;
} else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove
} // end KeyIterator
public class ValueIterator implements Iterator<V>
{
private int currentIndex;
private ValueIterator() { currentIndex = 0; } // end default constructor
public boolean hasNext() { return currentIndex < numberOfEntries; } // end hasNext
public V next()
{
V result;
if (hasNext())
{
result = dictionary[currentIndex].getValue();
currentIndex++;
} else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove() { throw new UnsupportedOperationException(); } // end remove
} // end KeyIterator
/*
* < Implementations of other methods in DictionaryInterface. > . . .
*/
@Override
public V remove(K key) {
int keyIndex = locateIndex(key);
V result = null;
if ((keyIndex < numberOfEntries) && key.equals(dictionary[keyIndex].getKey())){
result = dictionary[keyIndex].getValue();
removeArrayEntry(keyIndex);
}
return result;
}
@Override
public V getValue(K key) {
int keyIndex = locateIndex(key);
if ((keyIndex < numberOfEntries) && key.equals(dictionary[keyIndex].getKey()))
return dictionary[keyIndex].getValue();
else
return null;
}
@Override
public boolean contains(K key) {
int keyIndex = locateIndex(key);
if ((keyIndex < numberOfEntries) && key.equals(dictionary[keyIndex].getKey()))
return true;
else
return false;
}
@Override
public Iterator getKeyIterator() {
return new KeyIterator();
}
@Override
public Iterator getValueIterator() {
return new ValueIterator();
}
@Override
public boolean isEmpty() {
return numberOfEntries == 0;
}
@Override
public int getSize() {
return numberOfEntries;
}
@Override
public void clear() {
numberOfEntries = 0;
}
} // end SortedArrayDictionary