Assignment • FAQ • Development Guide • Code • Checklist

HW7 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. If at any point you are getting a compiler error for Tree.java because of missing return types, you may just add a return statement as placeholder so your code compiles. Make sure to change this later.
Write the methods debugOn() and debugOff(). They should both be simple, one line methods. Then write the Tree() constructor. The Tree constructor takes in it's name as a parameter, and has a variable field to store it's name. Be sure to initialize the values of the occupancy and root node pointer to 0 and null, respectively. The following tests are a small subset of the actual tests that you need to consider for your program to satisfy all the cases. Please use jdb for debugging your program and if you have forgotten some step then please refer to previous homeworks for refreshing your memory. You should have enough experience and confidence in using the debugging tools by now and so we skip the detailed output of them for sake of space as well as empowering you to use the tools and become proficient in them without following a step by step guides. Please remember that you could always type help in jdb and it will show you the list of commands that you could use and what those commands do.
Now test as follows:
Please remember to come up with other tests that could help you to unearth bugs in your programs. It is always a good practice to write test cases that you think your methods should pass before even finish writing the method.
% ./Driver -x
[Tree UCSDStudentTree - Allocating]

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.

Initial Symbol Table:
Tree UCSDStudentTree:
occupancy is 0 elements.
Please enter a command: ((a)llocate, , is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): a
Please enter name of new Tree to allocate: MyTree
[Tree MyTree - Allocating]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D
------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.

Final Symbol Table:
Tree MyTree:
occupancy is 0 elements.

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
Next, write the TNode constructor. All of the necessary variables for a TNode have been declared in the TNode class already, so just initialize them. The constructor takes a single parameter, which is the element to store in the data variable. All object fields should be initialized to null, and the balance/height variables should be set to 0. You may also want to think about how tree occupancy might change as more and more nodes(elements) are added to the tree.
Write the insert method and the TNode constructor. Follow your handouts and lecture notes. If you need some additional guidance: Your method is going to have three distinct parts. First, you'll have to handle inserting the first node if it hasn't been inserted yet. The remaining two parts will handle every other insertion. Ensure that you handle the insertion of duplicate elements as the user might try to insert the same values so this might be an edge case that you need to consider. First, search down the tree to find where the element you're going to insert belongs. You'll need to use the equals and isLessThan methods. Use a local variable to keep track of which TNode you're "on" and keep searching down the tree until you find the next empty spot where you can insert the new TNode. The last block of code will take care of reseting the height and balance data members of the TNodes that have been affected by the insertion.
Once you are done, test as follows:
% ./Driver -x
[Tree UCSDStudentTree - Allocating]

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.

Initial Symbol Table:
Tree UCSDStudentTree:
occupancy is 0 elements.
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Angie
Please enter UCSD student number: 111
[Tree UCSDStudentTree - Inserting Angie]

Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): w

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

The Symbol Table contains:
Tree UCSDStudentTree:
occupancy is 1 elements.
at height: 0 with balance: 0 name: Angie studentnum: 111
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Alvin
Please enter UCSD student number: 222
[Tree UCSDStudentTree - Comparing Alvin and Angie]
[Tree UCSDStudentTree - Inserting Alvin]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): w

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

The Symbol Table contains:
Tree UCSDStudentTree:
occupancy is 2 elements.
at height: 0 with balance: 0 name: Alvin studentnum: 222
at height: 1 with balance: 1 name: Angie studentnum: 111
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: James
Please enter UCSD student number: 333
[Tree UCSDStudentTree - Comparing James and Angie]
[Tree UCSDStudentTree - Inserting James]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): w

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

The Symbol Table contains:
Tree UCSDStudentTree:
occupancy is 3 elements.
at height: 0 with balance: 0 name: Alvin studentnum: 222
at height: 1 with balance: 0 name: Angie studentnum: 111
at height: 0 with balance: 0 name: James studentnum: 333
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Richard
Please enter UCSD student number: 5
[Tree UCSDStudentTree - Comparing Richard and Angie]
[Tree UCSDStudentTree - Comparing Richard and James]
[Tree UCSDStudentTree - Inserting Richard]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Phillip
Please enter UCSD student number: 9999
[Tree UCSDStudentTree - Comparing Phillip and Angie]
[Tree UCSDStudentTree - Comparing Phillip and James]
[Tree UCSDStudentTree - Comparing Phillip and Richard]
[Tree UCSDStudentTree - Inserting Phillip]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): w

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

The Symbol Table contains:
Tree UCSDStudentTree:
occupancy is 5 elements.
at height: 0 with balance: 0 name: Alvin studentnum: 222
at height: 3 with balance: -2 name: Angie studentnum: 111
at height: 2 with balance: -2 name: James studentnum: 333
at height: 0 with balance: 0 name: Phillip studentnum: 9999
at height: 1 with balance: 1 name: Richard studentnum: 5
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D
------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

