/* maintain a database of taxpayers and the tax for each
* @author Biagioni, Edoardo
* @assignment lecture 18
* @date March 14, 2008
* @bugs no error message if you remove a record not in the database
* @inspiration William Albritton's Menu.java,
* http://www2.hawaii.edu/~walbritt/ics211/treeBinarySearch/Menu.java
* @inspiration ShoppingMenu.java
* http://www2.ics.hawaii.edu/~esb/2008spring.ics211/ShoppingMenu.java.html
*/
import javax.swing.*;
import java.util.NoSuchElementException;
import java.util.Scanner;
import java.util.Iterator;
import java.util.regex.*;
import java.io.File;
import java.io.FileWriter;
import java.util.Stack;
public class ChengJade8 {
final static String databaseName = "database.csv";
/* do nothing, data fields are already initialized */
public ChengJade8() {
}
/* main method is invoked when the program is started
* @param arguments if a single command-line argument is given, it is
* the name of the file containing the database
*/
public static void main(String [] arguments) {
String thisDatabaseName = databaseName;
if (arguments.length == 1) {
thisDatabaseName = arguments[0];
}
BinarySearchTree<Taxpayer> database = null;
database = readFromDatabase(thisDatabaseName);
while (executeMenu(database)) {
// after every non-exit command, save to the database
saveToDatabase(database, thisDatabaseName);
}
System.exit(0);
}
/* @param database reference to a database of taxpayers
* @return whether to continue execution
*/
private static boolean executeMenu(BinarySearchTree<Taxpayer> db) {
String[] choices = { "add a new taxpayer record",
"change tax for a taxpayer",
"remove a taxpayer record",
"display the database", "find the previous record",
"find the next record", "exit program" };
// ask the user to tell us what they want to do
int choice =
JOptionPane.showOptionDialog(null, "please enter", "taxpayers",
JOptionPane.DEFAULT_OPTION,
JOptionPane.QUESTION_MESSAGE,
null, choices, -1);
switch(choice) {
case 0:
addNewRecord(db);
break;
case 1:
changeTax(db);
break;
case 2:
removeRecord(db);
break;
case 3:
System.out.println(db.toString());
break;
//----------------------------------------------------------------------------//
case 4:
System.out.println(findPreviousRecord(db));
break;
case 5:
System.out.println(findNextRecord(db));
break;
//----------------------------------------------------------------------------//
// case 6: handled below
}
// whatever we did is done, save the database and return
return (choice != (choices.length - 1));
}
/* read a database from a file
* @return database read from a file, or throws exception
*/
private static BinarySearchTree<Taxpayer> readFromDatabase(String file) {
BinarySearchTree<Taxpayer> db = new BinarySearchTree<Taxpayer>();
int readSuccessfully = 0;
try {
// database is assumed to be a sequence of lines, one item per line
File dbFile = new File(file);
Scanner dbRead = new Scanner(dbFile);
while (dbRead.hasNextLine()) {
String line = dbRead.nextLine();
Scanner lineScan = new Scanner(line);
// the record is comma-separated
lineScan.useDelimiter(",");
// each line should have the taxpayer name, followed
// by the SSN, followed by the tax, all separated by commas
// e.g. "Foo Bar,123456789,-3124.37
String taxpayer = lineScan.next();
// read the social security number
int SSN = lineScan.nextInt();
// read the tax
double tax = lineScan.nextDouble();
db.add(new Taxpayer(taxpayer, SSN, tax));
readSuccessfully++;
}
} catch (Exception e) {
if (readSuccessfully > 0) {
System.out.println("error " + e +
" reading database after reading " +
readSuccessfully + " entries");
} else {
System.out.println("error " + e + " reading database " +
file + "\nstarting with empty database");
}
}
return db;
}
/* @param database to save to the file
*/
private static void saveToDatabase(BinarySearchTree<Taxpayer> db,
String name) {
try {
// preorder traversal, so the same tree is built again
// when we read it back
Iterator<Taxpayer> it = db.preIterator();
FileWriter out = new FileWriter(name);
while (it.hasNext()) {
Taxpayer record = it.next();
out.write(record.getName() + "," + record.getSSN() + "," +
record.getTax() + "\n");
}
out.close();
} catch (Exception e) {
/* this is an error. Notify the user */
String message = "unable to save to file " + name;
JOptionPane.showMessageDialog(null, message);
}
}
/* get a taxpayer record from the user, save it in the database
* @param db to which the item is added
*/
private static void addNewRecord(BinarySearchTree<Taxpayer> db) {
final String prompt1 = "enter taxpayer name";
String name = JOptionPane.showInputDialog(null, prompt1);
if (name != null) { // null name if canceled
final String prompt2 = "enter SSN for taxpayer " + name;
Integer SSN = getUserInteger(prompt2);
if (SSN != null) { // null string means not a valid number
final String prompt3 = "enter amount of tax for " + name;
Double tax = getUserDouble(prompt3);
db.add(new Taxpayer(name, SSN, tax));
}
}
}
/* change the tax for a taxpayer in the database
* @param db in which the taxpayer record is changed
*/
private static void changeTax(BinarySearchTree<Taxpayer> db) {
final String prompt1 = "enter SSN of taxpayer";
Integer SSN = getUserInteger(prompt1);
if (SSN != null) { // null string means not a valid number
// build a key, that is, a taxpayer where only the SSN is valid
Taxpayer key = new Taxpayer(SSN);
Taxpayer record = db.get(key);
if (record == null) { // not in database, cannot change tax
JOptionPane.showMessageDialog(null,
"social security number " + SSN +
" not found in database");
} else { // is in database, get the new tax amount
final String prompt2 = "enter amount of tax for " +
record.getName();
Double tax = getUserDouble(prompt2);
record.setTax(tax);
// this addition should replace the original record
db.add(record);
}
}
}
/* remove a taxpayer from the database given the social security number
* @param db from which the taxpayer record is removed
*/
private static void removeRecord(BinarySearchTree<Taxpayer> db) {
final String prompt = "enter SSN of taxpayer to remove from database";
Integer SSN = getUserInteger(prompt);
if (SSN != null) { // null string means not a valid number
// build a key, that is, a taxpayer where only the SSN is valid
Taxpayer key = new Taxpayer(SSN);
db.remove(key);
}
}
//----------------------------------------------------------------------------//
/**
* finds a previous record in a taxpayer database based on user input
*
* @param db the taxpayer database
* @return a message containing the previous record if one exists
*/
private static String findPreviousRecord(BinarySearchTree<Taxpayer> db) {
final String prompt1 = "enter SSN of taxpayer";
final Integer SSN = getUserInteger(prompt1);
if (SSN == null) // null SSN if canceled
return "operation canceled";
final Taxpayer key = new Taxpayer(SSN.intValue());
try {
final Taxpayer entry = db.findPrevious(key);
if (entry == null) // null entry means no matching key
return "no matching record for SSN " + SSN;
return "previous record for SSN " + SSN + ": --> " + entry;
} catch (NoSuchElementException e) {
// error indicates key is found but no previous record
return "no previous record for SSN " + SSN;
}
}
/**
* finds a next record in a taxpayer database based on user input
*
* @param db the taxpayer database
* @return a message containing the next record if one exists
*/
private static String findNextRecord(BinarySearchTree<Taxpayer> db) {
final String prompt1 = "enter SSN of taxpayer";
final Integer SSN = getUserInteger(prompt1);
if (SSN == null) // null SSN if canceled
return "operation canceled";
final Taxpayer key = new Taxpayer(SSN.intValue());
try {
final Taxpayer entry = db.findNext(key);
if (entry == null) // null entry means no matching key
return "no matching record for SSN " + SSN;
return "next record for SSN " + SSN + ": --> " + entry;
} catch (NoSuchElementException e) {
// error indicates key is found but no next record
return "no next record for SSN " + SSN;
}
}
// ----------------------------------------------------------------------------//
/* @param prompt for the user
* @return null, or the integer the user entered
*/
private static Integer getUserInteger(String prompt) {
String userChoice = JOptionPane.showInputDialog(null, prompt);
if (userChoice == null) { // cancel returns a null string
return null;
}
Scanner scan = new Scanner(userChoice);
if (! scan.hasNextInt()) { // might not be an int
JOptionPane.showMessageDialog(null, "did not enter a number");
return null;
}
Integer choice = scan.nextInt();
return choice;
}
/* @param prompt for the user
* @return null, or the double the user entered
*/
private static Double getUserDouble(String prompt) {
String userChoice = JOptionPane.showInputDialog(null, prompt);
if (userChoice == null) { // cancel returns a null string
return null;
}
Scanner scan = new Scanner(userChoice);
if (! scan.hasNextDouble()) { // might not be a double
JOptionPane.showMessageDialog(null, "did not enter a number");
return null;
}
return scan.nextDouble();
}
}
/* a class for binary tree nodes
* @author Biagioni, Edoardo
* @assignment lecture 17
* @date March 12, 2008
* @inspiration William Albritton's binary search tree class,
http://www2.hawaii.edu/~walbritt/ics211/treeBinarySearch/BinarySearchTree.java
*/
class BinarySearchTree<T extends java.lang.Comparable<T>> {
/* the root of the tree is the only data field needed */
protected BinaryNode<T> root = null; // null when tree is empty
/* constructs an empty tree
*/
public BinarySearchTree() {
super();
}
/* constructs a tree with one element, as given
* @param value to be used for the one element in the tree
*/
public BinarySearchTree(T value) {
super();
root = new BinaryNode<T>(value);
}
/* constructs a tree with the given node as root
* @param newRoot to be used as the root of the new tree
*/
public BinarySearchTree(BinaryNode<T> newRoot) {
super();
root = newRoot;
}
/* find a value in the tree
* @param key identifies the node value desired
* @return the node value found, or null if not found
*/
public T get(T key) {
BinaryNode<T> node = root;
while (node != null) {
if (key.compareTo(node.getValue()) == 0) {
return node.getValue();
}
if (key.compareTo(node.getValue()) < 0) {
node = node.getLeft();
} else {
node = node.getRight();
}
}
return null;
}
/* add a value to the tree, replacing an existing value if necessary
* @param value to be inserted
*/
public void add(T value) {
root = add(value, root);
}
/* add a value to the tree, replacing an existing value if necessary
* @param value to be inserted
* @param node that is the root of the subtree in which to insert
* @return the subtree with the node inserted
*/
protected BinaryNode<T> add(T value, BinaryNode<T> node) {
if (node == null) {
return new BinaryNode<T>(value);
}
if (value.compareTo(node.getValue()) == 0) {
// replace the value in this node with a new value
node.setValue(value);
// alternative code creates new node, leaves old node unchanged:
//return new BinaryNode<T>(value, node.getLeft(), node.getRight());
} else {
if (value.compareTo(node.getValue()) < 0) { // add to left subtree
node.setLeft(add(value, node.getLeft()));
} else { // add to right subtree
node.setRight(add(value, node.getRight()));
}
}
return node;
}
/* remove a value from the tree, if it exists
* @param key such that value.compareTo(key) == 0 for the node to remove
*/
public void remove(T key) {
root = remove(key, root);
}
/* remove a value from the tree, if it exists
* @param key such that value.compareTo(key) == 0 for the node to remove
* @param node the root of the subtree from which to remove the value
* @return the new tree with the value removed
*/
protected BinaryNode<T> remove(T value, BinaryNode<T> node) {
if (node == null) { // key not in tree
return null;
}
if (value.compareTo(node.getValue()) == 0) { // remove this node
if (node.getLeft() == null) { // replace this node with right child
return node.getRight();
} else if (node.getRight() == null) { // replace with left child
return node.getLeft();
} else {
// replace the value in this node with value in the
// rightmost node of the left subtree
T replacement = getRightmost(node.getLeft());
// now remove the rightmost node in the left subtree,
// by calling ourselves recursively
BinaryNode<T> newNode = new
BinaryNode<T>(replacement,
remove(replacement, node.getLeft()),
node.getRight());
return newNode;
}
} else { // remove from left or right subtree
if (value.compareTo(node.getValue()) < 0) {
// remove from left subtree
node.setLeft(remove(value, node.getLeft()));
} else { // remove from right subtree
node.setRight(remove(value, node.getRight()));
}
}
return node;
}
//----------------------------------------------------------------------------//
/**
* finds a greatest record that is smaller than a given value in a binary
* search tree based a key value
*
* @param key identifies the value desired
* @return the previous node value if found, or null if not found
* @throws NoSuchElementException if the next node does not exist
*/
public T findPrevious(T key) {
if (key == null)
throw new NullPointerException("key");
return findPrevious(key, null, root);
}
/**
* finds a greatest record that is smaller than a given value in a binary
* search tree based a key value
*
* @param key identifies the value desired
* @param node is the root of the current subtree
* @param anchor keeps track of the parent node that might be the answer
* @return the previous node value if found, or null if not found
* @throws NoSuchElementException if the next node does not exist
*/
private T findPrevious(T key, BinaryNode<T> anchor, BinaryNode<T> node) {
// return null if there's no node matches with the key
if (node == null)
return null;
int comparison = key.compareTo(node.getValue());
// if the key node is found, return the right most node's value on its left
// subtree. If it don't have a left subtree, return the anchor's value. If
// the anchor didn't change, throw NoSuchElementException.
if (comparison == 0) {
if (node.getLeft() != null)
return rightMost(node.getLeft()).getValue();
if (anchor == null)
throw new NoSuchElementException();
return anchor.getValue();
}
// if the key is smaller than the current root's value, go left without
// change the anchor.
if (comparison < 0)
return findPrevious(key, anchor, node.getLeft());
// if the key is greater than the current root's value, update the anchor to
// the current root and go right.
return findPrevious(key, node, node.getRight());
}
/**
* finds a smallest record that is greater than a given value in a binary
* search tree based a key value
*
* @param key identifies the value desired
* @return the next node value if found, or null if not found
* @throws NoSuchElementException if the next node does not exist
*/
public T findNext(T key) {
if (key == null)
throw new NullPointerException("key");
return findNext(key, null, root);
}
/**
* finds a smallest record that is greater than a given value in a binary
* search tree based a key value
*
* @param key identifies the value desired
* @param node is the root of the current subtree
* @param anchor keeps track of the parent node that might be the answer
* @return the next node value if found, or null if not found
* @throws NoSuchElementException if the next node does not exist
*/
private T findNext(T key, BinaryNode<T> anchor, BinaryNode<T> node) {
// return null if there's no node matches with the key
if (node == null)
return null;
int comparison = key.compareTo(node.getValue());
// if the key node is found, return the left most node's value on its right
// subtree. If it don't have a right subtree, return the anchor's value. If
// the anchor doesn't updated, throw NoSuchElementException.
if (comparison == 0) {
if (node.getRight() != null)
return leftMost(node.getRight()).getValue();
if (anchor == null)
throw new NoSuchElementException();
return anchor.getValue();
}
// if the key is greater than the current root's value, go right without
// updating the anchor.
if (comparison > 0)
return findNext(key, anchor, node.getRight());
// if the key is smaller than the current root's value, update the anchor to
// the current root and go left.
return findNext(key, node, node.getLeft());
}
/**
* finds a right most node in the binary search tree from a given root
*
* @param node identifies the root node
* @return the node if found, or null if not found
*/
private BinaryNode<T> rightMost(BinaryNode<T> node) {
if (node == null)
return null;
if (node.getRight() == null)
return node;
return rightMost(node.getRight());
}
/**
* finds a left most node in the binary search tree from a given root
*
* @param node identifies the root node
* @return the node if found, or null if not found
*/
private BinaryNode<T> leftMost(BinaryNode<T> node) {
if (node == null)
return null;
if (node.getLeft() == null)
return node;
return leftMost(node.getLeft());
}
/**
* returns the string representation of the tree.
*
* @return the string representation of the tree
*/
@Override
public String toString() {
return this.toString(this.root, "");
}
/**
* returns the string representation of the tree.
*
* @param node identifies the root node
* @param indent the indentation (spaces) before the current node
* @return the string representation of the tree.
*/
private String toString(final BinaryNode<T> node, final String indent) {
if (node == null)
return "";
return this.toString(node.getRight(), indent + " ") + indent + node +
"\n" + this.toString(node.getLeft(), indent + " ");
}
//----------------------------------------------------------------------------//
protected T getRightmost(BinaryNode<T> node) {
assert(node != null);
BinaryNode<T> result = node.getRight();
if (node.getRight() == null) {
return node.getValue();
} else {
return getRightmost(node.getRight());
}
}
/* iterator, traverses the tree in order */
public Iterator<T> iterator() {
return new TreeIterator<T>(root);
}
/* traverses the tree in pre-order */
public Iterator<T> preIterator() {
return new TreeIterator<T>(root, true);
}
/* traverses the tree in post-order */
public Iterator<T> postIterator() {
return new TreeIterator<T>(root, false);
}
/* unit test
* @param arguments, ignored
*/
public static void main(String[] arguments) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
tree.add(5);
tree.add(7);
tree.add(9);
tree.add(3);
tree.add(1);
tree.add(2);
tree.add(4);
tree.add(6);
tree.add(8);
tree.add(10);
System.out.println(tree);
Iterator<Integer> it = tree.preIterator();
System.out.print("pre-order: ");
while (it.hasNext()) {
System.out.print(it.next() + ", ");
}
System.out.println("");
it = tree.iterator();
System.out.print("in-order: ");
while (it.hasNext()) {
System.out.print(it.next() + ", ");
}
System.out.println("");
it = tree.postIterator();
System.out.print("post-order: ");
while (it.hasNext()) {
System.out.print(it.next() + ", ");
}
System.out.println("");
if (! tree.get(5).equals(5)) {
System.out.println("error: tree does not have 5");
}
if (tree.get(13) != null) {
System.out.println("error: tree has 13, should not");
}
if (! tree.get(10).equals(10)) {
System.out.println("error: tree does not have 10");
}
tree.add(10);
System.out.println(tree);
tree.remove(10);
tree.remove(2);
tree.remove(5);
tree.remove(9);
tree.remove(10);
tree.remove(9);
System.out.println(tree);
if (tree.get(5) != null) {
System.out.println("error: tree has 5, should not");
}
if (tree.get(13) != null) {
System.out.println("error: tree has 13, should not");
}
if (! tree.get(3).equals(3)) {
System.out.println("error: tree does not have 3");
}
}
}
/* a class for binary tree nodes
* @author Biagioni, Edoardo
* @assignment lecture 16
* @date March 10, 2008
* @inspiration William Albritton's binary tree node class,
* http://www2.hawaii.edu/~walbritt/ics211/treeBinarySearch/BinaryNode.java
* @inspiration the Node class,
* http://www2.ics.hawaii.edu/~esb/2008spring.ics211/Node.java.html
*/
class BinaryNode<T> {
/* three data fields, the first to store the item itself,
* the other two for the left and right subtree,
* either or both of which may be null.
*/
protected T item;
protected BinaryNode<T> left;
protected BinaryNode<T> right;
/* no-argument constructor sets everything to null */
public BinaryNode() {
item = null;
left = null;
right = null;
}
/* one-argument constructor: value as given, subtrees are null
* @param value, the value for the node
*/
public BinaryNode(T value) {
item = value;
left = null;
right = null;
}
/* constructor:
* @param value, the value for the node
* @param left, the left subtree
* @param right, the right subtree
*/
public BinaryNode(T value, BinaryNode<T> leftSubtree,
BinaryNode<T> rightSubtree) {
item = value;
left = leftSubtree;
right = rightSubtree;
}
/* accessor methods */
public T getValue() {
return item;
}
public BinaryNode<T> getLeft() {
return left;
}
public BinaryNode<T> getRight() {
return right;
}
/* mutator methods */
public void setValue(T value) {
item = value;
}
public void setLeft(BinaryNode<T> newLeft) {
left = newLeft;
}
public void setRight(BinaryNode<T> newRight) {
right = newRight;
}
/* toString
* @returns the string representation of the item.
*/
public String toString() {
return item + "";
}
/* unit test
* @param arguments, ignored
*/
public static void main(String[] arguments) {
BinaryNode<Integer> x = new BinaryNode<Integer>(); // no-arguments constructor
BinaryNode<Integer> y = new BinaryNode<Integer>(3);
BinaryNode<Integer> z = new BinaryNode<Integer>(9, x, y);
printXyz(x, y, z);
z.setValue(65);
x.setValue(new Integer(16));
printXyz(x, y, z);
}
private static void printXyz(BinaryNode<Integer> x, BinaryNode<Integer> y,
BinaryNode<Integer> z) {
System.out.println("x is the node " + x +
", with left " + x.getLeft() +
" and right " + x.getRight());
System.out.println("y is the node " + y +
", with left " + y.getLeft() +
" and right " + y.getRight());
System.out.println("z is the node " + z +
", with left " + z.getLeft() +
" and right " + z.getRight());
}
}
/* an iterator class to iterate over binary trees
* @author Biagioni, Edoardo
* @assignment lecture 17
* @date March 12, 2008
*/
class TreeIterator<T> implements Iterator<T> {
/* the class variables keep track of how much the iterator
* has done so far, and what remains to be done.
* root is null when the iterator has not been initialized,
* or the entire tree has been visited.
* the first stack keeps track of the last node to return
* and all its ancestors
* the second stack keeps track of whether the node visited
* is to the left (false) or right (true) of its parent
*/
protected BinaryNode<T> root = null;
protected Stack<BinaryNode<T>> visiting = new Stack<BinaryNode<T>>();
protected Stack<Boolean> visitingRightChild = new Stack<Boolean>();
/* only one of these booleans can be true */
boolean preorder = false;
boolean inorder = true;
boolean postorder = false;
/* constructor for in-order traversal
* @param root of the tree to traverse
*/
public TreeIterator(BinaryNode<T> root) {
this.root = root;
visiting = new Stack<BinaryNode<T>>();
visitingRightChild = new Stack<Boolean>();
preorder = false;
inorder = true;
postorder = false;
}
/* constructor for pre-order or post-order traversal
* @param root of the tree to traverse
* @param inPreorder true if pre-order, false if post-order
*/
public TreeIterator(BinaryNode<T> root, boolean inPreorder) {
this.root = root;
visiting = new Stack<BinaryNode<T>>();
visitingRightChild = new Stack<Boolean>();
preorder = inPreorder;
inorder = false;
postorder = ! preorder;
}
public boolean hasNext() {
return (root != null);
}
public T next() {
if (! hasNext()) {
throw new java.util.NoSuchElementException("no more elements");
}
if (preorder) {
return preorderNext();
} else if (inorder) {
return inorderNext();
} else if (postorder) {
return postorderNext();
} else {
assert(false);
return null;
}
}
// return the node at the top of the stack, push the next node if any
private T preorderNext() {
if (visiting.empty()) { // at beginning of iterator
visiting.push(root);
}
BinaryNode<T> node = visiting.pop();
T result = node.getValue();
// need to visit the left subtree first, then the right
// since a stack is a LIFO, push the right subtree first, then
// the left. Only push non-null trees
if (node.getRight() != null) {
visiting.push(node.getRight());
}
if (node.getLeft() != null) {
visiting.push(node.getLeft());
}
// may not have pushed anything. If so, we are at the end
if (visiting.empty()) { // no more nodes to visit
root = null;
}
return node.getValue();
}
/* find the leftmost node from this root, pushing all the
* intermediate nodes onto the visiting stack
* @param node the root of the subtree for which we
* are trying to reach the leftmost node
* @changes visiting takes all nodes between node and the leftmost
*/
private void pushLeftmostNode(BinaryNode<T> node) {
// find the leftmost node
if (node != null) {
visiting.push(node); // push this node
pushLeftmostNode(node.getLeft()); // recurse on next left node
}
}
/* return the leftmost node that has not yet been visited
* that node is normally on top of the stack
* inorder traversal doesn't use the visitingRightChild stack
*/
private T inorderNext() {
if (visiting.empty()) { // at beginning of iterator
// find the leftmost node, pushing all the intermediate nodes
// onto the visiting stack
pushLeftmostNode(root);
} // now the leftmost unvisited node is on top of the visiting stack
BinaryNode<T> node = visiting.pop();
T result = node.getValue(); // this is the value to return
// if the node has a right child, its leftmost node is next
if (node.getRight() != null) {
BinaryNode<T> right = node.getRight();
// find the leftmost node of the right child
pushLeftmostNode (right);
// note "node" has been replaced on the stack by its right child
} // else: no right subtree, go back up the stack
// next node on stack will be next returned
if (visiting.empty()) { // no next node left
root = null;
}
return result;
}
/* find the leftmost node from this root, pushing all the
* intermediate nodes onto the visiting stack
* and also stating that each is a left child of its parent
* @param node the root of the subtree for which we
* are trying to reach the leftmost node
* @changes visiting takes all nodes between node and the leftmost
*/
private void pushLeftmostNodeRecord(BinaryNode<T> node) {
// find the leftmost node
if (node != null) {
visiting.push(node); // push this node
visitingRightChild.push(false); // record that it is on the left
pushLeftmostNodeRecord(node.getLeft()); // continue looping
}
}
//
private T postorderNext() {
if (visiting.empty()) { // at beginning of iterator
// find the leftmost node, pushing all the intermediate nodes
// onto the visiting stack
pushLeftmostNodeRecord(root);
} // the node on top of the visiting stack is the next one to be
// visited, unless it has a right subtree
if ((visiting.peek().getRight() == null) || // no right subtree, or
(visitingRightChild.peek())) { // right subtree already visited
// already visited right child, time to visit the node on top
T result = visiting.pop().getValue();
visitingRightChild.pop();
if (visiting.empty()) {
root = null;
}
return result;
} else { // now visit this node's right subtree
// pop false and push true for visiting right child
if (visitingRightChild.pop()) {
assert(false);
}
visitingRightChild.push(true);
// now push everything down to the leftmost node
// in the right subtree
BinaryNode<T> right = visiting.peek().getRight();
assert(right != null);
pushLeftmostNodeRecord(right);
// use recursive call to visit that node
return postorderNext();
}
}
/* not implemented */
public void remove() {
throw new java.lang.UnsupportedOperationException("remove");
}
/* give the entire state of the iterator: the tree and the two stacks */
public String toString() {
if (preorder) {
return "pre: " + toString(root) + "\n" + visiting + "\n";
}
if (inorder) {
return "in: " + toString(root) + "\n" + visiting + "\n";
}
if (postorder) {
return "post: " + toString(root) + "\n" + visiting + "\n" +
visitingRightChild;
}
return "none of pre-order, in-order, or post-order are true";
}
private String toString(BinaryNode<T> node) {
if (node == null) {
return "";
} else {
return node.toString() + "(" + toString(node.getLeft()) + ", " +
toString(node.getRight()) + ")";
}
}
/* unit test
* @param arguments, ignored
*/
public static void main(String[] arguments) {
BinaryNode<String> x = new BinaryNode<String>("x");
BinaryNode<String> z = new BinaryNode<String>("z");
BinaryNode<String> y = new BinaryNode<String>("y", x, z);
testIterator(new TreeIterator<String>(y));
testIterator(new TreeIterator<String>(y, true));
testIterator(new TreeIterator<String>(y, false));
BinaryNode<String> a = new BinaryNode<String>("a");
BinaryNode<String> c = new BinaryNode<String>("c");
BinaryNode<String> b = new BinaryNode<String>("b", a, null);
BinaryNode<String> m = new BinaryNode<String>("m", b, y);
testIterator(new TreeIterator<String>(m));
testIterator(new TreeIterator<String>(m, true));
testIterator(new TreeIterator<String>(m, false));
}
public static void testIterator(Iterator<String> it) {
System.out.println("it = " + it);
while (it.hasNext()) {
String result = it.next();
System.out.println("it.next gives " + result + "\n it = " + it);
}
}
}
/* a class for taxpayers in a database
* @author Biagioni, Edoardo
* @assignment lecture 17
* @date March 12, 2008
* @inspiration William Albritton's Person class,
* http://www2.hawaii.edu/~walbritt/ics211/treeBinarySearch/Person.java
*/
class Taxpayer implements java.lang.Comparable<Taxpayer> {
String name; // the taxpayer's full name
int SSN; // the taxpayer's social security number
double tax; // amount of tax owed by or to the taxpayer
/* constructor */
public Taxpayer(String name, int SSN, double tax) {
this.name = name;
this.SSN = SSN;
this.tax = tax;
}
/* a constructor to build a taxpayer record that is a key, that is,
* only the SSN is of interest
*/
public Taxpayer(int SSN) {
this.SSN = SSN;
}
/* accessor methods */
public String getName() {
return name;
}
public int getSSN() {
return SSN;
}
public double getTax() {
return tax;
}
/* mutator methods */
public void getName(String newName) {
name = newName;
}
public void setSSN(int newSSN) {
SSN = newSSN;
}
public void setTax(double newTax) {
tax = newTax;
}
public int compareTo(Taxpayer recordOrKey) {
/* only use SSN field, which exists in a key as well as in a complete
* record */
return SSN - recordOrKey.SSN;
}
public String toString() {
return "name: " + name + ", SSN: " + SSN + ", tax due: " + tax;
}
}
