CS 241 Lab 4: Royal Succession Order

Order of Succession in the Royal Family of Femenye

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:

• Read in the name of the file and open it up (or generate an error message if it can't be found).
• Read in the Queen’s name and create a new tree with her as the root (i.e., a new node with the Queen’s name and date; you’ll also want to enter this node into a HashMap using the name as a key).
• Continue reading in mother-daughter pairs (with birth years), creating a node for each, and entering it into the tree by searching for the appropriate place (by year) among the daughters of the given mother (you can find the mother’s node to start with by using the hash map to look her up). You’ll also want to enter each node into the hash map, i.e., at the same time you create it and insert it into the tree.

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:

• Create an empty queue.
• Start with the Queen (you will have a reference to her node as the root of the tree), adding her node to the queue.
• Using a while loop until the queue is empty, and repeatedly:
  • remove a node;
  • print the name in the node;
  • enqueue all the children of the node, in left-to-right order.

Regarding data structure implementations:

• You can implement the general tree using the first-child/next-sibling technique shown in the textbook. (This makes particular sense in the context of a family tree, since the tree terminology matches up exactly with the genealogical terminology!)
• You can implement a queue using a linked list with pointers to both the head and the tail items: note that this is much easier than using an array!
• You are hereby given permission to use the Java library implementation of hash map! We will try to cover hash map implementations in lecture, but you should at least be able to use an existing implementation.
  Just in case, here is a link to a short tutorial on using HashMaps.

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” for historical reasons; use Python dictionaries in your code!)

… and here’s another diagram with some more helpful implementation hints:

Acknowledgements

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