4.14.2 Test Set Generation

We need code to generate a random permutation of numbers to order insertion and deletion of items. We will support some other orders besides random permutation as well for completeness and to allow for overflow testing. Here is the complete list:

122. <Test declarations 122> =
/* Insertion order. */
enum insert_order 
  {
    INS_RANDOM,			/* Random order. */
    INS_ASCENDING,		/* Ascending order. */
    INS_DESCENDING,		/* Descending order. */
    INS_BALANCED,		/* Balanced tree order. */
    INS_ZIGZAG,			/* Zig-zag order. */
    INS_ASCENDING_SHIFTED,      /* Ascending from middle, then beginning. */
    INS_CUSTOM,			/* Custom order. */

    INS_CNT                     /* Number of insertion orders. */
  };

/* Deletion order. */
enum delete_order 
  {
    DEL_RANDOM,			/* Random order. */
    DEL_REVERSE,		/* Reverse of insertion order. */
    DEL_SAME,			/* Same as insertion order. */
    DEL_CUSTOM,			/* Custom order. */

    DEL_CNT                     /* Number of deletion orders. */
  };

See also 126, 134, 139, 140, and142.

The code to actually generate these orderings is left to the exercises.

Exercises:

1. Write a function to generate a random permutation of the n ints between 0 and n - 1 into a provided array. [answer]

*2. Write a function to generate an ordering of ints that, when inserted into a binary tree, produces a balanced tree of the integers from min to max inclusive. (Hint: what kind of recursive traversal makes this easy?) [answer]

3. Write one function to generate an insertion order of n integers into a provided array based on an enum insert_order and the functions written in the previous two exercises. Write a second function to generate a deletion order using similar parameters plus the order of insertion. [answer]

*4. By default, the C random number generator produces the same sequence every time the program is run. In order to generate different sequences, it has to be “seeded” using srand() with a unique value. Write a function to select a random number seed based on the current time. [answer]