//
// Created by max on 04.08.22.
//

#include <boost/test/unit_test.hpp>
#include <range/v3/all.hpp>

#include <set>

#include "setgraph/graph.hpp"

BOOST_AUTO_TEST_CASE(test_creation) {
    using namespace setgraph;
    SetGraph<int> graph;

    auto a = graph.addVertex(1);
    auto b = graph.addVertex(2);
    auto c = graph.addVertex(3);
    auto d = graph.addVertex(4);

    auto ab = *graph.addEdge(a, b);
    auto ba = *graph.addEdge(b, a);
    auto bc = *graph.addEdge(b, c);
    auto cd = *graph.addEdge(c, d);
    auto da = *graph.addEdge(d, a);
    BOOST_TEST(graph.source(ab) == a);
    BOOST_TEST(graph.target(ab) == b);
    BOOST_TEST(graph.source(ba) == b);
    BOOST_TEST(graph.target(ba) == a);
    BOOST_TEST(graph.source(bc) == b);
    BOOST_TEST(graph.target(bc) == c);
    BOOST_TEST(graph.source(cd) == c);
    BOOST_TEST(graph.target(cd) == d);
    BOOST_TEST(graph.source(da) == d);
    BOOST_TEST(graph.target(da) == a);

    BOOST_TEST(graph[a] == 1);
    BOOST_TEST(graph[b] == 2);
    BOOST_TEST(graph[c] == 3);
    BOOST_TEST(graph[d] == 4);

    BOOST_TEST(graph.edge(a, b).has_value());
    BOOST_TEST(graph.edge(b, a).has_value());
    BOOST_TEST(!graph.edge(a, c).has_value());
    BOOST_TEST(!graph.edge(a, d).has_value());
    BOOST_TEST(graph.edge(d, a).has_value());
}

BOOST_AUTO_TEST_CASE(test_deletion) {
    using namespace setgraph;
    SetGraph<int> graph;

    auto a = graph.addVertex(1);
    auto b = graph.addVertex(2);
    auto c = graph.addVertex(3);
    auto d = graph.addVertex(4);

    BOOST_TEST(graph.numVertices() == 4);

    auto ab = *graph.addEdge(a, b);
    auto ba = *graph.addEdge(b, a);
    auto bc = *graph.addEdge(b, c);
    auto cd = *graph.addEdge(c, d);
    auto da = *graph.addEdge(d, a);

    BOOST_TEST(graph.numEdges() == 5);

    BOOST_TEST(graph[a] == 1);
    BOOST_TEST(graph[b] == 2);
    BOOST_TEST(graph[c] == 3);
    BOOST_TEST(graph[d] == 4);

    BOOST_TEST(graph.edge(a, b).has_value());
    BOOST_TEST(graph.edge(b, a).has_value());
    BOOST_TEST(!graph.edge(a, c).has_value());
    BOOST_TEST(!graph.edge(a, d).has_value());
    BOOST_TEST(graph.edge(d, a).has_value());

    // removing non-out_edges should not do anything
    graph.removeEdge(a, c);
    graph.removeEdge(a, d);
    graph.removeEdge(c, b);
    BOOST_TEST(graph.numEdges() == 5);
    BOOST_TEST(graph.edge(a, b).has_value());
    BOOST_TEST(graph.edge(b, a).has_value());
    BOOST_TEST(!graph.edge(a, c).has_value());
    BOOST_TEST(!graph.edge(a, d).has_value());
    BOOST_TEST(graph.edge(d, a).has_value());

    graph.removeEdge(d, a);
    BOOST_TEST(graph.numEdges() == 4);
    BOOST_TEST(!graph.edge(d, a).has_value());
    BOOST_TEST(graph.edge(a, b).has_value());
    BOOST_TEST(graph.edge(b, a).has_value());
    BOOST_TEST(!graph.edge(a, c).has_value());
    BOOST_TEST(!graph.edge(a, d).has_value());

    graph.removeEdge(ab);
    BOOST_TEST(!graph.edge(d, a).has_value());
    BOOST_TEST(!graph.edge(a, b).has_value());
    BOOST_TEST(graph.edge(b, a).has_value());
    BOOST_TEST(!graph.edge(a, c).has_value());
    BOOST_TEST(!graph.edge(a, d).has_value());

    graph.removeVertex(c);
    BOOST_TEST(graph.numVertices() == 3);
    for (auto e: graph.edges()) {
        BOOST_TEST(graph.source(e) != c);
        BOOST_TEST(graph.target(e) != c);
    }

    BOOST_TEST(!graph.edge(d, a).has_value());
    BOOST_TEST(!graph.edge(a, b).has_value());
    BOOST_TEST(graph.edge(b, a).has_value());
    BOOST_TEST(!graph.edge(a, c).has_value());
    BOOST_TEST(!graph.edge(a, d).has_value());

    graph.removeEdge(ba);
    graph.removeEdge(bc);
    graph.removeEdge(cd);
    graph.removeEdge(da);

    BOOST_TEST(graph.numEdges() == 0);

    graph.removeVertex(a);
    graph.removeVertex(b);
    BOOST_TEST(graph.numVertices() == 1);
    graph.removeVertex(c);
    BOOST_TEST(graph.numVertices() == 1);
    graph.removeVertex(d);
    BOOST_TEST(graph.numVertices() == 0);
}

