返回顶部

收藏

PriorityQueue类的非交互式的测试程序

更多
// FILE: pqexam1.cxx
// Non-interactive test program for the PriorityQueue class,
// with improved test for heap leaks.

#include <string.h>  
#include <stdlib.h>  
#include "pqueue1.h"  
#include <iostream>

 using std::cout;
 using std::cin;
  using std::endl;
  using std::flush;

const size_t MANY_TESTS = 4;  
const int POINTS[MANY_TESTS+1] = {
    200,  // Total points for all tests.
    100,  // Test 1 points
     50,  // Test 2 points
     25,  // Test 3 points
     25   // Test 4 points
};
const char DESCRIPTION[MANY_TESTS+1][256] = {
    "tests for the PriorityQueue class",
    "simple tests of insert and get_front",
    "Testing for possible heap leaks",
    "Testing the copy constructor",
    "Testing the assignment operator"
};

const  size_t BORDER_SIZE     = 2*sizeof(double);
const  char   GARBAGE         = 'g';
const  char   BORDER          = 'b';
static size_t memory_used_now = 0;

void* operator new(size_t size)
{
    char   *whole_block;   
    size_t *size_spot;    
    char   *front_border;  
    char   *middle;       
    char   *back_border;  
    size_t i;             
    whole_block = (char *) malloc(2*BORDER_SIZE + size);
    if (whole_block == NULL)
    {
        cout << "Insufficient memory for a call to the new operator." << endl;
        exit(0);
    }

    size_spot = (size_t *) whole_block;
    front_border = (char *) (whole_block + sizeof(size_t));
    middle = (char *) (whole_block + BORDER_SIZE);
    back_border = middle + size;

    *size_spot = size;

    for (i = 0; i < BORDER_SIZE - sizeof(size_t); i++)
        front_border[i] = BORDER;
    for (i = 0; i < size; i++)
        middle[i] = GARBAGE;
    for (i = 0; i < BORDER_SIZE; i++)
        back_border[i] = BORDER;
    memory_used_now += size;
   return middle;
}

void operator delete(void* p)
{
    char   *whole_block;   
    size_t *size_spot;     
    char   *front_border;  
    char   *middle;        
    char   *back_border;   
    size_t i;              
    size_t size;          
    bool   corrupt;       

    whole_block = ((char *) (p)) - BORDER_SIZE;
    size_spot = (size_t *) whole_block;
    size = *size_spot;
    front_border = (char *) (whole_block + sizeof(size_t));
    middle = (char *) (whole_block + BORDER_SIZE);
    back_border = middle + size;

    corrupt = false;
    for (i = 0; i < BORDER_SIZE - sizeof(size_t); i++)
        if (front_border[i] != BORDER)
            corrupt = true;
    for (i = 0; i < BORDER_SIZE; i++)
        if (back_border[i] != BORDER)
            corrupt = true;

    if (corrupt)
    {
        cout << "The delete operator has detected that the program wrote\n";
        cout << "beyond the ends of a block of memory that was allocated\n";
        cout << "by the new operator. Program will be halted." << endl;
        exit(0);
    }
    else
    {
        for (i = 0; i < size + 2*BORDER_SIZE; i++)
            whole_block[i] = GARBAGE;
        free(whole_block);
        memory_used_now -= size;
    }
}

bool correct(PriorityQueue& test, size_t n, int items[])
{
    size_t i;
    bool answer = true;
    if (test.size( ) != n)
        answer = false;
    else if (test.is_empty( ) != (n == 0))
        answer = false;
    else
        for (i = 0; answer && (i < n); i++)
            if (items[i] != test.get_front( ))
                answer = false;
    cout << (answer ? "Test passed.\n" : "Test failed.\n") << endl;
    return answer;
}

