ChengJade09.java

import java.util.NoSuchElementException;
 
/**
 * Implementation of homework 9.
 *
 * @author     Cheng Jade
 * @assignment ICS211 Homework TA9
 * @date       Nov 12, 2008
 * @bugs       None
 */
public class ChengJade09 {
  /**
   * The main entry point of the program.
   *
   * @param args The command line arguments (not used)
   */
  public static void main(final String[] args) {
 
    // Define two family trees, dad's side and mom's side family trees.
    final FamilyTree dadTree = new FamilyTree();
    final FamilyTree momTree = new FamilyTree();
 
    // Add elements to dad's side family tree and print out the contents.
    tryAdd(dadTree, null, "grandpa");
    tryAdd(dadTree, "grandpa", "auntie");
    tryAdd(dadTree, "grandpa", "dad");
    tryAdd(dadTree, "grandpa", "uncle");
    tryAdd(dadTree, "auntie", "cousin1");
    tryAdd(dadTree, "auntie", "cousin2");
    tryAdd(dadTree, "dad", "jade");
    tryAdd(dadTree, "uncle", "cousin3");
    tryAdd(dadTree, "cousin1", "nephew");
    System.out.println(dadTree);
 
    // Add elements to mom's side family tree and print out the contents.
    tryAdd(momTree, null, "grandma");
    tryAdd(momTree, "grandma", "auntie");
    tryAdd(momTree, "grandma", "mom");
    tryAdd(momTree, "grandma", "uncle1");
    tryAdd(momTree, "grandma", "uncle2");
    tryAdd(momTree, "auntie", "cousin1");
    tryAdd(momTree, "mom", "jade");
    tryAdd(momTree, "uncle1", "cousin2");
    tryAdd(momTree, "uncle1", "cousin3");
    tryAdd(momTree, "cousin3", "niece");
    System.out.println(momTree);
 
    // Allow the Eclipse debugger to exit happily.
    System.exit(0);
  }
 
 
  /**
   * Attempts to add an item to the tree and displays an error if the add method
   * is unsuccessful.
   *
   * @param tree The family tree.
   * @param parent The name of the parent or null if this is the root node.
   * @param child The name of the child to add.
   */
  static void tryAdd(final FamilyTree tree, final String parent,
      final String child) {
    assert null != tree;
 
    try {
      tree.add(parent, child);
    } catch (final NoSuchElementException e) {
      System.err.println(e.getMessage());
    }
  }
}
 
/**
 * a family tree class.
 */
class FamilyTree {
  /**
   * The root node of the family tree.
   */
  private FamilyTreeNode myRoot = null;
 
 
  /**
   * Adds a node to the tree. This method searches for the parent and adds the
   * child to that node if it is found. If this is the root node, then the
   * parent parameter should be null. Only one root node is allowed per tree.
   *
   * @param parent The name of the parent to the child or null if the child
   *          should be the root of the tree.
   * @param name The name of the child to add.
   * @throws NoSuchElementException if the parent is not found or if the parent
   *           parameter is null and the root node is already assigned.
   * @throws NullPointerException if the name parameter is null.
   */
  public void add(final String parent, final String name) {
    if (name == null)
      throw new NullPointerException("name");
 
    // Check if assigning this child as the root of the tree.
    if (parent == null) {
 
      // Assign the root item if there is not already one set.
      if (myRoot == null) {
        myRoot = new FamilyTreeNode(null, name);
        return;
      }
 
      // Do not reassign the root item. Throw an exception instead.
      throw new NoSuchElementException("Cannot assign '" + name
          + "' as root because the root has already been assigned.");
    }
 
    // Try to add the child by searching through the tree, and throw an
    // exception if the parent is not found.
    if (!add(parent, name, myRoot))
      throw new NoSuchElementException("There is no matching parent '" + parent
          + "' to add child '" + name + "'.");
  }
 
 
  /**
   * Adds a node to the tree recursively.
   *
   * @param parent The name of the parent to the child.
   * @param name The name of the child to add.
   * @param node The parent node to examine.
   * @return True if the parent was found and the child was added or false if
   *         otherwise.
   */
  private boolean add(final String parent, final String name,
      final FamilyTreeNode node) {
    assert null != parent;
    assert null != node;
 
    // Add the child if the parent name is a match.
    if (parent.equalsIgnoreCase(node.name())) {
      node.addChild(name);
      return true;
    }
 
    // Loop over each child, and search for the parent recursively. Return
    // true if the child is added.
    for (int i = 0; i < node.numChildren(); i++)
      if (add(parent, name, node.child(i)))
        return true;
 
    // If the parent was not found, return false.
    return false;
  }
 
 
  /**
   * Returns the string representation of the class data. The nodes of the tree
   * are returned in pre-order.
   *
   * @return The string representation of the class data.
   */
  @Override
  public String toString() {
    final StringBuilder builder = new StringBuilder();
    toString(myRoot, builder);
    return builder.toString();
  }
 
 
  /**
   * Recursively builds the text returned by toString().
   *
   * @param node The node to examine during recursion.
   * @param builder The StringBuilder that is used to build the text returned by
   *          the public toString() method.
   */
  private static void toString(final FamilyTreeNode node,
      final StringBuilder builder) {
    assert null != builder;
 
    // Return "empty" if the node is null. This happens only when the root of
    // the tree is null.
    if (node == null) {
      builder.append("empty");
      return;
    }
 
    // This method builds the string in pre-order so first add this node's value
    // before adding the child nodes' values.
    builder.append(node);
 
    // This will display output like: "a { b, c, d { e, f } }", which indicates
    // that b, c, and d are children of a, and e and f are children of d.
    final int numChildren = node.numChildren();
    if (numChildren > 0) {
      builder.append(" { ");
      toString(node.child(0), builder);
      for (int i = 1; i < numChildren; i++) {
        builder.append(", ");
        toString(node.child(i), builder);
      }
      builder.append(" }");
    }
  }
}
 