BOOST_AUTO_TEST_CASE(test_iteration) {
    using namespace setgraph;
    SetGraph<int> graph;
    std::vector<int> vertex_values{1, 3, 5, 7, 9, 11};
    auto vertices = vertex_values | ranges::views::transform([&graph] (const auto& value) { return graph.template addVertex(
            value); }) | ranges::to<std::vector>();
    std::vector<std::pair<size_t, size_t>> edges{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 0}, {3, 1}, {0, 4}};
    auto edge_mapper = [&vertices] (const decltype(graph)::edge_descriptor& edge) { return std::make_pair(vertices[edge.first], vertices[edge.second]);};
    for (auto [u, v]: edges) graph.addEdge(vertices[u], vertices[v]);
    {
        auto all_vertices = vertices | ranges::to<std::set>;
        BOOST_TEST(graph.numVertices() == all_vertices.size());
        for (auto v: graph.vertices()) {
            BOOST_TEST(all_vertices.contains(v));
            all_vertices.erase(v);
        }
        BOOST_TEST(all_vertices.empty());
    }
    {
        auto all_edges = edges | ranges::views::transform(edge_mapper) | ranges::to<std::set>;
        BOOST_TEST(graph.numEdges() == all_edges.size());
        for (auto e: graph.edges()) {
            BOOST_TEST(all_edges.contains(e), "additional edge " << e.first << "->" << e.second << " enumerated but not inserted");
            all_edges.erase(e);
        }
        BOOST_TEST(all_edges.empty(), "graph.out_edges() did not enumerate all out_edges");
    }
    for (auto v: vertices) {
        auto out_neighbors = edges
                             | ranges::views::transform(edge_mapper)
                             | ranges::views::filter([v](auto edge) { return edge.first == v; })
                             | ranges::views::transform([](auto edge) { return edge.second; })
                             | ranges::to<std::set>;
        BOOST_TEST(graph.outDegree(v) == out_neighbors.size());
        for (auto w: graph.neighbors(v)) {
            BOOST_TEST(out_neighbors.contains(w));
            out_neighbors.erase(w);
        }
        BOOST_TEST(out_neighbors.empty());
    }
    for (auto v: vertices) {
        auto out_edges = edges
                             | ranges::views::transform(edge_mapper)
                             | ranges::views::filter([v](auto edge) { return edge.first == v; })
                             | ranges::to<std::set>;
        BOOST_TEST(graph.outDegree(v) == out_edges.size());
        for (auto e: graph.outEdges(v)) {
            BOOST_TEST(out_edges.contains(e));
            BOOST_TEST(graph.source(e) == v);
            BOOST_TEST(graph.target(e) == e.second);
            out_edges.erase(e);
        }
        BOOST_TEST(out_edges.empty());
    }
}

