CSE 373 Winter 2005

Homework #4

Testing LinkedList and BinarySearchTree

Due:

Objectives

• Learn how to create test cases using JUnit (with some advanced features)
• Learn how to generate test cases using black-box testing techniques (equivalence partitioning testing and boundary value testing)
• Learn how to use a code coverage tool called JCoverage to measure code coverage and generate new test cases to cover the uncovered statements

JCoverage tool setup

• There is quite a bit of set up.  You should start on this IMMEDIATELY.  Don't wait for further instructions or until the assignment is finalized.  Start now because otherwise you won't be able to do any of the "real" part of the assignment.
  
• Install Ant. See installation instructions here. (You won't have occasion to run it until a later step).  Ant is not primarily an application in and of itself.  It is a tool to run and deploy other applications.  For example, it could be used to do a series of compiles, make a jar file, create javadoc, copy files, and start a program in execution.  Our main use of it will be to run the jcoverage tool.
• Install JUnit if you haven't done so. [The site www.junit.org has downloads and examples (though they tend to make it seem more complicated than it is).  A local copy of junit.jar, which must be available to the Java compiler and to ant, is with the other homework 2 files. You can also donwload junit.jar here.] junit.jar is automatically included with Eclipse.  You can find it in C:\eclipse\plugins\org.junit_3.8.1 (assuming Eclipse was installed in c:\eclipse).
• junit.jar must be available to ant.  Copy it into ANT_HOME/lib (see ant installation instructions for a reminder of what ANT_HOME means).
  
• Download jcoverage-1.0.5-bin.zip and extract it to a directory, such as c:\jcoverage. Then you will have the following directory structure:
    c:\jcoverage 
                \jcoverage-1.0.5
                                \examples
                                         \src
                                             \com ....
                                \lib
        
• You will run jcoverage in a later step, using ant.
  
• Then create a directory hw4 under c:\jcoverage\jcoverage-1.0.5\examples\src. hw4 is a package name, so it has to be spelled exactly as shown. (If you did not place jcoverage in c:\jcoverage\jcoverage-1.0.5, you will of course have to modify the above and similar paths).  You then should copy the following LinkedList.java, LinkedListTest.java, BinarySearchTree.java, and BinarySearchTreeTest.java into that hw4 directory.
• Up to this point, you were probably working in the usual Windows GUI mode, using Explorer, etc.  The next step requires you to be in a command prompt window, which you can enter by going to START/RUN and typing in cmd.  This places you in a default directory, which you will have to change to in the next step.
  
• Open a command prompt window.  Change to (cd) the directory of c:\jcoverage\jcoverage-1.0.5\examples.  To verify that you are in the right place, type "dir" and you should see a file named build.xml and the src directory. 
  
• Once you are in the right place, type in "ant" in the command line.  What you are doing here is actually running jcoverage -- ant is just a package to run other programs.
• If you get something like "ant command not found", it means that the ANT_HOME and PATH variables are not correct -- go back and look at the ant installation information (it is at this point that you can type in the two "set" commands).  If you get something like "javac command not found", it means that the ant program started to run, but couldn't the java compiler.  This may mean that there is no JAVA_HOME variable set on your computer.  If this is the case, first locate the directory on your computer containing the Java SDK.  For example, suppose it is c:\j2sdk1.4.2_04.  In that case, the proper command is set JAVA_HOME=c:\j2sdk1.4.2_04
  
• Once ant has run,and thus jcoverage has run, jcoverage builds a directory "build" under c:\jcoverage\jcoverage-1.0.5\examples.  You can verify that it is there by typing "dir".  jcoverage will build this directory even if it encounters problems!  One problem you might see has to do with line 128 of the XML file, complaining that ant can't find the junit.jar file.  To solve this, see a previous step in which you should have copied junit.jar into the proper place for ant to find it.
• Once ant and jcoverage have run successfully, there will be a bunch of html files under C:\jcoverage-1.0.5\examples\build\coverage. JCoverage highlights those uncovered statements with yellow color.  You may find it easiest at this point to use Windows Explorer.  Double-click the html files to view them in a browser.

Description

Constructor:
public LinkedList(){ ... }

Methods with void returns:
public void addFirst(Object item) { ... }
public void removeFirst() { ... } 
public void reverse() { ... }

Methods with non-void returns:
public boolean contains(Object item) { ... }
public Object getFirst() { ... }
public int size() { ... }
public boolean equals(Object other) { ... }
public String toString() { ... }

We have prepared a a JUnit test class called LinkedListTest.java for you. In this class, we simply add a test method to test the constructor method. In this test class, you need to add test methods to fulfill the following testing tasks. You need to create meaningful names for your test methods, such as "testContainsWithEmptyList". You also need to document some statements within your test methods with comments if their test purposes are not easy to understand by just reading the code, such as "//boundary value 1 for the test condition s.size()" or "//cover statement: throw new NoSuchElementException();".  They not only help others read your test code but only help yourself check whether you have generated enough tests to cover the program under test. But note that don't write unnecessary comments for those statements that are simple or whose behavior can be easily understood. For example, it is unnecessary to write "//construct a LinkedList object" for the statement of "LinkedList t = new LinkedList();". 

• Use the black-box testing techniques to create test methods for testing the contains method (based on the classification tree presented in the class).
  Hints: 
  1. You need to create one test method for each  case instead of putting multiple cases into one test method.
  2. Think how you can construct a specific LinkedList object.
  3. Think whether you need to do other assertion checkings besides checking the return value of contains. What if a buggy contains method inserts the method argument into the LinkedList but still returns a correct boolean value?
  
  
• Use the black-box testing techniques to create test methods for testing the addFirst method (The add method presented in class is different from this addFirst method, see description of Java API documentation. When you are asserting the resulting object state, you can use some combinations of the methods with non-void returns.
  
  
• Use the black-box testing techniques to create test methods for testing the removeFirst method (You need to learn how to assert that an exception needs to be thrown by the test. See the Exceptions section of this JUnit introduction).
  
   
• Use the black-box testing techniques to create test methods for testing the reverse method.
  
  
• Run your test class with the JCoverage tool (see the above description of JCoverage tool setup). See whether your test class has already covered all statements of the LinkedList class. If not, you need to create more test methods to cover these uncovered statements. Although achieving 100% statement coverage is very difficult for a complex class, it is straightforward to generate test methods to cover all statements in LinkedList.
  

Constructor:
public BinarySearchTree(){ ... }

Methods with void returns:
public void add(Integer info) { ... }

Methods with non-void returns:
public int size() { ... }
public boolean equals(Object other) { ... }
public String toString() { ... }

We have prepared a a JUnit test class called BinarySearchTreeTest.java for you. In this class, we simply add a test method to test the constructor method. In this test class, you need to add test methods to fulfill the following testing tasks. Similar to testing LinkedList, you need to create meaningful names for your test methods. You also need to document your test methods with comments.

• Use the black-box testing techniques to create test methods for testing the add method (The add method presented in class is different from this addFirst method, see description of Java API documentation. When you are asserting the resulting object state, you can use some combinations of the methods with non-void returns).
  Hints (same as the hints for LinkedList), in addition,
  1. BinarySearchTree is more complicated then LinkedList, because a LinkedList with size N has just one shape of data structures but a BinarySearchTree with size N can have multiple different shapes. For example, a BinarySearchTree with size 2 can have 2 shapes and a BinarySearchTree with size 3 can have 3 shapes. In this exercise, you need to consider testing an add method on at least all shapes of a BinarySearchTree up to size 2.
  2. If you want to use the toString method for checking the resulting object state, you can try to invoke System.out.println(t.toString()); first to see what the string looks like. Then you can copy the string such as "{1}" into the assertion in the test code like assertTrue(t.toString().equals("{1}")); and remove the above line of System.out.println(t.toString()). Of course, when you need to make sure the printed string is the expected one.
  
  
  
• Run your test class with the JCoverage tool (see the above description of JCoverage tool setup). See whether your test class has already covered all statements of the BinarySearchTree class except for one (unreachable) statement. If not, you need to create more test methods to cover all these uncovered statements for one (unreachable) statement.
  

Note: Reorganize your code so that the classes are all in a package called "hw4"  (the provided LinkedList.java, LinkedListTest.java, BinarySearchTree.java, and BinarySearchTreeTest.java already contain the correct package declaration).  You will need to move the files into a directory with the name of "hw4".

Turn in:

• Any difficulties you had

Grading

• Correct use and structure of the JUnit tests
  
• Efficiency and elegance of the solutions
• Test cases
  
• Following instructions and specifications (including what materials are to be turned in, deadlines, etc. etc.)
  
• Programming practice (style, comments, etc.)
• The report