Final Symbol Table:
Tree UCSDStudentTree:
occupancy is 5 elements.
at height: 0 with balance: 0 name: Alvin studentnum: 222
at height: 3 with balance: -2 name: Angie studentnum: 111
at height: 2 with balance: -2 name: James studentnum: 333
at height: 0 with balance: 0 name: Phillip studentnum: 9999
at height: 1 with balance: 1 name: Richard studentnum: 5

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
Write the jettison method and jettisonAllNodes of Tree and jettison of TNode. Your jettison of TNode should be very similar to everything that you have done before. The jettison of Tree shall jettison all the TNode that your Tree has, and then jettison the Tree itself. To help you jettison all the TNode, you should call the jettisonAllNodes method on the root. jettisonAllNodes should be a post-order traversal that you have learned in class. Repeat the above procedure, and at the end you should NOT see the last
------------ TRACKED MEMORY ------------
section after you press ^D.
Write the lookup method. Use a similar loop as in insert, but this time stop once you find the node you're looking for instead of looking for an empty spot. Make sure to check the "hasBeenDeleted" variable before you return the data! Test as follows:
% ./Driver -x
[Tree UCSDStudentTree - Allocating]

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.

Initial Symbol Table:
Tree UCSDStudentTree:
occupancy is 0 elements.
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Brandon
Please enter UCSD student number: 222
[Tree UCSDStudentTree - Inserting Brandon]

Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Zachary
Please enter UCSD student number: 333
[Tree UCSDStudentTree - Comparing Zachary and Brandon]
[Tree UCSDStudentTree - Inserting Zachary]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Matt
Please enter UCSD student number: 444
[Tree UCSDStudentTree - Comparing Matt and Brandon]
[Tree UCSDStudentTree - Comparing Matt and Zachary]
[Tree UCSDStudentTree - Inserting Matt]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): w

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

The Symbol Table contains:
Tree UCSDStudentTree:
occupancy is 3 elements.
at height: 2 with balance: -2 name: Brandon studentnum: 222
at height: 0 with balance: 0 name: Matt studentnum: 444
at height: 1 with balance: 1 name: Zachary studentnum: 333
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): l
Please enter UCSD student name to lookup: Matt
[Tree UCSDStudentTree - Comparing Matt and Brandon]
[Tree UCSDStudentTree - Comparing Matt and Zachary]
[Tree UCSDStudentTree - Comparing Matt and Matt]
Student found!
name: Matt studentnum: 444
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): l
Please enter UCSD student name to lookup: Adam
[Tree UCSDStudentTree - Comparing Adam and Brandon]
student Adam not there!
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): l
Please enter UCSD student name to lookup: Dylan
[Tree UCSDStudentTree - Comparing Dylan and Brandon]
[Tree UCSDStudentTree - Comparing Dylan and Zachary]
[Tree UCSDStudentTree - Comparing Dylan and Matt]
student Dylan not there!
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D
------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

Final Symbol Table:
Tree UCSDStudentTree:
occupancy is 2 elements.
at height: 2 with balance: -2 name: Brandon studentnum: 222
at height: 0 with balance: 0 name: Matt studentnum: 444
at height: 1 with balance: 1 name: Zachary studentnum: 333

No memory leaks! All memory has been correctly deallocated.
Write the method remove. Use a similar loop as in lookup, but once you find the matching node, change the hasBeenDeleted field of the node to "remove" it from the tree in addition to returning the data. Test as follows:
% ./Driver -x
[Tree UCSDStudentTree - Allocating]

------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.

Initial Symbol Table:
Tree UCSDStudentTree:
occupancy is 0 elements.
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): r
Please enter UCSD student name to remove: Angie
student Angie not there!
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: Angie
Please enter UCSD student number: 111
[Tree UCSDStudentTree - Inserting Angie]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): i
Please enter UCSD student name to insert: James
Please enter UCSD student number: 222
[Tree UCSDStudentTree - Comparing James and Angie]
[Tree UCSDStudentTree - Inserting James]
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): r
Please enter UCSD student name to remove: Angie
[Tree UCSDStudentTree - Comparing Angie and Angie]
Student removed!
name: Angie studentnum: 111
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): r
Please enter UCSD student name to remove: James
[Tree UCSDStudentTree - Comparing James and Angie]
[Tree UCSDStudentTree - Comparing James and James]
Student removed!
name: James studentnum: 222
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): r
Please enter UCSD student name to remove: Angie
[Tree UCSDStudentTree - Comparing Angie and Angie]
student Angie not there!
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): r
Please enter UCSD student name to remove: James
[Tree UCSDStudentTree - Comparing James and Angie]
[Tree UCSDStudentTree - Comparing James and James]
student James not there!
Please enter a command: ((a)llocate, is(e)mpty, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D
------------ TRACKED MEMORY ------------
40 bytes of heap memory, created in main calling Tree Ctor for the Tree object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.
24 bytes of heap memory, created in main calling UCSDStudent Ctor for the UCSDStudent object.
48 bytes of heap memory, created in Tree.insert calling TNode Ctor for the TNode object.

Final Symbol Table:
Tree UCSDStudentTree:
occupancy is 0 elements.

No memory leaks! All memory has been correctly deallocated.
At this point, you should test your assignment extensively by coming up with your own test cases.
Be sure to test that the output of your calculator makes sense and matches the solution.
% ./Calc [-x]

You also have access to some test cases that we provided to you. The files start with calc.
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 hw7 in your home directory.

Assignment • FAQ • Development Guide • Code • Checklist