BOOST_AUTO_TEST_CASE(test_undirected) {
    using namespace setgraph;
    using UnGraph = SetGraph<Empty, Empty, EdgeDirection::Undirected>;
    using Vertex = UnGraph::vertex_descriptor;
    std::vector<set<std::pair<Vertex, Vertex>>> edgeLists({
        { {0, 1}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {4, 3}, {4, 5}, {2, 3}, {3, 6}, {3, 8}, {5, 10}, {5, 11}, {5, 12}, {10, 9}, {11, 12}, {12, 13}, {8, 9}, {8, 13}, {8, 6}, {6, 7} },
        { {0, 1}, {0, 14}, {0, 15}, {0, 16}, {1, 2}, {2, 3}, {2, 14}, {3, 4}, {3, 5}, {3, 17}, {4, 5}, {5, 6}, {5, 7}, {6, 7}, {6, 28}, {7, 8}, {8, 9}, {8, 10}, {8, 11}, {8, 12}, {8, 54}, {9, 11}, {9, 50}, {10, 12}, {10, 40}, {10, 42}, {11, 12}, {11, 15}, {11, 16}, {12, 13}, {12, 14}, {12, 48}, {13, 14}, {13, 45}, {14, 44}, {17, 18}, {18, 19}, {19, 20}, {20, 21}, {21, 22}, {21, 37}, {22, 23}, {23, 24}, {23, 25}, {25, 26}, {26, 27}, {27, 28}, {28, 51}, {24, 29}, {29, 30}, {30, 31}, {31, 32}, {31, 33}, {33, 34}, {34, 35}, {35, 36}, {35, 39}, {36, 37}, {36, 38}, {37, 43}, {37, 48}, {37, 47}, {38, 56}, {39, 55}, {40, 41}, {40, 42}, {40, 55}, {41, 55}, {43, 44}, {45, 46}, {46, 47}, {47, 48}, {48, 49}, {49, 50}, {51, 52}, {52, 53}, {53, 54}, {55, 56} }
    });
    for (const auto& edges: edgeLists) {
        UnGraph graph;
        std::vector<Vertex> vertices;
        size_t numVertices = ranges::max(edges | ranges::views::transform([](auto st) { return std::max(st.first, st.second); })) + 1;
        BOOST_TEST_MESSAGE("#vertices=" << numVertices);
        for (int i = 0; i < numVertices; ++i) vertices.push_back(graph.addVertex());
        auto vertexNames = vertices
                | ranges::views::enumerate
                | ranges::views::transform([](auto st) { return std::make_pair(st.second, st.first);})
                | ranges::to<map<UnGraph::vertex_descriptor, size_t>>();
        for (auto [s, t]: edges) {
            graph.addEdge(vertices[s], vertices[t]);
            BOOST_TEST(graph.edge(vertices[s], vertices[t]).has_value(), "edge " << s << "--" << t << " not found after insertion");
        }
        for (auto edge: graph.edges()) {
            auto s = graph.source(edge);
            auto t = graph.target(edge);
            auto u = vertexNames.at(s);
            auto v = vertexNames.at(t);
            BOOST_TEST((edges.contains({u, v}) || edges.contains({v, u})), "found unexpected edge " << u << "--" << v);
            BOOST_TEST(graph.neighbors(s).contains(t), "vertex " << v << " unexpectedly not a neighbor of " << u);
            BOOST_TEST(graph.neighbors(t).contains(s), "vertex " << u << " unexpectedly not a neighbor of " << v);
        }
        for (auto v: graph.vertices()) {
            for (auto w: graph.vertices()) {
                if (edges.contains({vertices[v], vertices[w]}) || edges.contains({vertices[w], vertices[v]})) {
                    BOOST_TEST(graph.neighbors(v).contains(w), "expected neighbor " << v << " of " << w << " not found");
                } else {
                    BOOST_TEST(!graph.neighbors(v).contains(w), "found unexpected neighbor " << w << " of " << v);
                    BOOST_TEST(!graph.edge(v, w).has_value(), "found unexpected edge " << v << "–" << w);
                }
            }
        }
        set<long> del{2, 3, 5, 7, 11};
        for (auto v: del) {
            graph.removeVertex(v);
        }
        for (auto v: graph.vertices()) {
            BOOST_TEST(!del.contains(v));
            for (auto w: graph.neighbors(v)) {
                BOOST_TEST(!del.contains(w));
            }
            for (auto w: graph.inNeighbors(v)) {
                BOOST_TEST(!del.contains(w));
            }
        }
        for (auto e: graph.edges()) {
            BOOST_TEST(!del.contains(graph.source(e)));
            BOOST_TEST(!del.contains(graph.target(e)));
        }
    }
}