Big Java / Java Concepts Lab 10

Unit Tests

Testing a class for run-time errors in the context of an ongoing project is always difficult. The source of an error may be obscured by other phenomena, there could be more than one error and it might arise under unusual circumstances or even appear to go away. Testing a new class in isolation, before adding it to a project, gives you an excellent opportunity to locate errors before they become lost in a broken project.

Testing in isolation is called unit testing. It requires a test harness, that is, a class that calls your methods with parameters obtained from 1) user input, 2) a file, or 3) a program that automatically generates parameter values.

You will write two test stubs for the following class. The first test stub takes test values from prompted user input. The second test stub generates test cases randomly.

public class Finder
{
    /**
        Constructs a finder that finds substrings in a given string.
        @param aString the string to analyze
    */
    public Finder(String aString)
    {
        s = aString;
    }

    /**
        Search for a substring.
        @param sub the string to look for
        @return if found, the integer position of sub in the string
        else, -1
    */
    public int findFirst(String sub)
    {
        int i = 0;

        while (sub.length() + i <= s.length())
        {
            if(s.substring(i, i + sub.length()).equals(sub))
                return i;
            else
                i++;
        }
        return -1;
    }

private String s;
}

First, provide a test harness that prompts the user for test cases.

2.	It is tedious to type in lots of test data every time you find a bug in your code. How can you reduce your workload?

Provide a test harness for randomly generated test cases.

When generating test cases randomly, be sure to include positive and negative tests.

Hint: We have no function to generate a completely random string, but you can write one. Make a string of the 26 lowercase letters, then extract single-character length substrings from it at positions generated by generator.nextInt(26) and concatenate them.

4.	Did you think of boundary cases? What are the boundary cases in this example?

Finding a Bug

Now run the following method through two test procedures (manual and automatic test case generation).

public class Finder
{
    . . .
    /**
        Searches for last occurrence of a string.
        @param sub the string to look for
        @return if found, the integer position of sub in s else, -1
    */
    public int findLast(String sub)
    {
        String sCopy = s;
        while (sub.length() <= sCopy.length())
        {
            if(sCopy.substring(sCopy.length() - sub.length(),                 sCopy.length()).equals(sub))
                return sCopy.length() - sub.length();
            else
                sCopy = sCopy.substring(0, sCopy.length() - 2);
        }
        return -1;
    }
    . . .

}

What is the error?

6.	Did one of your test cases catch it? If yes, which one?

Selecting Test Cases

Test cases should provide complete coverage of each instruction branch in your function. Every branch, for example both statement blocks in an if - else pairing, should succeed and fail at least once.

/**
    Simplified calculator to perform two variable arithmetic.
*/

public class Calculator
{
    public Calculator()
    {
        result = 0;
    }

    /**
        Gets the current result (the value that the calculator displays on its screen).
    */
    public double getResult()
    {
        return result;
    }

    /**
        Carries out a computation and sets the result to
        the value that is obtained by combining the old
        result with a value that the user supplied.
        @param op the arithmetic key that the user typed
        @param arg the number that the user typed
     */
    public void compute(String op, double arg)
    {
        if (op.equals("+"))
        {
            result = result + arg;
        }
        else if (op.equals("-"))
        {
            result = result + arg;
        }
        else if (op.equals("*"))
        {
            double = result * arg;
        }
        else if (op.equals("/"))
        {
            if (arg != 0)
            {
                result = result / arg;
            }
        }
    }

    private double result;
}

Give a set of test cases for op, and arg that provides complete coverage of all branches.

8.	Compile and run the class. Either use BlueJ or supply a test harness. Then enter the test cases that you supplied. Does each branch work as expected?

Test Case Evaluation

Having tested the input to a function, how can the output be validated? You can

pick inputs that have known results
write a test harness that verifies that the output values fulfill certain properties
compare a result with an answer obtained another way (using an oracle)

Test the following power method.

public class Numeric
{
    /**
        Compute an integral power of a number.
        @param a the number to be raised to an integral power
        @param n the power to which it is to be raised
        @return a to the nth power
    */

    public static double power(double a, int n)
    {
        double r = 1;
        double b = a;
        int i = n;

        while (i > 0)
        {
            if(i % 2 == 0) /* even */
            {
                b = b * b;
                i = i / 2;
            }
            else /* odd */
            {
                r = r * b;
                i--;
            }
        }

        return r;
    }

    /**
        Tests whether two floating-point numbers are
        equal, except for a roundoff error.
        @param x a floating-point number
        @param y a floating-point number
        @return true if x and y are approximately equal
    */
    public static boolean approxEqual(double x, double y)
    {
        final double EPSILON = 1E-12;
        return Math.abs(x - y) <= EPSILON;
    }
}

Write a program that uses the reciprocal Math.sqrt to test whether Math.sqrt(Numeric.power(x,2)) should be equal to x.

10.	If the test succeeds, how much confidence do you have that power is correct?

11.	Use the fact that x^y = e^{y log(x)}. Write a program that computes the power function in another way, and compares the two values.

