HW9 Code
public class SymTab<Whatever extends Base> extends Tree<Whatever> {
public SymTab (String datafile, Whatever sample, String caller) {
super (datafile, sample, caller);
}
}
import java.io.*;
public abstract class Base {
public Base copy () {
return null;
}
public String getName () {
return null;
}
public String getTrimName () {
return null;
}
public boolean isLessThan (Base base) {
return true;
}
public void jettison () {}
public void read (RandomAccessFile fio) {}
public void write (RandomAccessFile fio) {}
}
class Variable extends Base {
public String name; // name of variable
public long value; // value of interest
private Tracker tracker; // to track memory
public Variable () {
tracker = new Tracker ("Variable",
Size.of (name)
+ Size.of (value)
+ Size.of (tracker),
"Variable CTor");
}
public Variable (String nm, long val) {
tracker = new Tracker ("Variable " + nm,
nm.length ()
+ Size.of (val)
+ Size.of (tracker),
"Variable constructor");
// name = new String (nm);
name = String.format ("%1$-14s", nm);
value = val;
}
public Variable (Variable variable) {
tracker = new Tracker ("Variable " + variable.name,
variable.name.length ()
+ Size.of (variable.value)
+ Size.of (variable.tracker),
"Variable constructor");
// name = new String (variable.name);
name = String.format ("%1$-14s", variable.name);
value = variable.value;
}
public Base copy () {
return new Variable (name, value);
}
public void jettison () {
tracker.jettison ();
tracker = null;
}
public String getName () {
return name;
}
public String getTrimName () {
return name.trim ();
}
public boolean equals (Object other) {
if (this == other)
return true;
if (!(other instanceof Variable))
return false;
Variable otherVar = (Variable) other;
return name.equals (otherVar.getName ());
}
public boolean isLessThan (Base base) {
return (name.compareTo (base.getName ()) < 0) ? true : false;
}
public String toString () {
return name.trim () + "(" + value + ")";
}
public Variable assign (long val) {
Variable retval; // return value
// give variable its value
value = val;
retval = new Variable (this);
return retval;
}
// reading from the disk
public void read (RandomAccessFile fio) {
try {
name = fio.readUTF ();
value = fio.readLong ();
}
catch (IOException ioe) {
System.err.println ("IOException in Variable Read");
}
}
// Writing to the disk
public void write (RandomAccessFile fio) {
try {
fio.writeUTF (name);
fio.writeLong (value);
}
catch (IOException ioe) {
System.err.println ("IOException in Variable Write");
}
}
}
import java.io.*;
public class Tree {
private static final long BEGIN = 0;
// data fields
private RandomAccessFile fio; // to write to and read from disk
private long occupancy; // number of TNode's in the Tree
private long root; // position of the root of the Tree
private String representation; // String representation of Tree
private Base sample; // copy Base object in TNode's read CTor
private TNode sampleNode; // to call TNode searchTree
private Tracker tracker; // track Tree's memory
private long treeCount; // which Tree it is
private static long treeCounter;// how many Tree's are allocated
// debug flag
private static boolean debug;
// number of disk reads and writes
public static long cost = 0;
// number of insert, remove, locate operations
public static long operation = 0;
// debug messages
private static final String
TREE = "[Tree ",
ALLOCATE = " - Allocating]\n",
JETTISON = " - Jettisoning]\n",
COST_READ = "[Cost Increment (Disk Access): Reading ",
COST_WRITE = "[Cost Increment (Disk Access): Writing ",
AND = " and ",
COMPARE = " - Comparing ",
INSERT = " - Inserting ",
CHECK = " - Checking ",
UPDATE = " - Updating ",
REPLACE = " - Replacing ";
/*
* PositionBox class creates a PositionBox object to wrap a long type
* to be passed by reference in TNode methods.
*/
private class PositionBox {
public long position; // position value to be wrapped
/*
* Constructor for PositionBox object, wraps position parameter.
*
* @param position the value to be wrapped by PositionBox
*/
public PositionBox (long position) {
this.position = position;
}
}
public Tree (String datafile, Whatever sample, String caller) {
tracker = new Tracker ("Tree", Size.of (root)
+ Size.of (occupancy)
+ Size.of (representation)
+ Size.of (treeCount)
+ Size.of (tracker)
+ Size.of (fio)
+ Size.of (this.sample),
caller + " calling Tree CTor");
// DO NOT CHANGE TRACKER CODE ABOVE
// TODO: YOUR CODE GOES BELOW HERE
}
/**
* Disable debug messager
*/
public static void debugOff () {
debug = false;
}
/**
* Enable debug messages
*/
public static void debugOn () {
debug = true;
}
/**
* Debug accessor
*
* @return true if debug is one, false otherwise
*/
public static boolean getDebug () {
return debug;
}
/**
* Getter method for cost
*
* @return number of disk reads and writes of TNode
*/
public long getCost () {
return cost;
}
/**
* Getter method for operation
*
* @return number of insert, lookup, remove operations
*/
public long getOperation () {
return operation;
}
/**
* Count a TNode disk read or write
*/
public void incrementCost () {
cost++;
}
/**
* Count an insert, lookup, or remove
*/
public void incrementOperation () {
operation++;
}
public Whatever insert (Whatever element) {
// TODO: YOUR CODE GOES HERE
}
public boolean isEmpty () {
// TODO: YOUR CODE GOES HERE
}
/*
* jettison method for the Tree object. Untracks all memory associated
* with the Tree.
*/
public void jettison () {
// Debug messages
if (debug) {
System.err.print (TREE);
System.err.print (treeCount);
System.err.print (JETTISON);
}
write (); // write the final root and occupancy to disk
try {
fio.close (); // close the file accessor
} catch (IOException ioe) {
System.err.println ("IOException in Tree's jettison");
}
// Jettison TNodes and then tree itself
sampleNode.jettisonTNode ();
sampleNode = null;
tracker.jettison ();
tracker = null;
treeCounter--;
}
public void write () {
// TODO: YOUR CODE GOES HERE
}
public Whatever lookup (Whatever element) {
// TODO: YOUR CODE GOES HERE
}
public Whatever remove (Whatever element) {
// TODO: YOUR CODE GOES HERE
}
private void resetRoot () {
// TODO: YOUR CODE GOES HERE
}
/**
* Creates a string representation of this tree. This method first
* adds the general information of this tree, then calls the
* recursive TNode function to add all nodes to the return string
*
* @return String representation of this tree
*/
public String toString () {
representation = "Tree " + treeCount + ":\n"
+ "occupancy is " + occupancy + " elements.\n";
try {
fio.seek (fio.length ());
long end = fio.getFilePointer ();
long oldCost = getCost ();
if (root != end) {
TNode readRootNode = new TNode (root,
"Tree's toString");
readRootNode.writeAllTNodes ();
readRootNode.jettisonTNode ();
readRootNode = null;
}
cost = oldCost;
} catch (IOException ioe) {
System.err.println ("IOException in Tree's toString");
}
return representation;
}
private class TNode {
// positions of the TNode and its left and right children
private long left, right, position;
private Whatever data; // data to be stored in the TNode
private Tracker tracker;// to track memory of the tree
// left child's height - right child's height
private long balance;
// 1 + height of tallest child, or 0 for leaf
private long height;
// threshold to maintain in the Tree
private static final long THRESHOLD = 2;
/*
* TNode constructor to create an empty TNode
*
* @param caller method object was created in
*/
public TNode (String caller) {
tracker = new Tracker ("TNode", Size.of (data)
+ Size.of (left)
+ Size.of (right)
+ Size.of (position)
+ Size.of (height)
+ Size.of (balance)
+ Size.of (tracker),
caller + " calling TNode CTor");
}
public TNode (Whatever element, String caller) {
tracker = new Tracker ("TNode", Size.of (data)
+ Size.of (left)
+ Size.of (right)
+ Size.of (position)
+ Size.of (height)
+ Size.of (balance)
+ Size.of (tracker),
caller + " calling TNode CTor");
// DO NOT CHANGE TRACKER CODE ABOVE
// TODO: YOUR CODE GOES HERE
}
@SuppressWarnings ("unchecked")
public TNode (long position, String caller) {
tracker = new Tracker ("TNode", Size.of (data)
+ Size.of (left)
+ Size.of (right)
+ Size.of (position)
+ Size.of (height)
+ Size.of (balance)
+ Size.of (tracker),
caller + " calling TNode CTor");
// DO NOT CHANGE TRACKER CODE ABOVE
// TODO: YOUR CODE GOES HERE
}
public void read (long position) {
// TODO: YOUR CODE GOES HERE
}
public void write () {
// TODO: YOUR CODE GOES HERE
}
private Whatever insert (Whatever element,
PositionBox positionInParentBox) {
// TODO: YOUR CODE GOES HERE
}
/*
* Jettison method for TNode object, untracks memory associated
* with the calling TNode.
*/
private void jettisonTNode () {
left = right = 0; // reset left and right positions
// jettison the data stored
if (data != null) {
data.jettison ();
data = null;
}
// jettison tracker
tracker.jettison ();
tracker = null;
}
@SuppressWarnings ("unchecked")
private Whatever lookup (Whatever element) {
// TODO: YOUR CODE GOES HERE
}
@SuppressWarnings("unchecked")
private Whatever remove (Whatever element,
PositionBox positionInParentBox, boolean fromSHB) {
// TODO: YOUR CODE GOES HERE
}
@SuppressWarnings ("unchecked")
private Whatever replaceAndRemoveMin
(PositionBox positionInParentBox) {
// TODO: YOUR CODE GOES HERE
}
/*
* Reads in TNode from the disk at positionInParentBox.position
* so an action may be performed on that TNode. Centralizes the
* the operations needed when reading a TNode from the disk.
*
* @param element the data the action is to be performed on
* @param positionInParentBox the PositionBox holding the
* position of the TNode to be read from the disk
* @param action the action to be performed
* @return returns the result of the action
*/
private Whatever searchTree (Whatever element,
PositionBox positionInParentBox, String action) {
Whatever result = null;
TNode readNode = new TNode
(positionInParentBox.position, "searchTree " + action);
if (action.equals ("insert")) {
result = readNode.insert (element,
positionInParentBox);
}
else if (action.equals ("lookup"))
result = readNode.lookup (element);
else if (action.equals ("RARM")) {
result = readNode.replaceAndRemoveMin
(positionInParentBox);
}
else if (action.equals ("remove")) {
result = readNode.remove (element,
positionInParentBox, false);
}
readNode.jettisonTNode (); // rename to jettisonTNode
readNode = null;
return result;
}
/* The positionInParent parameter is used to pass to Remove
* and to Insert as the way to restructure the Tree if
* the balance goes beyond the threshold. You'll need to
* store the removed data in a working RTS TNode
* because the memory for the current TNode will be
* deallocated as a result of your call to Remove.
* Remember that this working TNode should not be
* part of the Tree, as it will automatically be dealloacted
* when the function ends. When calling Remove, remember to
* tell Remove that its being called from SetHeightAndBalance.
*
* @param positionInParentBox holds the position of the calling
* TNode on the disk
*/
@SuppressWarnings ("unchecked")
private void setHeightAndBalance
(PositionBox positionInParentBox) {
// TODO: YOUR CODE GOES HERE
}
/**
* Creates a string representation of this node. Information
* to be printed includes this node's height, its balance,
* and the data its storing.
*
* @return String representation of this node
*/
public String toString () {
return "at height: " + height + " with balance: "
+ balance + " " + data + "\n";
}
/**
* Writes all TNodes to the String representation field.
* This recursive method performs an in-order
* traversal of the entire tree to print all nodes in
* sorted order, as determined by the keys stored in each
* node. To print itself, the current node will append to
* tree's String field.
*/
private void writeAllTNodes () {
if (left != 0) {
TNode readLeftNode = new TNode (left,
"writeAllTNodes");
readLeftNode.writeAllTNodes ();
readLeftNode.jettisonTNode();
readLeftNode = null;
}
representation += this;
if (right != 0) {
TNode readRightNode = new TNode (right,
"writeAllTNodes");
readRightNode.writeAllTNodes ();
readRightNode.jettisonTNode();
readRightNode = null;
}
}
}
}
import java.io.*;
class UCSDStudent extends Base {
private String name;
private long studentNum;
private Tracker tracker;
private static long counter = 0;
private long count;
/*
* Default constructor for UCSDStudent object.
* Tracks the memory associated with the UCSDStudent object.
*/
public UCSDStudent () {
tracker = new Tracker ("UCSDStudent " + count + " " + name,
Size.of (name)
+ Size.of (studentNum)
+ Size.of (count)
+ Size.of (tracker),
"UCSDStudent Ctor");
count = ++counter;
name = String.format ("%1$-14s", "default");
}
/*
* Constructor for the UCSDStudent object given a name and student
* number. Tracks the memory associated with the UCSDStudent.
*
* @param nm the name of the UCSDStudent being created
* @param sn the student number of the UCSDStudent being created
*/
public UCSDStudent (String nm, long sn) {
tracker = new Tracker ("UCSDStudent " + count + " " + nm,
nm.length ()
+ Size.of (studentNum)
+ Size.of (count)
+ Size.of (tracker),
"UCSDStudent Ctor");
count = ++counter;
name = String.format ("%1$-14s", nm);
studentNum = sn;
}
// TODO: YOUR UCSDSTUDENT METHODS GO HERE
public String toString () {
if (Tree.getDebug ())
return "UCSDStudent #" + count + ": name: "
+ name.trim () + " studentnum: " + studentNum;
return "name: " + name.trim () + " studentnum: "
+ studentNum;
}
}
public class Driver {
private static final int
NULL = 0,
FILE = 0,
KEYBOARD = 1,
EOF = -1;
public static void main (String [] args) {
/* initialize debug states */
Tree.debugOff ();
/* check command line options */
for (int index = 0; index < args.length; ++index) {
if (args[index].equals ("-x"))
Tree.debugOn ();
}
UCSDStudent sample = new UCSDStudent ();
/* The real start of the code */
SymTab symtab =
new SymTab ("Driver.datafile",
sample, "Driver");
String buffer = null;
int command;
long number = 0;
UCSDStudent stu = null;
Writer os = new FlushingPrintWriter (System.out, true);
Reader is = new InputStreamReader (System.in);
int readingFrom = KEYBOARD;
System.out.println ("Initial Symbol Table:\n" + symtab);
// SUGGESTED TEST STUDENT NUMBERS FOR VIEWING IN OCTAL DUMPS
// 255, 32767, 65535, 8388607, 16777215
// FF 7FFF FFFF 7FFFFF FFFFFF
while (true) {
try {
command = NULL; // reset command each time in loop
os.write ("Please enter a command ((f)ile, (i)nsert, "
+ "(l)ookup, (r)emove, (c)heck memory, "
+ "(w)rite): ");
command = MyLib.getchar (is);
if (command == EOF) {
// TODO: YOUR CODE GOES HERE
}
if (command != EOF)
MyLib.clrbuf ((char) command, is);
switch (command) {
case 'f':
// TODO: YOUR CODE GOES HERE
// DON'T FORGET A BREAK STATEMENT
case 'c':
Tracker.checkMemoryLeaks ();
System.out.println();
break;
case 'i':
os.write
("Please enter UCSD student name to insert: ");
buffer = MyLib.getline (is);
os.write
("Please enter UCSD student number: ");
number = MyLib.decin (is);
MyLib.clrbuf ((char) command, is);
// create student and place in symtab
stu = new UCSDStudent (buffer, number);
symtab.insert (stu);
break;
case 'l':
UCSDStudent found;
os.write
("Please enter UCSD student name to "
+ "lookup: ");
buffer = MyLib.getline (is);
stu = new UCSDStudent (buffer, 0);
found = symtab.lookup (stu);
stu.jettison ();
stu = null;
if (found != null) {
System.out.println
("Student found!!!\n");
System.out.println (found);
found.jettison ();
found = null;
}
else
System.out.println
("student " + buffer
+ "not there!\n");
break;
case 'r':
// data to be removed
UCSDStudent removed;
os.write
("Please enter UCSD student name to remove: ");
buffer = MyLib.getline (is);
stu = new UCSDStudent (buffer, 0);
removed = symtab.remove (stu);
stu.jettison ();
stu = null;
if (removed != null) {
System.out.println ("Student "
+ "removed!!!");
System.out.println (removed);
removed.jettison ();
removed = null;
}
else
System.out.println
("student " + buffer + " not there!");
break;
case 'w':
System.out.print ("The Symbol Table " +
"contains:\n" + symtab);
break;
}
}
catch (IOException ioe) {
System.err.println ("IOException in Driver main");
}
}
System.out.print ("\nFinal Symbol Table:\n" + symtab);
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");
}
symtab.jettison ();
sample.jettison ();
Tracker.checkMemoryLeaks ();
}
}