Rice University - Comp 212 - Intermediate Programming
Spring 2005
Lecture #27 - An Array-based Implementation of IDictionary
Arrays in Java
-
Arrays...
-
are objects,
-
are dynamically created (via new), and
-
may be assigned to variables of type Object.
-
An array object contains zero or more unnamed variables of the same
type. These variables are commonly called the elements of
the array.
-
A non-negative integer is used to name each element. For example,
arrayOfInts[i]
refers to the i+1st element in the arrayOfInts array.
Array Types
-
An array type is written as the name of an element type followed by one
or more empty pairs of square brackets.
-
For example, int[] is the type corresponding to a one-dimensional
array of integers.
-
An array's length is not part of its type.
-
The element type of an array may be any type, whether primitive or reference,
including interface types and abstract class types.
Array Variables
-
Array variables are declared like other variables: a declaration consists
of the array's type followed by the array's name. For example,
double[][] matrixOfDoubles;
declares a variable whose type is a two-dimensional array of double-precision
floating-point numbers.
-
Declaring a variable of array type does not create an array object.
It only creates the variable, which can contain a reference to an array.
-
Because an array's length is not part of its type, a single variable of
array type may contain references to arrays of different lengths.
-
To complicate declarations, C/C++-like syntax is also supported, for example,
double rowvector[], colvector[], matrix[][];
This declaration is equivalent to
double[] rowvector, colvector, matrix[];
or
double[] rowvector, colvector;
double[][] matrix;
Please use the latter!
Array Creation
-
Array objects, like other objects, are created with new. For
example,
String[] arrayOfStrings = new String[10];
declares a variable whose type is an array of strings, and initializes
it to hold a reference to an array object with room for ten references
to strings.
-
Another way to initialize array variables is
int[] arrayOf1To5 = { 1, 2, 3, 4, 5 };
String[] arrayOfStrings = { "array",
"of",
"String" };
Widget[] arrayOfWidgets = { new Widget(),
new Widget() };
-
Once an array object is created, it never changes length!
int[][] arrayOfArrayOfInt = {{ 1, 2 }, { 3, 4 }};
-
The array's length is available as a final instance variable length.
For example,
int[] arrayOf1To5 = { 1, 2, 3, 4, 5 };
System.out.println(arrayOf1To5.length);
would print ``5''.
Array Accesses
-
All array accesses are checked at run time: An attempt to use an index
that is less than zero or greater than or equal to the length of the array
causes an IndexOutOfBoundsException to be thrown.
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 _firstEmptyPair >= _pairs.length;
}
/**
* 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;
}
}
Calculating the Computational Cost of findIndex()
-
Consider the following array and its possible traversals by findIndex().
-
In general, findIndex() examines at most ceil(log2(n+1))
keys, where n is the length of the array.