### Goals

By the end of this lab, you should be able to
• convert numbers to different bases.
• create different classes that implement the same interface, and use them polymorphically in test cases.
• implement ordered lists and binary search trees.

This is a two week assignment. Start well before the due date.

### Practice Problems

Expect exercises like these on the quiz. There will be a help session covering these exercises on Wednesday at 10:00am in the Steinberg 105 lecture hall. You will benefit most by doing the exercises before you look at the solutions or attend the Wednesday help session when they will be discussed.

Directions: There will be two parts to the quiz, and you can do either one:

1. You will be asked to implement a method related to the work you did in Module 9.
2. You will be asked to carry out base conversions, similar to the ones below. Complete the table, doing all the calculations by hand. (Calculators will not be allowed for the quiz.) Be sure to double-check your calculations before you look at the solutions. The first one has been done for you. The last one is a little tricky.

The number...in base...equals the number...in base...
1012510
11102 10
29010 2
25510 2
255 10 4
2103 8
637 2
100000002 10
12810242

### Project: Two implementations of a Map interface

In this lab, you will implement a "map" abstract data type two different ways. Both of the implementations will provide the same functionality, but will differ in their structure and efficiency. Think of a "map" ADT as a relation between a domain and a range. For example, a telephone directory is a map from names to telephone numbers. The domain is all possible names, and the range is all possible phone numbers. As another example, this kind of data structure could be useful, for example, to map stock names to their current prices in a stock trading application. Each entry in the map is a pair of elements, one from the domain and one from the range. Often, the domain and range are different types, but that is not a requirement. The test cases for this lab will map strings to integers, but your implementations should be able to handle any data types.

Implementation notes:

• One purpose of this lab is for you to learn how to design and implement different data structures. Therefore, do not use any of the data structures that are already provided by Java in the java.util package. Build your data structures from scratch.

• To compare objects, such as String values, use the provided `compareTo` method of the Comparable interface. For String values, this method uses lexicographic ordering (dictionary ordering); the `compareTo` method takes as its parameter another String, and returns an integer whose value is:
• negative if this string is less than the parameter,
• zero if this string is equal to the parameter, or
• positive if this string is greater than the parameter.

