The file ancestors.txt in the world-read folder for your section on the P: drive contains information about the family relationships in six generations of one family.  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 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; and "Member" is the name of a blood-relative in the family.

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.

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.

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 (there is no need to worry about joining pieces as in project #3).  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 pointers (one to the first child node, one to a sibling node, and one to a parents node).  Below is a small sample showing the root of the tree (Henry and Adella's node) and a few of their descendants and inlaws.  Pointers to the first child are in red; those to a sibling are in green; and pointers to the parents are in blue:  See the WebCT version for the colors.

After your program builds the complete family tree, it should repeatedly prompt for people's names.  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 his/her parents, grandparents, etc. are back to the family patriarch.  Thus, the display of a person's place will always end 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).

Siblings of James:  Thomas  Karen  David  Janice  Gale  Susan  Kathy  Ann
Children of James:
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

Actually, the lists of siblings and children are optional (they are extra credit elements); however the other lines of output are required to show James' place in the family.  For non-blood relatives, an additional 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.  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 shown.  The required output is

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 end.

Hand in a printout of your program and a printout showing the place in the family for the following people:  Crystal, Angie, Bruce, Eva, Adella, Lauryn, and Corie.  Name your source program after yourself and copy it to the hand-in folder on the P:\ drive for your section of COSC 310.

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

1.  List any siblings of a person who is a blood relative.  See James above.  If the person is a spouse of a blood relative, list the blood relative's siblings.

2.  List any children of the specified person.  See James above.  Below is an example, showing the output for Angie in which both of these extra credit elements are shown.

Angie is the wife of Matthew
Siblings of Matthew:  Mark  Daniel  Elizabeth
Children of Matthew:  Lane  Evan
Matthew is the son of Ken and Karen
Matthew is the grandson of Nelson and Margaret
Matthew is the great grandson of Lowell and Dorothy
Matthew is the great-great grandson of Henry and Adella

Following is the interface for a family tree class (named FTree) which I am providing for you in a file named ftree.h  This file is in the world-read folder for your section of COSC 310 on the P:\ drive.  With this class, I have also defined a Tnode class to create node objects for the family tree object you will need in your program.

template <typename Etype>
class Tnode
{
 public:
  Etype          info;
  Tnode<Etype>   *firstchild;
  Tnode<Etype>   *sibling;
  Tnode<Etype>   *parents;
  Tnode ();                    // Basic constructor
  Tnode (const Etype &);       // Constructor with data value
};

template <typename Etype>
class FTree
{
 private:
  Tnode<Etype> *root;                    // Pointer to root node
  void VisitAndDestroy(Tnode<Etype> *); // To erase subtree
  FTree(const FTree &);                 // Make copy constructor

 public:                                //  inaccessible
  class iterator;
  FTree();                              // Create empty tree
  FTree (const Etype &);                // Make single node tree
  ~FTree ();                            // Destroy tree
  bool empty () const;                  // Test for empty
  iterator begin() const;               // Set iterator to root
  iterator end() const;                 // Make iterator invalid
  iterator  insertL(iterator &, Etype &); // Add firstchild node
  iterator  insertR(iterator &, Etype &); // Add sibling node
  void erase (iterator &);              // Erase subtree

 class iterator        // Nested iterator
 {
  private:
   Tnode<Etype>  * current;           // Pointer to tree node
   iterator (Tnode<Etype> *)          // Make iterator point to a node

  public:
   friend class FTree<Etype>;         // Set relationship to tree
   iterator();                        // Make iterator for client
   bool operator == (iterator &);     // Compare iterators for =
   bool operator != (iterator &);     // Compare iterators for !=
                                      // Return reference to the
   Etype & operator* ();              //  data in the node
                                      // Return pointer to the
   Etype * operator-> ();             //  data in the node
                                      // Return iterator referencing
   iterator DownFirst ();             //  the firstchild node
                                      // Return iterator referencing
   iterator DownSibling ();           //  the next sibling node
                                      // Return iterator referencing
   iterator Up ();                    //  the parents node
 };
};