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