teaching machines

CS 245 Lecture 21 – The Problem of Lookup

November 14, 2013 by Chris Johnson. Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• what does this do?
• program this
• methods for mapping keys to values

TODO

• Read section 7.2 and 7.3. 1/4 sheet.

What Does This Do?

File hierarchy starting at directory 00.

What is printed by the following code?

Stack<File> unsearched = new Stack<File>();
unsearched.push(new File("00"));
while (!unsearched.isEmpty()) {
  File dir = unsearched.pop();
  System.out.println(dir);
  File[] children = dir.listFiles();
  for (File child : children) {
    if (child.isDirectory()) {
      unsearched.push(child);
    }
  }
}

What if Stack were replaced with Queue, push with enqueue, and pop with dequeue?

Lookup

We want to map keys to values: names to phone numbers (a phonebook), web addresses to IP addresses (DNS), terms to their definitions (dictionary), words to their pages of occurrence (index), etc. When someone feeds us a key, we can report back the associated value.

Program This

Code

Map.java

package lecture21;

public interface Map<K, V> {
  V get(K key);
  void add(K key, V value);
}

NickMap.java

package lecture21;

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class NickMap<K, V> implements Map<K, V> {
  private ArrayList<K> keys;
  private ArrayList<V> values;

  public NickMap() {
    keys = new ArrayList<K>();
    values = new ArrayList<V>();
  }

  @Override
  public V get(K key) {
    for (int i = 0; i < keys.size(); ++i) {
      if (keys.get(i).equals(key)) {
        return values.get(i);
      }
    }
    throw new NoSuchElementException();
  }

  public boolean hasKey(K key) {
    return keys.contains(key);
  }

  @Override
  public void add(K key,
                  V value) {
    if (hasKey(key)) {
      throw new RuntimeException("Duplicate key, foobag!");
    } else {
      keys.add(key);
      values.add(value);
    }
  }
}

Fastmap.java

package lecture21;

public class Fastmap<K, V> implements Map<K, V> {
  private V[] values;

  public Fastmap() {
    values = (V[]) new Object[100];
  }

  @Override
  public V get(K key) {
    return values[key];
  }

  @Override
  public void add(K key,
                  V value) {
    values[key] = value;
  }

  public static void main(String[] args) {
    Fastmap<Integer, String> ageToName = new Fastmap<Integer, String>();

    ageToName.add(5, "Lewis");
    ageToName.add(5, "Devin");

    System.out.println(ageToName.get(5));
  }
}

Haiku