#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "graph.h"
#include "string_key.h"

/* for testing coupling between different maps */

void test_has_vertex();
void test_has_vertices(size_t n);
void test_has_edge(bool self);
void test_has_edge_reversed();
void test_add_edge();
void test_bfs_distance(size_t n);
void test_common_neighbors(size_t n);
void test_common_neighbors_dense(size_t n);
void test_timing_bfs(size_t n, int on, bool dense);
void test_timing_common_neighbors(size_t n, int on, bool dense);

#define SMALL_TEST_SIZE 4
#define MEDIUM_SMALL_TEST_SIZE 20
#define MEDIUM_TEST_SIZE 100
#define LARGE_TEST_SIZE 1000
#define VERY_LARGE_TEST_SIZE 10000000
#define PRINT_PASSED fprintf(stdout, "PASSED\n")
#define MAX_INT_DIGITS (20)

char **make_words(const char *prefix, size_t n)
{
  size_t prefix_len = strlen(prefix);
  char **arr = malloc(sizeof(char *) * n);
  for (size_t i = 0; i < n; i++)
    {
      arr[i] = malloc(sizeof(char) * (prefix_len + MAX_INT_DIGITS + 1));
      sprintf(arr[i], "%s%lu", prefix, i);
    }

  return arr;
}

void free_words(char **arr, size_t n)
{
  for (size_t i = 0; i < n; i++)
    {
      free(arr[i]);
    }
  free(arr);
}

// these vars will be used for timing tests later
void foo(size_t n, int on) {
  return;
}

int main(int argc, char **argv)
{
  int test = 0;
  size_t n = 0;
  int on = 0;

  if (argc > 1)
  {
    test = atoi(argv[1]);
  }
  if (argc > 2)
  {
    // test size and on/off
    if (atoi(argv[2]) < 0)
    {
      fprintf(stderr, "%s: test size must be positive\n", argv[0]);
      return 1;
    }
    n = atoi(argv[2]);
    on = atoi(argv[3]) == 1;
    foo(n, on);
  }

  switch (test)
  {

  case 1:
    test_add_edge();
    break;

  case 2:
    test_has_vertex();
    break;

  case 3:
    test_has_edge(false);
    break;

  case 4:
    test_has_edge_reversed();
    break;

  case 5:
    test_has_vertices(LARGE_TEST_SIZE);
    break;

  case 6:
    test_bfs_distance(MEDIUM_SMALL_TEST_SIZE);
    break;

  case 7:
    test_common_neighbors(MEDIUM_SMALL_TEST_SIZE);
    break;

  case 8: // sparse graph
    test_timing_bfs(n, on, false);
    break;

  case 9: // sparse graph
    test_timing_common_neighbors(n, on, false);
    break;

  case 10: // dense graph
    test_timing_bfs(n, on, true);
    break;

  case 11: // dense graph
    test_timing_common_neighbors(n, on, true);
    break;

  case 12: // edge to self, test has_edge and add_edge
    test_has_edge(true);
    break;

  case 13: // fully connected graph, all nodes are neighbors
    test_common_neighbors_dense(MEDIUM_TEST_SIZE);
    break;

  default:
    fprintf(stderr, "USAGE: %s test-number\n", argv[0]);
  }
}

void test_add_edge() {
    undigraph *g = undigraph_create();
    char person_1[] = "Bob";
    char person_2[] = "Joe";
    undigraph_add_edge(g, person_1, person_2);
    PRINT_PASSED;
    undigraph_destroy(g);
    return;
}

void test_has_vertex() {
    undigraph *g = undigraph_create();
    char person_1[] = "Bob";
    char person_2[] = "Joe";
    undigraph_add_edge(g, person_1, person_2);
    if (!undigraph_has_vertex(g, person_1) || !undigraph_has_vertex(g, person_2)) {
        printf("FAILED -- both adds not detected\n");
        goto cleanup;
    }
    PRINT_PASSED;
    undigraph_destroy(g);
    return;

    cleanup:
        undigraph_destroy(g);
        return;
}

