CS 241 Lab 4: Royal Succession Order

Order of Succession in the Royal Family of Femenye


News flash!

Here are data files with royal princess data: royals1.txt (same sample data as below) and royals2.txt.


The Royal Family of Femenye needs your help to determine the proper order of succession in the monarchy before the impending death of the current queen: sad events such as these are traditionally marked by a “night of long knives” in which many of the candidates to the throne are found mysteriously deceased. The royal seneschal hopes that by posting a public decree with the proper order of succession for all to see, some of this tragic but tired melodrama can be avoided.

Now as it happens, the monarchy of Femenye is also a matriarchy—the men of the royal family are in no danger, as they never rise to the level of monarch. So the rules of succession concern only the female half of the royal family tree. More specifically, the rules state that the eldest daughter of the current queen will succeed her, followed by her next eldest sister, and so on through the daughters of the current queen. If none of the daughters of the current queen are available to serve, the succession proceeds to the daughters of the “first daughter”, in order from oldest to youngest, then the daughters of the next eldest daughter of the current queen, etc.

For example, here is a picture from the royal archives of a recent family tree (women only, of course):

In this picture, the daughters of a given femme royale are shown beneath her and are connected to her by lines, in order from eldest to youngest, proceeding from left to right.

The royal seneschal tells you that, according to the rules, the order of succession here would be as follows (including the Queen herself just for completeness):

  1. Amarantha (the current queen)
  2. Bethesda (her eldest daughter)
  3. Callipygia
  4. Depilitoria
  5. Edna
  6. Flegma
  7. Ganache
  8. Hildegarde
  9. Indicia
  10. Jaundice
  11. Kalahari
  12. Ludmilla
  13. Miasma

(Note that the succession here just happens to follow in alphabetical order: this will not be true in general, but was done for this example to make it easier to follow.)

The Problem Statement

Your program should read in data from a file, as specified by the user in response to a prompt (e.g., “Please enter filename here: ”). The data in the file will be organized line by line, with no empty lines. The first line will always be just the name of the current queen and the date of her birth, more specifically an (integer) year. All subsequent lines will hold two names and a date (also an integer year). These first name is the name of a mother and the second the name of a daughter, with the year being the year the daughter was born.

The data in the file will always “make sense”: a mother’s name will always appear on an earlier line in the file (or on the first line as the queen) before it shows up on a line with any of her daughters. All the names will be a single word, with no hyphens or other punctuation, just letters. Furthermore, daughters will always be born at least one year apart (twins do not run in the Royal Family), so that it will be clear from their birth years what the order of daughters is, from eldest to youngest.

On the other hand, the royal archives are otherwise in such disarray that the data may come in what seems an odd order: for example, daughters of a given mother may appear “out of order,” and the listing of daughters of a given mother may be “interrupted” by the listing of several other mother-daughter pairs. So you will have some work to do in getting the data organized properly.

Programming Strategy

The basic idea you should follow, if it is not clear already, is to put the names into a general (multi-branch) tree based on order of age, and then to walk through this tree using a left-to-right, breadth-first traversal, printing the names as you go.

In a bit more detail, your strategy for reading the data and creating the tree should be as follows:

Once you have the data read and the tree built (using the hash map to find mother nodes), you can proceed to the breadth-first traversal of the tree:

Regarding data structure implementations:

A Visual Guide to Programming Strategy

Here’s a diagrammatic overview of the two main stages of the program:

(Note: the diagram uses the term “hash table” rather than hash map for historical reasons; use the more modern HashMap in your code!)

Acknowledgements

(Special thanks to author Lin Carter, RIP, for some of the naming ideas.)