Assignment • FAQ • Development Guide • Code • Checklist •

HW8 Development Guide

You should use this guide to help you to complete your assingment. You should follow it step by step, resolving errors before going on to the next step. Once you can follow this guide without errors, you should come up with more test cases and compare the output of your program with that of the solution.

Fill in the YOUR CODE GOES HERE blocks in Driver.java. Look at the Variable class in Calculator.java in the code page to see how the UCSDStudent methods should be written. Essentially, you will need to write methods similar to those of the Variable class in Calculator.java. There should be an equivalent method for every method in the Variable class, except the copy constructor and the method called assignValue(). Please be aware that you might need to update some aspects of these methods and copying them exactly may not work as expected. Try to understand what each method does and then make the changes to fit the requirement the Tree implementation may have.
Write the debugOn, debugOff, isEmpty, Tree's constructor, TNode's constructor, jettisonTNodeOnly, and jettisonTNodeAndData methods. Then, write Tree's insert for the root node. Test as follows:
% ./Driver -x
[Tree 1 - Allocating]
Initial Symbol Table:
Tree 1:
occupancy is 0 elements.

Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: a
Please enter UCSD student number: 1
[Tree 1 - Inserting a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite:^D
Final Symbol Table:
Tree 1:
occupancy is 1 elements.
at height: 0 with balance: 0 name: a with studentnum: 1

...... Where memory leaks are expected ......

Note: The heights and balances in the output above reports 0 because the setHeightAndBalance method has yet to be written. If you've already implemented setHeightAndBalance, your heights and balances may be different from that listed below. Also, you might have memory leaks at this point. That is okay! They will disappear when we write jettisonAllTNodes later.
Tree's insert handles the root node on its own but delegates the rest to TNode's insert. Have Tree's insert delegate to TNode's insert. Write TNode's insert. Test as follows:
% ./Driver -x
[Tree 1 - Allocating]
Initial Symbol Table:
Tree 1:
occupancy is 0 elements.

Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: aaa
Please enter UCSD student number: 1
[Tree 1 - Inserting aaa]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: bbb
Please enter UCSD student number: 2
[Tree 1 - Comparing bbb and aaa]
[Tree 1 - Inserting bbb]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: ccc
Please enter UCSD student number: 3
[Tree 1 - Comparing ccc and aaa]
[Tree 1 - Comparing ccc and bbb]
[Tree 1 - Inserting ccc]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: ^D
Final Symbol Table:
Tree 1:
occupancy is 3 elements.
at height: 0 with balance: 0 name: aaa with studentnum: 1
at height: 0 with balance: 0 name: bbb with studentnum: 2
at height: 0 with balance: 0 name: ccc with studentnum: 3

...... Where memory leaks are expected ......
Write Tree's remove and TNode's remove. Remember that this time we're not doing a "lazy remove"! It'd be important to reattach the TNode's descendants first (this can be done through pointerInParentBox, and then delete the TNode to be removed. Also, when calling TNode's remove inside of Tree's remove, it would be helpful to save the return value into a local variable.
If you don't know how to get started, maybe you can refer to the faqs page and getting started notes to get a better handle of the method overall.
Don't worry about removing TNodes with 2 children at the moment; we will get to it very soon. Test as follows:
% ./Driver -x
[Tree 1 - Allocating]
Initial Symbol Table:
Tree 1:
occupancy is 0 elements.

Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: aaa
Please enter UCSD student number: 1
[Tree 1 - Inserting aaa]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: bbb
Please enter UCSD student number: 2
[Tree 1 - Comparing bbb and aaa]
[Tree 1 - Inserting bbb]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: ccc
Please enter UCSD student number: 3
[Tree 1 - Comparing ccc and aaa]
[Tree 1 - Comparing ccc and bbb]
[Tree 1 - Inserting ccc]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: r
Please enter UCSD student name to remove: bbb
[Tree 1 - Comparing bbb and aaa]
[Tree 1 - Comparing bbb and bbb]
Student removed!!!
name: bbb with studentnum: 2
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: ^D
Final Symbol Table:
Tree 1:
occupancy is 2 elements.
at height: 0 with balance: 0 name: aaa with studentnum: 1
at height: 0 with balance: 0 name: ccc with studentnum: 3

......
Write the method setHeightAndBalance, which should be called from TNode's insert, TNode's remove, and from RARM. Please be sure to implement the threshold check to remove and reinsert any elements whose TNodes have balances beyond the threshold. (HINT: a good way to check if the tree is becoming out of balance is to compare the current TNode's balance against THRESHOLD. Check to make sure the absolute value of the balance of current TNode is less than or equals to the THRESHOLD. And this is where you would want to think about how values for fromSHB should be passed into remove and how remove should handle it.) Test as follows:
% ./Driver -x
[Tree 1 - Allocating]
Initial Symbol Table:
Tree 1:
occupancy is 0 elements.
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: a
Please enter UCSD student number: 1
[Tree 1 - Inserting a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: b
Please enter UCSD student number: 2
[Tree 1 - Comparing b and a]
[Tree 1 - Inserting b]
[Tree 1 - Updating a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: c
Please enter UCSD student number: 3
[Tree 1 - Comparing c and a]
[Tree 1 - Comparing c and b]
[Tree 1 - Inserting c]
[Tree 1 - Updating b]
[Tree 1 - Updating a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: d
Please enter UCSD student number: 4
[Tree 1 - Comparing d and a]
[Tree 1 - Comparing d and b]
[Tree 1 - Comparing d and c]
[Tree 1 - Inserting d]
[Tree 1 - Updating c]
[Tree 1 - Updating b]
[Tree 1 - Updating a]
[Tree 1 - Comparing a and a]
[Tree 1 - Comparing a and b]
[Tree 1 - Inserting a]
[Tree 1 - Updating b]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: ^D
Final Symbol Table:
Tree 1:
occupancy is 4 elements.
at height: 0 with balance: 0 name: a with studentnum: 1
at height: 2 with balance: -1 name: b with studentnum: 2
at height: 1 with balance: -1 name: c with studentnum: 3
at height: 0 with balance: 0 name: d with studentnum: 4

......
Write the replaceAndRemoveMin method, it is only a few lines of code. Remember that you will want to go right once, and then go all the way left. But note how you call replaceAndRemoveMin inside of remove. It should be called when removing TNodes with 2 children. Test as follows:
% ./Driver -x
[Tree 1 - Allocating]
Initial Symbol Table:
Tree 1:
occupancy is 0 elements.

Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: a
Please enter UCSD student number: 1
[Tree 1 - Inserting a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: b
Please enter UCSD student number: 2
[Tree 1 - Comparing b and a]
[Tree 1 - Inserting b]
[Tree 1 - Updating a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: c
Please enter UCSD student number: 3
[Tree 1 - Comparing c and a]
[Tree 1 - Comparing c and b]
[Tree 1 - Inserting c]
[Tree 1 - Updating b]
[Tree 1 - Updating a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: d
Please enter UCSD student number: 4
[Tree 1 - Comparing d and a]
[Tree 1 - Comparing d and b]
[Tree 1 - Comparing d and c]
[Tree 1 - Inserting d]
[Tree 1 - Updating c]
[Tree 1 - Updating b]
[Tree 1 - Updating a]
[Tree 1 - Comparing a and a]
[Tree 1 - Comparing a and b]
[Tree 1 - Inserting a]
[Tree 1 - Updating b]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: e
Please enter UCSD student number: 5
[Tree 1 - Comparing e and b]
[Tree 1 - Comparing e and c]
[Tree 1 - Comparing e and d]
[Tree 1 - Inserting e]
[Tree 1 - Updating d]
[Tree 1 - Updating c]
[Tree 1 - Updating b]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: f
Please enter UCSD student number: 6
[Tree 1 - Comparing f and b]
[Tree 1 - Comparing f and c]
[Tree 1 - Comparing f and d]
[Tree 1 - Comparing f and e]
[Tree 1 - Inserting f]
[Tree 1 - Updating e]
[Tree 1 - Updating d]
[Tree 1 - Updating c]
[Tree 1 - Comparing c and c]
[Tree 1 - Comparing c and d]
[Tree 1 - Inserting c]
[Tree 1 - Updating d]
[Tree 1 - Updating b]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: g
Please enter UCSD student number: 7
[Tree 1 - Comparing g and b]
[Tree 1 - Comparing g and d]
[Tree 1 - Comparing g and e]
[Tree 1 - Comparing g and f]
[Tree 1 - Inserting g]
[Tree 1 - Updating f]
[Tree 1 - Updating e]
[Tree 1 - Updating d]
[Tree 1 - Updating b]
[Tree 1 - Comparing b and b]
[Tree 1 - Checking d]
[Tree 1 - Checking c]
[Tree 1 - Replacing c]
[Tree 1 - Updating d]
[Tree 1 - Comparing d and d]
[Tree 1 - Comparing d and e]
[Tree 1 - Inserting d]
[Tree 1 - Updating e]
[Tree 1 - Comparing b and c]
[Tree 1 - Comparing b and a]
[Tree 1 - Inserting b]
[Tree 1 - Updating a]
[Tree 1 - Updating c]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite:
Final Symbol Table:
Tree 1:
occupancy is 7 elements.
at height: 1 with balance: -1 name: a with studentnum: 1
at height: 0 with balance: 0 name: b with studentnum: 2
at height: 3 with balance: -1 name: c with studentnum: 3
at height: 0 with balance: 0 name: d with studentnum: 4
at height: 2 with balance: -1 name: e with studentnum: 5
at height: 1 with balance: -1 name: f with studentnum: 6
at height: 0 with balance: 0 name: g with studentnum: 7

......
Write Tree's lookup and TNode's lookup. Test as follows:
% ./Driver -x
[Tree 1 - Allocating]
Initial Symbol Table:
Tree 1:
occupancy is 0 elements.

Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: a
Please enter UCSD student number: 1
[Tree 1 - Inserting a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: b
Please enter UCSD student number: 2
[Tree 1 - Comparing b and a]
[Tree 1 - Inserting b]
[Tree 1 - Updating a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: i
Please enter UCSD student name to insert: c
Please enter UCSD student number: 3
[Tree 1 - Comparing c and a]
[Tree 1 - Comparing c and b]
[Tree 1 - Inserting c]
[Tree 1 - Updating b]
[Tree 1 - Updating a]
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: l
Please enter UCSD student name to lookup: b
[Tree 1 - Comparing b and a]
[Tree 1 - Comparing b and b]
Student found!!!
name: b with studentnum: 2
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite: l
Please enter UCSD student name to lookup: d
[Tree 1 - Comparing d and a]
[Tree 1 - Comparing d and b]
[Tree 1 - Comparing d and c]
student d not there!
Please enter a command:
(c)heck memory, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite:
Final Symbol Table:
Tree 1:
occupancy is 3 elements.
at height: 2 with balance: -2 name: a with studentnum: 1
at height: 1 with balance: -1 name: b with studentnum: 2
at height: 0 with balance: 0 name: c with studentnum: 3

.......
Write Tree's jettison and TNode's jettisonAllTNodes methods. Test with Driver. Make sure that there no memory leaks after ^D.
At this point, you should test your assignment extensively by coming up with your own test cases. To verify that your program behaves correctly, check the output against the solution's output.
A good testcase to use is the alphabet and the reverse alphabet. This file is located in the public/hw8/java directory.

% ./Driver [-x] < alphabet
% ./Driver [-x] < alphabet.rev

To better test your code, you might want to store the output of your code and the solution code in different files, and then use the diff command to compare the output.

% ./Driver [-x] < alphabet > my_sol.txt 2>&1
% ~/../public/hw8/java/Driver [-x] < alphabet > driver_output.txt 2>&1
% diff my_sol.txt driver_output.txt

The commands above will redirect both your standard input and output to a solution to a file, and then compare your output with our driver's output. If there are inconsistencies, make sure to compare the output to see if you need to debug your code.

Be sure to test that the output of your calculator makes sense.

% ./Calc [-x]

Make sure that you have fully commented your program and added method and file headers for any files and methods you edited. Make sure your style follows the Style Outline for CSE 12. Then turn in your program by following The Turnin Procedure.
Note that, in order for your homework to be collected correctly, you must name your files Tree.java and Driver.java and the files must be located in a folder called hw8/java in your home directory.

Assignment • FAQ • Development Guide • Code • Checklist •