#ifdef HAVE_CONFIG_H
# include <config.h>
#endif /* HAVE_CONFIG_H */

#include <check.h>
#include <limits.h>
#include "Eina_Graph.h"

static void
_feed_simple_graph(Eina_Graph *g)
{
   ck_assert(eina_graph_edge_add(g, 0, 5) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 4, 3) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 0, 1) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 9, 12) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 6, 4) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 5, 4) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 0, 2) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 11, 12) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 9, 10) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 0, 6) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 7, 8) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 9, 11) == EINA_TRUE);
   ck_assert(eina_graph_edge_add(g, 5, 3) == EINA_TRUE);
}

static void _bfs_tests(Eina_Bool directed,
                       unsigned int vertices[], unsigned int n)
{
   Eina_Graph *g;
   Eina_Graph_BFS *bfs;
   Eina_List *path, *l;
   void *data;
   int i;

   ck_assert(eina_graph_init() == 1);
   g = eina_graph_new(13, 2, directed);
   ck_assert(g != NULL);

   _feed_simple_graph(g);

   bfs = eina_graph_bfs_new(g, 0);
   ck_assert(eina_graph_bfs_source(bfs) == 0);
   ck_assert(eina_graph_bfs_has_path_to(bfs, 12) == EINA_FALSE);
   ck_assert(eina_graph_bfs_path_to(bfs, 12) == NULL);
   ck_assert(eina_graph_bfs_path_to(bfs, 15) == NULL);
   ck_assert(eina_graph_bfs_dist_to(bfs, 15) == UINT_MAX);
   ck_assert(eina_graph_bfs_has_path_to(bfs, 3) == EINA_TRUE);
   ck_assert(eina_graph_bfs_dist_to(bfs, 3) == 2);
   path = eina_graph_bfs_path_to(bfs, 3);
   ck_assert(path != NULL);
   ck_assert(eina_list_count(path) == n);
   i = 0;
   EINA_LIST_FOREACH(path, l, data)
     {
        ck_assert(vertices[i] == CAST_D(data));
        i++;
     }
   eina_graph_bfs_free(bfs);

   eina_graph_free(g);

   ck_assert(eina_graph_shutdown() == 0);
}

START_TEST (test_eina_graph_simple_bfs)
{
   unsigned int vertices[] = { 0, 5, 3 };
   _bfs_tests(EINA_FALSE, vertices, (sizeof(vertices)/sizeof(*vertices)));
}
END_TEST

START_TEST (test_eina_graph_directed_bfs)
{
   unsigned int vertices[] = { 0, 5, 3 };
   _bfs_tests(EINA_TRUE, vertices, (sizeof(vertices)/sizeof(*vertices)));
}
END_TEST

static void _dfs_tests(Eina_Bool r, Eina_Bool directed,
                       unsigned int vertices[], unsigned int n)
{
   Eina_Graph *g;
   Eina_Graph_DFS *dfs;
   Eina_List *path, *l;
   void *data;
   int i;

   ck_assert(eina_graph_init() == 1);
   g = eina_graph_new(13, 2, directed);
   ck_assert(g != NULL);

   _feed_simple_graph(g);

   dfs = eina_graph_dfs_new(g, 0, r);
   ck_assert(eina_graph_dfs_source(dfs) == 0);
   ck_assert(eina_graph_dfs_has_path_to(dfs, 12) == EINA_FALSE);
   ck_assert(eina_graph_dfs_path_to(dfs, 12) == NULL);
   ck_assert(eina_graph_dfs_path_to(dfs, 15) == NULL);
   ck_assert(eina_graph_dfs_has_path_to(dfs, 3) == EINA_TRUE);
   path = eina_graph_dfs_path_to(dfs, 3);
   ck_assert(path != NULL);
   ck_assert(eina_list_count(path) == n);
   i = 0;
   EINA_LIST_FOREACH(path, l, data)
     {
        ck_assert(vertices[i] == CAST_D(data));
        i++;
     }
   eina_graph_dfs_free(dfs);

   eina_graph_free(g);

   ck_assert(eina_graph_shutdown() == 0);
}

START_TEST (test_eina_graph_simple_dfs)
{
   unsigned int v0[] = { 0, 5, 4, 3 };
   unsigned int v1[] = { 0, 6, 4, 5, 3 };
   _dfs_tests(EINA_TRUE, EINA_FALSE, v0, (sizeof(v0)/sizeof(*v0)));
   _dfs_tests(EINA_FALSE, EINA_FALSE, v1, (sizeof(v1)/sizeof(*v1)));
}
END_TEST

START_TEST (test_eina_graph_directed_dfs)
{
   unsigned int v0[] = { 0, 5, 4, 3 };
   unsigned int v1[] = { 0, 6, 4, 3 };
   _dfs_tests(EINA_TRUE, EINA_TRUE, v0, (sizeof(v0)/sizeof(*v0)));
   _dfs_tests(EINA_FALSE, EINA_TRUE, v1, (sizeof(v1)/sizeof(*v1)));
}
END_TEST

