import java.util.NoSuchElementException;
 
/**
 * Implementation of homework 9.
 * 
 * @author Cheng Jade
 * @assignment ICS211 Homework TA9
 * @date Apr 10, 2010
 * @bugs None
 */
public class ChengJade9 {
    /**
     * 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 grandpaTree = new FamilyTree();
        final FamilyTree grandmaTree = new FamilyTree();
 
        // Add elements to dad's side family tree and print out the contents.
        tryAdd(grandpaTree, null, "grandpa");
        tryAdd(grandpaTree, "grandpa", "aunt");
        tryAdd(grandpaTree, "grandpa", "dad");
        tryAdd(grandpaTree, "grandpa", "uncle");
        tryAdd(grandpaTree, "aunt", "cousin1");
        tryAdd(grandpaTree, "aunt", "cousin2");
        tryAdd(grandpaTree, "dad", "jade");
        tryAdd(grandpaTree, "uncle", "cousin3");
        tryAdd(grandpaTree, "cousin1", "nephew1");
        tryAdd(grandpaTree, "cousin1", "niece");
        tryAdd(grandpaTree, "cousin1", "nephew2");
        System.out.println("Printing grandpa's family tree...");
        System.out.println(grandpaTree);
 
        // Add elements to mom's side family tree and print out the contents.
        tryAdd(grandmaTree, null, "grandma");
        tryAdd(grandmaTree, "grandma", "aunt");
        tryAdd(grandmaTree, "grandma", "mom");
        tryAdd(grandmaTree, "grandma", "uncle1");
        tryAdd(grandmaTree, "grandma", "uncle2");
        tryAdd(grandmaTree, "aunt", "cousin1");
        tryAdd(grandmaTree, "mom", "jade");
        tryAdd(grandmaTree, "uncle1", "cousin2");
        tryAdd(grandmaTree, "uncle1", "cousin3");
        tryAdd(grandmaTree, "cousin3", "second niece");
        tryAdd(grandmaTree, "cousin3", "second nephew");
        tryAdd(grandmaTree, "uncle1", "cousin4");
        tryAdd(grandmaTree, "second niece", "second niece's son");
        System.out.println("Printing grandma's family tree...");
        System.out.println(grandmaTree);
 
        // Test some bad situations.
        try {
            System.out.println("Adding \"orphan1\" to \"nobogy\" in grandpa's family tree...");
            tryAdd(grandpaTree, "nobody", "orphan1");
            Thread.sleep(500);
            System.out.println("\nAdding \"orphan2\" to \"null\" in grandpa's family tree...");
            tryAdd(grandpaTree, null, "orphan2");
            Thread.sleep(500);
            final FamilyTree emptyTree = new FamilyTree();
            System.out.println("\nPrinting an empty family tree...");
            System.out.println(emptyTree);
        } catch (final InterruptedException e) {
            System.err.println(e.getMessage());
            System.exit(1);
        }
 
        // 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());
            System.err.flush();
        }
    }
}
 
/**
 * 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 (this.myRoot == null) {
                this.myRoot = new FamilyTreeNode(null, name);
                return;
            }
 
            // Do not reassign the root item. Throw an exception instead.
            throw new NoSuchElementException("Error: 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 (!this.add(parent, name, this.myRoot))
            throw new NoSuchElementException("Error: 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 (this.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() {
        if (this.myRoot == null)
            return "Nobody's in this family tree";
        final StringBuilder builder = new StringBuilder();
        toString(builder, this.myRoot, "", "");
        return builder.toString();
    }
    /**
     * Returns the string representation of the class data. The nodes of the
     * tree are returned in pre-order.
     * 
     * @param builder
     *            The string builder.
     * @param node
     *            The current node.
     * @param indent1
     *            The indent with bullet that is printed before all nodes except
     *            the root node
     * @param indent2
     *            The indent with spaces that is printed before all nodes
     * @return The string representation of the class data.
     */
    private static void toString(
            final StringBuilder builder,
            final FamilyTreeNode node,
            final String indent1,
            final String indent2) {
 
        assert null != node;
 
        builder.append(indent1 + node + "\n");
 
        final int size = node.numChildren();
        for (int i = 0; i < size; i++) {
            if (i == size - 1)
                toString(builder, node.child(i), indent2 + "  +--- ", indent2 + "       ");
            else
                toString(builder, node.child(i), indent2 + "  +--- ", indent2 + "  |    ");
        }
    }
}
 
/**
 * 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");
 
        this.myParent = parent;
        this.myName = name;
        this.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 (this.myChildren == null) {
            this.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 = this.myChildren.length;
        final FamilyTreeNode[] newChildren = new FamilyTreeNode[size + 1];
        System.arraycopy(this.myChildren, 0, newChildren, 0, size);
        newChildren[size] = newChild;
        this.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 >= this.myChildren.length)
            throw new IndexOutOfBoundsException("index");
 
        return this.myChildren[index];
    }
 
    /**
     * Returns the person's name.
     * 
     * @return The person's name.
     */
    public String name() {
        return this.myName;
    }
 
    /**
     * Returns the number of children for the node.
     * 
     * @return The number of children for the node.
     */
    public int numChildren() {
        return this.myChildren == null ? 0 : this.myChildren.length;
    }
 
    /**
     * Returns the parent node or null if this is the root node.
     * 
     * @return The parent node.
     */
    public FamilyTreeNode parent() {
        return this.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 this.myName;
    }
}
 
Valid HTML 4.01 Valid CSS