public class SortedArrayDictionary
1: import java.util.Arrays;
2: import java.util.Iterator;
3: import java.util.NoSuchElementException;
4: /**
5: A class that implements the ADT dictionary by using a resizable sorted array.
6: The dictionary has distinct search keys.
7:
8: @author Frank M. Carrano
9: @author Timothy M. Henry
10: @version 4.0
11: */
12: public class SortedArrayDictionary<K extends Comparable<? super K>, V>
13: implements DictionaryInterface<K, V>
14: {
15: private Entry<K, V>[] dictionary; // Array of entries sorted by search key
16: private int numberOfEntries;
17: private boolean initialized = false;
18: private final static int DEFAULT_CAPACITY = 25;
19: private static final int MAX_CAPACITY = 10000;
20: /* < Constructors analogous to those in Listing 20-1. >
21: . . . */
22: // 20.11
23: /** Precondition: key and value are not null. */
24: public V add(K key, V value)
25: {
26: checkInitialization();
27: if ((key == null) || (value == null))
28: throw new IllegalArgumentException("Cannot add null to a dictionary.");
29: else
30: {
31: V result = null;
32: int keyIndex = locateIndex(key);
33: if ( (keyIndex < numberOfEntries) &&
34: key.equals(dictionary[keyIndex].getKey()) )
35: {
36: // Key found, return and replace entry's value
37: result = dictionary[keyIndex].getValue(); // Old value
38: dictionary[keyIndex].setValue(value); // Replace value
39: }
40: else // Key not found; add new entry to dictionary
41: {
42: makeRoom(keyIndex); // Make room for new entry
43: dictionary[keyIndex] = new Entry<>(key, value); // Insert new entry in array
44: numberOfEntries++;
45: ensureCapacity(); // Ensure enough room for next add
46: } // end if
47:
48: return result;
49: } // end if
50: } // end add
51: /* < Implementations of other methods in DictionaryInterface. >
52: . . . */
53:
54: // 20.12
55: // Returns the index of either the entry that contains key or
56: // the location that should contain key, if no such entry exists.
57: private int locateIndex(K key)
58: {
59: // Search until you either find an entry containing key or
60: // pass the point where it should be
61: int index = 0;
62: while ( (index < numberOfEntries) &&
63: key.compareTo(dictionary[index].getKey()) > 0 )
64: {
65: index++;
66: } // end while
67:
68: return index;
69: } // end locateIndex
70: // Makes room for a new entry at a given index by shifting
71: // array entries towards the end of the array.
72: // Precondition: keyIndex is valid; list length is old length.
73: private void makeRoom(int keyIndex)
74: {
75: // . . . To be implemented
76: } // end makeRoom
77: // Removes an entry at a given index by shifting array
78: // entries toward the entry to be removed.
79: private void removeArrayEntry(int keyIndex)
80: {
81: // . . . To be implemented
82: } // end removeArrayEntry
83: private class Entry<S, T>
84: {
85: private S key;
86: private T value;
87:
88: private Entry(S searchKey, T dataValue)
89: {
90: key = searchKey;
91: value = dataValue;
92: } // end constructor
93:
94: private S getKey()
95: {
96: return key;
97: } // end getKey
98:
99: private T getValue()
100: {
101: return value;
102: } // end getValue
103:
104: private void setValue(T dataValue)
105: {
106: value = dataValue;
107: } // end setValue
108: } // end Entry
109: } // end SortedArrayDictionary