For this assignment, you will implement the Map ADT using a binary search tree. In my videos, I implement nodes that don't keep parent pointers. Your book has pseudocode that does keep parent pointers and that is what I implemented myself for this. Remove is by far the hardest method. I would suggest you write it last. I have provided you with additional functions and some sample tests to help. Note that you are allowed to refer to the book's pseudocode for your implementation. Also, you will probably find that a fair bit of the code in the HashMap will work just as well for the BSTMap.
Be careful when comparing keys to use .equals instead of ==. If you don't recall this from CS2, == on object types does an identity check. It tells you if the two objects are the same object at the same location in memory. The .equals method will compare their contents to see if they have the same value. If you ever do something like key1 == key2 it will cause errors in some situations, likely in my tests, even if not yours.
There are times when it can be helpful to use the "trick" of having a trailing pointer. This is especially true if you don't keep a parent pointer. Even if you do have a parent pointer, there are times when it can simplify the logic if your "rover" falls off the bottom of the tree and the trailer is on the leaf node.
It is ideal if you do something to "set up" the iterator at the beginning. For this reason, I recommend using a named inner class and having a constructor.
For the keySet I was able to use an anonymous inner-class. Not that I gave you a Set.java file. If you accidentally import java.util.Set it won't work, so make sure you don't have that import. It has three methods in it and it is basically a wrapper around calls to the BSTMap. So it makes liberal use of calls like BSTMap.this.size(). One of the methods is iterator(). That method contains its own anonymous inner-class that includes the following private data.
private Iterator<KeyValuePair<K, V>> iter = BSTMap.this.iterator();
Note that I'm reusing the iterator I already wrote for the BSTMap, and I only return the key instead of the full KeyValuePair.
There are some minor variations in the higher-order methods. I got rid of the mutating ones to save you time. I replaced takes and drops with the logical exists and forall.
For the following, assume the following declaration, which is working code from one of my tests.
var hash = BSTMap.of(
Map.kvp("abc", 3),
Map.kvp("xyz", 19),
Map.kvp("bob", 16),
Map.kvp("jill", 51),
Map.kvp("pat", 32)
);
In the examples below I'm using an arrow to indicate a key/value pair. This would be valid in Scala. The Java way is just too much more verbose.
mapValues
hash.mapValues(v -> v*2) ====> ("abc" -> 6, "xyz" -> 38, "bob" -> 32, "jill" -> 102, "pat" -> 64)
filter
hash.filter(kvp -> kvp.value() % 2 == 0) ====> ("bob" -> 16, "pat" -> 32)
hash.filter(kvp -> kvp.key().length() > 3) ====> ("jill" -> 51)
find
hash.find(kvp -> kvp.key().length() > 3) ====> Optional.of("jill" -> 51)
hash.find(kvp -> kvp.value() > 100) ====> Optional.empty
fold (not directional as order is "random")
hash.fold(0, (sum, kvp) -> sum + kvp.value()) ====> 121
exists
hash.exists(kvp -> kvp.value() == 16) ====> true
hash.exists(kvp -> kvp.key().length() < 3) ====> false
forall
hash.forall(kvp -> kvp.value() < 100) ====> true
hash.forall(kvp -> kvp.value() < 40) ====> false
Your tests need to include calls to all methods.