The file descendants.txt is on the I: drive in the folder  I:\jlwolfe\310\s07  It contains information about the family relationships in six generations of one family, the descendants of Henry and Adella Garrett.  You are to write a program whose first task is to build a family tree based on the information in the file.  There are four types of records in the file

Patriarch record
P Name M Wife                     Example:  P Henry M Adella
Holds the Name of the family patriarch.  There is only one record like this and it is first in the file.  The 'M' indicates that the patriarch is male; the "Wife" is his wife's name.  The 'M' may seem redundant but the record is arranged like this to be consistent in form with other records in the file.

First Child record
F Name Sex Member        Example:  F Stella F Henry
Here "Name" is the name of the first born child of a family member and his/her spouse; "Sex" indicates the sex of the child (an 'M' or an 'F'); and "Member" is the name of a blood-relative in the family.  Stella is the first born child of Henry and Adella.

Sibling record
S Name Sex Member        Example:  S Linnie F Stella
Here "Name" is the name of a sibling (brother or sister) of a family member; "Sex" indicates the sex of the sibling; and "Member" is the name of a blood-relative in the family.  Linnie is Stella's sister.

Spouse record
C Name Sex Member        Example:  C Harry M Linnie
Here "Name" is the name of the spouse of a family member; "Sex" indicates the sex of the spouse and; "Member" is the name of a blood-relative in the family.  Harry is Linnie's husband.

The file is ordered so that each first-child record, sibling record, and spouse record contains the name of a blood-relative that has appeared in a previous record.  Thus, each record can be used to add to the family tree immediately by finding the referenced blood-relative.  In the family tree, each node needs to hold the name of two people (Husband and Wife), an indicator as to which is the blood relative, and three node references (one to the first child, one to a sibling, and one to the parents).  Below is a small sample showing the root of the tree (Henry and Adella's node) and a few of their descendants and inlaws.  Links to the first child are in red; those to a sibling are in green; and links to the parents are in blue:  See the WebCT version for the colors.

After your program has built the complete family tree, it should repeatedly prompt for people's names (until the word "stop" rather than a name is entered.  For each name entered, the program should determine that person's place in the family and display text that explains that place.  A person's place in the family is determined by who s/he is married to, who his/her parents, grandparents, etc. are back to the family patriarch.  Thus, the display of a person's place always ends with a reference to Henry and Adella, or at least to Henry.  For example, for James (me) it should show the following (or something similar).

James is married to Loretta
James is the son of Nelson and Margaret
James is the grandson of Lowell and Dorothy
James is the great-grandson of Henry and Adella

For non-blood relatives, a different line is needed to show their place - first, they must be connected to a blood relative; then show the blood relative's place in the family.  The first line shows the non-blood relative as wife or husband of a blood relative.  Consider Thelma for whom the required output is

Thelma is the wife of DeanB
DeanB is the son of William and Bernice
DeanB is the grandson of Henry and Adella

For some people, the information in the tree is incomplete - because a name is not known or because there is no appropriate entry; consider Justine whose father is not identified and who is not married.  The required output is

Justine has no identified spouse
Justine is the daughter of Laurie
Justine is the granddaughter of Joseph and Doris
Justine is the great-granddaughter of Lowell and Dorothy
Justine is the great-great-granddaughter of Henry and Adella

Naturally, for everyone in the family tree, the last entry will refer to Henry and Adella because they represent the beginning of the tree given.  Your program should be able to display some output for every person that appears in the tree, even for the names Henry and Adella.  If a name is entered that is not in the family tree, the program should display a message indicating the person was not found.

Hand in a printout of your well-documented program and a printout showing the place in the family for the following people:  Bruce, Eva, Adella, Brian, Belva, Ruth, Bud and Anabella.  Name your source program after yourself and copy the .java files you create for it to a P6 folder that you make in the  folder named after you on the P:\ drive for COSC 310.

Extra Credit:
You can get extra project points for doing either or both of the following, in addition to showing a person's place in the family.

1.  List all siblings of a person who is a blood relative.  If the person is a spouse of a blood relative, list the blood relative's siblings.

2.  List all children of the specified person.

Below is an example, showing the output for William and Zane in which both of these extra credit elements are shown.

William is husband of Bernice
Bernice is daughter of Henry and Adella
Bernice's siblings: Stella  Linnie  Dorothy  Eva
Bernice's children: Geraldine  DeanB  Malvin

Zane has no identified spouse
Zane is son of Ronald and Kathy
Zane is grandson of Nelson and Margaret
Zane is great-grandson of Lowell and Dorothy
Zane is great-great-grandson of Henry and Adella
Zane's siblings: Neil  Isaac  Jonathan  Sharon  Hannah
Zane has no identified children

To do this project, you should implement your own class for a family tree.  The book suggests some of what this class might contain in its BinaryTree class.  But, the binary tree you need has some special attributes.  It needs nodes with three references (one to the first child, one to a sibling, and one to the parent).  Each node needs to be able to hold the information about one couple (a husband and a wife and an indication as to which is the blood relative).  The class also needs an iterator to follow all three of these references in order to obtain the information you need to report on a person's position in the family tree (and the extra credit elements).  Thus, the class you make for a family tree needs two inner classes,  one to provide nodes and one to provide and manipulate iterators.  I recommend using an interface for the iterator that is something like this:

public interface TreeIterator <E> {
     E nextSibling();        // Follow sibling link
     E toChild();            // Follow first child link
     E toParent();           // Follow parent link
     boolean hasParent();    // Check if parent link exists
     boolean hasChild();     // Check if child link exists
     boolean hasSibling();   // Check if sibling link exists
}

It is not required that you use this interface; the interface is given here as a suggestion.

Once you have a working family tree class, your application class should be able to build the family tree from the data in the file.  Then, for the interactive portion of the project, you need to be able to search the tree for a person who may or may not be a blood relative.  After finding the person, display the family information about the person.  The program should stop prompting for a name to find only when the word "stop" is entered, instead of a name.