This is the archived website of IC 312 from the Fall 2015 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Homework 5: BST implementation of Map

  • Due before class on Wednesday, October 14
  • Submit using the submit program as 312 hw 05.

All of you are always identified by alpha, which is very frustrating for those of us who have no interest in memorizing which alpha corresponds to which midshipman. Let's fix the problem by making a Map implemented with a Binary Search Tree.

Starter code

Details

You'll write a class called AlphaMap which will map alphas to names, organizing data in the tree by alphas (small ones to the left, big ones to the right), and have methods such that main methods like the one below will work:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class MapMain {
  public static void main(String[] args) {
    Map<Integer,String> map = new AlphaMap();
    map.set(222222, "Ernest Hemingway");
    map.set(111111, "Ray Charles");
    map.set(333333, "John F Kennedy");
    System.out.println(map.get(333333)); // should print John F Kennedy
    System.out.println(map.get(222222)); // should print Ernest Hemingway
    String name = map.get(444444);
    if (name == null) 
      System.out.println("444444 is not in the map");   // should do this
    else
      System.out.println("this is not right: " + name); // not this
    System.out.println(map.size()); // should print 3
  }
}

Your AlphaMap class must implement the interface Map<Integer,String> as defined in the Map.java file:

1
2
3
4
5
6
7
8
9
10
11
12
13

public interface Map<K,V> {
  /** Retrieves the value associated with this key, or null if not found. */
  public V get(K key);
 
  /** Assigns a value to be associated with the given key.
   * If the key is not already in the map, it gets added.
   * Otherwise, if it's already in the map, its associated value is modified.
   */
  public void set(K key, V value);
 
  /** Returns the number of distinct keys in this map. */
  public int size();
}

You'll use methods very similar to ones we've already written in class, you just have to turn it into a Map.

For fun, I've included an implementation of Map<Integer,String>using linked lists, in the class AlphaMapLL.