Homework answers / question archive / Homework #15 due Monday, January 16, 10:00 PM In this assignment, you will update the generic \Map" container class from Homework #10 by adding \threading" to the binary search tree, Unlike in Homework # 10, the iterator will use threading, as explained in the \Navigating Trees" handout (in Module 9 on Canvas)

Homework #15 due Monday, January 16, 10:00 PM In this assignment, you will update the generic \Map" container class from Homework #10 by adding \threading" to the binary search tree, Unlike in Homework # 10, the iterator will use threading, as explained in the \Navigating Trees" handout (in Module 9 on Canvas)

Computer Science

Share With

Homework #15
due Monday, January 16, 10:00 PM
In this assignment, you will update the generic \Map" container class from Homework #10
by adding \threading" to the binary search tree, Unlike in Homework # 10, the iterator will use
threading, as explained in the \Navigating Trees" handout (in Module 9 on Canvas).
This homework assignment is a makeup assignment; you should have received information as to
how it can be used to improve your grade. Basically, you will need to fully complete this assignment,
because one cannot show mastery through repeated mediocre performance. In particular, you
should make every legitimate eort to pass every test that we give you, including eciency and
random tests.
To start the homework assignment, please use this link:
https://classroom.github.com/a/JM6LsBfy
1 Concerning the Threading
To support the iterator, we will link up all the nodes in the binary search tree in a linked list,
starting at a dummy node that is not part of the tree. The nodes are linked in in-order order, with
\null" at the end. Then the nodes in the binary search tree are also in a (singly) linked list (using
\next" pointers).
As explained in the \Navigating Trees" handout, adding threads makes extra work for:
• Checking the links as part of invariant.
The handout suggests a separate helper method when checking the \next" elds. Instead, we
will use one helper method checkSubtree that will check keys and also check \next" elds.
The helper method will take the \after" node pointer, which is what the last node (if any)
in the subtree should point to. It will return the \rst" node pointer, which is what the last
node before this subtree should point to. If the subtree is empty, then the \rst" node is the
same as the \after" pointer.
Since the recursive helper method returns a node, rather than an integer or a boolean, we
need a way to indicate a problem: the dummy node is returned to indicate that a problem
was found (and reported) in the subtree. We cannot use null, because this is a legal return
value for the end of the tree. But the dummy node cannot legally start any subtree, so it is
a suitable error value. You will need to check the return value of the helper method against
the dummy node to check for an already reported error (do not report a second error!).
• Updating the links when adding a new entry.
We provide an activity to help you gure out how to update the \next" links while adding
new entries. The code you develop is for a Set ADT (rather than a Map ADT), but the basic
ideas apply. You should write doPut recursively taking the \before" node, as described in the
activity. You can use get to determine the needed return value before you make the change.
• Updating the links when removing an entry.
As with doPut, the recursively helper method should be passed the \before" node for the
subtree. When you locate the node with the entry to remove, then if it doesn't have a
\left" subtree, then the \before" node for this node is indeed the node before this one on the
Fall 2022 page 1 of 3
CompSci 351 / CompSt 751: Data Structures & Algorithms Homework #15
linked list, which makes removal easy. Otherwise (if there is a non-null left subtree), then the
immediate predecessor node will be in that subtree. The immediate predecessor is also the
node previous to this one in the linked list. Plan carefully with pictures to gure out how to
correctly remove the entry from the tree and update the links correctly.
We provide a new set of internal tests you can use to test your updated well-formed-ness checker.
2 Concerning the Iterator of the Entry Set
As in previous assignments, we will create an instance of a nested class to implement the iterator.
Unlike in the previous assignments, the iterator will use the new threading links.
You should come up with a good data structure and implement an invariant for it. We recom-
mend one of these two data structures:
1. Have separate current and next elds in the iterator which are the same when there is
nothing to remove. Otherwise, the current node's \next" link should point to the next link.
The current pointer must be a node in the list.
2. Have a precursor eld and a boolean indicating whether the current element can be removed.
The precursor node must be a node in the list.
Use the dummy node to initialize things, so you can use \null" only to indicate being at the end
of the iteration.
You will need to write code for the invariant checker. You are encouraged but not required to
write internal test cases for this checker, by adding new tests to the end of the internal tests.
3 What You Need To Do
You need to complete the le TreeMap.java by implementing the following methods. For this
assignment, we give a suggested order so that you can avoid getting lost in the minor details before
implementing the important functionality.
• wellFormed, checkSubtree
These methods are used for invariant checking. Check that you pass the internal tests. (Don't
start the iterator's wellFormed() yet.)
• The unnished constructor (there is a \TODO").
• put(K, V)
This method should use a recursive helper method doPut. Make sure to follow the idea of
the Activity for the extra parameter (other than the subtree, the key and the value). You
will need compute the return value of put before doing the actual operation.
• Optional: clear in the entry set.
Having this method written will make it easier to test \clear" actions before remove is written.
• The MyIterator elds, invariant checker and constructor.
Choose one of the two implementations suggested above, or (after checking with the instruc-
tor) choose your own data structure. If you're not sure of how to check things, leave comments
in the code.
Fall 2022 page 2 of 3
CompSci 351 / CompSt 751: Data Structures & Algorithms Homework #15
• MyIterator.hasNext() and MyIterator.next()
These methods are central to getting iterators to work.
Now you have enough to test building maps except for removing (or clearing) them.
• TreeMap.remove(Object) and MyIterator.remove()
(Make sure to use @Override so that Eclipse will tell you if the argument type is wrong.)
You should be able to pass all tests in TestTreeMap now. Don't continue until you can.
You should also pass the eciency tests now, because we gave you all the extra methods you
need for eciency.
• Last, check your implementation with random tests.
4 Files
In your repository, you will nd the following:
src/edu/uwm/cs351/util/TreeMap.java Skeleton le of TreeMap.
src/TestTreeMap.java Test cases identical to those from Homework #10, except without
locking.
src/TestInternals.java Test cases for the invariant checker.
src/TestEciency.java Eciency tests.
src/TestUtil.java Utility methods for the test suites.
src/edu/uwm/cs351/util/DefaultEntry.java A default implementation of Map.Entry, you
do not need to modify it.
Random testing is provided in the JAR le.