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.Update your svn repository as usual to get the lab9 package.
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.
compareTomethod of the Comparable interface. For String values, this method uses lexicographic ordering (dictionary ordering); the
compareTomethod takes as its parameter another String, and returns an integer whose value is:
==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
falseif they are not the same object.
public class OrderedListMap<K extends Comparable<K>,V> implements Mapnear 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.
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.
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.
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.
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
instead of multiple spaces.