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

bool vnd3(Solution& sol, int d, RNG& rng) {
    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];
        double old_dist = g.dist(v, p);
        size_t old_edge = g.edge_id(v, p);

        for (int w = 0; w < n; ++w) {
            if (w == v || w == p) continue;
            if (sol.degree[w] <= 0) continue;
            if (sol.degree[w] >= d) continue;

            double new_dist = g.dist(v, w);
            if (new_dist < old_dist) {
                sol.remove_edge(old_edge);
                sol.add_edge(g.edge_id(v, w));
                return true;
            }
        }
    }

    return false;
}

bool vnd3bi(Solution& sol, int d, [[maybe_unused]] RNG& rng) {
    const auto& g = *sol.graph;
    const int n = g.size();

    double best_gain = 0.0;
    int best_v = -1, best_w = -1;
    size_t best_old_edge = 0;

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

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

        for (int w = 0; w < n; ++w) {
            if (w == v || w == p) continue;
            if (sol.degree[w] <= 0) continue;
            if (sol.degree[w] >= d) continue;

            double gain = old_dist - g.dist(v, w);
            if (gain > best_gain) {
                best_gain = gain;
                best_v = v; best_w = w;
                best_old_edge = old_edge;
            }
        }
    }

    if (best_v < 0) return false;

    sol.remove_edge(best_old_edge);
    sol.add_edge(g.edge_id(best_v, best_w));
    return true;
}