| Assignment • Development Guide • Code • Checklist |
You must turn in your program by Friday, December 3rd, 2021 at 11:59pm.
In this assignment, you are to implement a binary tree data structure to use the "generics" feature of Java
Your Tree.java code will implement a binary tree similar to that in hw8, but you will implement the binary tree as a binary tree on disk. You are to rewrite Driver.java to allow for input commands to come from an ASCII file or via the keyboard by default.
You will need to complete the definition for the UCSDStudent class in your Driver.java.
The TNode methods to write in Tree.java:
public TNode (Whatever element, String caller)
public TNode (long position, String caller)
public void read (long position)
public void write ()
private Whatever insert (Whatever element, PositionBox positionInParentBox)
private Whatever lookup (Whatever element)
private Whatever remove (Whatever element, PositionBox positionInParentBox, boolean fromSHB)
private Whatever replaceAndRemoveMin (PositionBox positionInParentBox)
private Whatever setHeightAndBalance (PositionBox positionInParentBox)
The Tree methods to write in Tree.java:
public Tree (String datafile, Whatever sample, String caller)
public Whatever insert (Whatever element)
public boolean isEmpty ()
public Whatever lookup (Whatever element)
public Whatever remove (Whatever element)
public void write ()
public void resetRoot ()
Code to write in Driver.java:
Add appropriate public class methods for UCSDStudent similar to Variable class from Variable.java
Fill in code for the f case
- Add the statement import java.io.* at the beginning of your file if it is not in it.
- We have decleared a Reader of the type InputStreamReader and assign it to System.in for you.
- We have declare an Writer of the type FlushingPrintWriter and assign it to System.out for you.
- 'f' is the Driver command for file input.
The input following 'f' is the name of the file for command input.
- file input terminates (when your command == EOF) with either
a) end of command input file
b) command such as "f newfile" within command input file.
If condition "a)" occurs, you need to continue reading from System.in.
If condition "b)" occurs, you need to read instead from "newfile."
- to start reading from a file for input, you'll need to assign your Reader to new FileReader (buffer)
where "buffer" is a character array holding the name of the file. This works because FileReader is a derived class from Reader.
- to terminate input from the file, you'll need to reassign the Reader back to a new InputStreamReader reading from System.in (only if not reading from KEYBOARD)
- make analogous changes with the Writer so that when input comes from an ASCII file, output goes to "/dev/null."
HINT: Check if there is any more input with Reader.
Then check if input is coming from keyboard,
if so then stop reading in input, otherwise,
reset Reader and Writer.
if (symtab.getOperation () != 0){
System.out.print ("\nCost of operations: ");
System.out.print (symtab.getCost());
System.out.print (" tree accesses");
System.out.print ("\nNumber of operations: ");
System.out.print (symtab.getOperation());
System.out.print ("\nAverage cost: ");
System.out.print (((float) (symtab.getCost ())) / (symtab.getOperation ()));
System.out.print (" tree accesses/operation\n");
}
else{
System.out.print ("\nNo cost information available.\n");
}
How to update your Tree.java for BINARY file input and output:
- the fields root, left, and right are now of type "long" since they now represent positions within a binary file.
- the binary datafile can be opened via the Tree constructor initialization through...
fio = new RandomAccessFile (datafile, "rw");
where "datafile" is the const char pointer parameter that contains the name of the binary file.fio.close ();
- However, because methods in java.io.* throw excpetions, you would need to use try catch blocks to handle them.try {
fio.close ();
}
catch (IOException ioe) {
System.err.println ("IOException in Tree's jettison");
}
long position = fio.getFilePointer ();// position in file
fio.seek (BEGIN); // seek to a the beginning of the file
fio.seek (position); // seek to a position in the file
fio.seek (fio.length ()); // seek to the end of the file
fio.writeLong (root); // write a long in the file at the current file pointer position
data.write (fio);
data.read (fio);
write () // call the write function of TNode to write the current node to the disk
TNode readNode = new TNode (positionInParentBox.position, "searchTree " + action); // reads
For all methods in this assignment, make sure to include code to display the corresponding catastrophic error and debug messages.
Note: The non-constant reference parameters (noted in red in Function Descriptions) are potentially updated within the body of that method.
TNode read constructor:
Called when reading a TNode present on disk into memory. You would need to first create a copy using the sample belongs to the tree and assign it to be the data of the newlly created TNode.
TNode write constructor:
Called when creating a TNode for the first time:
TNode's insert: /* called from Tree's insert and TNode's searchTree*/
Inserts an element into the binary tree. Returns the data inserted.
TNode's read: /* called from TNode's read constructor, and a loop-based Lookup */
Reads a TNode which is present on the datafile into memory. The TNode is read from position. The TNode's information in the datafile overwrites this TNode's data. In order to read in the data field of the TNode, because the read constructor has generated a data of the correct type, you can call the read method of your data to read in the information of data from the disk file.
TNode's remove: /* called from Tree's Remove, SetHeightAndBalance, and searchTree */
Removes the matching data from the binary tree. Returns true or false indicating success of removal.
searchTree: /* called from Tree's remove, insert, lookup, setHeightAndBalance and replaceAndRemoveMin */
We have provided you this method.
Read in a TNode from the position that is pointed by the positionInParentBox, and call the appropriate functions on the newly read in node.
This method has already implemented for you, just figure out where to call it.
replaceAndRemoveMin: /* called from searchTree */
Called when removing a TNode with 2 children, replaces that TNode with the minimum TNode in it's right subtree to maintain the Tree structure.
setHeightAndBalance: /* called from TNode's Remove, TNode's Insert, and ReplaceAndRemoveMin */
Updates the height and balance of the current TNode.
TNode's write: /* called from TNode's write constructor, and functions which update the TNodes in datafile */
Writes this TNode object to disk at position in the datafile.
Tree Constructor:
Allocates the tree object. Checks the datafile to see if it contains Tree data. If it is empty, root and occupancy fields are written to the file. If there is data in the datafile, root and occupancy fields are read into memory. HINT: You will want to seek before writing or reading anything to / from disk.
Tree's write: /* called from Tree's jettison */
Write the field root and occupancy fields at the beginning of the diskfile.
isEmpty:
Return whether the Tree is empty.
Tree's jettison:
Jettisons memory associated with the Tree and write the tree back to the disk. Then you would need to close the fio, and jettsion the sampleNode.
Tree's insert:
Inserts an element into the binary tree. Inserts at the root TNode if Tree is empty, otherwise delegates to TNode's insert by calling the searchTree method on the sampleTNode. Returns the data inserted.
Tree's lookup:
Searches for an element in the Tree. This function may be recursive or loop-based. If you use a recursive algorithm, you should make a TNode Lookup method by calling searchTree method on the sampleTNode (as in the remove and insert functions).
Tree's remove:
Removes an element from the Tree. Delegates to TNode's Remove by calling searchTree when Tree is not empty. Returns the removed object, null if the removal failed.
resetRoot:
Resets the root datafield of this tree to be at the end of the datafile. This should be called when the last TNode has been removed from the Tree.
TNode's insert and TNode's remove should be implemented via recursion.
TNode's lookup can be either loop-based or recursive.
Enter the following commands into the terminal.
| Assignment • Development Guide • Code • Checklist |