Question

Check the following classes and explain what each class does:

public class CompareTraits implements Comparator<TraitColumn> {
// Put the greater column at the beginning of the binary matrix

public int compare(TraitColumn t1, TraitColumn t2) {

int val1 = t1.getWeightedValue();
int val2 = t2.getWeightedValue();
return (val1 > val2) ? -1 : (val1 < val2) ? 1 : 0;

}
}

public class Parser {
private static Scanner scan;

public Parser(String file) {

try {
scan = new Scanner(new File(file)).useDelimiter("EOP\n");
} catch (IOException e) {
System.out.println(e);
}
}

public Phylogeny nextPhylogeny() {
return new Phylogeny(scan.next());
}

public Boolean hasPhylogeny() {
return scan.hasNext();
}
}

public class PhylogeneticTree {
private int id;
private String label;
private String leftEdgeLabel;
private String rightEdgeLabel;
private PhylogeneticTree left;
private PhylogeneticTree right;
private int children;

public PhylogeneticTree(String label) {
this.label = label;
id = 0;
children = 0;
}

// Adds a species path of traits to the Tree

public void addToTree(LinkedList<String> path, String speciesName) {
ListIterator<String> iterator = path.listIterator();
PhylogeneticTree tmp = this;

while (iterator.hasNext()) {
String nextEdgeLabel = iterator.next();
// First check if this trait already exists
if (tmp.getLeftEdgeLabel() == nextEdgeLabel) {
tmp = tmp.getLeftTree();
continue;
} else if (tmp.getRightEdgeLabel() == nextEdgeLabel) {
tmp = tmp.getRightTree();
continue;
}
// If we get this far, it means we need to add the label, check if
// we can add on either side
if (tmp.getLeftTree() == null) {
String nodeLabel = (nextEdgeLabel == "%") ? speciesName : null;
tmp.setLeftTree(new PhylogeneticTree(nodeLabel), nextEdgeLabel);
tmp = tmp.getLeftTree();
} else if (tmp.getRightTree() == null) {
String nodeLabel = (nextEdgeLabel == "%") ? speciesName : null;
tmp.setRightTree(new PhylogeneticTree(nodeLabel), nextEdgeLabel);
tmp = tmp.getRightTree();
}
}
}

// Below are all the standard getter and setter methods

public void setLeftTree(PhylogeneticTree leftTree, String edgeLabel) {
if (left == null) {
children++;
}
left = leftTree;
leftEdgeLabel = edgeLabel;
}

public void setRightTree(PhylogeneticTree rightTree, String edgeLabel) {
if (right == null) {
children++;
}
right = rightTree;
rightEdgeLabel = edgeLabel;
}

public int getCountChildren() {
return children;
}

public PhylogeneticTree getLeftTree() {
return left;
}

public PhylogeneticTree getRightTree() {
return right;
}

public void setLeftEdgeLabel(String label) {
leftEdgeLabel = label;
}

public void setRightEdgeLabel(String label) {
rightEdgeLabel = label;
}

public String getLeftEdgeLabel() {
return leftEdgeLabel;
}

public String getRightEdgeLabel() {
return rightEdgeLabel;
}

public String getLabel() {
return label;
}

public void setLabel(String label) {
this.label = label;
}

public void removeLeftTree() {
left = null;
}

public void removeRightTree() {
right = null;
}

public void setId(int id) {
this.id = id;
}

public int getId() {
return id;
}
}

