To accomplish this task, you will be given an instance of the Relationships class, which describes the relationships between people. There are a number of methods which you will be using in order to accomplish your task:

residents() which returns a list of resident names (as strings), List, of the form Last, First

distance(String, String) which returns the distance between the two specified residents

Do not assume that distances are symmetric! Resident Pomerville, Scott might have a distance of 2 to resident Hiebel, Jason, and resident Hiebel, Jason might have a distance of 4 to resident Pomerville, Scott. Why you might ask? Because Scotts office is on the 3rd floor and Jasons office is on the 1st, so Jason would have to go up two floors and that costs more than going down two floors.

We will provide a simple Tree interface which has methods for four tree traverals: Breadth-First, Depth-First, Preorder, and Postorder.

public interface Tree { public List preorderTraversal(); public List postorderTraversal(); public List breadthTraversal(); public List depthTraversal(); } 

You are responsible for completing the class ZombieInfectionTree which models the spread of the zombie infection as a tree as described above. ZombieInfectionTree must implement our Tree interface, and you may not modify the Tree interface in any way. You will provide a static method, createModel which will take the relationships and patient zero and construct the ZombieInfectionTree. You are responsible for implementing the tree data structure required for zombie bites and the four tree traversals.

public class ZombieInfectionTree implements Tree { \\ build your ZombieInfectionTree public List preorderTraversal(); public List postorderTraversal(); public List breadthTraversal(); public List depthTraversal(); public static ZombieInfectionTree createModel(Relationships houghton, String patient0) { \\ create and return a ZombieInfectionTree } } 

It is your responsibility to build a tree structure for this problem. Your program will be graded based on the final results of the tree construction using the traversals.

You are allowed (and encouraged) to use the data structures provided by java.util in order to complete this assignment. External libraries may not be used.

Case Study

To get you started, lets consider a simple example using the 1122 staff.

ZombiePanic.java - A sample main program

import java.util.*;

public class ZombiePanic {

public static void main(String[] args) {

List residents = Arrays.asList(

"Hiebel, Jason",

"Pommerville, Scott",

"Stomberg, Josh",

"Ureel, Leo"

);

double[][] distances = {

{0.0, 4.5, 0.5, 5.0},

{2.5, 0.0, 2.5, 3.5},

{0.5, 3.5, 0.0, 3.0},

{1.0, 2.5, 1.0, 0.0}

};

Relationships cs1122 = new Relationships(residents, distances);

for(String resident : cs1122.residents()) {

ZombieInfectionTree model =

ZombieInfectionTree.createModel(cs1122, resident);

System.out.printf("-- %s%n", resident);

System.out.printf("%s: %s%n", "Preorder ",

model.preorderTraversal());

System.out.printf("%s: %s%n", "Postorder ",

model.postorderTraversal());

}

}

}

Relationships.java - A sample Relationships class

import java.util.*;

public class Relationships {

private List residents;

private Map> distances;

public Relationships(List residents, double[][] distances) {

this.residents = Collections.unmodifiableList(residents);

this.distances = new HashMap();

for(int x = 0; x

Map toMap = new HashMap();

for(int y = 0; y

toMap.put(this.residents.get(y), distances[x][y]);

}

this.distances.put(this.residents.get(x), toMap);

}

}

public List residents() {

return residents;

}

public double distance(String rs, String re) {

return distances.get(rs).get(re);

}

}

Tree.java - The Tree interface

We have four people:

Hiebel

Pomerville

Stomberg

Ureel

We will use the following table of distances for our calculation:

Zombie\Target	Hiebel	Pomerville	Stomberg	Ureel
Hiebel	0.0	4.5	0.5	5.0
Pomerville	2.5	0.0	2.5	3.5
Stomberg	0.5	3.5	0.0	3.0
Ureel	1.0	2.5	1.0	0.0

If patient zero is Hiebel, then the following events happen:

On day 1: Hiebel (dist=0.5) chooses Stomberg as a victim and infects him.

On day 2: Hiebel (dist=4.5) chooses Pomerville as a victim and infects him; Stomberg (dist=3.0) choose Ureel as a victim and infects him.

On day 3: everyone is already infected.

If patient zero is Pomerville, then the following events happen:

On day 1: Pomerville (dist=2.5) chooses Hiebel as a victim and infects him.

On day 2: both Pomerville (dist=2.5) and Hiebel (dist=0.5) choose Stomberg as a victim. Hiebel infects him.

On day 3: Pomerville (dist=3.5), Hiebel (dist=5.0), and Stomberg (dist=3.0) choose Ureel as a victim. Stomberg infects him.

On day 4: everyone is already infected.

Running our sample code we get the following output:

-- Hiebel, Jason Preorder : [Hiebel, Jason, Stomberg, Josh, Ureel, Leo, Pomerville, Scott] Postorder : [Ureel, Leo, Stomberg, Josh, Pomerville, Scott, Hiebel, Jason] -- Pomerville, Scott Preorder : [Pomerville, Scott, Hiebel, Jason, Stomberg, Josh, Ureel, Leo] Postorder : [Ureel, Leo, Stomberg, Josh, Hiebel, Jason, Pomerville, Scott] -- Stomberg, Josh Preorder : [Stomberg, Josh, Hiebel, Jason, Pomerville, Scott, Ureel, Leo] Postorder : [Pomerville, Scott, Hiebel, Jason, Ureel, Leo, Stomberg, Josh] -- Ureel, Leo Preorder : [Ureel, Leo, Hiebel, Jason, Stomberg, Josh, Pomerville, Scott] Postorder : [Stomberg, Josh, Hiebel, Jason, Pomerville, Scott, Ureel, Leo]