Assignment 4: Automated Test Input Generation

Due Friday, March 27

Goals for This Assignment

By the time you have completed this work, you should be able to:

Write an automated test case generator for a binary tree

This assignment may be completed in groups.

Step-by-Step Instructions

Step 1: Prepare Base

This assignment is based directly off of Assignment 3, and you can start directly from your assignment 3 solution. In this assignment, you will write a test case generator for one method of your choosing.

(Optional) Step 1.5: Port to Another Language

The code from Assignment 3 uses Java and JUnit. If you'd prefer to use another language or testing library, you may do so. However, if you choose to use another language/library, you'll need to port the code over to your preferred language/library. Up to a 20% bonus is available for choosing to port to another language; this is an incentive to explore something else, and as a nod to the fact that you're doing extra work to port it.

Step 2: Select Implementation to Write

Select one of the following four methods to implement. You will later write an automated test case generator for your chosen method. As a hint, some of these are easier than others.

A breadth-first search over a tree, returning the items in the tree. Different method signatures are possible for this. If you're stuck, you can use the following signature:
```
          public static <A> ArrayList<A> bfs(final Node<A> root)
        
```
A pre-order traversal over a tree, returning the items in the tree. Different method signatures are again possible; you can use the following if you're stuck:
```
          public static <A> ArrayList<A> preorder(final Node<A> root)
        
```
A calculation of the maximum depth of a given tree. Different method signatures are again possible; you can use the following if you're stuck:
```
          public static <A> int maxDepth(final Node<A> root)
        
```
A calculation of the number of nodes in a given tree. Leaf nodes (null) count towards this count. Different method signatures are again possible; you can use the following if you're stuck:
```
          public static <A> int nodeCount(final Node<A> root)
        
```

You may write helper methods if you wish. You can re-use your implementation code from Assignment 3, but only pick one. You should write your method implementation in src/main/java/trees/TreeOperations.java.

Step 3: Write Automated Test Case Generator

Write an automated test case generator in src/test/java/trees/TreeOperationsTest.java. This can use any generation and search strategy you prefer. However, you should make some attempt to make sure the outputs are fairly diverse. In other words, try to avoid repeatedly generating the same test input. (Node that generating and then checking against previously-generated inputs isn't practical for this purpose.) See Assignment 3 for details of how to run the tests.

Step 4: Ensure 100% Coverage of Implemented Method

Gather code coverage information as you did for Assignment 3. While you don't need 100% coverage overall, for this assignment I'm requiring that your method you implemented was fully covered. You can determine this information by looking at the detailed report JaCoCo gives (the code coverage tool we're using), which will include a line-by-line analysis of your implementation. For a 100% covered implementation, each line should be highlighted in green, and each branch (conditions around if, while, for, etc.) will have a green node next to it.

If your implementation is not 100% covered, revisit your generator.

In theory, you can do the same thing with mutation analysis, but due to oddities with PIT (the mutation analysis tool we're using), it will always appear to have no coverage. There is a workaround to this problem (namely, rewriting your test case generator to work with JUnit's parameterized tests), but it's more trouble that it's worth.

Step 5: Submit Everything

Zip up everything in your coverage_mutation_template directory, including the target directory. Be sure your target directory holds up-to-date coverage results. Name your zipfile automated_coverage_mutation_solution, and submit it on Canvas. In the comments for the submission, list everyone you worked with, if applicable.