C Sc 227 Project # 11: OrderedMap remove and RandomWriterWithOrderedMap

This project has two parts 1) remove as a WebCat turnin, and 2) random writer requires a file to be emailed to your section leader. This project is to be completed solo (no partner). Due date: 5:00pm Wednesday, 5-May

1) OrderedMap Remove

Add a remove method to OrderedMap<K, V>. First get OrderedMap.java into an Eclipse project. You may begin with this unit test OrderedMapTest.java that includes three test methods for remove, all of which fail until the remove method works for the first two cases: 1) an empty tree and 2) removing the root when the root has no left child. You will have to add many other test methods to ensure your remove method works in a variety of situations.

Use the remove algorithm below that was (or will be) demonstrated during lecture. As you are implementing this remove algorithm, remember to test, test, test! The unit test has only a few test methods for remove and you will need many more test methods. You will build up a test driver as you test for special cases to the most difficult, which is probably Case 4 when the node to be removed has a left child. You will receive credit for all cases that work, even if it you do not get all cases working.
publicV remove(Kkey) {

Traverse the BST until key is found. Use curr and prev to find the key leaving curr
referring the node you want to remove. It may be the case that curr is null indicating
that key was not found. There are four cases to consider:

Case 1: Not found
return null
Case 2: The root is to be removed, and it has no left child.
root = root's right subtree (assuming root refers the root node in your BST)
Case 3: The node is further down the tree with no left child. Adjust the parent's link
if curr is on the left side of prev,
move parent's left link down to curr's right child
else
curr is on the right side of prev, so move parent's right down to curr's right child
Case 4: curr has a left child.
We can no longer ignore the left subtree. So find the maximum key in the left subtree
and move that object to the node referenced by curr. Then eliminate the maximum
in the left subtree, which is now being reference from the originalnode to remove.
The key was found in Cases 2, 3, and 4--return the value mapped to the key just removed

Warmup: Starting with the given keys and structure of the given BSTs, draw the keys and structure of each BST after the node has been removed by the given message:

50
/ \
25 75
\ \
30 80
remove(25) / 10
/ \
5 20
remove(10) / 50
/ \
25 75
\ \
30 90
/ \
80 95
remove(75) / 50
/ \
25 90
/ \
70 99
/ \
60 85
remove(70) / 50
/ \
25 90
/ \
70 99
/ \
60 85
/
80
remove(90) / 50
/ \
25 90
/ \
70 99
/ \
60 85
remove(50)

Grading Criteria

___/ 50pts Turn in to WebCat as often as you wish for code and problem coverage score before 17:00 Wed., 5-May

2) Probabilistic Text Generation with OrderedMap<K, V>

You are to implement class RandomWriterWithOrderedMap.java that provides a random writing application sing a different collection to store the seeds and list of followers. Email your class RandomWriterWithOrderedMap.java to your section leader before 21:00 Wednesday, 5-May While testing your code, use any input file you want from Project Gutenberg. Add this file to your Java Eclipse project that has the required OrderedMap (listing was on section handout)

Generate probabilistictext using OrderedMapand java.util.ArrayList using the following algorithmthis wasdone in section with the section handout included for those who missed section.

  1. Read all file input into one big string already done in RandomWriterWithOrderedMap.java
  2. Create anOrderedMapthat has all possible seeds of the given length as the key and an ArrayList of followers as the value you do this as a method named setUpMap()
  3. Pick a random seed from the original text already done in RandomWriterWithOrderedMap.java
  4. For each character you need to print you do thisas a method named printRandom(int numberOfCharsToPrint)
  • Randomly select one of the characters in the list of followers
  • Print that random character
  • Change the seed so the first character is gone and the just printed random character is appended

Example text: "Alice likes icy olives"

Using "Alice likes icy olives", create a OrderedMap<K, V> of seed/list mappings where the seed is a string of length 2 and the value mapped to each key is a list of ALL characters that follow that seed in the original text.

Seed / list toString()
"Al" / [i]
"li" / [c, k] // 'v' to be added
"ic" / [e, y]
"ce" / [ ] This ArrayList has one element (that you cannot see): a space ' '
"e " / [l]
" l" / [i]
"li" / "li"is already a key, add follower 'k' to the list already mapped to the key "li"
"ik" / [e]
"ke" / [s]
"es" / [ ] This ArrayList has one element: a space ' '. Another ' ' should be added later
"s " / [i]
" i" / [c]
"ic" / "ic"is already a key, add follower 'k'to the list already mapped to the key "ic"
... / ... 8 more possible seeds to map