You are going to create a family history program that will exercise your ability to work with maps and give you a chance to try using recursion.

You will write a program that performs the following functions:

1. Prompt the user for a filename, read in family history data from the file, and store it in a map. The key of the map is the ID string and the associated values are Person objects. Each person in the data file will have personal information along with an identifier for a father and mother.
2. Prompt the user for a last name and then print names and IDs for all people with the associated last name.
3. Prompt the user for an ID and print out a pedigree chart for that person and a family group sheet.

Each line will look something like this.

FirstName LastName Identifier FatherIdentifier MotherIdentifier BirthYear BirthCity, BirthState, BirthCountry

So data for the Bush family might look like

George Bush 016873 001244 001243 1946 New Haven, Connecticut, USA
George Bush 001244 000364 000367 1924 Milton, Massachusetts, USA
Barbara Pierce 001243 000372 000298 1925 New York City, New York, USA
Jed Bush 07465 001244 001243 1947 Miami, Florida, USA
Mary Bush 17309 001244 001243 1948 Provo, Utah, USA
Martin Frank 99934 88845 17309 1968 Kanab, Utah, USA
Gary Haws 77745 99934 66623 1988 Nephi, Utah, USA
Margie Smith 000367 111023 111024 1926 Orem, Utah, USA
John Bush 000364 211023 211024 1927 Eugene, Oregon, USA
Wilma Flinstone 211024 311023 311876 1907 Sacramento, California, USA

You can download the file Bushfor this data to your program for initial testing, but you will want to create some additional test cases. Notice a few things:

• birthplaces may have spaces, so when you get to that part of the line you may want to read the remainder of the line (i.e. city, state, and country) into a single birthplace string.
• Barbara has a father and mother too, but they are not in this file.
• The two people named “George Bush” are different people (as it so happens, father and son. How do you know which is which?)
• You should create some test cases. Once you have your own test cases working, you can look at some of the sample data sets here (note that for each example, there is a link to the sample data set used).

The toString() function in your Person class should print out all of the information in the object. Note that you are never explicitly required to call this function in your code, but it can be very helpful for debugging purposes, which is why you should do it early on.

Prompt the user to enter a last name. Print the names and identifiers of those who have that last name. You will need to use an iterator to look at all of the entries in the map for the given last name.

Prompt the user to input an identifier and print out the pedigree for that person. For example, if the user selected identifier 016873 from our sample data, then the following pedigree would be printed. Your output need not be formatted exactly like this, but should be something intuitive (if this format is confusing, see the extra credit for a more complete version of this format):

Pedigree for: 016873 
      /--John Bush, 1927,  Eugene, Oregon, USA
         \--Wilma Flinstone, 1907,  Sacramento, California, USA
   /--George Bush, 1924,  Milton, Massachusetts, USA
      \--Margie Smith, 1926,  Orem, Utah, USA
--George Bush, 1946,  New Haven, Connecticut, USA
   \--Barbara Pierce, 1925,  New York City, New York, USA

See the sample data sets and their outputs for more examples.

Together with the pedigree you should print the family group sheet where that same person (016873 George Bush) appears as a child. You should print children who have the same mother and the same father as the target individual. Again, you are free to choose another format if you wish.

Father: George Bush Birth:  1924 Milton, Massachusetts, USA
Mother: Barbara Pierce Birth: 1925 New York City, New York, USA
Children:
     George Bush Birth: 1946 New Haven, Connecticut, USA
     Jed Bush Birth: 1947 Miami, Florida, USA
     Mary Bush Birth: 1948 Provo, Utah, USA

1. Plan out the elements in your Person object. Think about what data members will make your job easier.
2. Break your program into small pieces and test each of them to make sure it responds correctly given simple data that you can figure out by hand.
3. Again, take a look at the examples.

You should create some test cases. The TA will evaluate your program with the data sets found here. You will need to have downloaded the smallest and the largest of these data sets in order to pass-off.

The following grading criteria will be used:

1. You have created test cases for your program. (5 points)
2. You have a separate .cpp and .h file for your Person class. (5 points)
3. You have created a Person class with a toString() function. (5 points)
4. Given a last name, you can look up and display the identifiers for everyone with that last name. (5 points)
5. Given an identifier, you display the pedigree chart for that person correctly using recursion (find ancestors by looking up their person ID in the map). (10 points)
6. Given an identifier, you display the family group sheet for that person (find person by looking up with a Map). (8 points)
7. Your code is properly formatted. (2 points)

5 points extra credit: We would encourage you to make sure you are caught up in all your classes before you consider doing the extra credit. For extra credit, format the pedigree chart to include the branch lines:

         /--JAMES MORELAND, 1693,  Chino, California, USA
      /--DONALD MORELAND, 1720,  Hinckley, Utah, USA
      |  \--MARIE JONES, 1693,  Los Angeles, California, USA
   /--BRIAN MORELAND, 1754,  Truckee, California, USA
   |  |  /--MARK FOWLER, 1694,  Hyde Park, Utah, USA
   |  \--MELINDA FOWLER, 1722,  Los Angeles, California, USA
   |     \--EUNICE KEELING, 1701,  Orange, California, USA
--THOMAS MORELAND, 1795,  San Diego, California, USA
   |     /--ROY LAROSA, 1687,  West Valley City, Utah, USA
   |  /--FRANK LAROSA, 1717,  Cypress, California, USA
   |  |  \--MARY RINEHART, 1693,  Orem, Utah, USA
   \--DENISE LAROSA, 1758,  Lehi, Utah, USA
      |  /--MARTIN GRANTHAM, 1698,  Moreno Valley, California, USA
      \--STEFANIE GRANTHAM, 1723,  Cedar Hills, Utah, USA
         \--MEGAN CLAY, 1701,  West Valley City, Utah, USA

• You should print out the tree by telling each of your parents to print themselves out (and then each of your parents can tell their parents to print themselves out). Think about how you are going to traverse the tree before you start writing your code.