12.	(Extra credit) Which way is actually faster, power(double a, int n) or exp(y * log(x))?

Program Traces

13.

A program trace is the result of print statements at known points in a program. It shows that the program has executed commands up to a certain point, and allows you to print the values of key variables at that point.

Add print statements to the preceding Numeric.power method to document all changes to variables r, b, and i.

14.	Show the resulting trace when power is called with a = 3 and n = 11.

15.	The disadvantage of print statements is that you need to remove them when your code is debugged. Therefore, it is better to use the logging facility. Replace the print statements with logging calls in the Numeric.power method.

16.	Run your modified method with a = 2 and n = 12. Exactly what logging output do you get?

17.

The following portion of the lab is designed to have you practice some of the basics of debugging. We will analyze a program that displays Pascal's triangle. This triangle is a sequence of integers that arises in numerous areas of math and computer science, especially combinatorics and probability. For example, the Pascal triangle of height 4 is:

1
1 1
1 2 1
1 3 3 1

1 4 6 4 1

Entries in Pascal's triangle are indexed by integers. n is the number of the row and k is the position from the leftmost member of the row. The indexes in both directions start at zero (0), so in the last row listed above, C(4,0) = 1, C(4,1) = 4, C(4,2) = 6, and so on.

The values themselves are computed by the formula C(n, k) = n! / (k! * (n-k)!), which is called a combination. n! denotes a factorial, that is, the product n*(n-1)*(n-2)*...*2*1. The combinations can be interpreted as the number of ways to choose k elements from a collection containing n elements. When described, it is customary to say "n choose k", for instance '4 choose 2 is 6' ".

If four objects are numbered 1 through 4, how many ways can you select two of them? Show all the possible pairings here. Then compute C(4, 2) by using the formula. Does it match the number of selections?

18.

Here is a class that makes a Pascal triangle of a given height. We also provide a test harness.

public class PascalTriangle
{
    /**
        Constructs a triangle of a given height.
        @param height the height (0-based)
    */
    public PascalTriangle(int height)
    {
        triangleString = "";
        int spacesToSkip = 2 * height; // spaces to skip at the beginning of each row
        // start a loop over the number of rows

        for (int n = 0; n <= height; n++)
        {
            skip(spacesToSkip); // space to make a triangle
            spacesToSkip = spacesToSkip - 2;

            for (int k = 0; k <= n; k++)
            {
                int comb = combination(n, k);
                String out = " " + comb; // pad to a length of 4
                triangleString = triangleString + out.substring(out.length() - 4);
            }

            triangleString = triangleString + " ";
            n++;
        }
    }

    /**
        Skip n spaces on a line.
        @param n - the number of spaces to skip
     */
    public void skip(int n)
    {
        for (int i = 0; i <= n; i++)
            triangleString = triangleString + "\n";
    }

    /**
        Calculate n factorial.
        @param n calculate the factorial of n
        @return n!
    */
    public static int factorial(int n)
    {
        int product = 1; // accumulator for the running product

        for (int i = 1; i <= n; i++)
            product = product * i ;
        return product;
    }

    /**
        Calculate the number of combinations of n things taken
        k at a time (n choose k).
        @param n the number of items to choose from
        @param k the number of items chosen
        @return n choose k
    */
    public static int combination(int n, int k)
    {
        int comb = factorial(n) / factorial(k) * factorial(n - k);
        return comb;
    }

    public String toString()
    {
        return triangleString;
    }

    private String triangleString;
}

/** File PascalTriangleTester.java */
import java.util.Scanner;

public class PascalTriangleTester
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter height: ");
        int h = in.nextInt();

PascalTriangle tri = new PascalTriangle(h);

System.out.println(tri.toString());

}
}

What output do you get when you request a triangle with a height of 5?

19.	When the height is 5, we expect six rows. There aren't enough rows. To find out why, set a breakpoint at the line skip(spacesToSkip); // space to make a triangle in the PascalTriangle constructor. What is the value of n when the breakpoint is reached?

20.	Now run the program until it reaches the breakpoint again. What value do you expect n to have, and what value do you actually observe?

21.

The variable n is supposed to take the values 0, 1, 2, 3, 4, 5, but it actually jumped from 0 to 2.

If you like, run the program again to the breakpoint. You'll find that n is now 4. Apparently, n is incremented twice each time the loop is traversed.

Determine the reason and fix it. What fix did you make?

22.	Run your corrected version again with a height of 5. You should now have six rows of output, but the values are still wrong. What values do you get? How do you know they are wrong?

23.	To determine why the values are still wrong, set a breakpoint at the line return comb; in the combination method. Run your program until the method is executed with the values n = 3, k = 1. What is the value of comb? What should it be?

24.	C(3, 1) is 3! / (1! * 2!) = 6 / (1 * 2) = 3. Check why the value is computed incorrectly, and fix the computation. What fix did you apply?

25.	After fixing the error, run the test again. What values do you get?

26.	Is the program correct now?