The following is an implementation of the IDictionary interface using a array of DictPair. This array grows dynamically as more storage space is needed. Java also provides a class called Vector to implement dynamically resizable arrays.
package genDict;
import genListFW.*;
/**
* An implementation of IDictionary<K, V> using an array to hold the
* DictPair<K, V>.
*
* @author Alan L. Cox
* @author Dung X. Nguyen ("generifier")
* @since 03/23/05
*/
public class DictArray<K, V> implements IDictionary<K, V> {
/*
* An array of DictPair<K, V> s ordered by key of type K.
* K must extends or implements Comparable.
*/
private int _firstEmptyPair = 0;
private DictPair<K, V>[] _pairs = new DictPair[1];
/**
* Clears the contents of the dictionary leaving it empty.
*
* Implemented by replacing the existing array with a new,
* empty one.
*/
public void clear() {
_firstEmptyPair = 0;
_pairs = new DictPair[1];
}
/**
* Returns true if the dictionary is empty and false otherwise.
*/
public boolean isEmpty() {
return _firstEmptyPair == 0;
}
public boolean isFull() {
return false; // the array will
grow in size as needed.
}
/**
* Returns an IList of DictPairs corresponding to the entire
* contents of the dictionary.
*/
public IList< DictPair<K, V> > elements(final IListFactory<
DictPair<K, V> > lf) {
IList< DictPair<K, V> > l =
lf.makeEmptyList();
for (int i = _firstEmptyPair - 1; i
>= 0; i--)
l =
lf.makeNEList(_pairs[i], l);
return l;
}
/**
* Binary Search Algorithm:
* Returns either (1) the index of the key if it is stored
* in the array or (2) the index of the next smaller key
* if it is NOT stored in the array. (If there is NOT
* a smaller key in the array, returns -1.)
* Complexity Analysis is done in a latter section below.
*/
private int findIndex(Comparable key) {
int lo = -1;
int hi = _firstEmptyPair;
while (lo + 1 != hi) {
int mid = (lo
+ hi)/2;
int result =
((Comparable)_pairs[mid].getKey()).compareTo(key);
if (result >
0) // _pairs[mid].getKey() > key
hi = mid;
else if
(result == 0) // _pairs[mid].getKey() == key
return mid;
else // _pairs[mid].getKey()
< key
lo = mid;
}
return lo;
}
/**
* Returns the DictPair with the given key. If there is not
* a DictPair with the given key, returns null.
*
* Returns a DictPair rather than the value alone so that
* the user can distinguish between not finding the key and
* finding the pair (key, null).
*/
public DictPair<K, V> lookup(K key) {
int index = findIndex((Comparable)key);
if ((index >= 0) &&
((Comparable)_pairs[index].getKey()).compareTo(key) == 0)
return _pairs[index];
return null;
}
/**
* Inserts the given key and value. If the given key is already
* in the dictionary, the given value replaces the key's old
* value.
*/
public void insert(K key, V value) {
int index = findIndex((Comparable)key);
if ((index >= 0) &&
((Comparable)_pairs[index].getKey()).compareTo(key) == 0) {
_pairs[index]
= new DictPair(key, value);
return;
}
if (_firstEmptyPair == _pairs.length)
{
DictPair<K,
V>[] newPairs = new DictPair[2*_pairs.length];
for (int i =
0; i < _pairs.length; i++)
newPairs[i] = _pairs[i];
_pairs =
newPairs;
}
int i = _firstEmptyPair;
for (index++; i > index; i--)
_pairs[i] = _pairs[i
- 1];
_pairs[i] = new DictPair(key, value);
_firstEmptyPair++;
}
/**
* Removes the DictPair with the given key and returns it.
* If there is not a DictPair with the given key, returns
* null.
*/
public DictPair<K, V> remove(K key) {
int index = findIndex((Comparable)key);
if ((index >= 0) &&
((Comparable)_pairs[index].getKey()).compareTo(key) == 0) {
DictPair<K,
V> pair = _pairs[index];
int i =
index;
for (_firstEmptyPair--;
i < _firstEmptyPair; i++)
_pairs[i] = _pairs[i + 1];
_pairs[i] =
null;
return pair;
}
return null;
}
}
Expected-case Cost | Worst-case Cost | ||
lookup() | O(n) (i.e. some constant times n) | O(n) | |
DictLRS | insert() | O(n) | O(n) |
remove() | O(n) | O(n) | |
lookup() | O(log n) (i.e. some constant times log n) | O(n) | |
DictBT | insert() | O(log n) | O(n) |
remove() | O(log n) | O(n) | |
lookup() | O(log n) | O(log n) | |
DictArray | insert() | O(n) | O(n) |
remove() | O(n) | O(n) | |