CSE 131 Module 9: ADT Representations


Note: We have two weeks for this module, and while you are welcome to get started on this lab, you may find it easier after this week's lecture and studio.

That said, you should definitely not put the lab off until the last minute. It would be a good idea to get OrderedListMap mostly done in this week and the TreeMap part next week.

Update your svn repository as usual to get the lab9 package.

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:


  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.

  2. Open the provided file OrderedListMap.java and read the provided code. Notice the line
    public class OrderedListMap<K extends Comparable<K>,V> 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.

    Notice also that the key type K 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.

  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 (e.g., a String), a range element (e.g., an Integer), 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 range element, 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:

                (bow wow,8)
    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.

Submitting your work (read carefully)

Last modified 22:14:03 CST 11 November 2009 by Ron K. Cytron