public class Phylogeny {
// name
private String name;

// Traits

private String[] traits;

// Species

private Species[] species;

// The Binary Matrix, consisting of columns of traits

private TraitColumn[] binary_matrix;

private Boolean perfect;

private PhylogeneticTree tree;

public Phylogeny(String species_traits) {
build(species_traits);
}

// Stores:
// All Species and their Traits
// A Distinct List of Traits

private void build(String species_traits) {
// Temporary Storage for Traits and Species
HashSet<String> traits = new HashSet<String>(200);
LinkedList<Species> species = new LinkedList<Species>();

String[] lines = species_traits.split("\n");
for (int i = 0; i < lines.length; i++) {
Species s = new Species();
String[] parts = lines[i].split(",");
// First string is species.
s.setName(parts[0]);
// Add all the Species' Traits
for (int j = 1; j < parts.length; j++) {
if (!traits.contains(parts[j])) {
traits.add(parts[j]);
}
s.addTrait(parts[j]);
}
species.add(s);
}
// Populate our Phylogeny's Species Array
ListIterator<Species> s_iterator = species.listIterator();
this.species = new Species[species.size()];
int i = 0;
while (s_iterator.hasNext()) {

this.species[i] = s_iterator.next();
i++;
}
// Populate our Phylogeny's Traits Array
Iterator<String> t_iterator = traits.iterator();
this.traits = new String[traits.size()];
i = 0;
while (t_iterator.hasNext()) {
this.traits[i] = t_iterator.next();
i++;
}
}

// Builds a Sorted Binary Matrix from the Phylogeny's Species and Trait data

public void buildBinaryMatrix() {
binary_matrix = new TraitColumn[traits.length];
for (int i = 0; i < traits.length; i++) {
Boolean[] tempArray = new Boolean[species.length];
for (int j = 0; j < species.length; j++) {
tempArray[j] = species[j].hasTrait(traits[i]);
}
binary_matrix[i] = new TraitColumn(traits[i], tempArray);
}
Arrays.sort(binary_matrix, new CompareTraits());
// Set if the Phylogeny is Perfect
checkPerfect();
}

// Builds the paths of traits from the Phylogeny's Binary Matrix

public void buildPaths() {
for (TraitColumn trait : binary_matrix) {
for (int i = 0; i < trait.getSpecies().length; i++) {
if (trait.getSpecies()[i]) {
species[i].addToPath(trait.getTrait());
}
}
}
// Symbolize the end of the path
for (Species singleSpecies : species) {
singleSpecies.addToPath("%");
}
}

// Construct the Tree Data Structure

public void buildTree() {
tree = new PhylogeneticTree(null);
// Add each Species to the Pathh
for (Species singleSpecies : species) {
tree.addToTree(singleSpecies.getPath(), singleSpecies.getName());
}
}

// Removes all the % signs

public void pruneTree() {
inOrderPrune(tree);
}

// Saves the Tree to a DOT file

public void saveTree() {
FileWriter outFile = null;
try {
outFile = new FileWriter(name + ".dot");
} catch (IOException e) {
e.printStackTrace();
}
PrintWriter out = new PrintWriter(outFile);
// Start our DOT file
out.println("digraph " + name + " {");
out.println("size=\"8,11\";");
out.println("node [shape=point];");
out.println("edge [arrowhead=none];");
inOrderSave(tree, out, 1);
out.println("}");
out.close();
}

// An Inorder Traversal of the Tree, assigning an ID to each Node so that a
// file can be generated.

private int inOrderSave(PhylogeneticTree t, PrintWriter out, int index) {
if (t.getLeftTree() != null) {
index = inOrderSave(t.getLeftTree(), out, index);
}
if (t.getId() == 0) {
t.setId(index);
index++;
if (t.getLabel() != null) {
out.println(t.getId() + "[shape=ellipse,label=" + t.getLabel()
+ "];");
}
if (t.getLeftTree() != null) {
String label = (t.getLeftEdgeLabel() != "") ? "[label="
+ t.getLeftEdgeLabel() + "]" : "";
out.println(t.getId() + "->" + t.getLeftTree().getId() + label
+ ";");
}
}

if (t.getRightTree() != null) {
index = inOrderSave(t.getRightTree(), out, index);
}

if (t.getRightTree() != null) {
String label = (t.getRightEdgeLabel() != "") ? "[shape=ellipse,label="
+ t.getRightEdgeLabel() + "]"
: "";
out.println(t.getId() + "->" + t.getRightTree().getId() + label
+ ";");
}

return index;
}

// An Inorder Traversal of the Tree, removing any unnecessary edges or
// nodes.

private void inOrderPrune(PhylogeneticTree t) {
if (t.getLeftTree() != null) {
inOrderPrune(t.getLeftTree());
}

if (t.getLeftEdgeLabel() == "%") {

if (t.getCountChildren() == 2) {
t.setLeftEdgeLabel("");
} else {
t.setLabel(t.getLeftTree().getLabel());
t.removeLeftTree();
}
} else if (t.getRightEdgeLabel() == "%") {
if (t.getCountChildren() == 2) {
t.setRightEdgeLabel("");
} else {
t.setLabel(t.getRightTree().getLabel());
t.removeRightTree();
}
}
if (t.getRightTree() != null) {
inOrderPrune(t.getRightTree());
}
}

// Check if each pair of traits are compatible with one another.

private void checkPerfect() {
for (int i = 0; i < binary_matrix.length; i++) {
for (int j = i + 1; j < binary_matrix.length; j++) {
if (!binary_matrix[i].isPerfectWith(binary_matrix[j])) {
perfect = false;
return;
}
}
}
perfect = true;
}

public Boolean isPerfect() {
return perfect;
}

public void setName(String name) {
this.name = name;
}

public String getName() {
return name;
}
}

