ChengJade8.java

/* 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;
    }
 
}
 
 
 
Valid HTML 4.01 Valid CSS