Description
Overview Implement, test, and compare alternate implementations of an abstract data type (ADT). The ADT is generic and defines operation for storing and retrieving (key, value) data pairs, where each key is Comparable and unique and has an associated value. Files Links are to files that can be downloaded individually or together in one file: p1.zip (https://canvas.wisc.edu/courses/202692/files/13055945/download?wrap=1) (contains all of these files and a couple of others) Given: interface DataStructureADT (https://canvas.wisc.edu/courses/202692/files/13055948/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13055948/download?wrap=1) – a generic interface for storing key,value pairs (DO NOT EDIT or SUBMIT) abstract class DataStructureADTTest (https://canvas.wisc.edu/courses/202692/files/13055949/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13055949/download?wrap=1) – super class for other test class (Must EDIT and SUBMIT) class DS_My (https://canvas.wisc.edu/courses/202692/files/13055950/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13055950/download?wrap=1) – class that will implement DataStructureADT (Must EDIT and SUBMIT) 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 2/9 class TestDS_My (https://canvas.wisc.edu/courses/202692/files/13055947/download?wrap=1) (https://canvas.wisc.edu/courses/202692/files/13055947/download?wrap=1) – a subclass of DataStructureADT that will test your DS_My (No need to edit) classes.zip (https://canvas.wisc.edu/courses/202692/files/13055952/download?wrap=1) – a compressed file containing several DS_ta.class files that each must be tested. DS_ta.class files are implementations of the interface created by the TAs and instructor for the spring 2020 version of CS400. (Do not DELETE, EDIT, or SUBMIT this file) p1.zip (https://canvas.wisc.edu/courses/202692/files/13055945/download?wrap=1) – a compressed file contain all of the above files. (If downloaded, it must be unzipped and installed as instructed below) Class Diagram (below) – a Unified Modeling Language (UML) style diagram provided to help you interpret and understand the relationships between various types (interfaces, abstract classes, and classes) of this project. The diagram shows that DataStructureADTTest is a super-abstract-class, and that there are multiple Test_DS classes that sub-class DataStructureADTTest and implement the abstract method createInstance(). This means that you must define test methods in the super-type and then define the createInstance() method for each sub-type. Note: It is because createInstance method is abstract (not defined) that the super-class is also abstract. Compare provided code with this diagram to help you understand how the design is reflected in a UML diagram. Note: The arrow is from the sub-class to its super-class because it is the sub-class that knows its super-class. 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 3/9 Requirements 1. Must implement interface DataStructureADT in class DS_My without using any built-in Java collection types. Use arrays or your own custom linked structures, not ArrayList, LinkedList or other built-in types. 2. Must leave the existing JUnit test methods and define new tests in DataStructureADTTest . (DataStructureADTTest is the abstract JUnit super-class that has a few example JUnit tests and 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 4/9 where you will add more tests.) 3. Must define the sub-class type TestDS_My and run this test class to test your implementation of interface DataStructureADT. 4. Must add new JUnit tests to DataStructureADTTest super-type. Add tests to ensure that your implementation works correctly. Rerun TestDS_My after each test add or edit. You may use Java’s built-in types ArrayList and LinkedList in the tests you write but not in your ADT implementation. 5. Must define new sub-class test types for each provided TA implementation: (Example: Must define TestDS_Sapan to test DS_Sapan, and so on. Hint: copy, paste, edit your TestDS_My) For each data structure implementation class provided in classes.zip, you must write a test class. In this case, we will be giving you many implementations to test so that means many test classes are required. However, we wish for the tests run for each test class to be the same. This is why we have designed this project to use inheritance. By inheriting tests from a super-type, we reduce the amount of code that needs to be written and still ensure that all implementations are tested with all tests. 6. Must run JUnit tests for all DS_types, and save screenshot(s) of test results 7. Must write a new class CompareDS that compares the performance of your implementation DS_My against any of one of the TA implementations that works (passes all of your tests). CompareDS must: 1. must be a public class named CompareDS in a file named CompareDS.java 2. must contain a public static void main(String [] args) method that does not require user input to run 3. must output the names of the classes being compared 4. must produce some output that describes your performance test using DS_My for a very large number of inserts and retrievals (large is 1,000,000,000 or more) and do the same comparison for a TA class being compared. 5. Output must display a brief description of the work done for each trial, run multiple trials for each data structure and data set size. At a minimum, compare the time it takes to do the work for N items where the test is run and reported for both implementation for values of N equal to 100, 1000, 10000, 100000. YOU DO NOT HAVE TO MATCH THIS EXAMPLE OUTPUT, just include the same or similar information: CompareDS.main Compares work time for: DS_My and DS_ta-name-here Description: DS_My is doing work for 100000 values It took 28131728 ns to process 100000 items DS_TA is doing work for 100000 values It took 1831728 ns to process 100000 items 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 5/9 Tip: You can use these Java functions to get the current time in nano seconds and then compute the elapsed time between a saved start time and a new end time. long startTime = System.nanoTime(); // work code to be timed for a single run long endTime = System.nanoTime(); You may notice a wide variation between runs. Multiple attempts will give you best idea about how long it takes on average, but you do not have to store or compute average run times for comparison. Note: You are given TA implementations of the ADT in the form of Java byte-code (class) files. You will need to extract the classes.zip file into a classes folder and edit Eclipse project’s build configuration to mark that folder as an “external folder” before you can use them in your code. See details below. Instructions CAUTION: the class files were compiled using Java v11, they will not compile if you are still using Java 8. Using the JUnit framework means that you can focus on what tests to define and how to define them. When you run JUnit tests in Eclipse you get a graphic display showing green for passed tests and red for tests that failed. Here are the steps to create an Eclipse project that can run JUnit 5 tests. Different IDEs will likely have similar, but different instructions. The green highlights indicate instructions that students like to skip. Please read and follow these instructions. 1. Get provided code to compile and run 1. Create a New Java Project: File -> New -> Java Project 1. Do not use separate src and bin folders. 2. Disable module-info.java creation. 3. For even more details on creating projects in Eclipse: p1 Getting Started In Eclipse (https://canvas.wisc.edu/courses/202692/pages/p1-getting-started-in-eclipse) 2. Add a JUnit Test class: File -> New -> JUnit Test Case 1. remove the package name from the wizard dialog 2. select the “New JUnit Jupiter Test” option, then Finish 3. select “Add JUnit 5 library to Build Path”, then Finish 4. We will not need this TestClass, so it can be deleted from the project. 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 6/9 3. Copy the assignment starter files to your project folder (p1.zip (https://canvas.wisc.edu/courses/202692/files/13055945/download?wrap=1) contains all files) 1. download p1.zip (https://canvas.wisc.edu/courses/202692/files/13055945/download?wrap=1) to your Eclipse project folder 2. unzip p1.zip (you should have java files, a Makefile, and classes.zip file) 1. If the files were placed in a sub-folder p1, move all files up one directory to the project folder. 3. unzip classes.zip (if you do not have a classes folder with DS_*.class files already present) 4. Get provided code to compile. 1. Add unimplemented methods to DS_My 2. Add stub (fake) return values as needed for each unimplemented method to compile. 3. Resolve any other compiler problems before continuing. 5. Run the TestDS_My test class 1. Double-click to open the TestDS_My.java file in the Eclipse editor. 2. Run -> Run As -> JUnit Test 3. If the above steps do not work, try 1. right-click on your project 2. choose Refresh 3. Repeat Note: An alternative way is to download the JUnit 5 library and place a copy of the junit-platform-console-standalone-1.5.2.jar in your project folder. This step should not be necessary with Java v11. This file is also included in the p1.zip file. If you wish to try this option, you will likely need to add this file to the build path: 1. Right-click on the jar file 2. Select Build Path 3. Select Add to Build Path 2. Define required Tests in the DataStructureADTTest class Now, that your project is setup, you are ready to add tests in the DataStructureADTTest class. We have some required tests to help you get started. Complete the DataStructureADTTest class that has been started for you. This class includes comments to help guide your work at the start. But, it is not complete. There is one complete test and you must define tests as described here and you must define additional tests to detect any problems. Recall: sequences that should throw exceptions must also be tested. ProTip: Try running and check your tests after each test edit and update. These tests have been provided to help you understand the test pattern: 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 7/9 1. test01_insert_one() – insert one key value pair into the data structure and then confirm that size() is 1. Tip: use a call to fail(“message string”) or assertEquals(leftsidevalue,rightsidevalue) to get it count as a fail. If no fail occurs, it counts as a pass. 2. test02_insert_remove_one_size_0() – insert one key,value pair and remove it, then confirm size is 0. 3. test03_duplicate_exception_thrown – insert a few key,value pairs such that one of them has the same key as an earlier one. Confirm that a RuntimeException is thrown. 4. test04_remove_returns_false_when_key_not_present – insert some key,value pairs, then try removing a key that was not inserted. Confirm that the return value is false. These tests must be written by you: 1. test05_insert_remove_one – inserts one item and fails if unable to remove it 2. test06_insert_many_size – inserts many items and fails if size is not correct 3. test07_ duplicate_values – inserts two pairs with different keys, but same values; fails if second doesn’t insert 4. TODO: add more tests to ensure that you can detect implementations that fail in some other way(s). Tip: consider different sequences of inserts and removes. Check results of method like: size(), get(), contains(), remove(). Can you figure out if those methods work or not? Run your tests on the DS_My class by running the TestDS_My JUnit test class. Open the file and click the run button. Assuming that you have not yet completed your version, we expect most tests to fail. 3. Complete DS_My (your class implementation) Implement your own data structure in the class DS_My. Be sure that DS_My implements DataStructureADT and does not have any public or package level fields or inner classes. You should also keep you methods private, except for the ones that implement methods from the interface DataStructureADT. As you implement each method in the class, run your TestDS_My class. You should be able see more and more tests passing as your implementation is completed. This process may also help you to identify new things to test for. WARNING: Your DS_My may not use any Java Collection classes as internal data members. You must implement using your own arrays, linked lists, or other. Your DS_My implementation may use String for key type and String for value type. 4. Add classes as an external class folder You will need to do more configuration, to add TA implementation classes as external folder. 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 8/9 Your project should have a classes folder that will contain the TA implementations that must also be tested. You must add this folder as an “External Class Folder”. Don’t worry if the files are GONE. Eclipse deletes class files that do not have a corresponding source file until you place them in a folder that is designated as an external class folder. Just keep unzipping and re-copying them into your project’s classes folder as needed until you get the project configuration correct with classes as an external folder. 1. Right-click the “classes” folder within your project folder 2. Select Build-Path -> Configure Build Path 3. Select Libraries tab 4. Select “Add External Class Folder” 5. Find the classes folder in the project workspace 6. Apply and Close 7. Now, you can extract the files from classes.zip into the classes folder and they will not be deleted by Eclipse. 5. Create TestDS_* classes for each sub-class of DataStructureADTTest To test each TA class, you must make a new sub-class of the DataStructureADTTest class for each Test class. 1. Right-click the TestDS_My class 2. Click Ctrl-C to copy 3. Click Ctrl-V to paste the copy in the same folder 4. Set the name as TestDS_TaName (where TaName is replaced with the particular TA implementation to be tested 5. Edit the source code in the newly created class so that it constructs an instance of the particular DS_ type 6. Save and repeat for all other DS implementations 6. Try running your tests on the TA implementation classes 1. Open and run each TestDS_ class independently to test that test class. 2. If the compiler complains that it can not find the various DS_TaName types, you may need to unzip the class files into the classes folder again. See or repeat Step 4 for this folder. 7. Save a Screenshot of your test results After you complete your tests, make the additional Test classes, and complete your implementation in DS_My , run All Tests and take a screen shot of the results. Edit the Run Configuration to run all tests at once. 2020/12/2 p1 Implement and Test an ADT: COMPSCI400: Programming III (002) DHH SU20 https://canvas.wisc.edu/courses/202692/pages/p1-implement-and-test-an-adt 9/9 1. Run -> Run Configurations 2. Select “Run All Tests” from the configuration dialog 3. Name the configuration “Run All Tests” 4. Apply and run the tests 5. Take a screenshot of your test results (they must be your results) and name it screenshot.png. Make sure that you include all your test results in the screenshot(s) (pass / fail for each test method in the suite) and the overall results (number of passed and failed tests). 8. Add additional tests to DataStructureADTTest This is an individual project and each student must figure out their own tests for this assignment. These ideas will help you get started for things to test on your data structure. Additional Test Ideas test that a key can be re-added if the key was inserted and then removed (this should not be a duplicate) check that it can store at least 1,000 items, should be able remove all of them too think of your own additional tests to ensure that you can detect problems It’s your development process that will win the day! Use Incremental Development (https://canvas.wisc.edu/courses/202692/pages/Incremental%20Development?titleize=0) and try Test Driven Development (http://agiledata.org/essays/tdd.html) strategies right from the start. Finally, don’t forget to Submit your latest work (daily or more frequently): p1 Testing, Debugging and Performance (https://canvas.wisc.edu/courses/202692/assignments/833515)
