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; } }