Www2.cs.arizona.edu



C Sc 227 Project # 11: OrderedMap remove and RandomWriterWithOrderedMap

This project has two parts, remove is a WebCat turnin, the random writer requires a file to be sent to your section leader

1) OrderedMap Remove

Add a remove method to OrderedMap. 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.

public boolean remove(K key) {

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 original node to remove. 

Key found so 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 | 10 | 50 | 50 | 50 | 50 |

|/ \ |/ \ |/ \ |/ \ |/ \ |/ \ |

|25 75 |5 20 |25 75 |25 90 |25 90 |25 90 |

|\ \ | |\ \ |/ \ |/ \ |/ \ |

|30 80 | |30 90 |70 99 |70 99 |70 99 |

| | |/ \ |/ \ |/ \ |/ \ |

| | |80 95 |60 85 |60 85 |60 85 |

| | | | |/ | |

|remove(25) |remove(10) |remove(75) |remove(90) |80 |remove(50) |

| | | | |remove(90) | |

| | | | | | |

| | | | | | |

| | | | | | |

| | | | | | |

| | | | | | |

| | | | | | |

| | | | | | |

| | | | | | |

| | | | | | |

Grading Criteria

___/ 50pts Turn in to WebCat as often as you wish for code and problem coverage score

2) Probabilistic Text Generation with OrderedMap

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 class RandomWriterWithOrderedMap.java to your section leader by 21:00 4-May While testing your code, use any input file you want from Project Gutenberg.  Generate Probabilistic text using java.util.OrderedMap and java.util.ArrayList with the following algorithm. 

1. Read all file input into one big string (already done in RandomWriterWithOrderedMap.java)

2. Create a OrderedMap object that has all possible seeds of the given length as the key and an ArrayList of followers as the value. (You do this)

3. Pick a random seed from the original text. (already done in RandomWriterWithOrderedMap.java)

4. For each character you need to print (You do this)

• 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 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 |

Warmup Section Activity: Probabilistic Text Generation with OrderedMap

Here is a class that uses our familiar OrderedMap class. It is intended to provide a start to the second part of the Project: RandomWriterWithOrderedMap. Method makeTheText reads all of the text from an input file into one big StringBuilder object. The StringBuilder class has the methods of the String class with a very efficient append method that we recommend you use. It also has code to get a random seed initially setRandomSeed. Feel free to use this code as a start

// The beginning of the probabalistic text generation

public class RandomWriterWithOrderedMap {

public static void main(String[] args) {

// Assume there is a file named alice with the text: "Alice likes icy olives"

RandomWriterWithOrderedMap rw = new RandomWriterWithOrderedMap("alice", 2);

rw.printRandom(100);

}

private OrderedMap all;

private int seedLength;

private String fileName;

private StringBuilder theText;

private static Random generator;

private String seed;

public RandomWriterWithOrderedMap(String fileName, int seedLength) {

this.fileName = fileName;

this.seedLength = seedLength;

generator = new Random();

makeTheText();

setRandomSeed();

setUpMap(); // Algorithm to be considered during section

}

private void makeTheText() {

Scanner inFile = null;

try {

inFile = new Scanner(new File(fileName));

}

catch (FileNotFoundException e) {

e.printStackTrace();

}

theText = new StringBuilder();

while (inFile.hasNextLine()) {

theText = theText.append(inFile.nextLine().trim());

theText = theText.append(' ');

}

}

public void setRandomSeed() {

generator = new Random();

int start = generator.nextInt(theText.length() - seedLength);

seed = theText.substring(start, start + seedLength);

}

}

Consider algorithms for these two methods that use the put and get methods of OrderedMap

private void setUpMap()

Example text: "Alice likes icy olives"

Using "Alice likes icy olives", an OrderedMap of seed/list mappings would look like the following when viewed "sideways". In this example, the seed has length 2 and the value mapped to each key is an ArrayList of ALL characters that follow the many seeds in the input file. Here is the tree printed sideways with a height of 5 and size of 17:

| // From OrderedMap | 'y ' ->[o] |

| |'ve' ->[s] |

|public String sideways() { |'s ' ->[i] |

|return sideways(root, 0); |'ol' ->[i] |

|} |'li' ->[c, k, v] |

| |'ke' ->[s] |

|private String sideways(MapNode t, int level) { |'iv' ->[e] |

|if (t == null) |'ik' ->[e] |

|return ""; |'ic' ->[e, y] |

|else { |'es' ->[ ] |

|String pad = ""; |'e ' ->[l] |

|for (int i = 0; i < level; i++) |'cy' ->[ ] |

|pad += " "; |'ce' ->[ ] |

| |'Al' ->[i] |

|return sideways(t.right, level + 1) |' o' ->[l] |

|+ pad + "'" + t.key + "' ->" + t.value + "\n" |' l' ->[i] |

|+ sideways(t.left, level + 1); |' i' ->[c] |

|} | |

|} | |

Sample output (does it look like a bit like the original text?):

cy olikes ice lice lives ice likes icy olice lice

lives icy olives ice lice lives icy olives icy oli

Altogether now

1) Build an OrderedMap from the root down of the following text when the seedLength is 3. Do not print sideways, but keep the keys/value mappings in order by key in a BST. The first two seeds and their first followers are given. Remember, the Map is built first and only once to store the list of all followers (take more memory, but runs much faster).

the true try the truths

"the" [ ' '

"he " [ 't'

void printRandom(int n)

2) Walk through generating 8 probabilistic characters of code with an initial seed of "e t"

This is somehow the text box from page 1, ignore it (but don't delete it)

-----------------------

[Type a quote from the document or the summary of an interesting point. You can position the text box anywhere in the document. Use the Text Box Tools tab to change the formatting of the pull quote text box.]

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download