// FILE: tests12.cxx
// Written by: Michael Main (main@colorado.edu), Nov 26, 1996
//
// This file contains a function to test of the quicksort
// function from quick1.cxx. It should be compiled and then linked with
// quick1.cxx.

#include <iostream.h>
#include <stdlib.h>
#include "quick1.h"

const size_t TEST_SIZE = 3000; // Number of items in a random array
const int MAX = 1000;          // Items in random array range from 0...MAX

bool correct(int data[ ], int right[ ], size_t n)
// Precondition: data and right are arrays with at least n elements.
// If data[0] ... data[n] is the same as right[0] ... right[n], then
// "Test passed" is printed and the return value is true. Otherwise 
// "Incorrect sort" is printed and the return value is false.
{
    size_t i;
    
    for (i = 0; i < n; i++)
    {
        if (data[i] != right[i])
        {
            cerr << "Incorrect sort." << endl;
            return false;
        }
    }
    cerr << "Test passed." << endl << endl;
    return true;
}

int test1( )
// Postcondition: Tests have been run on the quicksort. If the tests are
// passed, then the function returns 80. Otherwise the function returns zero.
{
    int test[TEST_SIZE+2];      // Has an extra item on either end
    int right[TEST_SIZE];       // Correct data
    size_t occurrences[MAX+1];  // occurrences[i] is the number of times that
                                // i appears in a large random array.
    char test_letter = 'A';
    size_t i;                   // Used as an index of test or right
    int n;                      // A random number put into the test array
    size_t many;                // Number of random items put into the test array

    cerr << test_letter++ << ". ";
    cerr << "Testing quicksort with n=0. There should be no work." << endl;
    cerr << endl;
    quicksort(test+1, 0);
    cerr << "Test passed." << endl << endl;

    cerr << test_letter++ << ". ";
    cerr << "Testing quicksort with n=1. There should be no work." << endl;
    test[1] = 1;
    right[1] = 1;
    quicksort(test+1, 1);
    if (!correct(test+1, right+1, 1)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Testing quicksort to sort 1 through 10." << endl;
    cerr << "The numbers in the data array start in order." << endl;
    for (i = 2; i <= 10; i++)
    {
        test[i] = i;
        right[i] = i;
    }
    quicksort(test+1, 10);
    if (!correct(test+1, right+1, 10)) return 0;
    
    cerr << test_letter++ << ". ";
    cerr << "Testing quicksort to sort 10 downto 1." << endl;
    cerr << "The numbers in the data array start in backward order." << endl;
    for (i = 1; i <= 10; i++)
        test[i] = 11-i;
    quicksort(test+1, 10);
    if (!correct(test+1, right+1, 10)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Testing quicksort to sort two copies of 1 through 10." << endl;
    for (i = 11; i <= 20; i++)
        test[i] = i-10;
    for (i = 1; i <= 20; i++)
        right[i] = (i+1) / 2;
    quicksort(test+1, 20);
    if (!correct(test+1, right+1, 20)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Testing quicksort to sort " << TEST_SIZE << " random items.";
    cerr << endl;
    for (n = 0; n <= MAX; n++)
        occurrences[n] = 0;
    for (i = 1; i <= TEST_SIZE; i++)
    {
        n = rand( ) % (MAX + 1);
        test[i] = n;
        occurrences[n]++;
    }
    many = 0;
    for (n = 0; n <= MAX; n++)
    {   // Put occurrences[n] copies of n into the right array
        for (i = 1; i <= occurrences[n]; i++)
            right[many+i] = n;
        many += occurrences[n];
    }
    quicksort(test+1, TEST_SIZE);
    if (!correct(test+1, right+1, TEST_SIZE)) return 0;

    return 100;
}

int main( )
{
 
    cerr << "Running quicksort test:" << endl;
 
    if (test1( ) > 0) cerr << "Test passed." << endl << endl;
    else cerr << "Test failed." << endl << endl; 

    return 0;

}