CSC152 2005F, Class 45: Dictionaries (1): The Basics

Admin:
* No homework
* Maybe prospectives
* Extra credit for attending YGB Concert, Saturday, 19 Nov, 4pm
* Extra credit for attending campus band concert, 8-10, Gardner
* First home men's basketball game tonight, 7 pm. the *new!!!!* Darby

Overview:
* The PAMI of Dictionaries
* Java's versions: Dictionary and Map
* Implementation strategy one: Association List
* Implementation strategy two: Binary Search Tree

Philosophy of Dictionaries (Map) (KeyedTable)
* Collection of values, indexed by the "reasonable" type of your choice (traditionally, strings)

Terminology: We often say "key" for position"

Methods:
* put(KeyType key, OtherType value)
* OtherType get(KeyType key) - does not remove; acts like "get" for Vectors or ArbityrarilyLarageIntegerArrays
  * No duplication of positions
  * Yes you may duplicate values
* int size()
* void remove(KeyType key)

Application: Why?  (Can focus on indexing by string)
* Might want to build a dictionary (or Wikipedia)
* Phone book, student directory, class list, etc: wide variety of cases in which we seem to use names as indices
* Analysis of texts: Use strings to index counters

Java makes our life to complex in its designs.  Too bad.

Implementation:
* Strategy (from Scheme): Association list
  * Make a list of pairs
  * The car of each pair is the key
  * The cdr of each pair is the value
  * The built in operation assoc (and assq and assv, I think)
    searches for a key and returns the key/value pair.
* In Java, make a Vector of these pairs
KeyedValue(K,V)
{
  K key;
  V value;
}
public AssociationList<K,V>
{
  Vector<KeyedValue<K,V>> contents;
  ...
}
* get is O(n)
  Look at each keyed value in the vector.  If the key is equal
  to the key we want, return the value
* Design question: What happens if the key doesn't appear
  - Return null
  - Throw exception
  public V get(K key)
    throws NoSuchKeyException
  {
    int len = contents.size();
    for (int i = 0; i < len; i++) {
      KeyedValue<K,V> tmp = contents.get(i);
      if (tmp.key.equals(key)) {
        return tmp.value;
      }
    } // for
    // Whoops!  No keys matched
    throw new NoSuchKeyException("Could not find " + key.toString());
  } // get(K)
  public class NoSuchKeyException
    extends Exception
  {
    public NoSuchKeyException(String reason)
    {
      super(reason);
    }
  }

* put is O(1) in most cases
  Make a new key/value pair
  Shove it at the end
  Cross your fingers that the vector doesn't need to expand
  * The "Amortized" cost is O(1)
  public void put(K key, V value)
  {
    this.contents.add(new KeyedValue<K,V>(key,value));
  }

How do we make this faster?
* Divide and conquer