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 implements DictionaryInterface

{

private Entry[] dictionary; // Array of unsorted entries

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[] tempDictionary = (Entry[])new Entry[initialCapacity];

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 getKeyIterator()

{

return new KeyIterator();

} // end getKeyIterator

public Iterator getValueIterator()

{

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 currentEntry = dictionary[currentIndex];

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 currentEntry = dictionary[currentIndex];

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 { /** 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 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 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

--------------------------------------------

// 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 nameList = new ArrayDictionary<>();

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 dictionary)

{

Iterator keyIterator = dictionary.getKeyIterator();

Iterator valueIterator = dictionary.getValueIterator();

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.