HW8 Code
public class SymTab<Whatever extends Base> extends Tree<Whatever> {
public SymTab (String caller) {
super (caller);
}
}
public abstract class Base {
public Base copy () {
return null;
}
public String getName () {
return null;
}
public boolean isLessThan (Base base) {
return true;
}
public void jettison () {};
}
class Variable extends Base {
public String name; // name of variable
public long value; // value of interest
private Tracker tracker; // to track memory
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);
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);
value = variable.value;
}
public void jettison () {
tracker.jettison ();
tracker = null;
}
public Base copy () {
return new Variable (name, value);
}
public String getName () {
return name;
}
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 + "(" + value + ")";
}
public Variable assign (long val) {
Variable retval; // return value
// give variable its value
value = val;
retval = new Variable (this);
return retval;
}
}
import java.io.*;
class UCSDStudent extends Base {
private String name;
private long studentNum;
private Tracker tracker;
public UCSDStudent (String nm, long sn) {
// YOUR CODE GOES HERE
}
public void jettison () {
// YOUR CODE GOES HERE
}
public Base copy () {
// YOUR CODE GOES HERE
}
public String getName () {
// YOUR CODE GOES HERE
}
public boolean equals (Object object) {
// YOUR CODE GOES HERE
}
public boolean isLessThan (Base base) {
// YOUR CODE GOES HERE
}
public String toString () {
return "name: " + name + " with studentnum: " + studentNum;
}
}
public class Driver {
private static final short NULL = 0;
private static final int 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 ();
}
/* The real start of the code */
SymTab symtab =
new SymTab ("Driver");
String buffer = null;
int command;
long number = 0;
UCSDStudent stu = null;
System.out.println ("Initial Symbol Table:\n" + symtab);
while (true) {
command = NULL; // reset command each time in loop
System.out.print ("Please enter a command:\n "
+ "(c)heck memory, is(e)mpty, "
+ "(i)nsert, (l)ookup, "
+ "(r)emove, (w)rite: ");
command = MyLib.getchar ();
if (command == EOF)
break;
MyLib.clrbuf ((char) command); // get rid of return
switch (command) {
case 'c':
Tracker.checkMemoryLeaks ();
System.out.println ();
break;
case 'e':
if (symtab.isEmpty ())
System.out.println ("Tree is empty.");
else
System.out.println (
"Tree is not empty.");
break;
case 'i':
System.out.print
("Please enter UCSD student name to insert: ");
buffer = MyLib.getline ();// formatted input
System.out.print
("Please enter UCSD student number: ");
number = MyLib.decin ();
// get rid of return
MyLib.clrbuf ((char) command);
// create student and place in symbol table
stu = new UCSDStudent (buffer, number);
symtab.insert (stu);
stu = null;
break;
case 'l':
UCSDStudent found; // whether found or not
System.out.print
("Please enter UCSD student name to lookup: ");
buffer = MyLib.getline ();// formatted input
stu = new UCSDStudent (buffer, 0);
found = symtab.lookup (stu);
if (found != null) {
System.out.println ("Student found!!!");
System.out.println (found);
found.jettison ();
found = null;
}
else
System.out.println ("student " + buffer
+ " not there!");
stu.jettison ();
stu = null;
break;
case 'r':
UCSDStudent removed; // data to be removed
System.out.print
("Please enter UCSD student name to remove: ");
buffer = MyLib.getline ();
stu = new UCSDStudent (buffer, 0);
removed = symtab.remove (stu);
if (removed != null) {
System.out.println (
"Student removed!!!");
System.out.println (removed);
removed.jettison ();
removed = null;
}
else
System.out.println ("student "
+ buffer
+ " not there!");
stu.jettison ();
stu = null;
break;
case 'w':
System.out.print ("The Symbol Table " +
"contains:\n" + symtab);
}
}
System.out.print ("\nFinal Symbol Table:\n" + symtab);
symtab.jettison ();
Tracker.checkMemoryLeaks ();
}
}
public class Tree<Whatever extends Base> {
/* data fields */
private TNode root;
private long occupancy;
private String representation;
private long treeCount;
private Tracker tracker;
private static long treeCounter;
/* debug flag */
private static boolean debug;
/* debug messages */
private static final String ALLOCATE = " - Allocating]\n";
private static final String JETTISON = " - Jettisoning]\n";
private static final String AND = " and ";
private static final String CLOSE = "]\n";
private static final String COMPARE = " - Comparing ";
private static final String INSERT = " - Inserting ";
private static final String CHECK = " - Checking ";
private static final String UPDATE = " - Updating ";
private static final String REPLACE = " - Replacing ";
private static final String TREE = "[Tree ";
private class PointerBox {
public TNode pointer;
public PointerBox (TNode pointer) {
this.pointer = pointer;
}
}
public Tree (String caller) {
tracker = new Tracker ("Tree", Size.of (root)
+ Size.of (occupancy)
+ Size.of (representation)
+ Size.of (treeCount)
+ Size.of (treeCounter)
+ Size.of (tracker),
caller + " calling Tree CTor");
// DO NOT CHANGE THIS PART ABOVE
// YOUR CODE GOES HERE
}
public void jettison () {
// YOUR CODE GOES HERE
}
public static void debugOff () {
// YOUR CODE GOES HERE
}
public static void debugOn () {
// YOUR CODE GOES HERE
}
public boolean isEmpty () {
// YOUR CODE GOES HERE
}
public boolean insert (Whatever element) {
// YOUR CODE GOES HERE
}
public Whatever lookup (Whatever element) {
// YOUR CODE GOES HERE
}
public Whatever remove (Whatever element) {
// 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";
if (root != null)
root.writeAllTNodes();
return representation;
}
private class TNode {
private Whatever data;
private TNode left, right;
private Tracker tracker;
/* left child's height - right child's height */
private long balance;
/* 1 + height of tallest child, or 0 for leaf */
private long height;
private static final long THRESHOLD = 2;
public TNode (Whatever element, String caller) {
tracker = new Tracker ("TNode", Size.of (data)
+ Size.of (left)
+ Size.of (right)
+ Size.of (height)
+ Size.of (balance)
+ Size.of (tracker),
caller + " calling Tree CTor");
// DO NOT CHANGE THIS PART ABOVE
// YOUR CODE GOES HERE
}
private void jettisonTNodeOnly () {
// YOUR CODE GOES HERE
}
private void jettisonTNodeAndData () {
// YOUR CODE GOES HERE
}
private void jettisonAllTNodes () {
// YOUR CODE GOES HERE
}
private boolean insert (Whatever element,
PointerBox pointerInParentBox) {
// YOUR CODE GOES HERE
}
@SuppressWarnings("unchecked")
private Whatever lookup (Whatever element) {
// YOUR CODE GOES HERE
}
private Whatever remove (Whatever element,
PointerBox pointerInParentBox,
boolean fromSHB) {
// YOUR CODE GOES HERE
}
private void replaceAndRemoveMin (TNode targetTNode,
PointerBox pointerInParentBox) {
// YOUR CODE GOES HERE
}
// The PointerInParent 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 deallocated when the
// function ends. When calling Remove, remember to tell Remove
// that its being called from SetHeightAndBalance.
private void setHeightAndBalance
(PointerBox pointerInParentBox) {
}
/**
* 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 != null)
left.writeAllTNodes ();
representation += this;
if (right != null)
right.writeAllTNodes ();
}
}
}