/*
 * Copyright 2011 Steven Gribble
 *
 *  This file is part of the UW CSE 333 course project sequence
 *  (333proj).
 *
 *  333proj is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  333proj is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with 333proj.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "hashtable.h"
#include "CUnit/Basic.h"

// we're white-box testing; clients normally don't need to include
// any of the following three
#include "hashtable_priv.h"
#include "ll.h"
#include "ll_priv.h"

// our CUnit suite initialization/cleanup functions
void HTSAddPoints(int points);
int HTSInit(void);
int HTSCleanup(void);

// our CUnit test functions
void HTSTestAllocFree(void);
void HTSTestInsertLookupRemove(void);
void HTSTestIterator(void);

// our main function
int main(int argc, char **argv) {
  CU_pSuite pSuite = NULL;

  // initialize the test registry
  if (CU_initialize_registry() != CUE_SUCCESS) {
    return CU_get_error();
  }

  // add a suite to the registry
  pSuite = CU_add_suite("hash table suite", HTSInit, HTSCleanup);

  if (pSuite == NULL) {
    CU_cleanup_registry();
    return CU_get_error();
  }

  // add the tests to the suite
  if ((CU_ADD_TEST(pSuite, HTSTestAllocFree) == NULL) ||
      (CU_ADD_TEST(pSuite, HTSTestInsertLookupRemove) == NULL) ||
      (CU_ADD_TEST(pSuite, HTSTestIterator) == NULL)) {
    CU_cleanup_registry();
    return CU_get_error();
  }

  // run all of the tests using the CUnit basic interface
  CU_basic_set_mode(CU_BRM_VERBOSE);
  CU_basic_run_tests();
  CU_cleanup_registry();
  return CU_get_error();
}


/*** OUR TEST FUNCTIONS AND SUITE INITIALIZATION GO BELOW HERE ***/

// our payload structure
typedef struct payload_st {
  int magic_num;
  int payload_num;
} Payload;

// number of payload frees
static int num_payload_frees;

// our payload free test function
void TestPayloadFree(void *payload) {
  num_payload_frees++;
  CU_ASSERT_EQUAL_FATAL(((Payload *) payload)->magic_num, 0xDEADBEEF);
  free(payload);
}

static const int MAXGRADE = 100;
static int yourgrade = 0;

void HTSAddPoints(int points) {
  yourgrade += points;
  printf("(%d/%d)", yourgrade, MAXGRADE);
}

void HTSFinalGrade() {
  printf("\n\nYour unit test grade is %d/%d [%.02f%%]\n",
         yourgrade, MAXGRADE, (100.0*yourgrade)/MAXGRADE);
}


int HTSInit(void) {
  yourgrade = 0;
  printf("There are %d unit-testing points available.\n",
         MAXGRADE);
  return 0;  // return 0 on success, non-zero otherwise
}

int HTSCleanup(void) {
  HTSFinalGrade();
  return 0;  // return 0 on success, non-zero otherwise
}

void HTSTestAllocFree(void) {
  // simple create / delete test
  HashTable table = AllocateHashTable(3);
  HashTableRecordPtr ht = (HashTableRecordPtr) table;
  CU_ASSERT_EQUAL_FATAL(ht->num_elements, 0);
  CU_ASSERT_EQUAL_FATAL(ht->num_buckets, 3);
  CU_ASSERT_PTR_NOT_NULL(ht->buckets);
  CU_ASSERT_EQUAL_FATAL(NumElementsInLinkedList(ht->buckets[0]), 0);
  CU_ASSERT_EQUAL_FATAL(NumElementsInLinkedList(ht->buckets[1]), 0);
  CU_ASSERT_EQUAL_FATAL(NumElementsInLinkedList(ht->buckets[2]), 0);
  FreeHashTable(table, &TestPayloadFree);
  HTSAddPoints(10);
}

