// FILE: vsetexam.cxx
// Written by: Michael Main (main@colorado.edu), Nov 16, 2009
// Each function tests part of the set class, returning some
// number of points to indicate how much of the test was passed.
// Maximum points for all of the tests is 75.

#include <iostream>
#include <malloc.h>
#include <string.h>
#include "vset.h"
using namespace std;
using namespace csci2270;

// **************************************************************************
// Replacements for new and delete:
// The next two functions replace the new and delete operators. Any code
// that is linked with this .cxx file will use these replacements instead
// of the standard new and delete. The replacements provide three features:
// 1. The global variable memory_used_now keeps track of how much memory has
//    been allocated by calls to new. (The global variable is static so that
//    it cannot be accessed outside of this .cxx file.)
// 2. The new operator fills all newly allocated memory with a GARBAGE char.
// 3. Each block of newly allocated memory is preceeded and followed by a
//    border of BORDER_SIZE characters. The first part of the front border
//    contains a copy of the size of the allocated memory. The rest of the
//    border contains a BORDER char.
// During any delete operation, the border characters are checked. If any
// border character has been changed from BORDER to something else, then an
// error message is printed and the program is halted. This stops most
// cases of writing beyond the ends of the allocated memory.
// **************************************************************************

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;   // Pointer to the entire block that we get from heap
    size_t *size_spot;     // Spot in the block where to store a copy of size
    char   *front_border;  // The border bytes in front of the user's memory 
    char   *middle;        // The memory to be given to the calling program
    char   *back_border;   // The border bytes at the back of the user's memory
    size_t i;              // Loop control variable

    // Allocate the block of memory for the user and for the two borders.
    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);
    }

    // Figure out the start points of the various pieces of the block.
    size_spot = (size_t *) whole_block;
    front_border = (char *) (whole_block + sizeof(size_t));
    middle = (char *) (whole_block + BORDER_SIZE);
    back_border = middle + size;

    // Put a copy of the size at the start of the block.
    *size_spot = size;

    // Fill the borders and the middle section.
    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;

    // Update the global static variable showing how much memory is now used.
    memory_used_now += size;
    
    return middle;
}

void operator delete(void* p)
{
    char   *whole_block;   // Pointer to the entire block that we get from heap
    size_t *size_spot;     // Spot in the block where to store a copy of size
    char   *front_border;  // The border bytes in front of the user's memory 
    char   *middle;        // The memory to be given to the calling program
    char   *back_border;   // The border bytes at the back of the user's memory
    size_t i;              // Loop control variable
    size_t size;           // Size of the block being returned
    bool   corrupt;        // Set to true if the border was corrupted

    // Figure out the start of the pieces of the block, and the size.
    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;

    // Check the borders for the BORDER character.
    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
    {
        // Fill memory with garbage in case program tries to use it
        // even after the delete.
        for (i = 0; i < size + 2*BORDER_SIZE; i++)
            whole_block[i] = GARBAGE;
        free(whole_block);
        memory_used_now -= size;
    }
    
}

const int TESTSIZE = 3000;

// Function to determine if a set is correct.
bool correct(const set& test, bool empty, bool occur[], size_t max)
// Postcondition: Some tests have been run on the test set.
// The value of empty is true provided that the entire set is empty.
// The value of occur[i] is true provided that i appears in the
// set (for i in the range 0 to max). If these requirements are met by the
// set, then the function has printed
// "Test passed." to cerr and returned true. Otherwise the function
// has printed "Test failed." to cerr and returned false.
{
    size_t i;
    bool answer = true;
    if (test.empty( ) != empty)
        answer = false;
    else
        for (i = 0; answer && (i <= max); i++)
        {
            if (occur[i] != test.contains(i))
                answer = false;
        }
    cerr << (answer ? "Test passed.\n" : "Test failed.\n") << endl;
    return answer;
}

