#include "vnd4.hpp"
#include <algorithm>
#include <vector>

bool vnd4(Solution& sol, int d, RNG& rng) {
    if (d < 2) return false;  // v would end up with degree 2

    const auto& g = *sol.graph;
    const int n = g.size();

    // Collect all leaves (degree-1 nodes)
    std::vector<int> leaves;
    for (int v = 0; v < n; ++v) {
        if (sol.degree[v] == 1) leaves.push_back(v);
    }

    // Fisher-Yates shuffle
    for (int i = static_cast<int>(leaves.size()) - 1; i > 0; --i) {
        int j = static_cast<int>(rng.next_int(static_cast<uint32_t>(i + 1)));
        std::swap(leaves[i], leaves[j]);
    }

    for (int v : leaves) {
        if (sol.degree[v] != 1) continue;

        int p = sol.adj[v][0];
        size_t vp_edge = g.edge_id(v, p);
        double vp_dist = g.dist(vp_edge);

        // Try splitting each solution edge (a,b) through v
        // Snapshot edges since we return immediately on improvement
        for (size_t idx = 0; idx < sol.edges.size(); ++idx) {
            size_t ab_edge = sol.edges[idx];
            if (ab_edge == vp_edge) continue;

            auto [a, b] = g.edge_nodes(ab_edge);
            double ab_dist = g.dist(ab_edge);

            double new_cost = g.dist(a, v) + g.dist(v, b);
            if (new_cost < vp_dist + ab_dist) {
                sol.remove_edge(vp_edge);
                sol.remove_edge(ab_edge);
                sol.add_edge(g.edge_id(a, v));
                sol.add_edge(g.edge_id(v, b));
                return true;
            }
        }
    }

    return false;
}

bool vnd4bi(Solution& sol, int d, [[maybe_unused]] RNG& rng) {
    if (d < 2) return false;

    const auto& g = *sol.graph;
    const int n = g.size();

    double best_gain = 0.0;
    int best_v = -1, best_a = -1, best_b = -1;
    size_t best_vp_edge = 0, best_ab_edge = 0;

    for (int v = 0; v < n; ++v) {
        if (sol.degree[v] != 1) continue;

        int p = sol.adj[v][0];
        size_t vp_edge = g.edge_id(v, p);
        double vp_dist = g.dist(vp_edge);

        for (size_t idx = 0; idx < sol.edges.size(); ++idx) {
            size_t ab_edge = sol.edges[idx];
            if (ab_edge == vp_edge) continue;

            auto [a, b] = g.edge_nodes(ab_edge);
            double old_cost = vp_dist + g.dist(ab_edge);
            double new_cost = g.dist(a, v) + g.dist(v, b);
            double gain = old_cost - new_cost;

            if (gain > best_gain) {
                best_gain = gain;
                best_v = v; best_a = a; best_b = b;
                best_vp_edge = vp_edge;
                best_ab_edge = ab_edge;
            }
        }
    }

    if (best_v < 0) return false;

    sol.remove_edge(best_vp_edge);
    sol.remove_edge(best_ab_edge);
    sol.add_edge(g.edge_id(best_a, best_v));
    sol.add_edge(g.edge_id(best_v, best_b));
    return true;
}