People who are interested in geneology try to identify their ancestors and find out about their lives.  This project is about taking relationship information that has been  gleaned from various sources and assembling it into an ancestory tree.  The relationship information has been placed in a file in a specific format.  You are to write a program that reads the file, creates the ancestory tree and then displays in a specific form the ancestors of the person who is the root of the tree.  Here is a sample of what might be in a small relationship file holding only three generations.

Ronald father of Sharon
Maria mother of Josue
Sharon mother of Grace
Juan father of Josue
Josue father of Grace
Kathy mother of Sharon

Each line of the relationship file contains a parent's name followed by the words "mother of" or "father of" followed by a child's name.  From this information, your program should construct an ancestory tree that looks like the one at the right above.  All names are guaranteed to be a single word and are guaranteed not to be repeated.  In addition, all data should fit into a  single ancestory tree.

Then, the program should display the ancestory information like this:

Subject
    Grace
Parents
    Josue
    Sharon
Grandparents
    Juan
    Maria
    Ronald
    Kathy

Here the ancestory tree is listed starting at the root by generations in left to right order.  For each generation, the father is to the left and the mother is to the right.

You might have noticed that the ancestory tree is sort of upside down from the family trees that were described in class.  Here, the successor of a node is either the father (on the left) or mother (on the right) of that node.  Thus, we have approximately reversed the terms "parent" and "child" from the way we discussed family trees.

To do this project, you need to implement your own AncestoryTree class, including an inner Node class.  You may use the BinaryTree class that is in the book as a model for some of the elements of this class; however, a node will typically have father and mother references rather than left and right child references.  The AncestoryTree class must be generic, so that the data may be of any class.  In addition, because the ancestory data is not in any particular order, you will not be able to build the AncestoryTree from the top down.  You will have to build pieces of the tree and connect them together as branches of a bigger tree, until you have built the entire tree.  I found it handy to keep a linked list of AncestoryTrees which I fit together as I read in sufficient information to know how they fit.  When my program finished, I had a single AncestoryTree on the linked list and it contained everything.

There are two files of ancestor information on the I: drive for you to use.  The file at  I:\jlwolfe\310\f07\3generations.txt contains the information used as an example here.  The second file at  I:\jlwolfe\310\f07\6generations.txt  contains ancestory information that I want you to use when you execute your program.  Capture the output from an execution on 6generations.txt to hand in. Hand in a printout of your well-documented program, and a printout of thecaptured output.  You must create a folder named p6 under the folder named after you on the P: drive for COSC 310.  Copy into p6 all .java files that you created for this project.

Extra Credit:

After you have displayed the ancestory tree, have the program repeatedly prompt for a person's name until the word "stop" is entered.  For each name entered, display that person's descendants (child, grandchild, etc.).  These are the names of the people on a path from the root to the node representing the named person.  For example, in the small sample ancestory tree, if Ronald is entered, the program should display the names Sharon and Grace; if the name Josue is entered, the program should display Grace; if the name Grace is entered, the program should indicate there are no descendants.