Question: import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; /** A class that implements the ADT dictionary by using a resizable array. The dictionary is unsorted and has
import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
A class that implements the ADT dictionary by using a resizable array.
The dictionary is unsorted and has distinct search keys.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public class ArrayDictionary
{
private Entry
private int numberOfEntries;
private boolean initialized = false;
private final static int DEFAULT_CAPACITY = 25; // 6 is for testing
private static final int MAX_CAPACITY = 10000;
public ArrayDictionary()
{
this(DEFAULT_CAPACITY); // Call next constructor
} // end default constructor
public ArrayDictionary(int initialCapacity)
{
checkCapacity(initialCapacity);
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
Entry
dictionary = tempDictionary;
numberOfEntries = 0;
initialized = true;
} // end constructor
/** 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 found, return and replace entry's value
result = dictionary[keyIndex].getValue(); // Get old value
dictionary[keyIndex].setValue(value); // Replace value
}
else // Key not found; add new entry to dictionary
{
// Add at end of array
dictionary[numberOfEntries] = new Entry<>(key, value);
numberOfEntries++;
ensureCapacity(); // Ensure enough room for next add
} // end if
return result;
} // end if
} // end add
public V remove(K key)
{
checkInitialization();
V result = null;
int keyIndex = locateIndex(key);
if (keyIndex < numberOfEntries)
{
// Key found; remove entry and return its value
result = dictionary[keyIndex].getValue();
dictionary[keyIndex] = dictionary[numberOfEntries - 1]; // Replace removed entry with last entry
dictionary[numberOfEntries - 1] = null;
numberOfEntries--;
} // end if
// Else result is null
return result;
} // end remove
public V getValue(K key)
{
checkInitialization();
V result = null;
int keyIndex = locateIndex(key);
if (keyIndex < numberOfEntries)
{
result = dictionary[keyIndex].getValue(); // Key found; return value
} // end if
return result;
} // end getValue
public boolean contains(K key)
{
return getValue(key) != null;
} // end contains
public boolean isEmpty()
{
return numberOfEntries == 0;
} // end isEmpty
public int getSize()
{
return numberOfEntries;
} // end getSize
public final void clear()
{
checkInitialization();
// Clear entries but retain array; no need to create a new array
for (int index = 0; index < numberOfEntries; index++)
dictionary[index] = null;
numberOfEntries = 0;
} // end clear
public Iterator
{
return new KeyIterator();
} // end getKeyIterator
public Iterator
{
return new ValueIterator();
} // end getValueIterator
// Returns the array index of the entry that contains key, or
// returns numberOfEntries if no such entry exists.
private int locateIndex(K key)
{
// Sequential search
int index = 0;
while ( (index < numberOfEntries) && !key.equals(dictionary[index].getKey()) )
index++;
return index;
} // end locateIndex
// Doubles the size of the array dictionary if it is full.
private void ensureCapacity()
{
if (numberOfEntries >= dictionary.length)
{
int newCapacity = 2 * dictionary.length;
checkCapacity(newCapacity);
dictionary = Arrays.copyOf(dictionary, newCapacity);
} // end if
} // end ensureCapacity
// Throws an exception if this object is not initialized.
private void checkInitialization()
{
if (!initialized)
throw new SecurityException ("ArrayDictionary object is not initialized properly.");
} // end checkInitialization
// Ensures that the client requests a capacity
// that is not too small or too large.
private void checkCapacity(int capacity)
{
if (capacity < DEFAULT_CAPACITY)
capacity = DEFAULT_CAPACITY;
else if (capacity > MAX_CAPACITY)
throw new IllegalStateException("Attempt to create a dictionary " +
"whose capacity is larger than " +
MAX_CAPACITY);
} // end checkCapacity
// Since iterators implement Iterator, methods must be public.
// Same as SortedArrayDictionary.
private class KeyIterator implements Iterator
{
private int currentIndex;
private KeyIterator()
{
currentIndex = 0;
} // end default constructor
public boolean hasNext()
{
return currentIndex < numberOfEntries;
} // end hasNext
public K next()
{
K result = null;
if (hasNext())
{
Entry
result = currentEntry.getKey();
currentIndex++;
}
else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove()
{
throw new UnsupportedOperationException();
} // end remove
} // end KeyIterator
private class ValueIterator implements Iterator
{
private int currentIndex;
private ValueIterator()
{
currentIndex = 0;
} // end default constructor
public boolean hasNext()
{
return currentIndex < numberOfEntries;
} // end hasNext
public V next()
{
V result = null;
if (hasNext())
{
Entry
result = currentEntry.getValue();
currentIndex++;
}
else
{
throw new NoSuchElementException();
} // end if
return result;
} // end next
public void remove()
{
throw new UnsupportedOperationException();
} // end remove
} // end getValueIterator
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 ArrayDictionary
----------------------------------------
import java.util.Iterator; /** An interface for a dictionary with distinct search keys. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public interface DictionaryInterface
--------------------------------------------
// Change DEFAULT_CAPACITY in ArrayDictionary to 6
import java.util.Iterator;
/**
A driver that demonstrates the class ArrayDictionary.
@author Frank M. Carrano
@version 4.0
*/
public class Driver
{
public static void main(String[] args)
{
testDictionary();
System.out.println(" Done.");
} // end main
public static void testDictionary()
{
String dirk = "Dirk";
String abel = "Abel";
String miguel = "Miguel";
String tabbie = "Tabatha";
String tom = "Tom";
String sam = "Sam";
String reiss = "Reiss";
String bette = "Bette";
String carole = "Carole";
String derek = "Derek";
String nancy = "Nancy";
String bogus = "Bo";
// Create a dictionary of initial size 11
DictionaryInterface
System.out.println("Create a dictionary: ");
System.out.println("Initial dictionary should be empty; isEmpty() returns " +
nameList.isEmpty());
// Test add
System.out.println(" Testing add(): ");
nameList.add(dirk, "555-1234");
nameList.add(abel, "555-5678");
nameList.add(miguel, "555-9012");
nameList.add(tabbie, "555-3456");
nameList.add(tom, "555-5555");
nameList.add(sam, "555-7890");
nameList.add(reiss, "555-2345");
nameList.add(bette, "555-7891");
nameList.add(carole, "555-7892");
nameList.add(derek, "555-7893");
nameList.add(nancy, "555-7894");
System.out.println(nameList.getSize() + " (should be 11) items in dictionary, as follows: ");
display(nameList);
// Test getValue
System.out.println(" Testing getValue(): ");
System.out.println(" Abel: " + nameList.getValue(abel) + " should be 555-5678");
System.out.println(" Sam: " + nameList.getValue(sam) + " should be 555-7890");
System.out.println(" Tom: " + nameList.getValue(tom) + " should be 555-5555");
System.out.println(" Reiss: " + nameList.getValue(reiss) + " should be 555-2345");
System.out.println(" Miguel: " + nameList.getValue(miguel) + " should be 555-9012");
// Test contains
System.out.println(" Testing contains(): ");
if ( nameList.contains(sam) )
System.out.println(" Sam is in dictionary - OK");
else
System.out.println("Error in contains()");
if ( nameList.contains(abel) )
System.out.println(" Abel is in dictionary - OK");
else
System.out.println("Error in contains()");
if ( nameList.contains(miguel) )
System.out.println(" Miguel is in dictionary - OK");
else
System.out.println("Error in contains()");
if ( nameList.contains(tom) )
System.out.println(" Tom is in dictionary - OK");
else
System.out.println("Error in contains()");
if (!nameList.contains(bogus))
System.out.println(" Bo is not in dictionary - OK");
else
System.out.println("Error in contains()");
// Remove first item
System.out.println(" Removing first item Dirk - Dirk's number is " +
nameList.remove(dirk) + " should be 555-1234");
// Test replacing value
System.out.println("Replacing phone number of Reiss and Miguel: ");
String oldNumber = nameList.add(reiss, "555-5432");
System.out.println("Reiss's old number " + oldNumber + " is replaced by 555-5432");
oldNumber = nameList.add(miguel, "555-2109");
System.out.println("Miguel's old number " + oldNumber + " is replaced by 555-2109");
System.out.println(" " + nameList.getSize() +
" (should be 10) items in dictionary, as follows: ");
display(nameList);
// Remove interior and last items
System.out.println(" Removing interior item Reiss: ");
nameList.remove(reiss);
System.out.println(" " + nameList.getSize() +
" (should be 9) items in dictionary, as follows: ");
display(nameList);
System.out.println(" Removing last item Carole: ");
nameList.remove(carole);
System.out.println(" " + nameList.getSize() +
" (should be 8) items in dictionary, as follows: ");
display(nameList);
// Remove Bo (not in dictionary)
System.out.println(" Removing Bo (not in dictionary): ");
String result = nameList.remove(bogus);
if (result == null)
System.out.println("Bo was not found in the dictionary.");
else
System.out.println("Error in remove().");
System.out.println(" " + nameList.getSize() +
" (should be 8) items in dictionary, as follows: ");
display(nameList);
// Test clear
System.out.println(" Testing clear(): ");
nameList.clear();
System.out.println("Dictionary should be empty; isEmpty() returns " +
nameList.isEmpty());
} // testDictionary
public static void display(DictionaryInterface
{
Iterator
Iterator
while (keyIterator.hasNext() && valueIterator.hasNext())
System.out.println(keyIterator.next() + " : " + valueIterator.next());
System.out.println();
} // end display
} // end Driver
/*
Look at this annotated solution. Look at each .java file . Next make a list of the methods (a table with three columns). In the first column of the table give the method name. In the next column detail what the method does. In the third column show the output.
2. Implement an array-based dictionary using the same data as in the above illustration, but maintain the search keys insorted order. At the end of your driver class write a comment as an annotation that explains what you did to put the search keys in sorted order and refer to the classe(s) by name and refer to the line numbers where you made the appropriate changes.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help