void test_has_edge(bool self) {
    undigraph *g = undigraph_create();
    char person_1[] = "Bob";
    char person_2[] = "Joe";
    if (self) {
      person_2[0] = 'B';
      person_2[2] = 'b';
    }
    undigraph_add_edge(g, person_1, person_2);
    if (!undigraph_has_edge(g, person_1, person_2)) {
        printf("FAILED -- edge not detected\n");
        goto cleanup;
    }
    PRINT_PASSED;
    undigraph_destroy(g);
    return;

    cleanup:
        undigraph_destroy(g);
        return;
}

// has_edge should work even if order of vertices is reversed
void test_has_edge_reversed() {
    undigraph *g = undigraph_create();
    char person_1[] = "Bob";
    char person_2[] = "Joe";
    undigraph_add_edge(g, person_1, person_2);
    if (!undigraph_has_edge(g, person_2, person_1)) {
        printf("FAILED -- edge not detected\n");
        goto cleanup;
    }
    PRINT_PASSED;
    undigraph_destroy(g);
    return;

    cleanup:
        undigraph_destroy(g);
        return;
}

void test_has_vertices(size_t n) {
    undigraph *g = undigraph_create();
    const char *prefix = "Bob";
    char **words = make_words(prefix, n);
    for (size_t i = 0; i < n - 1; i += 2) {
        undigraph_add_edge(g, words[i], words[i + 1]);
    }
    for (size_t i = 0; i < n - 1; i += 2) {
        if (!undigraph_has_edge(g, words[i], words[i + 1])) {
            printf("FAILED -- edge between %s and %s not detected\n", words[i], words[i + 1]);
            goto cleanup;
        }
    }
    undigraph_destroy(g);
    free_words(words, n);
    PRINT_PASSED;
    return;

    cleanup:
        undigraph_destroy(g);
        free_words(words, n);
        return;
}

void test_bfs_distance(size_t n) {
    undigraph *g = undigraph_create();
    const char *prefix = "Bob";
    char **words = make_words(prefix, n);
    for (size_t i = 0; i < n - 1; i += 1) {
        undigraph_add_edge(g, words[i], words[i + 1]);
    }
    for (size_t i = 0; i < n - 1; i++) {
    	for (size_t j = 0; j < n - 1; j++) {
	    size_t dist = undigraph_bfs_distance(g, words[i], words[j]);
	    size_t real_dist = i > j ? i - j : j - i;

	    if (dist != real_dist) {
        printf("FAILED -- distance beetween %s and %s outputted %ld instead of %ld\n", 
				words[i], words[j], dist, real_dist);
        goto cleanup;
      }
	}
    }
    PRINT_PASSED;
    undigraph_destroy(g);
    free_words(words, n);
    return;

    cleanup:
        undigraph_destroy(g);
        free_words(words, n);
        return;
}

void test_common_neighbors(size_t n) {
    undigraph *g = undigraph_create();
    const char *prefix = "Bob";
    char **words = make_words(prefix, n);
    for (size_t i = 0; i < n - 1; i += 1) {
        undigraph_add_edge(g, words[i], words[i + 1]);
    }
    for (size_t i = 0; i < n - 1; i++) {
    	for (size_t j = 0; j < n - 1; j++) {
        if (i == j) {
          continue;
        }
        size_t count = 0;
        bool success = false;
        char **name = undigraph_common_neighbors(g, words[i], words[j], &count, &success);
        size_t real_count=0;
        if (i-j == 2 || j-i == 2)
          real_count = 1;
        if (count != real_count) {
          printf("FAILED -- common neighbors beetween %s and %s outputted %ld instead of %ld\n", 
          words[i], words[j], count, real_count);
          for (size_t k = 0; k < count; k++) {
            free(name[k]);
          }
          free(name);
          goto cleanup;
        }
        if (count != 0) {
          size_t neighbor = i>j ? i-1 : i+1;
          if (strcmp(name[0], words[neighbor]) != 0) {
            printf("FAILED -- common neighbors beetween %s and %s outputted %s instead of %s\n", 
            words[i], words[j], name[0], words[neighbor]);
            for (size_t k = 0; k < count; k++) {
              free(name[k]);
            }
            free(name);
            goto cleanup;
          }
        }
        for (size_t k = 0; k < count; k++) {
          free(name[k]);
        }
        free(name);
	    }
    }
    PRINT_PASSED;
    undigraph_destroy(g);
    free_words(words, n);
    return;

    cleanup:
        undigraph_destroy(g);
        free_words(words, n);
        return;
}