public class Species {

private String name;

// A Set of this Species' traits, used for quickly determining what traits
// this Species has.

private HashSet<String> traits;

// The path of Traits that lead to this Species in the Phylogeny

private LinkedList<String> path;

public Species() {
traits = new HashSet<String>();
path = new LinkedList<String>();
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public void addTrait(String c) {
traits.add(c);
}

public Boolean hasTrait(String t) {
return traits.contains(t);
}

public HashSet<String> getTraits() {
return traits;
}

public void setPath(LinkedList<String> path) {
this.path = path;
}

public LinkedList<String> getPath() {
return path;
}

public void addToPath(String trait) {
path.add(trait);
}
}

public class TraitColumn {

// The name of the trait

private String trait;

// An array of Booleans indicating if this trait is found in each species

private Boolean[] species;

// The integer representing this column of the binary matrix

private int weightedValue;

public TraitColumn(String name, Boolean[] species) {
this.trait = name;
this.species = species;
setWeightedValue();
}

private void setWeightedValue() {
weightedValue = 0;
int max_shift = species.length - 1;
for (int i = 0; i < species.length; i++) {
int bit = (species[i]) ? 1 : 0;
weightedValue |= bit << (max_shift - i);
}
}

// Checks if this column is perfect with respect to another column ahead of
// it using bitwise operations.
// 1.Use & to see if the other trait depends on this trait. If not, return
// true
// 2.If it is dependent, make sure it does not occur without this trait
// occurring first.

public Boolean isPerfectWith(TraitColumn other_trait) {

if ((weightedValue & other_trait.getWeightedValue()) != 0) {
int xor = weightedValue ^ other_trait.getWeightedValue();
int masked = xor & (~weightedValue);
return (masked == 0) ? true : false;
}
return true;
}

public int getWeightedValue() {
return weightedValue;
}

public String getTrait() {
return trait;
}

public Boolean[] getSpecies() {
return species;
}
}

public class Algorithm {
private static void buildPhylogeneticTree(Phylogeny p, int index) {
p.setName("case " + index);
p.buildBinaryMatrix();
if (!p.isPerfect()) {
System.out.println("Not a perfect phylogeny.");
return;
}
p.buildPaths();
p.buildTree();
p.pruneTree();
p.saveTree();
}

public static void main(String[] args)

{
// Get the file

Parser p = new Parser("species.input");

// Perform the algorithm
int i = 0;
while (p.hasPhylogeny()) {
System.out.println("Case " + i + ":");
buildPhylogeneticTree(p.nextPhylogeny(), i);
i++;
}
}
}

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

CompareTraits:
Simple method to compare two traits based on their weighted values. If t1 is greater than t2 return -1, or if t2 is greater than t1 return 1, else return 0.

Parser:
Simple class to just get phylogenies from a file that the user enters into the constructor. Simply returns the next scanned String from the file. Can also check the file if there are any more strings or phylogenies to scan.

PhylogeneticTree:
This class represents that hold a binary tree that holds all traits for all species. The first main function, addToTree(), takes a linkedlist of paths that represent a species traits. It traverses the tree using the linked list path and once it reaches an empty leaf of the tree it adds a new node based on the species name that was passed in or a null. This takes O(n) time because it is possible to have a binary tree where each node has only one child. setLeftTree and setRightTree are simple methods that just add a new child to a node in the tree. The rest of the functions are simple mutators and accessors....

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Java & UML Programming Problems
Homework Solution
$20.00
Java
UML
Programming
Coding
Computer Science
Fraction
Denominator
Numerator
Big Integers
Printing Outputs
Decimal Values
Arithmetic Operations
Java Program And UML Diagram For Divers
Homework Solution
$20.00
Java
Programming
Computer Science
Coding
Divers
Testers
UML Diagram
Methods
Loops
Statements
Average Scores
Variables
Input Files
Output Files
Contest
Winner
Records
Data Sets
Java Problems: Euclidean Distance and Arrays
Homework Solution
$20.00
Java
Programming
Computer Science
Coding
Euclidean Distance
Reversing an Array
String Values
Integer Values
Boolean Arrays
Input
Output
Square Root
Sum of Squares
Mathematics
Vectors
Rows
Columns
Builder Dash Game in Java
Homework Solution
$163.00
Java
Programming
Computer Science
Codes
Algorithms
Classes
Timers
Statements
Variables
Moves
Instances
Graphics
Animations
Get help from a qualified tutor
Live Chats