Data Structures and Algorithms

Equivalence Classes

A simple example

Let's consider a function that converts lower-case ASCII characters to upper-case: 
char upcase( char x )
/* PRE-CONDITION: x is an ASCII character 
/* POST-CONDITION: if x is in ('a','z'), then 
                       return the corresponding character from ('A','Z')
                   else return x
*/

We want to partition the possible values of the x into partitions. The elements of each sub-set in a partition are related in some way: in this case, they are processed in exactly the same way by the function. Having derived the partition, then we can choose one element at random from each of the equivalence classes (sub-sets) of the partition and test the function with it.

It cannot be emphasized too strongly that this is the only place where the word random has any place in the generation of test data!
Random selections of values for testing before the analysis for equivalence classes will, in general, have two consequences:
The omission of some necessary tests from the software verification process leads to time bombs - software systems which contain errors that are just waiting to be triggered by the "forgotten" input!

Exhaustive testing

For this simple function, one simple verification strategy is to simply test every possible input value. Since there are only 256 ASCII characters, this Simple strategies are always good ones and when the number of inputs is small, exhaustive testing should always be considered. Your only difficulty with this strategy is ensuring that you have, in fact, covered all possible inputs.

However the number of possible inputs has a nasty habit of blowing out to extraordinarily large numbers very quickly.

  1. I want to test a sort routine that must sort 100 integers drawn from a fixed set. The number of possible inputs is the number of permutations of 100 items, or 100! (See if your pocket calculator can work out how big that is!).
  2. I have a function with 6 inputs which can take no more than 10 different values each. I must test each value of each input combined with each possible value of every other input, giving a total number of tests as 10x10x10x10x10x10 = 106. If the function isn't too complex, a modern processor will breeze through 106 test cases before you've finished your coffee break. But let's suppose each input can take 100 values, how long will it take now? Thus, for real problems, we need a "smarter" approach to testing!

    Lazy testing

    Since we all have more interesting things to do than test software, and since we don't want to end up with egg all over our face when a time-bomb that we left in a piece of software explodes, we would like to find out just how little testing we can do and still have confidence in our software.

    So let's examine our simple upcase function a little further. From the specification, it would seem that we have two equivalence classes:
    values of x
    • in ('a','z'), and
    • other values.
    Which implies that we only need two tests to verify this function.

    Let's look at a possible implementation of upcase: 
    char upcase( char x ) {
  if ( (x > 'a') && (x < 'z') )
    return x + ('A'-'a');
  else return x;
  }
    		Of course, we've included a little bit of C hacking here: we used the fact that C will convert characters to integers (which, conveniently, will be the ASCII representations of the characters) so that we can do arithmetic on the characters. However, most other languages will provide us with a means of mapping an element of a set (the set of characters in this case) to an ordinal position in the set (eg Pascal's ord, Ada's 'POS attribute), so that this little function could be trivially translated to most other languages.

    A careful programmer would identify three equivalence classes now:
    values of x
    • in ('a','z'),
    • less than 'a' and
    • greater than 'z'
    because we have two parts to the test for lower case letters - either of which could fail.

    This highlights the difference between:
    black-box testing The software is a "black box", we can only see the specification.
    So we examine the rules in the specification and derive our equivalence classes from them.
    glass-box testing We can see the code of the function to be tested.
    Here we would determine the number of paths that can be followed through the code and generate a set of tests which ensured that every path was followed.

    Generally, but not always, the glass-box approach will identify more test cases than the black-box approach. This is because implementation details, such as the choice of data structure, cannot be seen in the specification.

    For example, a specification for a search function may simply require that if an item with a certain key exists in the collection, it returns true, otherwise false. This leads to two equivalence classes: keys in the collection and keys which are not. But if the implementation used a binary tree, you would certainly want to make sure that the code for processing both the left and right branches was correct. This would lead to at least three classes:

    1. key < root,
    2. key = root, and
    3. key > root.
    I put "at least three" above, because you should combine cases 1 and 3 with the "found | not found" possibilities to give 5 tests.

    Despite the fact that test cases generated from a black-box analysis may lack some tests that analysis of the code would require, black-box analysis is important:

    Additional tests

    The theory of equivalence classes states that all members of an equivalence class are related (in this case by the way that the function under test processes them) and that any one can be chosen as a representative.

    However, an experienced programmer will add some additional cases - for a very good reason!

    There is a mistake in the code above for upcase: can you spot it? Look carefully before you click here!

    Back
    Table of Contents
    © John Morris, 1996