Rice University - Comp 212 - Intermediate Programming

Fall 2002

Lecture #31 - An Array-based Implementation of a Dictionary - Binary Search

Today's menu:

1. Discuss Recursive Descent Parser Lab.
2. Discuss dictionary concept and array implementation.
   

• 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.

• 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 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 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''.

• 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 dict;

import java.lang.*;

/**
 * Implements a key/value pair for use by a Dictionary.
 */
public class DictionaryPair implements Comparable {
    private Comparable _key;
    private Object     _value;

    /**
     * Initialize a key/value pair.
     */
    public DictionaryPair(Comparable key, Object value) {
	_key   = key;
	_value = value;
    }

    /**
     * Delegate compareTo() to the key.
     */
    public int compareTo(Object other) {
	return _key.compareTo(((DictionaryPair)other)._key);
    }

    /**
     * Returns the key.
     */
    public Comparable getKey() {
	return _key;
    }

    /**
     * Returns the value.
     */
    public Object getValue() {
	return _value;
    }

    /**
     * Converts the key/value pair into a string
     * of the form "(key,value)".
     */
    public String toString() {
	return "(" + _key + "," + _value + ")";
    }
}

package dict;

import listFW.*;

/*
 * Defines an interface for a simple dictionary that contains DictionaryPairs.
 */
public interface IDictionary {
    /**
     * Clears the contents of the dictionary leaving it empty.
     */
    public void clear();

    /**
     * Returns true if the dictionary is empty and false otherwise.
     */
    public boolean isEmpty();

    /**
     * Returns an IList of DictionaryPairs corresponding to the entire
     * contents of the dictionary.
     */
    public IList elements();

    /**
     * Returns the DictionaryPair with the given key.  If there is not
     * a DictionaryPair with the given key, returns null.
     * Returns a DictionaryPair rather than the value alone so that
     * the user can distinguish between not finding the key and
     * finding the pair (key, null).
     */
    public DictionaryPair lookup(Comparable key);

    /**
     * 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(Comparable key, Object value);

    /**
     * Removes the DictionaryPair with the given key and returns it.
     * If there is not a DictionaryPair with the given key, returns
     * null.
     */
    public DictionaryPair remove(Comparable key);
}

import listFW.*;
import listFW.factory.*;

/**
 * An implementation of IDictionary using an array to hold the
 * DictionaryPairs.
 *
 * @author Alan L. Cox
 * @since 03/26/02
 * @since 11/11/02 modified by DXN
 */
public class DictArray implements IDictionary {
    /*
     * An array of DictionaryPairs ordered by key
     */
    private int              _firstEmptyPair = 0;
    private DictionaryPair[] _pairs = new DictionaryPair[1];

    /*
     * An IList factory used by elements()
     */
    private IListFactory _lf = new CompositeListFactory();

    /**
     * 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 DictionaryPair[1];
    }

    /**
     * Returns true if the dictionary is empty and false otherwise.
     */
    public boolean isEmpty() {
        return _firstEmptyPair == 0;
    }

    /**
     * Returns an IList of DictionaryPairs corresponding to the entire
     * contents of the dictionary.
     */
    public IList elements() {
        IList 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.)
     */
    private int findIndex(Comparable key) {
        int lo = -1;
        int hi = _firstEmptyPair;

        while (lo + 1 != hi) {
            int mid = (lo + hi)/2;
            int result = _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 DictionaryPair with the given key.  If there is not
     * a DictionaryPair with the given key, returns null.
     *
     * Returns a DictionaryPair rather than the value alone so that
     * the user can distinguish between not finding the key and
     * finding the pair (key, null).
     */
    public DictionaryPair lookup(Comparable key) {
        int index = findIndex(key);

        if ((index >= 0) &&
            (_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.
     * If the array is full, then double its size!
     */
    public void insert(Comparable key, Object value) {
        int index = findIndex(key);

        if ((index >= 0) &&
            (_pairs[index].getKey().compareTo(key) == 0)) {
            _pairs[index] = new DictionaryPair(key, value);
            return;
        }
        if (_firstEmptyPair == _pairs.length) {
            // Create a new array whose size is twice that of the old array.
            DictionaryPair[] newPairs = new DictionaryPair[2*_pairs.length];
            // Copy over the old array:
            for (int i = 0; i < _pairs.length; i++) {
                newPairs[i] = _pairs[i];
            }
            // Re-assign the old array to the new array:
            _pairs = newPairs;
        }
        int i = _firstEmptyPair;

        for (index++; i > index; i--) {
            _pairs[i] = _pairs[i - 1];
        }
        _pairs[i] = new DictionaryPair(key, value);

        _firstEmptyPair++;
    }

    /**
     * Removes the DictionaryPair with the given key and returns it.
     * If there is not a DictionaryPair with the given key, returns
     * null.
     */
    public DictionaryPair remove(Comparable key) {
        int index = findIndex(key);

        if ((index >= 0) &&
            (_pairs[index].getKey().compareTo(key) == 0)) {

            DictionaryPair pair = _pairs[index];

            int i = index;

            for (_firstEmptyPair--; i < _firstEmptyPair; i++) {
                _pairs[i] = _pairs[i + 1];
            }
            _pairs[i] = null;

            return pair;
        }
        return null;
    }
}

• 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.