teaching machines

CS 245 Lecture 13 – Generics and Maps

March 4, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• midterm – next Tuesday
  • interfaces
  • inheritance (overriding, augmenting)
  • binary search
  • informal computational complexity (linear vs. quadratic vs. linearithmic, etc.)
  • growable arrays
  • recursion
  • code tracing
  • code writing
  • conceptual knowledge (not APIs)
• code reuse?
• making ArrayList reusable
• making ArrayList generic
• the map abstract data type

TODO

• Read Core Java, chapter 12 through section 12.6 (Restrictions and Limitations). 1/4 sheet.

Think About This

Code

OurrayList.java

package lecture13;

public class OurrayList {
  private Object[] items;
  private int itemCount;

  public OurrayList(int initialCapacity) {
    items = new Object[initialCapacity];
    itemCount = 0;
  }

  public OurrayList() {
    this(10);
  }

  public int size() {
    return itemCount;
  }

  public Object get(int i) {
    if (i < 0 || i >= itemCount) {
      throw new IndexOutOfBoundsException("Hey, foobag! " + i + " isn't welcome here.");
    }
    return items[i];
  }

  public void add(Object s) {
    // Are we full?
    if (itemCount == items.length) {
      Object[] moreItems = new Object[2 * items.length];
      for (int i = 0; i < items.length; ++i) {
        moreItems[i] = items[i];
      }
      items = moreItems;
    }

    items[itemCount] = s;
    ++itemCount;
  }

  public void remove(int i) {
    --itemCount;
    for (int j = i; j < itemCount; ++j) {
      items[j] = items[j + 1];
    }
    items[itemCount] = null;
  }

  public int indexOf(Object s) {
    for (int i = 0; i < itemCount; ++i) {
      if (items[i].equals(s)) {
        return i;
      }
    }
    return -1;
    // throw new NoSuchElementException();
  }

  public void remove(Object s) {
    int i = indexOf(s);
    if (i >= 0) {
      remove(i);
    }
  }

  public String toString() {
    String s = "[";

    if (size() > 0) {
      s += items[0];
      for (int i = 1; i < size(); ++i) {
        s += ", " + items[i];
      }
    }

    return s + "]";
  }

  public static void main(String[] args) {
    OurrayList l = new OurrayList(1);
    l.add("Alice");
    l.add("Bob");
    l.add("Carol");
    l.add("Moon Unit");
    System.out.println(l);
    
    // This shouldn't be allowed!
    l.add(new StackOverflowError());
    
    l.remove(0);
    System.out.println(l);
    
    String head = (String) l.get(0);
    System.out.println(head);
  }
}

OurrayListGeneric.java

package lecture13;

public class OurrayListGeneric<T> {
  private T[] items;
  private int itemCount;

  public OurrayListGeneric(int initialCapacity) {
    items = (T[]) new Object[initialCapacity];
    itemCount = 0;
  }

  public OurrayListGeneric() {
    this(10);
  }

  public int size() {
    return itemCount;
  }

  public T get(int i) {
    if (i < 0 || i >= itemCount) {
      throw new IndexOutOfBoundsException("Hey, foobag! " + i + " isn't welcome here.");
    }
    return items[i];
  }

  public void add(T s) {
    // Are we full?
    if (itemCount == items.length) {
      T[] moreItems = (T[]) new Object[2 * items.length];
      for (int i = 0; i < items.length; ++i) {
        moreItems[i] = items[i];
      }
      items = moreItems;
    }

    items[itemCount] = s;
    ++itemCount;
  }

  public void remove(int i) {
    --itemCount;
    for (int j = i; j < itemCount; ++j) {
      items[j] = items[j + 1];
    }
    items[itemCount] = null;
  }

  public int indexOf(T s) {
    for (int i = 0; i < itemCount; ++i) {
      if (items[i].equals(s)) {
        return i;
      }
    }
    return -1;
    // throw new NoSuchElementException();
  }

  public void remove(T s) {
    int i = indexOf(s);
    if (i >= 0) {
      remove(i);
    }
  }

  public String toString() {
    String s = "[";

    if (size() > 0) {
      s += items[0];
      for (int i = 1; i < size(); ++i) {
        s += ", " + items[i];
      }
    }

    return s + "]";
  }

  public static void main(String[] args) {
    OurrayListGeneric<String> l = new OurrayListGeneric<String>(1);
    l.add("Alice");
    l.add("Bob");
    l.add("Carol");
    l.add("Moon Unit");
    System.out.println(l);

    // This isn't allowed!
    // l.add(new StackOverflowError());

    l.remove(0);
    System.out.println(l);

    String head = l.get(0);
    System.out.println(head);
  }
}

Map.java

package lecture13;

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

TwoListsMap.java

package lecture13;

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

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

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

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

  @Override
  public V get(K key) {
    int indexOfKey = keys.indexOf(key);
    if (indexOfKey < 0) {
      throw new NoSuchElementException("No value for key " + key);
    } else {
      return values.get(indexOfKey);
    }
  }

  @Override
  public void remove(K key) {
    if (hasKey(key)) {
      int indexOfKey = keys.indexOf(key);
      values.remove(indexOfKey);
      keys.remove(indexOfKey);
    }
  }

  @Override
  public void add(K key,
                  V value) {
    int indexOfKey = keys.indexOf(key);
    if (indexOfKey >= 0) {
      // Throw an exception or update the existing record? Let's update!
      values.set(indexOfKey, value);
    } else {
      keys.add(key);
      values.add(value);
    }
  }
}

StateQuiz.java

package lecture13;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class StateQuiz {
  public static void main(String[] args) throws FileNotFoundException {

    TwoListsMap<String, String> statesToCapitals = new TwoListsMap<String, String>();
    ArrayList<String> justTheStates = new ArrayList<String>();
    
    // statesToCapitals.add("Wisconsin", "Rhinelander");
    // System.out.println(statesToCapitals.get("Wisconsin"));
    
    Scanner in = new Scanner(new File("/Users/johnch/Desktop/states.txt"));
    while (in.hasNextLine()) {
      String line = in.nextLine();
      String[] fields = line.split(",");
      justTheStates.add(fields[0]);
      statesToCapitals.add(fields[0], fields[1]);
    }
    in.close();
    
    in = new Scanner(System.in);
    Collections.shuffle(justTheStates);
    for (int i = 0; i < justTheStates.size(); ++i) {
      String state = justTheStates.get(i);
      System.out.print("What's the capital of " + state + "? ");
      String capital = in.nextLine();
      String expectedCapital = statesToCapitals.get(state);
      if (expectedCapital.equals(capital)) {
        System.out.println("Wow! You are a founding father/mother!");
      } else {
        System.out.println("No, that's the capital of Puerto Rico.");
      }
    }
  }
}

Haiku