void HTSTestInsertLookupRemove(void) {
  // create the table
  HashTable table = AllocateHashTable(3);
  HashTableRecordPtr ht = (HashTableRecordPtr) table;

  // allocate and insert a bunch of elements
  uint64_t i;

  for (i = 0; i < 100; i++) {
    // do the insert
    Payload *np = (Payload *) malloc(sizeof(Payload));
    HTKeyValue old, new;
    assert(np != NULL);
    np->magic_num = 0xDEADBEEF;
    np->payload_num = (int) i;
    new.key = i;
    new.value = (void *) np;
    CU_ASSERT_EQUAL_FATAL(InsertHashTable(table, new, &old), 1);

    // test double insert
    CU_ASSERT_EQUAL_FATAL(InsertHashTable(table, new, &old), 2);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    CU_ASSERT_PTR_EQUAL_FATAL(old.value, (void *) np);

    // test lookup
    old.key = 1;
    old.value = NULL;
    CU_ASSERT_EQUAL_FATAL(LookupHashTable(table, i, &old), 1);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    CU_ASSERT_PTR_EQUAL_FATAL(old.value, (void *) np);

    // test bad lookup
    CU_ASSERT_EQUAL_FATAL(LookupHashTable(table, i+1, &old), 0);

    // test bad remove
    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i+1, &old), 0);

    // test good remove and reinsert
    old.key = 1;
    old.value = NULL;
    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 1);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    CU_ASSERT_PTR_EQUAL_FATAL(old.value, (void *) np);
    CU_ASSERT_EQUAL(NumElementsInHashTable(table), (uint64_t) i);
    CU_ASSERT_EQUAL_FATAL(InsertHashTable(table, new, &old), 1);
    CU_ASSERT_EQUAL_FATAL(InsertHashTable(table, new, &old), 2);
    CU_ASSERT_EQUAL(NumElementsInHashTable(table), (uint64_t) i+1);
  }
  HTSAddPoints(10);

  // delete every other key
  for (i = 0; i < 100; i += 2) {
    HTKeyValue old;

    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 1);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    TestPayloadFree(old.value);
    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 0);
  }
  CU_ASSERT_EQUAL_FATAL(ht->num_elements, 50);

  // delete the remaining keys
  for (i = 1; i < 100; i += 2) {
    HTKeyValue old;

    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 1);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    TestPayloadFree(old.value);
    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 0);
  }
  CU_ASSERT_EQUAL_FATAL(ht->num_elements, 0);

  // try a final add / remove pass
  for (i = 0; i < 100; i++) {
    // do the insert
    Payload *np = (Payload *) malloc(sizeof(Payload));
    HTKeyValue old, new;
    assert(np != NULL);
    np->magic_num = 0xDEADBEEF;
    np->payload_num = (int) i;
    new.key = i;
    new.value = (void *) np;
    CU_ASSERT_EQUAL_FATAL(InsertHashTable(table, new, &old), 1);

    // test lookup
    old.key = 1;
    old.value = NULL;
    CU_ASSERT_EQUAL_FATAL(LookupHashTable(table, i, &old), 1);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    CU_ASSERT_PTR_EQUAL_FATAL(old.value, (void *) np);
  }
  CU_ASSERT_EQUAL_FATAL(ht->num_elements, 100);

  // delete most of the remaining keys
  for (i = 0; i < 98; i++) {
    HTKeyValue old;

    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 1);
    CU_ASSERT_EQUAL_FATAL(old.key, i);
    TestPayloadFree(old.value);
    CU_ASSERT_EQUAL_FATAL(RemoveFromHashTable(table, i, &old), 0);
  }
  CU_ASSERT_EQUAL_FATAL(ht->num_elements, 2);

  // delete the HT and the final keys
  num_payload_frees = 0;
  FreeHashTable(table, &TestPayloadFree);
  CU_ASSERT_EQUAL_FATAL(num_payload_frees, 2);
  HTSAddPoints(10);
}

