» CS 245 Lecture 21 – The Problem of Lookup

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?

4:00

show

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

show

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

show