Assignment •  Development Guide •  Code •  Checklist  

HW9 Development Guide

 

You should use this guide to help you to complete your assignment. 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 provided solution output files. Note that in these tests, if your Driver.datafile was corrupted, you should perform "make fresh" to start again. Likewise, you should use "make fresh" to begin a new test of your Driver with an empty datafile.
Control+D functionality will not work until break logic is added to the while loop in the main function of Driver.java.
Also, please note that we will not be testing the contents of your datafile when we are grading your assignment. Likewise, the UCSDStudent allocation number that gets printed with the -x option will vary based on your implementation, so this also does not have to match the provided output or the solution executable.

For this assignment, you will be writing a Tree and its TNodes to a binary file on the disk. To examine this file, you will use the octal dump UNIX command to view its contents. To help you understand the output from the octal dump, here's an octal dump diagram of a UCSDStudent stored in a TNode.

Note: the name field of UCSDStudent should be NO MORE THAN 14 characters so that the TNodes align. (To assist you, the UCSDStudent constructor left-justifies (for alphabetization) and pads with spaces to give a length of 14 characters):

/**********************************************
The outputfile will look like:
offset        ---------root---------   ------occupancy------
0000000 0000 0000 0000 1000 0000 0000 0000 0200
                 --------------------name---------------------
0000020 0e00 4141 4141 4141 4141 4141 4141 4141
                 --------number------- --------height--------
0000040 0001 0000 0000 5000 0000 0000 0000 0100
                 ---balance-- ------left child-------
0000060 ffff ffff ffff ffff 0000 0000 0000 0000
                 ------right child------ -----this_position------
0000100 0050 0000 0000 0000 0010 0000 0000 0000
-----------another TNode is below--------------
0000120 0e00 4242 4242 4242 4242 4242 4242 4242
0000140 0002 0000 0000 0000 0000 0000 0000 0000
0000160 0000 0000 0000 0000 0000 0000 0000 0000
0000200 0000 0000 0000 0000 0050 0000 0000 0000
***********************************************/

