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