CS 245 Lecture 21 – The Problem of Lookup

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

How might you support lookup where the keys are of type String and the value is of generic type T?

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

I called, “Hey, Jenny!”
Thirty women looked at me
The rest were Sarah

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *