// Comprueba lo que afirman los apuntes. Se compila con sanitizers.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <iostream>
#include <map>
#include <random>
#include <vector>

#include "flow.h"
#include "flow_checks.h"

namespace {

void test_pairs() {
    FlowNetwork net(3);
    const int first = net.add_edge(0, 1, 7);
    const int second = net.add_edge(1, 0, 4);  // antiparalela: otro par, independiente
    assert(first == 0 && second == 2);
    assert((first ^ 1) == 1 && (second ^ 1) == 3);
    assert(net.head(first) == 1 && net.tail(first) == 0);
    assert(net.head(first ^ 1) == 0 && net.tail(first ^ 1) == 1);
    assert(net.residual(first) == 7 && net.residual(first ^ 1) == 0);
    assert(net.capacity(second) == 4 && net.flow_on(second) == 0);
    net.push({first}, 3);
    assert(net.flow_on(first) == 3 && net.residual(first) == 4 && net.residual(first ^ 1) == 3);
    assert(net.flow_on(second) == 0 && net.capacity(first) == 7);
}

void test_first_network() {
    const std::vector<EdgeSpec> edges = first_network();

    FlowNetwork stuck = build_network(4, edges);
    assert(ford_fulkerson(stuck, 0, 3, longest_forward_rule).value == 4);
    assert(flow_is_valid(stuck, 0, 3));

    std::vector<long long> outcomes;
    greedy_outcomes(build_network(4, edges), 0, 3, outcomes);
    std::map<long long, int> tally;
    for (long long value : outcomes) tally[value]++;
    assert(tally.size() == 2 && tally[4] == 2 && tally[5] == 4);

    FlowNetwork net = build_network(4, edges);
    std::vector<Augmentation> log;
    const FlowRun run = ford_fulkerson(net, 0, 3, longest_path_rule, &log);
    assert(run.value == 5 && run.iterations == 3);
    assert(brute_min_cut(net, 0, 3) == 5);
    assert(log[1].path.size() == 3 && log[1].path[1] % 2 == 1);  // la segunda vuelta usa una inversa
    assert(count_min_cuts(net, 0, 3) == 2);

    // El error común: la inversa con capacidad c deja pasar flujo por una arista al revés.
    FlowNetwork right = build_network(4, {{0, 2, 1}, {1, 2, 1}, {1, 3, 1}});
    assert(edmonds_karp(right, 0, 3).value == 0);
    FlowNetwork wrong = build_network(4, {{0, 2, 1}, {2, 0, 1}, {1, 2, 1}, {2, 1, 1}, {1, 3, 1}, {3, 1, 1}});
    assert(edmonds_karp(wrong, 0, 3).value == 1);
}

void test_diamond() {
    for (long long big : {1LL, 10LL, 1000LL, 1000000LL}) {
        FlowNetwork adversary = build_network(4, diamond_network(big));
        const FlowRun bad = ford_fulkerson(adversary, 0, 3, longest_path_rule);
        assert(bad.value == 2 * big && bad.iterations == 2 * big);  // la pregunta de repaso 3
        FlowNetwork shortest = build_network(4, diamond_network(big));
        const FlowRun good = edmonds_karp(shortest, 0, 3);
        assert(good.value == 2 * big && good.iterations == 2);
    }
    FlowNetwork dfs = build_network(4, diamond_network(1000000));
    const FlowRun run = ford_fulkerson(dfs, 0, 3, depth_first_rule);
    assert(run.value == 2000000 && run.iterations == 4);
    // El total no cabe en int, aunque cada capacidad sí.
    FlowNetwork large = build_network(4, diamond_network(2000000000));
    assert(edmonds_karp(large, 0, 3).value == 4000000000LL);
}

// La definición: en todo corte, flujo neto = valor ≤ capacidad. Y el corte que da lo alcanzable.
void check_flow_and_cuts(const FlowNetwork& net, int source, int sink, long long value) {
    assert(flow_is_valid(net, source, sink));
    assert(net.flow_value(source) == value);
    for (unsigned mask : all_cuts(net.node_count(), source, sink)) {
        assert(net_across_cut(net, mask) == value);
        assert(value <= cut_capacity(net, mask));
    }
    const std::vector<char> side = residual_side(net, source);
    assert(side[static_cast<std::size_t>(source)] && !side[static_cast<std::size_t>(sink)]);
    assert(cut_capacity(net, mask_of(side)) == value);
    for (int e = 0; e < net.edge_count(); e++) {
        const int edge = 2 * e;
        const bool tail_in = side[static_cast<std::size_t>(net.tail(edge))];
        const bool head_in = side[static_cast<std::size_t>(net.head(edge))];
        if (tail_in && !head_in) assert(net.flow_on(edge) == net.capacity(edge));
        if (!tail_in && head_in) assert(net.flow_on(edge) == 0);
    }
}

void test_random_networks() {
    std::mt19937 rng(11);
    for (int round = 0; round < 3000; round++) {
        const int nodes = 2 + static_cast<int>(rng() % 6);
        const int count = static_cast<int>(rng() % 14);
        const unsigned max_capacity = round % 2 == 0 ? 5U : 1000000000U;
        const std::vector<EdgeSpec> edges = random_edges(rng, nodes, count, max_capacity);
        const int sink = nodes - 1;

        FlowNetwork by_bfs = build_network(nodes, edges);
        const long long expected = brute_min_cut(by_bfs, 0, sink);
        const FlowRun bfs = edmonds_karp(by_bfs, 0, sink);
        assert(bfs.value == expected);
        check_flow_and_cuts(by_bfs, 0, sink, expected);

        FlowNetwork by_dfs = build_network(nodes, edges);
        assert(ford_fulkerson(by_dfs, 0, sink, depth_first_rule).value == expected);
        check_flow_and_cuts(by_dfs, 0, sink, expected);

        // Cuesta millones de vueltas con capacidades grandes: esta regla solo con las pequeñas.
        if (max_capacity == 5U) {
            FlowNetwork by_long = build_network(nodes, edges);
            assert(ford_fulkerson(by_long, 0, sink, longest_path_rule).value == expected);
            check_flow_and_cuts(by_long, 0, sink, expected);
        }
    }
}

void test_edges_around_source_and_sink() {
    // Un ciclo por la fuente no aporta al valor. Una arista que sale del sumidero tampoco.
    FlowNetwork net = build_network(3, {{0, 1, 5}, {1, 0, 5}, {1, 2, 1}, {2, 1, 4}});
    assert(edmonds_karp(net, 0, 2).value == 1);
    assert(brute_min_cut(net, 0, 2) == 1);
    // Fuente y sumidero sin conexión: flujo 0, corte sin aristas.
    FlowNetwork apart = build_network(4, {{0, 1, 3}, {2, 3, 3}});
    assert(edmonds_karp(apart, 0, 3).value == 0);
    assert(cut_capacity(apart, mask_of(residual_side(apart, 0))) == 0);
    // Solo una arista hacia atrás: tampoco hay flujo.
    FlowNetwork back = build_network(2, {{1, 0, 9}});
    assert(edmonds_karp(back, 0, 1).value == 0);
    assert(brute_min_cut(back, 0, 1) == 0);
}

long long flow_of(int nodes, const std::vector<EdgeSpec>& edges) {
    FlowNetwork net = build_network(nodes, edges);
    return edmonds_karp(net, 0, nodes - 1).value;
}

void test_saturated_outside_the_cut() {
    FlowNetwork net = build_network(4, saturated_network());
    assert(edmonds_karp(net, 0, 3).value == 3);
    assert(count_min_cuts(net, 0, 3) == 1);  // un solo corte mínimo: no hay otro donde pueda cruzar
    const std::vector<char> side = residual_side(net, 0);
    assert(side[0] && side[1] && side[2] && !side[3]);
    const int s_to_b = 2;
    assert(net.flow_on(s_to_b) == net.capacity(s_to_b));
    long long saturated = 0;
    for (int e = 0; e < net.edge_count(); e++) {
        if (net.flow_on(2 * e) == net.capacity(2 * e)) saturated += net.capacity(2 * e);
    }
    assert(saturated == 5);
}

void test_increase_one_edge() {
    assert(flow_of(3, {{0, 1, 5}, {1, 2, 5}}) == 5);
    assert(flow_of(3, {{0, 1, 6}, {1, 2, 5}}) == 5);
    assert(flow_of(3, {{0, 1, 5}, {1, 2, 6}}) == 5);
    assert(flow_of(3, {{0, 1, 6}, {1, 2, 6}}) == 6);
    assert(count_min_cuts(build_network(3, {{0, 1, 5}, {1, 2, 5}}), 0, 2) == 2);

    std::mt19937 rng(23);
    int unique_cases = 0;
    for (int round = 0; round < 2000; round++) {
        const int nodes = 2 + static_cast<int>(rng() % 5);
        std::vector<EdgeSpec> edges = random_edges(rng, nodes, 1 + static_cast<int>(rng() % 10), 6U);
        FlowNetwork net = build_network(nodes, edges);
        const long long before = edmonds_karp(net, 0, nodes - 1).value;
        const bool unique = count_min_cuts(net, 0, nodes - 1) == 1;
        const std::vector<char> side = residual_side(net, 0);
        for (std::size_t k = 0; k < edges.size(); k++) {
            std::vector<EdgeSpec> raised = edges;
            raised[k].capacity++;
            const long long after = flow_of(nodes, raised);
            assert(after == before || after == before + 1);  // nunca sube más de 1
            const bool crosses = side[static_cast<std::size_t>(edges[k].from)] && !side[static_cast<std::size_t>(edges[k].to)];
            if (unique && crosses) {
                assert(after == before + 1);  // con corte único, una arista suya sí sube el flujo
                unique_cases++;
            }
        }
    }
    assert(unique_cases > 100);
}

void test_edmonds_karp_idea() {
    // Las distancias residuales no bajan, cada arco es crítico a lo sumo V / 2 veces, y hay a lo sumo VE vueltas.
    std::mt19937 rng(37);
    for (int round = 0; round < 3000; round++) {
        const int nodes = 2 + static_cast<int>(rng() % 9);
        const int count = static_cast<int>(rng() % 26);
        FlowNetwork net = build_network(nodes, random_edges(rng, nodes, count, 20U));
        const int sink = nodes - 1;
        std::vector<int> critical(2 * static_cast<std::size_t>(count), 0);
        std::vector<int> dist = residual_distances(net, 0);
        long long rounds = 0;
        while (true) {
            const std::vector<int> path = shortest_path_rule(net, 0, sink);
            if (path.empty()) break;
            assert(static_cast<int>(path.size()) == dist[static_cast<std::size_t>(sink)]);
            const long long amount = net.bottleneck(path);
            for (int arc : path) {
                if (net.residual(arc) == amount) critical[static_cast<std::size_t>(arc)]++;
            }
            net.push(path, amount);
            rounds++;
            const std::vector<int> next = residual_distances(net, 0);
            for (std::size_t v = 0; v < next.size(); v++) {
                if (dist[v] < 0) assert(next[v] < 0);                // lo inalcanzable sigue inalcanzable
                else if (next[v] >= 0) assert(next[v] >= dist[v]);   // la distancia no baja
            }
            dist = next;
        }
        for (int times : critical) assert(times <= nodes / 2);
        assert(rounds <= static_cast<long long>(nodes) * count);
    }
}

void test_trace_network() {
    FlowNetwork net = build_network(6, trace_network());
    std::vector<Augmentation> log;
    const FlowRun run = edmonds_karp(net, 0, 5, &log);
    assert(run.value == 8 && run.iterations == 4 && brute_min_cut(net, 0, 5) == 8);
    assert(log[0].path.size() == 3 && log[1].path.size() == 3 && log[2].path.size() == 4 && log[3].path.size() == 5);
    // El corte de los apuntes: S = {s, c}, y sus aristas s -> b, c -> a, c -> b suman 8.
    const std::vector<char> side = residual_side(net, 0);
    assert(mask_of(side) == ((1U << 0) | (1U << 3)));
    assert(cut_capacity(net, mask_of(side)) == 8);
    assert(net.flow_on(2 * 7) == net.capacity(2 * 7));  // d -> t saturada, con los dos extremos en T
    assert(net.flow_on(2 * 3) == 1);                    // b -> a bajó de 3 a 1 en la última vuelta
    for (long long factor : {1000LL, 1000000LL, 1000000000LL}) {
        std::vector<EdgeSpec> edges = trace_network();
        for (EdgeSpec& e : edges) e.capacity *= factor;
        FlowNetwork scaled = build_network(6, edges);
        const FlowRun same = edmonds_karp(scaled, 0, 5);
        assert(same.value == 8 * factor && same.iterations == 4);
    }
}

}  // namespace

int main() {
    test_pairs();
    test_first_network();
    test_diamond();
    test_random_networks();
    test_edges_around_source_and_sink();
    test_saturated_outside_the_cut();
    test_increase_one_edge();
    test_edmonds_karp_idea();
    test_trace_network();
    std::cout << "Todas las pruebas de la semana 11 pasaron.\n";
}