• Do not use the `==` operator to compare objects for equality. When `==` is used on objects, it evaluates to true if both sides of the comparison refer to the same exact memory location (i.e., it's the exact same object). For example, even if two String objects contain the same text, the `==` test for equality on the two objects would return `false` if they are not the same object.
Directions:
1. Open the provided file Map.java and study the provided code in that file. Notice that the file does not contain a class definition, but instead contains an interface. Recall that an interface is just a collection of method names with parameter types and return types. It cannot be instantiated, because it doesn't actually contain implementations of any of the methods. That is, the methods have no bodies.

Notice that the key type is any Comparable object. This will allow you to call the `compareTo` method on the keys. The values associated with key can be objects of any type.

2. Open the provided file OrderedListMap.java and read the provided code. Notice the line
```public class OrderedListMap implements Map
```
near the top of the file. The phrase "implements Map" means that this class conforms to the Map interface. In other words, this class must define all of the methods contained in the Map interface, and the compiler will check that this is indeed the case.

3. In general, Java's support for interfaces provides the power to define the interface of an ADT and write programs in terms of that interface. Then, you can implement the ADT in different ways and use those implementations interchangably. For example, look at the testAllMethods procedure in the provided file MapTest.java. Notice that the method calls another method to create a Map object. Any object returned by that method must implement the Map interface, and so the testAllMethods procedure may call any of the methods in the Map interface on the object returned. There are two other JUnit test cases provided, one for OrderedListMap and one for TreeMap. Each of these extends the MapTest and so each of them inherits testAllMethods. Each of these test cases overrides the method that creates the Map, to create an OrderedListMap and a TreeMap, respectively. So, when you run each of those test cases, they will use the same test method, but will use different type of object.

4. Study again the interface definition in the file Map.java, paying attention to the documentation for each method. Complete the implementation in the file OrderedListMap.java, being sure to satisfy the specification given in the interface file. For your internal representation, use a linked list, where each list item contains a domain element (a String), a range element (a double), and a next pointer (to another list item). If you like, you can use dummy nodes at the beginning and end of the list. Also, feel free to create a doubly linked list (with previous pointers) if you find that easier.

One of the representation invariants for your OrderedListMap implementation should be that the list is kept in alphabetically sorted order according to the domain element. Use the fact that the list is kept in sorted order in order to improve the efficiency of the methods.

5. You can write additional test cases, but when you are finished, the provided test case OrderedListMapTest should run correctly. Also, be sure to verify that your toString methods produce the correct output. Verify that your list is being kept in sorted order.

6. Complete the implementation in the file TreeMap.java, being sure to satisfy the specification given in the interface file. To do this, you'll need to define a TreeNode class. Each node in the tree will have a domain element (a String), a range element (a double), a (possibly null) left subtree and a (possibly null) right subtree. Your implementation should satisfy the representation invariant that for each node, all strings in the left subtree are alphabetically less, and all strings in the right subtree are alphabetically greater. Make use of this invariant to improve the efficiency of the methods.

Your remove method will require deleting elements from the tree. The usual way to delete nodes from a binary search tree is somewhat complicated, as discussed in class. Therefore, we are leaving the proper implementation of delete as an optional extension for this lab. If you don't want to do that extension, then you can implement delete by adding a boolean instance variable called deleted to your tree nodes. If you delete an element from the tree, you can just set deleted to true. Then, when a search reaches that node for the get or contains method, you can act as if the element is not in the tree.

Implement the `toString` method so that it returns a readable representation of the tree. Display the tree sideways, with the root of the tree at the left edge of the page. Your return String should have one node per line, something like this:

```
(quack,4)
(oink,5)
(moo,7)
(meow,2)
()
(bow wow,8)
(baa,5)

```
This is called an in-order traversal of the tree, since one subtree is traversed first, then the node itself, and then the other subtree. You can use the special character `'\n'` in a String to cause the terminal to advance to a new line as it prints the string.

Hint: The depth of the node in the tree determines how much to indent. So, use a helper procedure with a String parameter that keeps track of the leading spaces for each line of output. Start it out with the value `""` and then concatenate a String of spaces to create the indentation String parameter for the recursive calls on both subtrees. If you want, you can use the special tab character `'\t'` instead of multiple spaces.

7. You can write additional test cases, but when you are finished, the provided test case TreeMapTest should run correctly. Also, be sure to verify that your toString methods produce the correct output. Verify that your list is being kept in sorted order. Look at the printed values to be sure that the representation invariant is being preserved by your implementation.

### Optional Extension 1: Binary Search Tree Deletion

Implement deletion properly in your binary search tree. In particular, suppose you want to remove node x from the tree.

1. If x is a leaf, let x's parent refer to null instead.
2. If x has only one child, let x's parent refer to x's child instead.
3. In the difficult case, when x has two children, you can replace x in the tree by the rightmost element in x's left subtree.

### Optional Extension 2: ArrayMap

In the file ArrayMap.java complete the implementation of the class ArrayMap to implement the Map interface. For your internal representation, create an array of references to `Pair` objects, where each pair contains a domain element (a String) and a range element (a double). Create the array to allow enough space for 100 pairs. One of your representation invariants should be that the array is kept in sorted order according to the values of the String in each pair.

To find the right location in the array for the put, get, contains, and remove methods, use binary search on the array. This will be much more efficient than searching linearly through the array. Note that when you insert an item that belongs somewhere in the middle of the array, you'll have to bump all the items after it down by one to make room for it in the array.

Create a JUnit test case ArrayMapTest.java similar to the others. Again, notice that the test procedure only cares that the object's type implements the map interface. Verify that the output is correct. Look at the printed values of the map to be sure that your array is being kept in sorted order.

### What To Turn In:

Follow these submission instructions to turn in the following files and demonstrate your running program for a TA.
1. cover-page.txt -- Be sure to fill in all information.
2. Map.java and MapTest.java (provided)
3. OrderedListMap.java and OrderedListMapTest.java
4. TreeMap.java and TreeMapTest.java
5. ArrayMap.java and ArrayMapTest.java (for optional extension 2)

Kenneth J. Goldman (kjg@cse.wustl.edu)