Input generation and property-based testing

For each of the following classes, implement functions that generate input for test cases and write the properties that should be tested.

1. List Reversal

   This class implements an in-place reversal of arrays. An array is reversed by swapping the first element of the array with the last element, the second with the second-to-last, and so forth.

   • Implement a function that generates random arrays.
   • Come up with properties that test the function and fix any bugs you find.

   Solution:

     public static int[] generate(int length) {
       int[] result = new int[length];
       for (int i = 0; i < length; i++)
         result[i] = rand.nextInt(100);
       return result;
     }
   
     public static boolean test(int[] array) {
       int[] input = array.clone();
       int[] output = array.clone();
       try {
         reverse(output);
         reverse(output);
         return Arrays.equals(input, output);
       } catch (Exception e) {
         e.printStackTrace();
         return false;
       }
     }
   

   The test finds a bug; the reverse function does not use a temporary variable when swapping elements.

2. Base64Test

   This class implements Base64 encoding and decoding. A description of Base64 can be found on Wikipedia.

   • Implement a function that generates random input to the Base64 function; note the assumption on the encoding function.
   • Come up with a property that should hold on Base64 encoding/decoding and implement it in the test function.

   Solution:

     public static byte[] generate() {
       Random rand = new Random();
       int length = rand.nextInt(30) * 3;
       byte[] out = new byte[length];
       for (int i = 0; i < length; i++) {
         out[i] = (byte) rand.nextInt(256);
       }
       return out;
     }
   
     public static boolean test(byte[] input) {
       try {
         return Arrays.equals(input, base64Decode(base64Encode(input)));
       } catch (Exception e) {
         e.printStackTrace();
         return false;
       }
     }
   

   The test finds no bugs (note that the generated input should be divisible by 3).

3. Greatest Common Divisor

   This class implements two ways of computing the greatest common divisor of two numbers. Both methods are described on Wikipedia.

   • Implement a function that generates random values for the functions, complying with the assumptions of both methods.
   • Come up with properties that test these functions. If you find a bug, compare the wikipedia pseudo codes to the implementation.

   Solution:

     public static int randomValue() {
       return rand.nextInt(100) + 1;
     }
   
     public static boolean testEqual(int a, int b) {
       try {
         return binary(a,b) == euclid(a,b);
       } catch (Exception e) {
         e.printStackTrace();
         return false;
       }
     }
   
     public static boolean testDividesBinary(int a, int b) {
       try {
         int res = binary(a,b);
         return (a % res) == 0 && (b % res) == 0;
       } catch (Exception e) {
         e.printStackTrace();
         return false;
       }
     }
   

   The test finds a bug; the first || in the binary method should be &&.