/**
 * a family tree node class.
 */
class FamilyTreeNode {
  /**
   * An array of children. When the node has no children, this array is null.
   * When there are N children, the array has a length of N.
   */
  private FamilyTreeNode[]     myChildren;
 
  /**
   * The person's name.
   */
  private final String         myName;
 
  /**
   * A pointer to the parent node.
   */
  private final FamilyTreeNode myParent;
 
 
  /**
   * Initializes a new instance of the class. Initially, the node has no
   * children.
   *
   * @param parent A pointer to the parent node of this new node or null if this
   *          is the root node.
   * @param name The name of person.
   * @throws NullPointerException if the name parameter is null.
   */
  public FamilyTreeNode(final FamilyTreeNode parent, final String name) {
    if (name == null)
      throw new NullPointerException("name");
 
    myParent = parent;
    myName = name;
    myChildren = null;
  }
 
 
  /**
   * Adds a child node to this node.
   *
   * @param name The name of the child to add.
   * @throws NullPointerException if the name parameter is null.
   */
  public void addChild(final String name) {
    if (name == null)
      throw new NullPointerException("name");
 
    // Create the new node.
    final FamilyTreeNode newChild = new FamilyTreeNode(this, name);
 
    // Create the array if this is the first node.
    if (myChildren == null) {
      myChildren = new FamilyTreeNode[] { newChild };
      return;
    }
 
    // Otherwise, duplicate the array, copy the old values, and add the new node
    // to the end of the array.
    final int size = myChildren.length;
    final FamilyTreeNode[] newChildren = new FamilyTreeNode[size + 1];
    System.arraycopy(myChildren, 0, newChildren, 0, size);
    newChildren[size] = newChild;
    myChildren = newChildren;
  }
 
 
  /**
   * Returns the child at the specified index.
   *
   * @param index The index of the node, which must range from 0 to the value
   *          returned by numChildren.
   * @return The node at the specified index.
   * @throws IndexOutOfBoundsException if the index is invalid.
   */
  public FamilyTreeNode child(final int index) {
    if (index < 0 || index >= myChildren.length)
      throw new IndexOutOfBoundsException("index");
 
    return myChildren[index];
  }
 
 
  /**
   * Returns the person's name.
   *
   * @return The person's name.
   */
  public String name() {
    return myName;
  }
 
 
  /**
   * Returns the number of children for the node.
   *
   * @return The number of children for the node.
   */
  public int numChildren() {
    return myChildren == null ? 0 : myChildren.length;
  }
 
 
  /**
   * Returns the parent node or null if this is the root node.
   *
   * @return The parent node.
   */
  public FamilyTreeNode parent() {
    return myParent;
  }
 
 
  /**
   * Returns the string representation of the class data. This method returns
   * the person's name.
   *
   * @return A string representation of the class data.
   */
  @Override
  public String toString() {
    return myName;
  }
}
 
Valid HTML 4.01 Valid CSS