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

#include "lugraph.h"

int num_vertices = 6;
int test_edges[][2] = {{0, 1}, {1, 2}, {1, 3}, {2, 3}, {0, 4}};
int num_edges = sizeof(test_edges) / sizeof(int[2]);

void test_connected(const lugraph *g, int v1, int v2, bool expected, bool on);
void test_distance(const lugraph *g, int v1, int v2, int expected, bool on);
void test_path(const lugraph *g, int v1, int v2, int expected, bool on);

lugraph *make_dense_layered_graph(int n, int *layer_size);
lugraph *make_line_graph(int n);
lugraph *make_bipartite_graph(int n);
lugraph *make_diamond_graph(int n);
void test_connected_time(int n, int on, lugraph *(*maker)(int));
void test_distance_time(int n, int on, lugraph *(*maker)(int));
void test_path_time(int n, int on, lugraph *(*maker)(int));

int main(int argc, char **argv)
{
  if (argc == 1)
    {
      return 0;
    }
  int test = atoi(argv[1]);
  
  lugraph *g = lugraph_create(num_vertices);
  lugraph *g2 = lugraph_create(num_vertices + 1);
  if (g == NULL || g2 == NULL)
    {
      if (g != NULL)
	{
	  lugraph_destroy(g);
	}
      
      if (g2 != NULL)
	{
	  lugraph_destroy(g2);
	}
      
      printf("FAILED -- could not allocate graph\n");
      return 1;
    }

  for (int i = 0; i < num_edges; i++)
    {
      lugraph_add_edge(g, test_edges[i][0], test_edges[i][1]);
      lugraph_add_edge(g2, test_edges[i][0], test_edges[i][1]);
    }
  lugraph_add_edge(g2, 5, 6);

  switch (test)
    {
    case 1:
      test_connected(g, 0, 3, true, true);
      break;

    case 2:
      test_connected(g, 0, 5, false, true);
      break;

    case 3:
      test_distance(g, 0, 0, 0, true);
      break;

    case 4:
      test_distance(g, 0, 1, 1, true);
      break;

    case 5:
      test_distance(g, 0, 3, 2, true);
      break;

    case 6:
      test_distance(g, 5, 0, -1, true);
      break;

    case 7:
      test_path(g, 0, 0, 0, true);
      break;

    case 8:
      test_path(g, 0, 1, 1, true);
      break;

    case 9:
      test_path(g, 4, 1, 2, true);
      break;

    case 10:
      test_path(g, 4, 3, 3, true);
      break;

    case 11:
      test_path(g, 5, 0, -1, true);
      break;

    case 12:
      test_connected(g, -1, 3, false, true);
      break;

    case 18:
      test_connected(g2, 6, 5, true, true);
      break;

    case 25:
      test_connected(g2, 5, 6, true, true);
      break;

    case 24:
      test_connected(g2, 7, 3, false, true);
      break;

    case 19:
      test_connected(g, 5, 6, false, true);
      break;

    case 13:
      test_connected(g, 5, -1, false, true);
      break;

    case 20:
      test_distance(g, -1, 0, -1, true);
      break;

    case 14:
      test_distance(g2, 5, 6, 1, true);
      break;

    case 26:
      test_distance(g2, 6, 5, 1, true);
      break;

    case 27:
      test_distance(g2, 7, 5, -1, true);
      break;

    case 15:
      test_distance(g, 5, -1, -1, true);
      break;

    case 21:
      test_distance(g2, 5, 7, -1, true);
      break;

    case 16:
      test_path(g, -1, 5, -1, true);
      break;

    case 22:
      test_path(g2, 6, 5, 1, true);
      break;

    case 28:
      test_path(g2, 7, 5, -1, true);
      break;

    case 23:
      test_path(g, 0, -1, -1, true);
      break;

    case 17:
      test_path(g2, 0, 6, -1, true);
      break;

    case 29:
      test_path(g2, 0, 7, -1, true);
      break;

    case 30:
      test_connected_time(1000000, 1, make_line_graph);
      break;

    case 31:
      test_distance_time(1000000, 1, make_line_graph);
      break;

    case 32:
      test_path_time(1000000, 1, make_line_graph);
      break;

    case 33:
      test_connected_time(1000, 1, make_diamond_graph);
      break;

    case 34:
      test_distance_time(1000, 1, make_diamond_graph);
      break;

    case 35:
      test_path_time(1000, 1, make_diamond_graph);
      break;

    case 36:
      {
	int n = atoi(argv[2]);
	int on = atoi(argv[3]);
	
	test_connected_time(n, on, make_line_graph);
      }
      break;

    case 37:
      {
	int n = atoi(argv[2]);
	int on = atoi(argv[3]);
	
	test_distance_time(n, on, make_line_graph);
      }
      break;

    case 38:
      {
	int n = atoi(argv[2]);
	int on = atoi(argv[3]);
	
	test_path_time(n, on, make_line_graph);
      }
      break;

      
    default:
      printf("INVALID TEST NUMBER %s\n", argv[1]);
      break;
    }
      
  lugraph_destroy(g);
  lugraph_destroy(g2);
}

void test_connected(const lugraph *g, int v1, int v2, bool expected, bool on)
{
  if (on)
  {
    bool result = lugraph_connected(g, v1, v2);
    if ((result && !expected) || (!result && expected))
      {
	printf("FAILED\n");
      }
    else
      {
	printf("PASSED\n");
      }
  }
  else
    {
      printf("PASSED\n");
    }
}