The left column contains an octal representation of locations into the file (essentially how many bytes from the beginning of the file). Generally, you should focus on the hexidecimal contents of the octal dump and not focus on the octal offsets. Remember that root, left, right, and position are values representing offsets into the binary datafile where the respective TNodes begin. Each is of type long and is 8 bytes in length. Try to think about why our name field is double the size of our other fields. How big is each TNode? (it is the sum of the sizes of each field of the TNode that is on the disk.)

  1. Change the code for UCSDStudent using the Variable class as a guide. You don't need to impelement the assign function. Write the Tree's constructor and write. In the Tree's constructor, the sampleNode should be initialzied by the empty constructor of TNode (which we have impelemented for you). Test as follows:

    % make fresh
    % ./Driver
    Initial Symbol Table:
    Tree 1:
    occupancy is 0 elements.
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D
    Final Symbol Table:
    Tree 1:
    occupancy is 0 elements.

    No cost information available.

    No memory leaks! All memory has been correctly jettisoned.
    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0000
    0000020

    Note that the numbers 0000 0000 0000 1000 and 0000 0000 0000 0000 from above are the values for the root occupancy data fields, respectively, once they are written out to disk. After each action in the Driver code, you should examine the octal dump in another window. If your data is incorrect, resolve the problem before moving onward. Remember, a fresh test case occurs when you run make fresh before testing again. This principle also applies throughout developing and testing hw9.

  2. Run the Driver directly entering ^D again and verify that your octal dump is unchanged. The first run of your Driver took the path through your constructor without a Tree existing, and the second run of your Driver took the path through the constructor with a Tree existing, yet the Tree is empty. Check that the output and the octal dump is the same. You should also run "ls -l Driver.datafile" to verify the size of your Driver.datafile is 16 bytes.


  3. Write the two TNode constructors (TNode's write constructor that calls TNode's write to add a TNode to the end of the binary disk file and TNode's read constructor that calls TNode's read to bring in a TNode from the disk into memory) and the write and read methods for TNode. Verify that your read and write methods for UCSDStudent are complete.
    You also need to call incrementCost in the write and read methods.

  4. Write the Tree's insert method. To start with the rest of the code, copy over the method bodies you wrote in hw8 into the empty method bodies of hw9. You may want to do this method by method as you implement, test, and verify each method in hw9 before moving on to the next method. Note: you can write code to insert the root TNode, compile, and test once the portion of Tree's insert is done that handles inserting into an empty Tree. When you are ready, you can complete the rest of your insert code for Tree and TNode. Also, be sure to call incrementOperation in Tree's insert (and Tree's lookup, and Tree's remove) methods since these are directly called from the user. Since your recursive calls to insert go down the Tree, you'll need to call searchTree and pass in the corresponding parameters. In insert, remove, lookup, replaceAndRemoveMin, and setHeightAndBalance, convert appropriate lines of hw8 code (the ones that go down the Tree) similarly as follows:

    PointerBox rootBox = new PointerBox (root);
    result = root.insert (element, rootBox);
    root = rootBox.pointer;

    Will become

    PositionBox rootBox = new PositionBox (root);
    result = sampleNode.searchTree (element, rootBox, "insert");
    root = rootBox.position;

    Test as follows:

    % ./Driver -x
    [Tree 1 - Allocating]
    Initial Symbol Table:
    Tree 1:
    occupancy is 0 elements.

    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: Tracker
    Please enter UCSD student number: 255
    [Tree 1 - Inserting Tracker]
    [Cost Increment (Disk Access): Writing Tracker]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D [Cost Increment (Disk Access): Reading Tracker]

    Final Symbol Table:
    Tree 1:
    occupancy is 1 elements.
    at height: 0 with balance: 0 UCSDStudent #3: name: Tracker studentnum: 255

    Cost of operations: 1 tree accesses
    Number of operations: 1
    Average cost: 1.0 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.

    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0100
    0000020 0e00 7254 6361 656b 2072 2020 2020 2020
    0000040 0000 0000 0000 ff00 0000 0000 0000 0000
    0000060 0000 0000 0000 0000 0000 0000 0000 0000
    0000100 0000 0000 0000 0000 0000 0000 0000 1000
    0000120

  5. Write TNode's insert method and setHeightAndBalance.

    Note: when handling the threshold in setHeightAndBalance, you will have to call remove directly (since you are not moving down the Tree) and call insert using searchTree (since you are moving down the Tree). Note: You'll need to test the threshold part of setHeightAndBalance after you've implemented TNode's remove. Test as follows:

    % ./Driver -x
    [Tree 1 - Allocating]
    [Cost Increment (Disk Access): Reading Tracker]
    Initial Symbol Table:
    Tree 1:
    occupancy is 1 elements.
    at height: :0 with balance: 0 UCSDStudent #2: name: Tracker studentnum: 255
    … Notice how we read in Tracker, this is because we didn't run make fresh. If you already ran make fresh, then simply insert Tracker with 255 and enter ^D then go back to the top of this step.
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: AAAAAAA
    Please enter UCSD student number: 32767
    Tree 1 - Inserting AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing AAAAAAA and Tracker]
    [Tree 1 - Inserting AAAAAAA]
    [Cost Increment (Disk Access): Writing AAAAAAA]
    [Tree 1 - Updating Tracker]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Writing Tracker]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: ZZZZZZZ
    Please enter UCSD student number: 65535
    [Tree 1 - Inserting ZZZZZZZ]
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing ZZZZZZZ and Tracker]
    [Tree 1 - Inserting ZZZZZZZ]
    [Cost Increment (Disk Access): Writing ZZZZZZZ]
    [Tree 1 - Updating Tracker]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Cost Increment (Disk Access): Writing Tracker]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D [Cost Increment (Disk Access): Reading Tracker]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]

    Final Symbol Table:
    Tree 1:
    occupancy is 3 elements.
    at height: 0 with balance: 0 UCSDStudent #11: name: AAAAAAA studentnum: 32767
    at height: 1 with balance: 0 UCSDStudent #10: name: Tracker studentnum: 255
    at height: 0 with balance: 0 UCSDStudent #12: name: ZZZZZZZ studentnum: 65535

    Cost of operations: 9 tree accesses
    Number of operations: 2
    Average cost: 4.5 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.
    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0300
    0000020 0e00 7254 6361 656b 2072 2020 2020 2020
    0000040 0000 0000 0000 ff00 0000 0000 0000 0100
    0000060 0000 0000 0000 0000 0000 0000 0000 5000
    0000100 0000 0000 0000 9000 0000 0000 0000 1000
    0000120 0e00 4141 4141 4141 2041 2020 2020 2020
    0000140 0000 0000 0000 ff7f 0000 0000 0000 0000
    0000160 0000 0000 0000 0000 0000 0000 0000 0000
    0000200 0000 0000 0000 0000 0000 0000 0000 5000
    0000220 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000240 0000 0000 0000 ffff 0000 0000 0000 0000
    0000260 0000 0000 0000 0000 0000 0000 0000 0000
    0000300 0000 0000 0000 0000 0000 0000 0000 9000
    0000320

  6. Write Tree's remove, TNode's remove, replaceAndRemoveMin, and resetRoot. As before, you should be able to copy these over from hw8 and make changes similarly as you made in the insert methods. Test remove as follows:

    % ./Driver -x
    [Tree 1 - Allocating]
    [Cost Increment (Disk Access): Reading Tracker]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    Initial Symbol Table:
    Tree 1:
    occupancy is 3 elements.
    at height: 0 with balance: 0 UCSDStudent #3: name: AAAAAAA studentnum: 32767
    at height: 1 with balance: 0 UCSDStudent #2: name: Tracker studentnum: 255
    at height: 0 with balance: 0 UCSDStudent #4: name: ZZZZZZZ studentnum: 65535

    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): r
    Please enter UCSD student name to remove: Tracker
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Tracker and Tracker]
    [Cost Increment (Disk Access): Reading ZZZZZZZ
    [Tree 1 - Checking ZZZZZZZ]
    [Tree 1 - Replacing ZZZZZZZ]
    [Tree 1 - Updating ZZZZZZZ]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Writing ZZZZZZZ
    Student removed!!!
    UCSDStudent #10: name: Tracker studentnum: 255
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading AAAAAAA]

    Final Symbol Table:
    Tree 1:
    occupancy is 2 elements.
    at height: 0 with balance: 0 UCSDStudent #12: name: AAAAAAA studentnum: 32767
    at height: 1 with balance: 1 UCSDStudent #11: name: ZZZZZZZ studentnum: 65535

    Cost of operations: 4 tree accesses
    Number of operations: 1
    Average cost: 4.0 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.
    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0200
    0000020 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000040 0000 0000 0000 ffff 0000 0000 0000 0100
    0000060 0000 0000 0000 0100 0000 0000 0000 5000
    0000100 0000 0000 0000 0000 0000 0000 0000 1000
    0000120 0e00 4141 4141 4141 2041 2020 2020 2020
    0000140 0000 0000 0000 ff7f 0000 0000 0000 0000
    0000160 0000 0000 0000 0000 0000 0000 0000 0000
    0000200 0000 0000 0000 0000 0000 0000 0000 5000
    0000220 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000240 0000 0000 0000 ffff 0000 0000 0000 0000
    0000260 0000 0000 0000 0000 0000 0000 0000 0000
    0000300 0000 0000 0000 0000 0000 0000 0000 9000
    0000320

    Notice how your octal dump now shows ZZZZZZZ where Tracker used to be. This is done via replaceAndRemoveMin when it replaces the data of the targetTNode with the data of its predecessor (in this case Tracker). Also notice that the previous position where ZZZZZZZ was still remains, yet its position isn't found in any left, right or root offset in other TNodes. Although that TNode is on the disk, it is not in the tree.

  7. Now test that reinsertion of a TNode behaves correctly:

    % ./Driver -x
    [Tree 1 - Allocating]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    Initial Symbol Table:
    Tree 1:
    occupancy is 2 elements.
    at height: :0 with balance: 0 name: AAAAAAA studentnum: 32767
    at height: :1 with balance: 1 name: ZZZZZZZ studentnum: 65535

    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: Tracker
    Please enter UCSD student number: 255
    [Tree 1 - Inserting Tracker]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Tree 1 - Comparing Tracker and ZZZZZZZ]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Tree 1 - Comparing Tracker and AAAAAAA]
    [Tree 1 - Inserting Tracker]
    [Cost Increment (Disk Access): Writing Tracker]
    [Tree 1 - Updating AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Cost Increment (Disk Access): Writing AAAAAAA]
    [Tree 1 - Updating ZZZZZZZ]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Writing ZZZZZZZ]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove (w)rite): ^D [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]

    Final Symbol Table:
    Tree 1:
    occupancy is 3 elements.
    at height: 1 with balance: -1 UCSDStudent #9: name: AAAAAAA studentnum: 32767
    at height: 0 with balance: 0 UCSDStudent #11: name: Tracker studentnum: 255
    at height: 2 with balance: 2 UCSDStudent #10: name: ZZZZZZZ studentnum: 65535

    Cost of operations: 7 tree accesses
    Number of operations: 1
    Average cost: 7 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.
    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0300
    0000020 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000040 0000 0000 0000 ffff 0000 0000 0000 0200
    0000060 0000 0000 0000 0200 0000 0000 0000 5000
    0000100 0000 0000 0000 0000 0000 0000 0000 1000
    0000120 0e00 4141 4141 4141 2041 2020 2020 2020
    0000140 0000 0000 0000 ff7f 0000 0000 0000 0100
    0000160 ffff ffff ffff ffff 0000 0000 0000 0000
    0000200 0000 0000 0000 d000 0000 0000 0000 5000
    0000220 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000240 0000 0000 0000 ffff 0000 0000 0000 0000
    0000260 0000 0000 0000 0000 0000 0000 0000 0000
    0000300 0000 0000 0000 0000 0000 0000 0000 9000
    0000320 0e00 7254 6361 656b 2072 2020 2020 2020
    0000340 0000 0000 0000 ff00 0000 0000 0000 0000
    0000360 0000 0000 0000 0000 0000 0000 0000 0000
    0000400 0000 0000 0000 0000 0000 0000 0000 d000
    0000420

    Notice that in our octal dump, Tracker is just written to the end of the file but is now AAAAAAA's right child. Whenever we insert a new TNode in our Tree, it should always be written to the end of the file. The way we have access to it is through updating the left and right fields of each node as we would have in HW8.

  8. Now check that your program behaves correctly when the root TNode is deleted:

    % ./Driver -x
    [Tree 1 - Allocating]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    Initial Symbol Table:
    Tree 1:
    occupancy is 3 elements.
    at height: 1 with balance: -1 UCSDStudent #2: name: AAAAAAA studentnum: 32767
    at height: 0 with balance: 0 UCSDStudent #4: name: Tracker studentnum: 255
    at height: 2 with balance: 2 UCSDStudent #3: name: ZZZZZZZ studentnum: 65535

    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove, (w)rite): r
    Please enter UCSD student name to remove: ZZZZZZZ
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Tree 1 - Comparing ZZZZZZZ and ZZZZZZZ]
    Student removed!!!
    UCSDStudent #7: name: ZZZZZZZ studentnum: 65535
    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove (w)rite): ^D [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]

    Final Symbol Table:
    Tree 1:
    occupancy is 2 elements.
    at height: 1 with balance: -1 UCSDStudent #9: name: AAAAAAA studentnum: 32767
    at height: 0 with balance: 0 UCSDStudent #8: name: Tracker studentnum: 255
    Cost of operations: 1 tree accesses
    Number of operations: 1
    Average cost: 1.0 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.
    % od -x Driver.datafile
    0000000 0000 0000 0000 5000 0000 0000 0000 0200
    0000020 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000040 0000 0000 0000 ffff 0000 0000 0000 0200
    0000060 0000 0000 0000 0200 0000 0000 0000 5000
    0000100 0000 0000 0000 0000 0000 0000 0000 1000
    0000120 0e00 4141 4141 4141 2041 2020 2020 2020
    0000140 0000 0000 0000 ff7f 0000 0000 0000 0100
    0000160 ffff ffff ffff ffff 0000 0000 0000 0000
    0000200 0000 0000 0000 d000 0000 0000 0000 5000
    0000220 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000240 0000 0000 0000 ffff 0000 0000 0000 0000
    0000260 0000 0000 0000 0000 0000 0000 0000 0000
    0000300 0000 0000 0000 0000 0000 0000 0000 9000
    0000320 0e00 7254 6361 656b 2072 2020 2020 2020
    0000340 0000 0000 0000 ff00 0000 0000 0000 0000
    0000360 0000 0000 0000 0000 0000 0000 0000 0000
    0000400 0000 0000 0000 0000 0000 0000 0000 d000
    0000420
    Notice that while the old nodes are on disk, they are not in the tree.

    You will see that in this case, we set the root offset to be AAAAAAA. This is almost like restructuring the Tree in HW8. Which output parameter helps with this?

    Please note this is different from the resetRoot case. resetRoot simply points the root offset to the end of the file so think about in which case you want to do this.

  9. Write Tree's lookup (and TNode's lookup if you implement it recursively). Test as follows:

    % ./Driver -x
    [Tree 1 - Allocating]
    Initial Symbol Table:
    Tree 1:
    occupancy is 2 elements.
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    at height: 1 with balance: -1 UCSDStudent #2: name: AAAAAAA studentnum: 32767
    at height: 0 with balance: 0 UCSDStudent #3: name: Tracker studentnum: 255

    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove (w)rite): l
    Please enter UCSD student name to lookup: AAAAAAA
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Tree 1 - Comparing AAAAAAA and AAAAAAA]
    Student found!!!

    UCSDStudent #6: name: AAAAAAA studentnum: 32767
    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: Brandon
    Please enter UCSD student number: 823
    [Tree 1 - Inserting Brandon]
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Tree 1 - Comparing Brandon and AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Brandon and Tracker]
    [Tree 1 - Inserting Brandon]
    [Cost Increment (Disk Access): Writing Brandon]
    [Tree 1 - Updating Tracker]
    [Cost Increment (Disk Access): Reading Brandon]
    [Cost Increment (Disk Access): Writing Tracker]
    [Tree 1 - Updating AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Cost Increment (Disk Access): Writing AAAAAAA]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove (w)rite): l
    Please enter UCSD student name to lookup: Brandon
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Tree 1 - Comparing Brandon and AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Brandon and Tracker]
    [Cost Increment (Disk Access): Reading Brandon]
    [Tree 1 - Comparing Brandon and Brandon]

    Student found!!!

    UCSDStudent #16: name: Brandon studentnum: 823
    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove, (w)rite): l
    Please enter UCSD student name to lookup: James
    [Cost Increment (Disk Access): Reading AAAAAAA]
    [Tree 1 - Comparing James and AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing James and Tracker]
    [Cost Increment (Disk Access): Reading Brandon]
    [Tree 1 - Comparing James and Brandon]
    student James not there!

    Please enter a command ((c)heck memory, (f)ile, (i)nsert), (l)ookup, (r)emove (w)rite): ^D [Cost Increment (Disk Access): Reading AAAAAAA]
    [Cost Increment (Disk Access): Reading Tracker]
    [Cost Increment (Disk Access): Reading Brandon]

    Final Symbol Table:
    Tree 1:
    occupancy is 3 elements.
    at height: 2 with balance: -2 UCSDStudent #21: name: AAAAAAA studentnum: 32767
    at height: 0 with balance: 0 UCSDStudent #23: name: Brandon studentnum: 823
    at height: 1 with balance: 1 UCSDStudent #22: name: Tracker studentnum: 255

    Cost of operations: 14 tree accesses
    Number of operations: 4
    Average cost: 3.5 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.

    % od -x Driver.datafile
    0000000 0000 0000 0000 5000 0000 0000 0000 0300
    0000020 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000040 0000 0000 0000 ffff 0000 0000 0000 0200
    0000060 0000 0000 0000 0200 0000 0000 0000 5000
    0000100 0000 0000 0000 0000 0000 0000 0000 1000
    0000120 0e00 4141 4141 4141 2041 2020 2020 2020
    0000140 0000 0000 0000 ff7f 0000 0000 0000 0200
    0000160 ffff ffff ffff feff 0000 0000 0000 0000
    0000200 0000 0000 0000 d000 0000 0000 0000 5000
    0000220 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000240 0000 0000 0000 ffff 0000 0000 0000 0000
    0000260 0000 0000 0000 0000 0000 0000 0000 0000
    0000300 0000 0000 0000 0000 0000 0000 0000 9000
    0000320 0e00 7254 6361 656b 2072 2020 2020 2020
    0000340 0000 0000 0000 ff00 0000 0000 0000 0100
    0000360 0000 0000 0000 0100 0000 0000 0000 1001
    0000400 0000 0000 0000 0000 0000 0000 0000 d000
    0000420 0e00 7242 6e61 6f64 206e 2020 2020 2020
    0000440 0000 0000 0000 3703 0000 0000 0000 0000
    0000460 0000 0000 0000 0000 0000 0000 0000 0000
    0000500 0000 0000 0000 0000 0000 0000 0000 1001
    0000520

  10. Update your Driver.java file to accept input from ASCII file. You should add an 'f' option to the switch statement. This option will allow the user to input commands from an ASCII file. For further instructions on how to do this, refer to the assignment page!
    Java documentation for FileReader
    Java documentation for FileWriter (keep in mind we created FlushingFileWriter from extending from FileWriter)

    Lets take a look:

    % cat morecommands
    l
    Tracker
    l
    Gary
    l
    Dylan
    l
    Navid
    l
    Matt

    % cat commands
    i
    Tracker 111
    i
    Gary 222
    i
    Brandon 333
    i
    James 444
    i
    Harvey 555
    f
    morecommands

    Note that the file commands use option f to read from morecommands. Before running commands, let's make sure that the simple case of a single input file works:

    % make fresh
    % ./Driver -x
    [Tree 1 - Allocating]
    Initial Symbol Table:
    Tree 1:
    occupancy is 0 elements.

    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: Tracker
    Please enter UCSD student number: 255
    [Tree 1 - Inserting Tracker]
    [Cost Increment (Disk Access): Writing Tracker]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): i
    Please enter UCSD student name to insert: ZZZZZZZ
    Please enter UCSD student number: 65535
    [Tree 1 - Inserting ZZZZZZZ]
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing ZZZZZZZ and Tracker]
    [Tree 1 - Inserting ZZZZZZZ]
    [Cost Increment (Disk Access): Writing ZZZZZZZ]
    [Tree 1 - Updating Tracker]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]
    [Cost Increment (Disk Access): Writing Tracker]
    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): f
    Please enter file name for commands: morecommands
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Tracker and Tracker]
    Student found!!!

    UCSDStudent #8: name: Tracker with studentnum: 255
    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Gary and Tracker]
    student Gary not there!

    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Dylan and Tracker]
    student Dylan not there!

    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Navid and Tracker]
    student Navid not there!

    [Cost Increment (Disk Access): Reading Tracker]
    [Tree 1 - Comparing Matt and Tracker]
    student Matt not there!

    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D [Cost Increment (Disk Access): Reading Tracker]
    [Cost Increment (Disk Access): Reading ZZZZZZZ]

    Final Symbol Table:
    Tree 1:
    occupancy is 2 elements.
    at height: :1 with balance: -1 UCSDStudent #17: name: Tracker studentnum: 255
    at height: :0 with balance: 0 UCSDStudent #18: name: ZZZZZZZ studentnum: 65535

    Cost of operations: 10 tree accesses
    Number of operations: 7
    Average cost:              1.42857 tree accesses/operation
    [Tree 1 - Jettisoning]

    No memory leaks! All memory has been correctly jettisoned.

    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0200
    0000020 0e00 7254 6361 656b 2072 2020 2020 2020
    0000040 0000 0000 0000 ff00 0000 0000 0000 0100
    0000060 ffff ffff ffff ffff 0000 0000 0000 0000
    0000100 0000 0000 0000 5000 0000 0000 0000 1000
    0000120 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000140 0000 0000 0000 ffff 0000 0000 0000 0000
    0000160 0000 0000 0000 0000 0000 0000 0000 0000
    0000200 0000 0000 0000 0000 0000 0000 0000 5000
    0000220

  11. Now let's try to use the commands file:

    % ./Driver
    Initial Symbol Table:
    Tree 1:
    occupancy is 2 elements.
    at height: 1 with balance: -1 name: Tracker studentnum: 255
    at height: 0 with balance: 0 name: ZZZZZZZ studentnum: 65535

    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): f
    Please enter file name for commands: commands
    Student found!!!

    name: Tracker studentnum: 111
    Student found!!!

    name: Gary studentnum: 222
    student Dylan not there!

    student Navid not there!

    student Matt not there!

    Please enter a command ((c)heck memory, (f)ile, (i)nsert, (l)ookup, (r)emove, (w)rite): ^D
    Final Symbol Table:
    Tree 1:
    occupancy is 6 elements.
    at height: 0 with balance: 0 name: Brandon studentnum: 333
    at height: 2 with balance: -1 name: Gary studentnum: 222
    at height: 0 with balance: 0 name: Harvey studentnum: 555
    at height: 1 with balance: 1 name: James studentnum: 444
    at height: 3 with balance: 2 name: Tracker studentnum: 111
    at height: 0 with balance: 0 name: ZZZZZZZ studentnum: 65535

    Cost of operations: 48 tree accesses
    Number of operations: 10
    Average cost: 4.8 tree accesses/operation

    No memory leaks! All memory has been correctly jettisoned.

    % od -x Driver.datafile
    0000000 0000 0000 0000 1000 0000 0000 0000 0600
    0000020 0e00 7254 6361 656b 2072 2020 2020 2020
    0000040 0000 0000 0000 6f00 0000 0000 0000 0300
    0000060 0000 0000 0000 0200 0000 0000 0000 9000
    0000100 0000 0000 0000 5000 0000 0000 0000 1000
    0000120 0e00 5a5a 5a5a 5a5a 205a 2020 2020 2020
    0000140 0000 0000 0000 ffff 0000 0000 0000 0000
    0000160 0000 0000 0000 0000 0000 0000 0000 0000
    0000200 0000 0000 0000 0000 0000 0000 0000 5000
    0000220 0e00 6147 7972 2020 2020 2020 2020 2020
    0000240 0000 0000 0000 de00 0000 0000 0000 0200
    0000260 ffff ffff ffff ffff 0000 0000 0000 d000
    0000300 0000 0000 0000 1001 0000 0000 0000 9000
    0000320 0e00 7242 6e61 6f64 206e 2020 2020 2020
    0000340 0000 0000 0000 4d01 0000 0000 0000 0000
    0000360 0000 0000 0000 0000 0000 0000 0000 0000
    0000400 0000 0000 0000 0000 0000 0000 0000 d000
    0000420 0e00 614a 656d 2073 2020 2020 2020 2020
    0000440 0000 0000 0000 bc01 0000 0000 0000 0100
    0000460 0000 0000 0000 0100 0000 0000 0000 5001
    0000500 0000 0000 0000 0000 0000 0000 0000 1001
    0000520 0e00 6148 7672 7965 2020 2020 2020 2020
    0000540 0000 0000 0000 2b02 0000 0000 0000 0000
    0000560 0000 0000 0000 0000 0000 0000 0000 0000
    0000600 0000 0000 0000 0000 0000 0000 0000 5001
    0000620

  12. 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.
  13. A good testcase to use is the alphabet and the reverse alphabet. And you can compare the result with driver_output_alphabet.txt

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

  14. Be sure to test that the output of your calculator makes sense and matches the solution.
  15. Make sure that you have fully commented your program and added function and file headers for any files and functions you edited. Make sure your style follows the Style Outline for CSE 12. Then turn in your program by following The Turnin Procedure.

    If you worked with a partner, only ONE of you should turn in the homework. You will be prompted to give the login of your partner.

 

  Assignment •  Development Guide •  Code •  Checklist