void test_common_neighbors_dense(size_t n) {
    undigraph *g = undigraph_create();
    // make a linked list
    char prefix[] = "node";
    char **words = make_words(prefix, (2 * n));
    for (size_t i = 0; i < (2 * n) - 1; i++) {
        undigraph_add_edge(g, words[i], words[i + 1]);
    }
    // connect the top to the bottom, forming a circle
    undigraph_add_edge(g, words[0], words[(2 * n) - 1]);
    
    // connect all edges
    for (size_t i = 0; i < n * 2; i++) {
      for (size_t j = 0; j < n * 2; j++) {
        if (i == j) {
          continue;
        }
        if (!undigraph_has_edge(g, words[i], words[j])) {
          undigraph_add_edge(g, words[i], words[j]);
        }
      }
    }

    qsort(words, n * 2, sizeof(char *), string_ptr_compare);

    for (size_t i = 0; i < n; i++) {
      size_t count = 0;
      bool success = false;
      char **neighbors = undigraph_common_neighbors(g, words[i], words[n + i], &count, &success);

      if (!success) {
        printf("FAILED -- success flag not raised\n");
        free_words(neighbors, count);
        goto cleanup;
      }

      if (count != (n * 2) - 2) {
        printf("FAILED -- number of neighbors between %s and %s is %zu instead of %zu\n", words[i], words[n + i], count, (n * 2) - 2);
        free_words(neighbors, count);
        goto cleanup;
      }

      qsort(neighbors, count, sizeof(char *), string_ptr_compare);

      size_t words_iterator = 0;
      for (size_t k = 0; k < count; k++) {
        if (words_iterator == i || words_iterator == n + i) {
          words_iterator++;
        }
        if (strcmp(neighbors[k], words[words_iterator]) != 0) {
          printf("FAILED -- expected neighbor %s, got neighbor %s\n", words[words_iterator], neighbors[k]);
          free_words(neighbors, count);
          goto cleanup;
        }
        words_iterator++;
      }

      free_words(neighbors, count);
    }

    PRINT_PASSED;
    undigraph_destroy(g);
    free_words(words, n * 2);
    return;
    cleanup:
      undigraph_destroy(g);
      free_words(words, n * 2);
      return;
}

void test_timing_bfs(size_t n, int on, bool dense) {
    undigraph *g = undigraph_create();
    // make a linked list
    char prefix[] = "node";
    char **words = make_words(prefix, (2 * n));
    for (size_t i = 0; i < (2 * n) - 1; i++) {
        undigraph_add_edge(g, words[i], words[i + 1]);
    }
    // connect the top to the bottom
    undigraph_add_edge(g, words[0], words[(2 * n) - 1]);

    if (dense) {
      for (size_t i = 0; i < n * 2; i++) {
        for (size_t j = 0; j < n * 2; j++) {
          if (i == j) {
            continue;
          }
          if (!undigraph_has_edge(g, words[i], words[j])) {
            undigraph_add_edge(g, words[i], words[j]);
          }
        }
      }
    }

    // call bfs on different sides of the circle
    if (on) {
      for (size_t i = 0; i < 10; i++) {
        size_t distance = undigraph_bfs_distance(g, words[i], words[i + n]);
        if ((!dense && distance != n) || (dense && distance != 1)) {
          printf("FAILED -- distance between %s and %s is %zu instead of %zu\n", words[i], words[i + n], distance, n);
          goto cleanup;
        }
      }
    }
    undigraph_destroy(g);
    free_words(words, n * 2);
    return;
    cleanup:
      undigraph_destroy(g);
      free_words(words, n * 2);
      return;
}