int test1( )
{
    const size_t TEST_SIZE = 400;
    const unsigned int PRIORITY_LIMIT = 100;

    PriorityQueue test;
    int items[8] = { 100, 200, 3, 4, 5, 6, 8, 7 };
    int occurs[PRIORITY_LIMIT];
    int rand_items[TEST_SIZE];
    char test_letter = 'A';
    int i;
    unsigned int priority;

    cout << test_letter++ << ". ";
    cout << "Testing size and is_empty for an empty priority queue.";
    cout << endl;
    if (!correct(test, 0, items)) return 0;

    cout << test_letter++ << ". ";
    cout << "Adding one item to the queue, and then testing\n";
    cout << "   is_empty, size, and get_front.";
    cout << endl;
    test.insert(100, 1);
    if (!correct(test, 1, items)) return 0;

    cout << test_letter++ << ". ";
    cout << "Inserting two items (first has higher priority).\n";
    cout << "   Then checking that both items come out correctly.";
    cout << endl;
    test.insert(100, 10);
    test.insert(200, 5);
    if (!correct(test, 2, items)) return 0;

    cout << test_letter++ << ". ";
    cout << "Inserting two items (second has higher priority).\n";
    cout << "   Then checking that both items come out correctly.";
    cout << endl;
    test.insert(200, 5);
    test.insert(100, 10);
    if (!correct(test, 2, items)) return 0;

    cout << test_letter++ << ". ";
    cout << "Inserting eight items with priorities of\n";
    cout << "   8, 10, 3, 3, 8, 6, 10, 6 (in that order)\n";
    cout << "   Then checking that all items come out correctly.";
    cout << endl;
    test.insert(3, 8);
    test.insert(100, 10);
    test.insert(8, 3);
    test.insert(7, 3);
    test.insert(4, 8);
    test.insert(5, 6);
    test.insert(200, 10);
    test.insert(6, 6);
    if (!correct(test, 8, items)) return 0;

    cout << test_letter++ << ". ";
    cout << "Inserting " << TEST_SIZE << " random items with random\n";
    cout << "   priorities, and checking that all items come out right.";
    cout << endl;
    for (priority = 0; priority < PRIORITY_LIMIT; priority++)
        occurs[priority] = 0;
    for (i = 0; i < TEST_SIZE; i++)
    {
        // Insert a bunch of random items, using items themselves as priorities
        priority = (unsigned) (rand( ) % 100);
        test.insert((int) priority, priority);
        occurs[priority]++;
    }
    priority = PRIORITY_LIMIT-1;
    for (i = 0; i < TEST_SIZE; i++)
    {
        while (occurs[priority] == 0)
            priority--;
        rand_items[i] = (int) priority;
        occurs[priority]--;
    }
    if (!correct(test, TEST_SIZE, rand_items)) return 0;

    return POINTS[1];
}

int run_a_test(int number, const char message[], int test_function( ), int max)
{
    int result;

    cout << endl << "START OF TEST " << number << ":" << endl;
    cout << message << " (" << max << " points)." << endl;
    result = test_function( );
    if (result > 0)
    {
        cout << "Test " << number << " got " << result << " points";
        cout << " out of a possible " << max << "." << endl;
    }
    else
        cout << "Test " << number << " failed." << endl;
    cout << "END OF TEST " << number << "." << endl << endl;

    return result;
}

int main( )
{
    int sum = 0;

    cout << "Running " << DESCRIPTION[0] << endl;

    sum += run_a_test(1, DESCRIPTION[1], test1, POINTS[1]);
    sum += run_a_test(2, DESCRIPTION[2], test2, POINTS[2]);
    sum += run_a_test(3, DESCRIPTION[3], test3, POINTS[3]);
    sum += run_a_test(4, DESCRIPTION[4], test4, POINTS[4]);

    cout << "If you submit this PriorityQueue now, you will have\n";
    cout << sum << " points out of the " << POINTS[0];
    cout << " points from this test program.\n";

    system("PAUSE");
    return EXIT_SUCCESS;

}

标签:测试

收藏

0人收藏

支持

0

反对

0