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

const size_t MANY_TESTS = 5;
const int POINTS[MANY_TESTS + 1] = {
                                     25,
                                     11,
                                     5,
                                     3,
                                     3,
                                     3 };
const char DESCRIPTION[MANY_TESTS + 1][256] = {
      "tests for Table template class",
      "Testing insert and the const member functions",
      "Testing remove",
      "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; }
}

struct TRec {
  int key;
  double examdata;
};

const int MAX_KEY = 5000;
bool correct(const Table<TRec>& test, double right_data[]) {
  size_t i;
  bool answer = true;
  bool find_result, is_present_result, should_be_present;
  TRec find_record;
  size_t n = 0;
  for (i = 0; answer && (i <= MAX_KEY); i++) {
    should_be_present = (right_data[i] >= 0);
    is_present_result = test.is_present(i);
    test.find(i, find_result, find_record);
    if (should_be_present != is_present_result)
      answer = false;
    else if (should_be_present != find_result)
      answer = false;
    else if (should_be_present && (right_data[i] != find_record.examdata))
      answer = false;
    if (should_be_present)
      n++; }
  if (test.size( ) != n)
    answer = false;
  cout << (answer ? "Test passed.\n" : "Test failed.\n") << endl;
  return answer;
}

int test1( ) {
  const size_t TESTSIZE = 3000;
  Table<TRec> test;
  TRec test_record;
  double right_data[MAX_KEY + 1];
  char test_letter = 'A';
  size_t i;
  int next;
  for (i = 0; i <= MAX_KEY; i++)
    right_data[i] = -1;
  cout << test_letter++ << ". ";
  cout << "Testing size, is_present and find for an empty table.";
  cout << endl;
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a record with key 4 to the Table, and then testing\n";
  cout << "   size, is_present and find.";
  cout << endl;
  test_record.key = 4;
  test_record.examdata = right_data[4] = 40.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a record with key 813 to the Table, and then testing\n";
  cout << "   size, is_present and find.";
  cout << endl;
  test_record.key = 813;
  test_record.examdata = right_data[813] = 8130.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a NEW record with key 4 to the Table, and then testing.\n";
  cout << "   This should change the record with key number 4.";
  cout << endl;
  test_record.key = 4;
  test_record.examdata = right_data[4] = 400.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a record with key 811 to the Table, and then testing.\n";
  cout << endl;
  test_record.key = 811;
  test_record.examdata = right_data[811] = 8110.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a record with key 810 to the Table, and then testing.\n";
  cout << endl;
  test_record.key = 810;
  test_record.examdata = right_data[810] = 8100.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a record with key 1611 to the Table, and then testing.\n";
  cout << endl;
  test_record.key = 1611;
  test_record.examdata = right_data[1611] = 16110.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a record with key 0 to the Table, and then testing.\n";
  cout << endl;
  test_record.key = 0;
  test_record.examdata = right_data[0] = 42.0;
  test.insert(test_record);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Inserting " << TESTSIZE << " random items with keys\n";
  cout << "between 0 and " << MAX_KEY << ", and then testing.";
  cout << endl;
  for (i = 6; i < TESTSIZE; i++) {
    next = rand( ) % (MAX_KEY + 1);
    test_record.key = next;
    test_record.examdata = right_data[next] = next / 10.0;
    test.insert(test_record); }
  if (!correct(test, right_data))
    return 0;
  return POINTS[1];
}

int test2( ) {
  const size_t TESTSIZE = 3000;
  Table<TRec> test;
  TRec test_record;
  double right_data[MAX_KEY + 1];
  char test_letter = 'A';
  size_t i;
  int next;
  for (i = 0; i <= MAX_KEY; i++)
    right_data[i] = -1;
  cout << test_letter++ << ". ";
  cout << "Putting one record into the Table, then removing it.\n";
  test_record.key = 0;
  test_record.examdata = 42.0;
  test.insert(test_record);
  test.remove(0);
  cout << endl;
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Adding a records with keys 4,5,6 to the Table, and then\n";
  cout << "   removing the 5 before testing.";
  cout << endl;
  test_record.key = 4;
  test_record.examdata = right_data[4] = 40.0;
  test.insert(test_record);
  test_record.key = 5;
  test_record.examdata = 50.0;
  test.insert(test_record);
  test_record.key = 6;
  test_record.examdata = right_data[6] = 60.0;
  test.insert(test_record);
  test.remove(5);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Trying to remove a key that is not present.\n";
  cout << "   This should have no effect on the Table.";
  cout << endl;
  test.remove(815);
  if (!correct(test, right_data))
    return 0;
  cout << test_letter++ << ". ";
  cout << "Inserting " << TESTSIZE << " random items with keys\n";
  cout << "between 0 and " << MAX_KEY << ", and then removing about half.";
  cout << endl;
  for (i = 0; i < TESTSIZE; i++) {
    next = rand( ) % (MAX_KEY + 1);
    test_record.key = next;
    test_record.examdata = right_data[next] = next / 10.0;
    test.insert(test_record); }
  for (i = 0; i < MAX_KEY; i++) {
    if (rand( ) % 2 == 0) {
      test.remove(i);
      right_data[i] = -1; } }
  if (!correct(test, right_data))
    return 0;
  return POINTS[2];
}

