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

Tic-Tac-Toe Program in Java
Homework Solution
$40.00
Programming
Java
Coding
Tic-Tac-Toe
Game Development
Array
Private Data Members
Board
Players
Public Data Members
UML Diagram
Statements
Variables
Wins
Loses
Ties
Directed Graph in Java
Homework Solution
$40.00
Java
Programming
Codes
Algorithms
Graphs
Nodes
Edges
Dept-First-Search
Statements
Variables
Loops
Variables
Input
Output
Java Programming Problems
Homework Solution
$30.00
Java
Programming
Computer Science
Arrays
Fractions
Variables
Strings
Numerator
Denominator
Statements
Constructor
Object
Initialization
Java Program For Restaurants
Homework Solution
$18.00
Java
Restaurants
Computer Science
Programming
Tips
Variables
Functions
Dollar Amounts
Functions
Input
Output
Statements
Multiplication
Bills
Percentage
Division
NumberFormat Class
Simple Calculator in Java
Homework Solution
$25.00
Programming
Computer Science
Java
Calculator
Mathematics
Operations
Variables
Statements
Functions
Methods
Strings
Integers
Sentences
Expressions
Wrong Inputs
Errors
Simple & Compound Interest Using Java
Homework Solution
$65.00
Java
Programming
Codes
Algorithms
Computer Science
Statements
Variables
Loops
Input
Output
Integers
Strings
Simple Interest
Compound Interest
Money
Finance
Annual Rates
Calculations
Functions
Screen Messages
Get help from a qualified tutor
Live Chats