START_TEST (test_eina_graph_simple)
{
   FILE *outf;
   Eina_Graph *g;

   ck_assert(eina_graph_init() == 1);
   ck_assert(eina_graph_init() == 2);

   g = eina_graph_new(13, 2, EINA_FALSE);
   ck_assert(g != NULL);

   _feed_simple_graph(g);

   ck_assert(eina_graph_directed(g) == EINA_FALSE);

   ck_assert(eina_graph_edge_add(g, -1, 3) == EINA_FALSE);
   ck_assert(eina_graph_edge_add(g, 3, -1) == EINA_FALSE);
   ck_assert(eina_graph_edge_add(g, 13, 3) == EINA_FALSE);
   ck_assert(eina_graph_edge_add(g, 3, 13) == EINA_FALSE);

   ck_assert(eina_graph_vertices_count(g) == 13);
   ck_assert(eina_graph_edges_count(g) == 13);
   ck_assert(eina_graph_degree(g, 4) == 3);
   ck_assert(eina_graph_degree(g, 0) == 4);
   ck_assert(eina_graph_degree(g, 15) == 0);
   ck_assert(eina_graph_degree_max(g) == 4);
   ck_assert(eina_graph_degree_avg(g) == 2.0);
   ck_assert(eina_graph_self_loops(g) == 0);

   ck_assert(eina_graph_edge_add(g, 0, 0) == EINA_TRUE);

   ck_assert(eina_graph_vertices_count(g) == 13);
   ck_assert(eina_graph_edges_count(g) == 14);
   ck_assert(eina_graph_degree(g, 4) == 3);
   ck_assert(eina_graph_degree(g, 0) == 5);
   ck_assert(eina_graph_degree_max(g) == 5);
   ck_assert(eina_graph_degree_avg(g) > 2.153);
   ck_assert(eina_graph_degree_avg(g) < 2.154);
   ck_assert(eina_graph_self_loops(g) == 1);

   outf = fopen("./eina_graph.dot", "w");
   eina_graph_dot_write(g, outf);
   fclose(outf);

   eina_graph_free(g);

   ck_assert(eina_graph_shutdown() == 1);
   ck_assert(eina_graph_shutdown() == 0);
}
END_TEST

START_TEST (test_eina_graph_directed)
{
   FILE *outf;
   Eina_Graph *g;

   ck_assert(eina_graph_init() == 1);
   ck_assert(eina_graph_init() == 2);

   g = eina_graph_new(13, 2, EINA_TRUE);
   ck_assert(g != NULL);

   _feed_simple_graph(g);

   ck_assert(eina_graph_directed(g) == EINA_TRUE);

   ck_assert(eina_graph_edge_add(g, -1, 3) == EINA_FALSE);
   ck_assert(eina_graph_edge_add(g, 3, -1) == EINA_FALSE);
   ck_assert(eina_graph_edge_add(g, 13, 3) == EINA_FALSE);
   ck_assert(eina_graph_edge_add(g, 3, 13) == EINA_FALSE);

   ck_assert(eina_graph_vertices_count(g) == 13);
   ck_assert(eina_graph_edges_count(g) == 13);
   ck_assert(eina_graph_degree(g, 4) == 1);
   ck_assert(eina_graph_degree(g, 0) == 4);
   ck_assert(eina_graph_degree(g, 15) == 0);
   ck_assert(eina_graph_degree_max(g) == 4);
   ck_assert(eina_graph_degree_avg(g) == 2.0);
   ck_assert(eina_graph_self_loops(g) == 0);

   ck_assert(eina_graph_edge_add(g, 0, 0) == EINA_TRUE);

   ck_assert(eina_graph_vertices_count(g) == 13);
   ck_assert(eina_graph_edges_count(g) == 14);
   ck_assert(eina_graph_degree(g, 4) == 1);
   ck_assert(eina_graph_degree(g, 0) == 5);
   ck_assert(eina_graph_degree_max(g) == 5);
   ck_assert(eina_graph_degree_avg(g) > 2.153);
   ck_assert(eina_graph_degree_avg(g) < 2.154);
   ck_assert(eina_graph_self_loops(g) == 1);

   outf = fopen("./eina_graph_directed.dot", "w");
   eina_graph_dot_write(g, outf);
   fclose(outf);

   eina_graph_free(g);

   ck_assert(eina_graph_shutdown() == 1);
   ck_assert(eina_graph_shutdown() == 0);
}
END_TEST

Suite *
eina_graph_suite (void)
{
   TCase *tc;
   Suite *s = suite_create ("Eina Graph");

   tc = tcase_create ("Simple Graph");
   tcase_add_test (tc, test_eina_graph_simple);
   suite_add_tcase (s, tc);

   tc = tcase_create ("Directed Graph");
   tcase_add_test (tc, test_eina_graph_directed);
   suite_add_tcase (s, tc);

   tc = tcase_create ("Simple Graph DFS");
   tcase_add_test (tc, test_eina_graph_simple_dfs);
   suite_add_tcase (s, tc);

   tc = tcase_create ("Directed Graph DFS");
   tcase_add_test (tc, test_eina_graph_directed_dfs);
   suite_add_tcase (s, tc);

   tc = tcase_create ("Simple Graph BFS");
   tcase_add_test (tc, test_eina_graph_simple_bfs);
   suite_add_tcase (s, tc);

   tc = tcase_create ("Directed Graph BFS");
   tcase_add_test (tc, test_eina_graph_directed_bfs);
   suite_add_tcase (s, tc);

   return s;
}

int
main(int argc EINA_UNUSED, char *argv[] EINA_UNUSED)
{
   int number_failed;
   Suite *s = eina_graph_suite();
   SRunner *sr = srunner_create(s);
   srunner_run_all(sr, CK_ENV);
   number_failed = srunner_ntests_failed(sr);
   srunner_free(sr);
   return ((number_failed == 0) ? 0: 1);
}