int test3( ) {
  const size_t TESTSIZE = 3000;
  Table<TRec> test, empty;
  Table<TRec>* table_ptr;
  size_t i;
  size_t base_usage;
  TRec test_record;
  cout << "Checking for possible heap leak." << endl;
  base_usage = memory_used_now;
  table_ptr = new Table<TRec>;
  test_record.examdata = 42.0;
  for (i = 0; i < TESTSIZE; i++) {
    test_record.key = i;
    table_ptr->insert(test_record); }
  delete table_ptr;
  if (memory_used_now != base_usage) {
    cout << "    Test failed. Possible heap leak in destructor." << endl;
    return 0; }
  for (i = 0; i < TESTSIZE; i++) {
    test_record.key = i;
    test.insert(test_record); }
  test = empty;
  if (memory_used_now != base_usage) {
    cout << "    Test failed. Possible heap leak in assignment operator." << endl;
    return 0; }
  for (i = 0; i < TESTSIZE; i++) {
    test_record.key = i;
    test.insert(test_record); }
  for (i = 0; i < TESTSIZE; i++)
    test.remove(i);
  if (memory_used_now != base_usage) {
    cout << "    Test failed. Possible heap leak in remove function." << endl;
    return 0; }
  cout << "No heap leaks found." << endl;
  return POINTS[3];
}

int test4( ) {
  Table<TRec> test;
  double right_data[MAX_KEY + 1];
  TRec test_record;
  size_t i;
  for (i = 0; i <= MAX_KEY; i++)
    right_data[i] = -1;
  cout << "A. Testing that copy constructor works okay for empty table...";
  cout << flush;
  Table<TRec> copy1(test);
  if (!correct(copy1, right_data))
    return 0;
  cout << "B. Testing copy constructor with Table that has 4,5,6,7 keys...";
  cout << flush;
  for (i = 4; i <= 7; i++) {
    test_record.key = i;
    test_record.examdata = right_data[i] = i / 10.0;
    test.insert(test_record); }
  Table<TRec> copy2(test);
  test_record.key = 8;
  test.insert(test_record);
  if (!correct(copy2, right_data))
    return 0;
  cout << "Copy constructor seems okay." << endl;
  return POINTS[4];
}

int test5( ) {
  Table<TRec> test;
  double right_data[MAX_KEY + 1];
  TRec test_record;
  char *oldbytes = new char[sizeof(Table<TRec>)];
  char *newbytes = new char[sizeof(Table<TRec>)];
  size_t i;
  for (i = 0; i <= MAX_KEY; i++)
    right_data[i] = -1;
  cout << "A. Testing that assignment works okay for empty table...";
  cout << flush;
  Table<TRec> copy1;
  copy1 = test;
  if (!correct(copy1, right_data))
    return 0;
  cout << "B. Testing assignment with Table that has 4,5,6,7 keys...";
  cout << flush;
  for (i = 4; i <= 7; i++) {
    test_record.key = i;
    test_record.examdata = right_data[i] = i / 10.0;
    test.insert(test_record); }
  Table<TRec> copy2;
  copy2 = test;
  test_record.key = 8;
  test.insert(test_record);
  if (!correct(copy2, right_data))
    return 0;
  cout << "C. Testing assignment operator for a self-assignment...";
  cout << flush;
  memcpy(oldbytes, &test, sizeof(Table<TRec>));
  test = test;
  memcpy(newbytes, &test, sizeof(Table<TRec>));
  for (i = 0; i < sizeof(Table<TRec>); i++)
    if (oldbytes[i] != newbytes[i]) {
      cout << "failed." << endl;
      return 0; }
  cout << "passed.\n";
  cout << "Assignment operator seems okay." << endl;
  return POINTS[5];
}

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]);
  sum += run_a_test(5, DESCRIPTION[5], test5, POINTS[5]);
  cout << "If you submit your program now, you will have\n";
  cout << sum << " points out of the " << POINTS[0];
  cout << " points from this test program.\n";
  return EXIT_SUCCESS;
}