#include <algorithm>
#include <catch2/catch_test_macros.hpp>
#include <cmath>
#include <cstddef>
#include <random>
#include <string>
#include <vector>

#include "fold/detect/detail/edit_distance.hpp"

namespace {

std::size_t scalarDistance(const std::string& a, const std::string& b) {
    if (a.empty())
        return b.size();
    if (b.empty())
        return a.size();

    std::vector<std::size_t> prev(b.size() + 1), cur(b.size() + 1);
    for (std::size_t j = 0; j <= b.size(); ++j)
        prev[j] = j;
    for (std::size_t i = 1; i <= a.size(); ++i) {
        cur[0] = i;
        for (std::size_t j = 1; j <= b.size(); ++j) {
            const std::size_t cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            cur[j] = std::min({prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost});
        }
        std::swap(prev, cur);
    }
    return prev[b.size()];
}

double scalarSimilarity(const std::string& a, const std::string& b) {
    const std::size_t len = std::max(a.size(), b.size());
    if (len == 0)
        return 1.0;
    return 1.0 - static_cast<double>(scalarDistance(a, b)) / static_cast<double>(len);
}

std::string randomString(std::mt19937& rng, std::size_t len) {
    static constexpr char alphabet[] = "abcd{}$#0123";
    std::uniform_int_distribution<std::size_t> pick(0, sizeof(alphabet) - 2);
    std::string out;
    out.reserve(len);
    for (std::size_t i = 0; i < len; ++i)
        out.push_back(alphabet[pick(rng)]);
    return out;
}

bool nearlyEqual(double a, double b) { return std::abs(a - b) < 1e-12; }

} // namespace

TEST_CASE("rapidfuzz edit distance adapter matches scalar Levenshtein") {
    using fold::detect::detail::editDistance;

    const std::vector<std::pair<std::string, std::string>> fixed = {
        {"", ""},
        {"", "abc"},
        {"abc", ""},
        {"abc", "abc"},
        {"kitten", "sitting"},
        {std::string(63, 'a'), std::string(62, 'a') + 'b'},
        {std::string(64, 'a'), std::string(63, 'a') + 'b'},
        {std::string(65, 'a'), std::string(64, 'a') + 'b'},
        {std::string(900, 'a'), std::string(899, 'a') + 'b'},
    };
    for (const auto& [a, b] : fixed)
        REQUIRE(editDistance(a, b) == scalarDistance(a, b));

    std::mt19937 rng(0xF01D);
    for (std::size_t len_a : {0U, 1U, 7U, 31U, 64U, 65U, 127U, 160U}) {
        for (std::size_t len_b : {0U, 2U, 9U, 33U, 63U, 66U, 128U}) {
            const auto a = randomString(rng, len_a);
            const auto b = randomString(rng, len_b);
            REQUIRE(editDistance(a, b) == scalarDistance(a, b));
        }
    }
}

TEST_CASE("cutoff distance returns exact distance inside the band and cutoff+1 outside") {
    using fold::detect::detail::editDistanceCutoff;

    const std::string a = "aaaaaaaaaabbbbbbbbbb";
    const std::string b = "aaaaaaaaaacccccccccc";
    const auto exact = scalarDistance(a, b);
    REQUIRE(exact == 10);

    for (std::size_t cutoff = 0; cutoff <= 12; ++cutoff) {
        const auto got = editDistanceCutoff(a, b, cutoff);
        if (exact <= cutoff)
            REQUIRE(got == exact);
        else
            REQUIRE(got == cutoff + 1);
    }
}

TEST_CASE("thresholded normalized similarity preserves exact scores for passing pairs") {
    using fold::detect::detail::normalizedSimilarity;
    using fold::detect::detail::normalizedSimilarityAtLeast;

    const std::vector<std::pair<std::string, std::string>> pairs = {
        {"", ""},
        {"aaaaaaaaaa", "aaaaaaaabb"},
        {"aaaaaaaaaa", "bbbbbbbbbb"},
        {std::string(65, 'a'), std::string(64, 'a') + 'b'},
        {std::string(900, 'a'), std::string(899, 'a') + 'b'},
    };
    const std::vector<double> thresholds = {0.0, 0.5, 0.7, 0.8, 0.95, 1.0};

    for (const auto& [a, b] : pairs) {
        const double exact = scalarSimilarity(a, b);
        REQUIRE(nearlyEqual(normalizedSimilarity(a, b), exact));
        for (double threshold : thresholds) {
            const double got = normalizedSimilarityAtLeast(a, b, threshold);
            if (exact + 1e-12 >= threshold)
                REQUIRE(nearlyEqual(got, exact));
            else
                REQUIRE(got == 0.0);
        }
    }
}

TEST_CASE("q-gram filter is conservative relative to exact similarity") {
    using fold::detect::detail::canMeetSimilarityByQGram;

    std::mt19937 rng(0xC10A);
    const std::vector<double> thresholds = {0.5, 0.7, 0.85, 0.95, 1.0};
    for (std::size_t len_a : {3U, 7U, 31U, 64U, 127U}) {
        for (std::size_t len_b : {3U, 8U, 29U, 66U, 128U}) {
            for (int repeat = 0; repeat < 20; ++repeat) {
                const auto a = randomString(rng, len_a);
                const auto b = randomString(rng, len_b);
                const double exact = scalarSimilarity(a, b);
                for (double threshold : thresholds) {
                    if (exact + 1e-12 >= threshold) {
                        REQUIRE(canMeetSimilarityByQGram(a, b, threshold));
                    }
                }
            }
        }
    }

    REQUIRE(!canMeetSimilarityByQGram(std::string(120, 'a'), std::string(120, 'b'), 0.90));
}