void test_distance(const lugraph *g, int v1, int v2, int expected, bool on)
{
  lug_search *s = lugraph_bfs(g, v1);
  if (s == NULL && v1 >= 0 && v1 < lugraph_size(g))
    {
      printf("FAILED -- no search results\n");
      return;
    }
  else if (s == NULL)
    {
      // no search results b/c invalid vertex is OK
      printf("PASSED\n");
      return;
    }

  if (on)
    {
      int d = lug_search_distance(s, v2);
      
      if (d != expected)
	{
	  printf("FAILED -- reported distance is %d, not %d\n", d, expected);
	}
      else
	{
	  printf("PASSED\n");
	}
    }
  else
    {
	  printf("PASSED\n");
    }
  
  lug_search_destroy(s);
}

void test_path(const lugraph *g, int v1, int v2, int expected, bool on)
{
  lug_search *s = lugraph_bfs(g, v1);
  if (s == NULL && v1 >= 0 && v1 < lugraph_size(g))
    {
      printf("FAILED -- no search results\n");
      return;
    }
  else if (s == NULL)
    {
      // no search results b/c invalid vertex is OK
      printf("PASSED\n");
      return;
    }

  if (on)
    {
      int d;
      int *path = lug_search_path(s, v2, &d);
      if (path == NULL && expected != -1)
	{
	  // no path returned and there should have been one
	  printf("FAILED -- no path\n");
	}
      else if (d != expected)
	{
	  // path returned is not of the expected distance
	  printf("FAILED -- reported distance is %d, not %d\n", d, expected);
	}
      else if (d != -1)
	{
	  // there is a path; check the endpoints and edges
	  if (path[0] != v1 || path[d] != v2)
	    {
	      printf("FAILED -- wrong endpoints\n");
	    }
	  else
	    {
	      int i = 1;
	      while (i < d && lugraph_has_edge(g, path[i - 1], path[i]))
		{
		  i++;
		}
	      if (i < d)
		{
		  // found an invalid edge
		  printf("FAILED -- path has invalid edge (%d, %d)\n", path[i - 1], path[i]);
		}
	      else
		{
		  // all edges checked out; done!
		  printf("PASSED\n");
		}
	    }
	}
      else
	{
	  printf("PASSED\n");
	}
      
      free(path);
    }
  else
    {
      printf("PASSED\n");
    }
  
  lug_search_destroy(s);
}

lugraph *make_dense_layered_graph(int n, int *layer_size)
{
  int num_vertices = 0;
  for (int i = 0; i < n; i++)
    {
      if (layer_size[i] > 0)
	{
	  num_vertices += layer_size[i];
	}
      else
	{
	  // nonpositive layer size -- abort
	  return NULL;
	}
    }

  lugraph *g = lugraph_create(num_vertices);
  if (g == NULL)
    {
      return g;
    }

  for (int from_layer = 0, first_vertex = 0;
       from_layer < n - 1;
       first_vertex += layer_size[from_layer], from_layer++)
    {
      for (int i = 0; i < layer_size[from_layer]; i++)
	{
	  for (int j = 0; j < layer_size[from_layer + 1]; j++)
	    {
	      lugraph_add_edge(g,
			       first_vertex + i,
			       first_vertex + layer_size[from_layer] + j);
	    }
	}
    }
  return g;
}

lugraph *make_line_graph(int n)
{
  int* sizes = malloc(sizeof(int) * n);
  if (sizes == NULL)
    {
      return NULL;
    }

  for (int i = 0; i < n; i++)
    {
      sizes[i] = 1;
    }
  
  lugraph *g = make_dense_layered_graph(n, sizes);

  free(sizes);
  return g;
}

lugraph *make_bipartite_graph(int n)
{
  int sizes[2] = {n, n};
  
  lugraph *g = make_dense_layered_graph(n, sizes);

  return g;
}

lugraph *make_diamond_graph(int n)
{
  int* sizes = malloc(sizeof(int) * n);
  if (sizes == NULL)
    {
      return NULL;
    }

  for (int i = 0; i < n; i++)
    {
      if (i < n / 2)
	{
	  sizes[i] = i + 1;
	}
      else
	{
	  sizes[i] = n - i;
	}
    }
  
  lugraph *g = make_dense_layered_graph(n, sizes);

  free(sizes);
  return g;
}

void test_connected_time(int n, int on, lugraph *(*maker)(int))
{
  lugraph *g = maker(n);
  if (g == NULL)
    {
      printf("FAILED -- could not create graph\n");
      return;
    }

  test_connected(g, 0, lugraph_size(g) - 1, true, on);

  lugraph_destroy(g);
}

void test_distance_time(int n, int on, lugraph *(*maker)(int))
{
  lugraph *g = maker(n);
  if (g == NULL)
    {
      printf("FAILED -- could not create graph\n");
      return;
    }

  test_distance(g, 0, lugraph_size(g) - 1, n - 1, on);
  
  lugraph_destroy(g);
}
  
void test_path_time(int n, int on, lugraph *(*maker)(int))
{
  lugraph *g = maker(n);
  if (g == NULL)
    {
      printf("FAILED -- could not create graph\n");
      return;
    }

  test_path(g, 0, lugraph_size(g) - 1, n - 1, on);
  
  lugraph_destroy(g);
}