A second principle of testing is that you need to know what the expected output is for some test input, otherwise it is a waste to do the test run!
A third principle is not to do ``testing on the fly'' by typing in input from the terminal, or editing a previous test file. Always prepare and save test data either in a file or a program so you can re-run the test easily later. Why? Well, after you change your program to fix an error, you need to go back and redo the previous tests - some things that worked before may not work now!!! (In general code that is a bug-fix is much more likely to be buggy itself!)
So now we are ready to talk about how to test. One approach is to use a random number generator to produce test data and keep on testing as long as you can. This is not as easy as it sounds. Most systematic approaches to testing are based on the idea of dividing the class of inputs into subclasses so that if you run a test for one member of the subclass, you assume you would get the same result for the other inputs in the same subclass (and so you do not have to run them).
Of course, this is a catch-all category, so anything else you suspect could cause problems goes here.
public class MCS{
public int mcs(int [] A, int N ) throws IllegalN;
/* Find some subsequence of a given list, which has maximal sum.
parameters
N: the number of elements in the list
A: the list,as an array with indices staring at 0;
(notation will be A[0..N])
returns
the sum of values A[seqStart],...A[seqEnd]
(abbreviated A[seqStart..seqEnd])
modifies
int seqStart //the starting index of the subsequence
int seqEnd // the ending index of the subsequence
exceptions
IllegalN when not(0 <= N-1 <= A.length - 1)
ASSUMES A[0..N-1] is initialized
EFFECTS:
At least one non-negative value in A[0..N-1] and
0 <= seqStart <= seqEnd <= N-1 and
return >= SUM{A[j..k]} for any 0<=j<=k<=N-1
**OR**
all A[i] < 0 and returns=0, seqStart=seqEnd=N+1
*/
}
In this case the inputs are array A and integer N, and the outputs are
two ``global'' variables, seqStart and seqEnd, plus the
value returned. The ``ASSUMES'' clause indicates what conditions are assumed
and
not checked by the method. If you call the method without the assumption
being true, all bets are off. Note that this is different from error conditions
checked, for which exceptions are raised. (For your information, I include
at the end a way of presenting the above kind of information as part of
JavaDoc format.)
For valid outputs, we expect 0 <= seqStart <= SeqEnfd <= N-1.
Boundary analysis suggests trying { seqStart=seqEnd=0 }, { seqStart=seqEnd=N-1
}, and { seqStart=0, seqEnd=N-1 }. (The other combination: { seqStart=N-1,seqEnd=0
} is not possible.)
If possible, one can also try to find ways to get
invalid outputs: return value less than 0, mixed up seqStart and end values,
etc.
To put these all together:
Here then would be one collection of test-data for the above example:
N |A.length| A[0],A[1],... | seqStart | seqEnd | result ------------------------------------------------------------------ 1 | 1 | -3 | | 0 | | 3 ---------------------------------------------------- 3 | 4 | -3,-3,-3 | | | -3,0,-3 | | | 4,-5,1 | 0 | 0 | | 1,-5,4 | 2 | 2 | | 5,-4,1 | 0 | 2 ---------------------------------------------------- invalid: ---------------------------------------------------- 0 | ---------------------------------------------------- -1 | ---------------------------------------------------- 2 | 1 | 3 -----------------------------------------------------
One thing to do is to first start with the black-box tests and see what remains to be done. At the very least, you need to add test data to achieve ``statement coverage''.
Consider the O(n) algorithm that has the following structure
maxsume=0;thissum=0;
for (i=0,j=0; j<a.length; j++) {
thissum += a[j];
if( thissume=maxsum ) { // test1
maxsum=thissum; seqStart=i; seqEnd=j; }
else
if( thissum < 0 ) //test2
{i=j+1; thissum=0;}
}
If you look carefully, the original set of black-box test data was good
enough to do statement coverage. To do more, your test sets should cause the
loop to execute on some run 0 times. On three other runs the loop would
be executed 1 time, with three different cases: { test1=test2=false },
{ test1=true,test2=false }, { test1=test2=true }. On nine other runs, the
loop would be executed twice, each of these independetly having the three
test combinations above. This is getting to be labor intensive, but then
who said it will be easy?!
This would lead to the following tests with stack
1. s=new stack(); s.isEmpty(); s.top() ;
---------------------------------------------
2. s=new stack(); s.pop(); s.isEmpty(); s.top() ;
---------------------------------------------
3. [..set up a stack..] s.push("A"); s.isEmpty(); s.top() ;
---------------------------------------------
4. [..set up a stack..] s.push("A"); s.pop(); s.isEmpty(); s.top() ;
As usual, error cases should be run separately. And you may need to do
more "set-up" before each sequence. Note that the principles mentioned
in the first section apply here too. So, one would like to do different
stack set ups, so that, if possible, isEmpty() returns both true and false
in each of the above test categories. (Category 4 is the only one where
you can do this: you can have the set up be just s=new stack();
or s=new stack(); s.push("B");.) Also, test changes/lookups occuring
at the beginning/end of data structures.
public string toString() {
String res = "aStack<topOfStack=" + topOfStack + "; theArray=[";
for(int j=0;j<=topOfStack; j++){
res += theArray[j].toString() + "; " ;
res+= "]; array length =" + theArray.length + ">";
return res;
}}
Note that we even include the array length in the "state display".
public void push(Object x){
// a stub
theArray[0]="A"; theArray[1]= "B";
topOfStack = 1;
}
makes it so that Stack s = new Stack(); s.push("anything"); leaves
you in a precisely known situation, in which you can test your
toString()
function, to make sure it returns the right thing:
Some stubs compute or return the same thing all the time, like push above. Others, can be made to return a series of different values, depending on whether this is the first, second, etc. call to it. For example, suppose that for testing some other class, you need a stack, for which the first topAndPop returns "B", and the second one "F". Well, you can add to the class Stack a little helper array to store the "canned" responses of your function, as below:
class Stack... {
...
Object [] popResults = ("B" , "E");
int popCt =0;
public Object topAndPop()
{//a stub
return popResults[popCt++];
}
...
Note that this can be done to *any* implementation of Stack -- even
if the final stack will use linked lists, a stub can use an array to save
its responses..
public class MCS{
/**
* Find some subsequence of a given list, which has maximal sum.
* @param A the list,as an array with indices staring at 0;
* @param N the number of elements in the list <pre>
* MODIFIES int seqStart //the starting index of the subsequence
* MODIFIES int seqEnd // the ending index of the subsequence </pre>
* @exception IllegalN when not(0 <= N-1 <= A.length - 1)) <pre>
* ASSUMES A[0..N-1] is initialized </pre>
* @return the sum of values A[seqStart..seqEnd]
* <pre>
* EFFECTS:
* At least one non-negative value in A[0..N-1] and
* 0 <= seqStart <= seqEnd <= N-1
* return >= SUM{A[j..k]} for any 0<=j<=k<=N-1
* *OR*
* A[0..N-1] < 0 and returns=0, seqStart=seqEnd=N+1
* </pre>
*/
public int mcs(int [] A, int N ) throws IllegalN;
}