Java Programming Question: Background: Phylogenetic Trees A phylogenetic (or evolutionary) tree represents the evolution of species over time. Each node in the tree corresponds to a species and parent-child relationship represents an evolution from one species to another. Scientists build such trees based on genetic and fossil data, indicating that one species evolved from another. In particular, given a sequence of statements of the form X evolved from Y, a computer can be used to build a phylogenetic tree. Problem: Generating a Phylogenetic Tree Given a series of statements of the form X evolved from Y, where X and Y denote species, construct a corresponding phylogenetic tree. The tree should then be displayed in a manner similar to the output in Assignment 3. For example, given the input leeches evolved from flatworms cecil evolved from snakes monkeys evolved from one-celled forms lochness monster evolved from snakes snakes evolved from one-celled forms flatworms evolved from one-celled forms fung evolved from sponges sponges evolved from one-celled forms end Figure 2: Sample phylogenetic data. the result phylogenetic tree would look like: one-celled forms |-flatworms | |-leeches |-monkeys |-snakes | |-cecil | |-lochness monster |-sponges | |-fung Figure 3: A representation a phylogenetic tree generated from data in Figure 2 Your task is to create a program that generates phylogenetic tree based on phylogenetic data and output a representation of the tree. Write a program called EvoTree.java that reads in phylogenetic data from the console (System.int) and outputs the corresponding phylogenetic tree. Your EvoTree class must implement the provided Tester interface and also contain the main() method where your program starts running. This is because your program will be tested via this interface. The interface contains a single method: public ArrayList compute( Scanner input ); This method must perform the required computation. Input The compute() method takes a Scanner object, which contains one or more lines. Each line, except the last one, is of the form Species A evolved from Species B where Species A and Species B are names of specific species. The species names can comprise one or more words, but will never contain the words evolved from. The last line of input is simply the word end. See Figure 2 for an example. Hint: Use the nextLine() method of the Scanner object to read one line of input at a time, and then parse the line. See the solution for Assignment 1 for how to parse input one line at a time. Semantics Each line of the form Species A evolved from Species B represents a direct evolution from species B to species A. The input lines are in arbitrary order. All data will generate a single tree. That is, there will only be one species that is not evolved from some other species (the root of the tree). Each species (except the root) will be evolved from exactly one species, but multiple species may evolve from a single species, as in the example. (This is a simplification.) Output The method compute( Scanner input ) should return an ArrayList of Strings denoting the phylogenetic tree. Each species should be a separate String. All children of a node in the tree are to be displayed in lexically sorted order. Each species should be prefixed with d 1 | followed by |- followed by the species name where d is the depth of the node and denotes a space. This is exemplified in Figure 3. Example Sample Input Sample Output leeches evolved from flatworms one-celled forms cecil evolved from snakes |-flatworms monkeys evolved from one-celled forms | |-leeches lochness monster evolved from snakes |-monkeys snakes evolved from one-celled forms |-snakes flatworms evolved from one-celled forms | |-cecil fung evolved from sponges | |-lochness monster sponges evolved from one-celled forms |-sponges end Hints and Suggestions The sample solution uses a 2-pass algorithm. The first pass builds the phylogenetic tree. This can be done iteratively. The second pass recursively outputs the tree. Test Program using these Classes Below: import java.util.ArrayList; import java.util.Scanner; public interface Tester { // This method takes a Scanner object contianint the input // and returns an ArrayList object containing the output. // // Parameters: // Scanner input: is a Scanner object that is a stream of text // containing the input to your program. // // Returns: an ArrayList of Strings. Each string is a line of output // from your program. public ArrayList compute( Scanner log ); } import static org.junit.jupiter.api.Assertions.*; import java.util.ArrayList; import java.util.Scanner; import org.junit.jupiter.api.Test; class EvoTreeTest { private static String testInput0 = "end"; private static String [] testOutput0 = {}; private static String testInput1 = "Human evolved from Ameoba " + "end"; private static String [] testOutput1 = { "Ameoba", "|-Human" }; private static String testInput2 = "Homo Sapien evolved from Homo Ergastur "+ "end"; private static String [] testOutput2 = { "Homo Ergastur", "|-Homo Sapien" }; private static String testInput3 = "Human evolved from Ergastur " + "Ergastur evolved from Ameoba " + "end"; private static String [] testOutput3 = { "Ameoba", "|-Ergastur", "| |-Human" }; private static String testInput4 = "Ergastur evolved from Ameoba " + "Human evolved from Ergastur " + "end"; private static String [] testOutput4 = { "Ameoba", "|-Ergastur", "| |-Human" }; private static String testInput5 = "Human evolved from Ameoba " + "Koala evolved from Ameoba " + "end"; private static String [] testOutput5 = { "Ameoba", "|-Human", "|-Koala" }; private static String testInput6 = "Koala evolved from Ameoba " + "Human evolved from Ameoba " + "end"; private static String [] testOutput6 = { "Ameoba", "|-Human", "|-Koala" }; private static String testInput7 = "Koala evolved from Ameoba " + "Ergastur evolved from Ameoba " + "Human evolved from Ergastur " + "end"; private static String [] testOutput7 = { "Ameoba", "|-Ergastur", "| |-Human", "|-Koala" }; private static String testInput8 ="leeches evolved from flatworms " + "cecil evolved from snakes " + "monkeys evolved from one-celled forms " + "lochness monster evolved from snakes " + "snakes evolved from one-celled forms " + "flatworms evolved from one-celled forms " + "fung evolved from sponges " + "sponges evolved from one-celled forms " + "end "; private static String [] testOutput8 = { "one-celled forms", "|-flatworms", "| |-leeches", "|-monkeys", "|-snakes", "| |-cecil", "| |-lochness monster", "|-sponges", "| |-fung" }; private static Scanner mkTest( String input ) { return new Scanner( input ); } private static ArrayList mkOutput( String [] output ) { ArrayList al = new ArrayList(); for( String s : output ) { al.add( s ); } return al; } private static boolean doTest( String input, String [] output ) { Tester t = new EvoTree(); ArrayList al = t.compute( mkTest( input ) ); System.out.println( "Input: " ); System.out.println( input ); System.out.println( "Generated output" ); for( String s : al ) { System.out.println( s ); } System.out.println( "Expected output" ); for( String s : output ) { System.out.println( s ); } System.out.println( "---------------------------------------------------" ); return al != null && al.equals( mkOutput( output ) ); } @Test void testEmpty() { assertTrue( doTest( testInput0, testOutput0 ), "Empty test" ); } @Test void test1() { assertTrue( doTest( testInput1, testOutput1 ), "One level test" ); } @Test void test2() { assertTrue( doTest( testInput2, testOutput2 ), "Multi-word species test" ); } @Test void test3() { assertTrue( doTest( testInput3, testOutput3 ), "Multilevel tree test" ); } @Test void test4() { assertTrue( doTest( testInput4, testOutput4 ), "Multilevel tree test" ); } @Test void test5() { assertTrue( doTest( testInput5, testOutput5 ), "Ordering test (order ok)" ); } @Test void test6() { assertTrue( doTest( testInput6, testOutput6 ), "Ordering test (reorder)" ); } @Test void test7() { assertTrue( doTest( testInput7, testOutput7 ), "Indentation test" ); } @Test void test8() { assertTrue( doTest( testInput8, testOutput8 ), "Assignment example" ); } }