Genealogical Research

These days, everyone seems to be exploring their ancestry. This effort is supported by fam- ily history software, now marketed by a num- ber of vendors. Unfortunately this software is expensive and runs only on the McDoze X oper- ating system. You are to write an open-source equivalent. Input Your program accepts a series of commands, one per line. The commands are described by the following syntax: command ::= birth ::= death ::= ancestors ::= descendants ::= QUIT birth ::= BIRTH child: date: mother: father death ::= DEATH person: date ancestors ::= ANCESTORS person descendants ::= DESCENDANTS person child ::= name mother ::= name father ::= name person ::= name date ::= name name ::= <> Spaces in the input are ignored except where they appear within name. The ‘BIRTH’ and DEATH commands record the birth and death of an individual. You may assume that each individual has a unique name. The ‘ANCESTORS’ and ‘DESCENDANTS’ commands are queries: they print a family tree or a reverse family tree for the named person, using the ‘BIRTH’ and DEATH information entered by previous commands. The ‘QUIT’ command indicates the end of input.

2/2 Output The ‘BIRTH’, ‘DEATH’, and ‘QUIT’ commands have no output. For each ‘ANCESTORS’ (‘DESCENDANTS’) command, print the following information:

1. Print a line containing ‘ANCESTORS of’ (‘DESCENDANTS of’) followed by the person’s name
2. Indented 2 spaces from the previous line, print the person’s first parent (child) in alphabetical order, followed by the parent’s (child’s) birth date, followed by a space, followed by a hyphen, and, if the parent (child) has died, another space and the date of death. If there is no birth record for the parent (child), print the name alone.
3. Print the ancestry (descendant) information for the parent (child), indented another 2 spaces, using these same steps (i.e. steps 2-4).
4. Repeat steps 2-4 for the remaining parent (children). Indentation should be the same as for the previous parent (child). Leave an empty line between the output sequences for successive commands. You may assume that no input line exceeds 100 characters, and that there are not more than 250 lines of input. You may assume that ‘DEATH’, ‘ANCESTORS’, and ‘DESCENDANTS’ commands refer to a name for which a ‘BIRTH’ command has previously been given. ‘QUIT’ appears only as the last line of input. Sample Input BIRTH John Doe : January 7, 1599 : Jane Doe : Adam Doe BIRTH Mary Worth : May 18, 1666 : Jane Doe : Adam Doe BIRTH Casper Ghost : Jan 2, 1959 : Mary Worth : John Doe DEATH Mary Worth : Jan 3, 1959 ANCESTORS Casper Ghost DESCENDANTS John Doe QUIT Sample Output ANCESTORS of Casper Ghost John Doe January 7, 1599 - Adam Doe Jane Doe Mary Worth May 18, 1666 - Jan 3, 1959 Adam Doe Jane Doe DESCENDANTS of John Doe Casper Ghost Jan 2, 1959 -