void test_timing_common_neighbors(size_t n, int on, bool dense) {
    undigraph *g = undigraph_create();

    size_t DISTRACTION_FACTOR = 10;

    char **words_left_left;
    char **words_right_right;

    // make a small linked list
    char prefix[] = "middle";
    char **words = make_words(prefix, n);

    if (dense) {
      // a large set of vertices connected to a left node of interest
      char prefix_left_left[] = "leftleft";
      words_left_left = make_words(prefix_left_left, n * DISTRACTION_FACTOR);
    
      for (size_t i = 0; i < (n * DISTRACTION_FACTOR) - 1; i++) {
          undigraph_add_edge(g, words_left_left[i], "left");
      }

      // another very large set, connected to a right node of interest
      char prefix_right_right[] = "rightright";
      words_right_right = make_words(prefix_right_right, n * DISTRACTION_FACTOR);

      for (size_t i = 0; i < (n * DISTRACTION_FACTOR) - 1; i++) {
          undigraph_add_edge(g, words_right_right[i], "right");
      }

      // connect each node in the linked list to each node in the left_left and right_right sets
      for (size_t i = 0; i < n; i++) {
        for (size_t j = 0; j < i * DISTRACTION_FACTOR; j++) {
          undigraph_add_edge(g, words[i], words_left_left[j]);
          undigraph_add_edge(g, words[i], words_right_right[j]);
        }
      }
    }

    for (size_t i = 0; i < n - 1; i++) {
        undigraph_add_edge(g, words[i], words[i + 1]);
    }

    // connect each node in the linked list to the two nodes of interest
    for (size_t i = 0; i < n; i++) {
      undigraph_add_edge(g, "left", words[i]);
      undigraph_add_edge(g, "right", words[i]);
    }

    char **neighbors;

    // call mutual on the two nodes of interest
    if (on) {
      size_t N_ITERATIONS = 3;
      for (size_t i = 0; i < N_ITERATIONS; i++) {
        size_t count = 0;
        bool valid = true;
        neighbors = undigraph_common_neighbors(g, "left", "right", &count, &valid);
        if (count != n) {
          printf("FAILED -- count between left node and right node is %zu instead of %zu\n", count, n);
          free_words(neighbors, n);
          goto cleanup;
        }
        free_words(neighbors, n);
      }

      // don't test correctness (don't want to introduce nlogn term)
      /*
      size_t SUBGRAPH_SIZE = 20;

      qsort(neighbors, SUBGRAPH_SIZE, sizeof(char *), string_ptr_compare);
      qsort(words, SUBGRAPH_SIZE, sizeof(char *), string_ptr_compare);

      for (size_t i = 0; i < SUBGRAPH_SIZE; i++) {
        if (strcmp(neighbors[i], words[i]) != 0) {
            printf("FAILED -- neighbor %zu is %s while expected neighbor is %s\n", i, neighbors[i], words[i]);
            free_words(neighbors, n);
            goto cleanup;
        }
      }
      free_words(neighbors, n);
      */
    }

    undigraph_destroy(g);
    free_words(words, n);
    if (dense) {
      free_words(words_right_right, n * DISTRACTION_FACTOR);
      free_words(words_left_left, n * DISTRACTION_FACTOR);
    }
    return;
    cleanup:
      undigraph_destroy(g);
      free_words(words, n);
      if (dense) {
        free_words(words_right_right, n * DISTRACTION_FACTOR);
        free_words(words_left_left, n * DISTRACTION_FACTOR);
      }
      return;
}