int test1( )
// Postcondition: A handful of simple tests have been run on the 
// set data type. If all tests are passed, then the function
// returns 33. Otherwise the function returns zero.
{
    set test;
    bool items[8] = { false, false, false, false, false, false, false, false };
    bool rand_items[5000];
    char test_letter = 'A';
    int i;
    int next;

    cerr << test_letter++ << ". ";
    cerr << "Testing empty and contains for an empty set.";
    cerr << endl;
    if (!correct(test, true, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Adding the number 4 to the set, and then testing\n";
    cerr << "   empty and contains.";
    cerr << endl;
    test.insert(4);
    items[4] = true;
    if (!correct(test, false, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Inserting the number 2 into the set.\n";
    cerr << "   Then checking empty and contains.";
    cerr << endl;
    test.insert(2);
    items[2] = true;
    if (!correct(test, false, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Inserting the number 1 into the set.\n";
    cerr << "   Then checking empty and contains.";
    cerr << endl;
    test.insert(1);
    items[1] = true;
    if (!correct(test, false, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Inserting the number 3 into the set.\n";
    cerr << "   Then checking empty and contains.";
    cerr << endl;
    test.insert(3);
    items[3] = true;
    if (!correct(test, false, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Inserting another 2 into the set.\n";
    cerr << "   Then checking empty and contains.";
    cerr << endl;
    test.insert(2);
    if (!correct(test, false, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Inserting the numbers 5, 6, and 7 into the set.\n";
    cerr << "   Then checking empty and contains.";
    cerr << endl;
    test.insert(5);
    test.insert(6);
    test.insert(7);
    items[5] = true;
    items[6] = true;
    items[7] = true;
    if (!correct(test, false, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Clearing the set and testing empty and contains for an empty set.";
    cerr << endl;
    test.clear( );
    for (i = 0; i < 8; i++)
        items[i] = false;
    if (!correct(test, true, items, 7)) return 0;

    cerr << test_letter++ << ". ";
    cerr << "Inserting " << TESTSIZE << " random items between 0 and 4999\n";
    cerr << "   and then checking empty and contains.";
    cerr << endl;
    for (i = 0; i < 5000; i++)
        rand_items[i] = false;
    for (i = 0; i < TESTSIZE; i++)
    {
        next = rand( ) % 5000;
        rand_items[next] = true;
        test.insert(next);
    }
    if (!correct(test, false, rand_items, 4999)) return 0;

    return 33;
}

int needed_for_1000( )
// This function creates a local variable that is a set.
// It puts 1000 things in the set and calculates the dynamic memory
// used at that point. This value is returned.
{
    set test;
    int i;
    int answer;

    for (i=0; i < 1000; i++)
        test.insert(i);

    answer = memory_used_now;
    return answer;
}

int test2( )
// Postcondition: A heap leak test has been run on the set. If the
// test was passed, then the return value is 9. Otherwise, the return
// value is zero.
{
    set test;
    int i;
    int big_usage, final_usage;
  
    cerr << "Testing for heap leak in destructor ... " << flush;
    big_usage = needed_for_1000( );
    final_usage = memory_used_now;
    if (final_usage >= big_usage)
    {
        cerr << "failed." << endl;
        return 0;
    }
    else
        cerr << "passed." << endl;

    cerr << "Testing for heap leak in assignment operator ... " << flush;
    for (i = 0; i < TESTSIZE; i++)
        test.insert(i);
    set copy;
    big_usage = memory_used_now;
    test = copy; // Should return test's nodes to the heap
    final_usage = memory_used_now;
    if (final_usage >= big_usage)
    {
        cerr << "failed." << endl;
        return 0;
    }
    else
        cerr << "passed." << endl;

    cerr << "Testing for heap leak in remove function ... " << flush;
    for (i = 0; i < TESTSIZE; i++)
        test.insert(i);
    big_usage = memory_used_now;
    for (i = 0; i < TESTSIZE; i++)
        test.erase(i);
    final_usage = memory_used_now;
    if (final_usage >= big_usage)
    {
        cerr << "failed." << endl;
        return 0;
    }
    else
        cerr << "passed." << endl;
    
    cerr << "Testing for heap leak in clear member function... " << flush;
    for (i = 0; i < TESTSIZE; i++)
        test.insert(i);
    big_usage = memory_used_now;
    test.clear( ); // Should return test's nodes to the heap
    final_usage = memory_used_now;
    if (final_usage >= big_usage)
    {
        cerr << "failed." << endl;
        return 0;
    }
    else
        cerr << "passed." << endl;

    cerr << "No heap leaks found." << endl;
    return 9;
}

int test3( )
// Postcondition: The set's copy constructor has been tested.
// The return value is 6 if the test was passed. Otherwise the return
// value is zero.
{
    set test;
    bool items[5000];
    size_t i;

    for (i = 0; i < 5000; i++)
        items[i] = false;
    cerr << "A. Testing that copy constructor works okay for empty set...";
    cerr << flush;
    set copy1(test);
    if (!correct(copy1, true, items, 3)) return 0;

    cerr << "B. Testing copy constructor with 3-item set...";
    cerr << flush;
    test.insert(0);
    test.insert(1);
    test.insert(2);
    set copy2(test);
    test.insert(3); // Alter the original, but not the copy
    items[0] = items[1] = items[2] = true;
    if (!correct(copy2, false, items, 3)) return 0;
    
    cerr << "C. Testing copy constructor with 2500-item set...";
    cerr << flush;
    items[3] = true;
    for (i = 4; i < 5000; i += 2)
    {
        test.insert(i);
        items[i] = true;
    }
    set copy3(test);
    test.erase(3); // Alter the original, but not the copy
    if (!correct(copy3, false, items, 3)) return 0;

    cerr << "Copy constructor seems okay." << endl;
    return 6;
}

int test4( )
// Postcondition: set's assignment operator has been tested.
// The return value is 6 if the test was passed. Otherwise the return
// value is zero.
{
    set test;
    bool items[5000];
    char *oldbytes = new char[sizeof(set)];
    char *newbytes = new char[sizeof(set)];
    size_t i;

    for (i = 0; i < 5000; i++)
        items[i] = false;

    cerr << "A. Testing that assignment operator works okay for empty set...";
    cerr << flush;
    set copy1;
    copy1.insert(1);
    copy1 = test;
    if (!correct(copy1, true, items, 3)) return 0;

    cerr << "B. Testing assignment operator with 3-item set...";
    cerr << flush;
    test.insert(0);
    test.insert(1);
    test.insert(2);
    set copy2;
    copy2 = test;
    test.insert(3); // Alter the original, but not the copy
    items[0] = items[1] = items[2] = true;
    if (!correct(copy2, false, items, 3)) return 0;

    cerr << "C. Testing assignment operator for a self-assignment...";
    cerr << flush;
    memcpy(oldbytes, &test, sizeof(set));
    test = test;
    memcpy(newbytes, &test, sizeof(set));
    for (i=0; i < sizeof(set); i++)
        if (oldbytes[i] != newbytes[i])
        {
            cerr << "failed." << endl;
            return 0;
        }
    cerr << "passed.\n";        

    cerr << "D. Testing copy constructor with 2500-item set...";
    cerr << flush;
    items[3] = true;
    for (i = 4; i < 5000; i += 2)
    {
        test.insert(i);
        items[i] = true;
    }
    copy2 = test;
    test.erase(3); // Alter the original, but not the copy
    if (!correct(copy2, false, items, 3)) return 0;
    
    cerr << "Assignment operator seems okay." << endl;
    return 6;
}

int test5( )
// Postcondition: Some tests of the set's remove function have been run.
// If these tests were passed, then the return value is 21.
// Otherwise, the return value is zero.
{
    set test;
    bool rand_items[5000];
    char test_letter = 'A';
    int i;
    int next;

    cerr << test_letter++ << ". ";
    cerr << "Inserting " << TESTSIZE << " random items between 0 and 4999\n";
    cerr << "   and then removing about half of them...";
    cerr << endl;
    for (i = 0; i < 5000; i++)
        rand_items[i] = false;
    for (i = 0; i < TESTSIZE; i++)
    {
        next = rand( ) % 5000;
        rand_items[next] = true;
        test.insert(next);
    }
    for (i = 0; i < 5000; i += 2)
    {
        test.erase(i);
        if (rand_items[i])
            rand_items[i] = false;
    }
    if (!correct(test, false, rand_items, 4999)) return 0;
    
    cerr << test_letter++ << ". ";
    cerr << "Now I'll remove the rest...";
    cerr << endl;
    for (i = 1; i < 5000; i += 2)
    {
        test.erase(i);
        rand_items[i] = false;
    }
    if (!correct(test, true, rand_items, 4999)) return 0;

    return 21;
}
    
    
int main( )
{
    int value = 0;
    int result;
    
    cerr << "Running set tests:" << endl;

    cerr << "TEST 1:" << endl;
    result = test1( );
    value += result;
    if (result > 0) cerr << "Test 1 passed." << endl << endl;
    else cerr << "Test 1 failed." << endl << endl; 
 
    cerr << "\nTEST 2:" << endl;
    result = test2( );
    value += result;
    if (result > 0) cerr << "Test 2 passed." << endl << endl;
    else cerr << "Test 2 failed." << endl << endl; 
 
    cerr << "\nTEST 3:" << endl;
    result = test3( );
    value += result;
    if (result > 0) cerr << "Test 3 passed." << endl << endl;
    else cerr << "Test 3 failed." << endl << endl; 
 
    cerr << "\nTEST 4:" << endl;
    result = test4( );
    value += result;
    if (result > 0) cerr << "Test 4 passed." << endl << endl;
    else cerr << "Test 4 failed." << endl << endl; 

    cerr << "\nTEST 5:" << endl;
    result = test5( );
    value += result;
    if (result > 0) cerr << "Test 5 passed." << endl << endl;
    else cerr << "Test 5 failed." << endl << endl; 

    cerr << "If you submit the set now, you will have\n";
    cerr << value << " points out of the possible 75 points.\n";

    return EXIT_SUCCESS;
}