P1. 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.

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
  */
  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;
}

Provide a test harness that prompts the user for test cases.

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. Use a random substring taken from the test string and another random string.

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.

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

R1. Finding a Bug

Now run the following function 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 s, String sub)
  {
     int n = s.length;

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

What is the error?

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

R2. 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 int 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("*"))
     {
          answer = result * arg;
     }
     else if (op.equals("/")
     {
          if (arg != 0)
          {
              result = result / arg;
          }
     }
  }

  private int result;
}

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

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?

P2. Test Case Evaluation

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

   pick inputs that have known results
   use an inverse function to undo a result in order to compare it with the input
   compare a result with an answer obtained another way.

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)   /* n is even */
        {
           b = b * b;
           i = i / 2;
        }
        else             /* n is odd */
        {
           r = r * b;
           i--;
        }
    }

    return r;
  }
}

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

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

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.

(Extra credit) Which way is actually faster, power(double a, int n) or x^y = e^y.log(x)?

R3. Program Traces

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, a, and n.

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

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.

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

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?

Here is a class that makes a Pascal triangle of a given height. It also makes 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 + " ";
  }

  /**
     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;
}

public class PascalTriangleTest
{
  public static void main(String[] args)
  {
     String input = JOptionPane.showInputDialog("Enter height");
     int h = Integer.parseInt(input);
     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?

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?

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?

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?

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?

To dtermine 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?

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?

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

Is the program correct now?