Java Data Structure

Overview

Goals

The goals of this assignment are to:

• Understand, implement, and use a Tree node type to store data and children of a general tree.
• Understand, implement, and use a general tree to store ancestry information about researchers and their Principle Investigator (Professor).
• Implement Stack and Queue classes to be used in the algorithm to find the lowest common ancestor in the Ancestor Tree you create.
• Reuse your LinkedList and LinkedListIterator classes from your program 2 assignment.

Description

In this assignment, your goal is to build a genealogy tree of Ancestors by parsing a text file.  The input text file contains a list of parent-child relationships.  The parent is the primary investigator and the child is the researcher .  Once created, the genealogy tree will be used by a main program to find the least common ancestor of two scientists.  The least common ancestor is the common ancestor of two researchers that is closest to the to two researchers.   The researcher at the root is a common ancestor to all researchers in the tree.

The genealogy tree traces the history of each academician to his/her Ph.D. advisor. It consists of professors and students with a professor as a parent node and all his/her students as its children nodes. These students (who later become professors) can it turn have their own students as their children node.

Specifications

The assignment consists of the following files (skeleton files are provided for some classes in p4.zip):

• Ancestor.java – the main class that provides a user interface to the GenealogyTree .
• EmptyQueueException.java – a new exception type to be thrown when queues are empty
• GenealogyTree.java – a general tree class that stores (professor->student) pair relationships.
• TreeNode.java – the node that the GenealogyTree must use.
• LinkedList.java – class that implements the ListADT (get this from your Program 2).
• LinkedListIterator.java – the iterator class that the LinkedList iterator method returns (get this from your program 2).
• ListNode.java – the node type that the LinkedList must use
• ListADT.java – interface that LinkedList must implement.
• Queue.java – generic class that implements the generic QueueADT.  public Queue<T> implements QueueADT<T> { ... }
• QueueADT.java – interface the class Queue must implement.
• Stack.java – generic class that implements the generic StackADT.  public Stack<T> implements StackADT<T> { ... }
• StackADT.java  – interface that class Stack must implement.

ListADT.java, ListNode.java and LinkedListIterator.java are the same as in Assignment 2. Be sure to fix any errors that were in your p2 implementation.  The LinkedList must use the Listnode class and the LinkedListIIterator class.

You must define Stack, and Queue classes such that they correctly implement their respective ADTs.  The Stack and Queue classes must use an instance of the LinkedList class for their internal data structure.  Instances of the Stack and Queue classes will be used loading, traversing, and printing the tree.

The GenealogyTree class contains methods to build the genealogy tree by reading ancestor relationships from a file. All the relationships in the file are given in parent -> children format. The relationships are listed in the file in level-order.  The very first parent of the very first relationship will be the root of the genealogy tree.   Every new researcher (except the root) appearing in the file will first appear as a child of some other researcher already in the tree.

Sample input files

• input1.txt  – valid input file
• input_error.txt – looks okay, but it has a blank line at end, and blank lines cause file read errors
• p4_input.txt – larger file of professor -> student pairs
• test.txt – another sample input file to play with
• make your own sample input file to tests different conditions

Input Example

The input1.txt file contains the following lines (relationships):

a -> b
a -> c
a -> d
b -> e
d -> f
d -> g

Therefore, it will have a as the root researcher.  The root “a” will have three children b, c, d, and so on.

The tree created from the above input file would be:

Output Example

The GenealogyTree class contains a method to print the tree in pre-order traversal. The above tree would be printed as:

a
..b
....e
..c
..d
....f
....g

Sample Run #1 (user input)

java Ancestor input1.txt
(c)heck, (p)rint, (q)uit
p
a
..b
....e
..c
..d
....f
....g
(c)heck, (p)rint, (q)uit
c
Please input name 1
f
Please input name 2
g
Lowest common ancester is d
(c)heck, (p)rint, (q)uit
c
Please input name 1
b
Please input name 2
d
Lowest common ancester is a
(c)heck, (p)rint, (q)uit
x
Unrecognized command
(c)heck, (p)rint, (q)uit
c
Please input name 1
a
Please input name 2
p
Can not find name: p
(c)heck, (p)rint, (q)uit
c
Please input name 1
q
Please input name 2
e
Can not find name: q
(c)heck, (p)rint, (q)uit
c
Please input name 1
o
Please input name 2
x
Can not find name: o
Can not find name: x
(c)heck, (p)rint, (q)uit
good bye
Unrecognized command
(c)heck, (p)rint, (q)uit
q

Sample Run #2 (file does not exist)

java Ancestor no_file.txt
Error loading genealogy from file
Unable to initialize Ancestor

Sample Run #3 (file format error in file that does exist – input_error.txt has blank line at end)

java Ancestor input_error.txt
Error loading genealogy from file
Unable to initialize Ancestor

Sample Run #4 (one researcher is ancestor of the other)

java Ancestor input1.txt
(c)heck, (p)rint, (q)uit
p
a
..b
....e
..c
..d
....f
....g
(c)heck, (p)rint, (q)uit
c
Please input name 1
d
Please input name 2
g
Lowest common ancester is d
(c)heck, (p)rint, (q)uit
q

How to find the closest (lowest level) common ancestor

Ancestor.java contains the main method and methods to construct a GenealogyTree among other things.  It also contains the method(s) to find the closest (lowest level on tree) common ancestor of any two researchers in the tree.

1. Run the program with the command:  java Ancestor input.txt (where input.txt is a file with tree node relationship information)
2. Prompt for first researcher’s name
3. Prompt for second researcher’s name
4. Find ancestors of first researcher. The result should be a stack with root at bottom and researcher at top.  Tip: Do a pre-order traversal of the genealogy tree until researcher or end of tree is reached.  Return an empty tree if the researcher is not found by the time that end of the tree is reached.
5. Reverse the stack so that the “root” researcher is on the top and the researcher you were asked to find is on the bottom of the stack.
6. Repeat steps 4 and 5 for second researcher.
7. Compare the researchers listed in each stack until they do not match.  Report the last common ancestor that you found.

Documentation

The javadocs for all classes provided to you is here. You are expected to complete those sections of it marked as “//TODO”.

You may not add any other public methods than those listed in the provided files.

You may not modify any class in any way except where noted as “//TODO”.