void HTSTestIterator(void) {
  HTKeyValue old, new;

  // create the table
  HashTable table = AllocateHashTable(3);

  // try using an iterator on an empty table
  HTIter iter = HashTableMakeIterator(table);
  HTIterRecord *it = (HTIterRecord *) iter;
  CU_ASSERT_EQUAL_FATAL(it->is_valid, 0);
  CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 1);
  CU_ASSERT_EQUAL_FATAL(HTIteratorGet(iter, &old), 0);
  HTIteratorFree(iter);
  HTSAddPoints(10);

  // allocate and insert a bunch of elements
  uint64_t i;

  for (i = 0; i < 100; i++) {
    // do the insert
    Payload *np = (Payload *) malloc(sizeof(Payload));
    assert(np != NULL);
    np->magic_num = 0xDEADBEEF;
    np->payload_num = (int) i;
    new.key = i;
    new.value = (void *) np;
    CU_ASSERT_EQUAL_FATAL(InsertHashTable(table, new, &old), 1);
  }
  // create an iterator on the table
  iter = HashTableMakeIterator(table);
  it = (HTIterRecord *) iter;
  CU_ASSERT_EQUAL_FATAL(it->is_valid, 1);
  HTSAddPoints(10);

  // iterate through, verifying each value is found exactly once
  int valarray[100] = { 0 };   // array of 100 0's
  for (i = 0; i < 100; i++) {
    Payload *op;

    CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 0);
    CU_ASSERT_EQUAL_FATAL(HTIteratorGet(iter, &old), 1);
    CU_ASSERT_EQUAL_FATAL(valarray[(int) old.key], 0);
    valarray[(int) old.key] = 1;
    op = (Payload *) old.value;
    CU_ASSERT_EQUAL_FATAL(op->magic_num, 0xDEADBEEF);
    CU_ASSERT_EQUAL_FATAL(op->payload_num, (int) old.key);
    if (i == 99) {
      CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 0);
      CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 1);
    } else {
      CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 1);
      CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 0);
    }
  }
  for (i = 0; i < 100; i++) {
    CU_ASSERT_EQUAL_FATAL(valarray[i], 1);
  }
  CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 0);
  HTIteratorFree(iter);
  HTSAddPoints(20);

  // Iterate through again, deleting every third key.
  iter = HashTableMakeIterator(table);
  it = (HTIterRecord *) iter;
  CU_ASSERT_EQUAL_FATAL(it->is_valid, 1);
  for (i = 0; i < 100; i++) {
    Payload *op;

    valarray[i] = 0;
    CU_ASSERT_EQUAL_FATAL(HTIteratorGet(iter, &old), 1);
    if (((int) old.key) % 3 == 0) {
      int oldnumelements, newnumelements;

      oldnumelements = (int) NumElementsInHashTable(table);
      op = (Payload *) old.value;
      CU_ASSERT_EQUAL_FATAL(op->payload_num, (int) old.key);
      if (i == 99) {
        CU_ASSERT_EQUAL_FATAL(HTIteratorDelete(iter, &old), 2);
      } else {
        CU_ASSERT_EQUAL_FATAL(HTIteratorDelete(iter, &old), 1);
      }
      newnumelements = (int) NumElementsInHashTable(table);
      CU_ASSERT_EQUAL_FATAL(oldnumelements-1, newnumelements);
      op = (Payload *) old.value;
      free(op);
    } else {
      if (i == 99) {
        CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 0);
        CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 1);
      } else {
        CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 1);
        CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 0);
      }
    }
  }
  // Free the iterator
  HTIteratorFree(iter);
  HTSAddPoints(10);

  // Iterate through one last time, making sure we get only
  // the non-zero mod 3 keys.
  iter = HashTableMakeIterator(table);
  it = (HTIterRecord *) iter;
  CU_ASSERT_EQUAL_FATAL(it->is_valid, 1);
  for (i = 0; i < 66; i++) {
    CU_ASSERT_EQUAL_FATAL(HTIteratorGet(iter, &old), 1);
    valarray[(int) old.key] = 1;
    if (i == 65) {
      CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 0);
      CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 1);
    } else {
      CU_ASSERT_EQUAL_FATAL(HTIteratorNext(iter), 1);
      CU_ASSERT_EQUAL_FATAL(HTIteratorPastEnd(iter), 0);
    }
  }
  for (i = 0; i < 100; i++) {
    if (i % 3 == 0) {
      CU_ASSERT_EQUAL_FATAL(valarray[i], 0);
    } else {
      CU_ASSERT_EQUAL_FATAL(valarray[i], 1);
    }
  }
  // Free the iterator
  HTIteratorFree(iter);
  HTSAddPoints(10);

  // delete the HT and the final keys
  num_payload_frees = 0;
  FreeHashTable(table, &TestPayloadFree);
  CU_ASSERT_EQUAL_FATAL(num_payload_frees, 66);
  HTSAddPoints(10);
}