#include "experiment1-algorithms.hpp"
#include <array>
#include <iostream>
#include <numeric>
#include <string>

using namespace experiment1;
namespace {
std::size_t checks = 0, sorting_inputs = 0, closest_inputs = 0;
std::size_t match_inputs = 0, rejected_matches = 0;

void require(bool condition, const char* message) {
    ++checks;
    if (!condition) throw std::runtime_error(message);
}

template<class F>
void rejects(F action, const char* message) {
    bool rejected = false;
    try { action(); } catch (const std::invalid_argument&) { rejected = true; }
    require(rejected, message);
}

void check_sort(const std::vector<int>& input) {
    ++sorting_inputs;
    auto expected = input;
    std::sort(expected.begin(), expected.end());
    for (int method = 0; method < 7; ++method) {
        auto actual = input;
        if (method == 0) Insertion(actual);
        if (method == 1) Selection(actual);
        if (method >= 2 && method <= 4) Shell(actual, method - 1);
        if (method == 5) Quicksort(actual);
        if (method == 6) Mergesort(actual);
        require(actual == expected, "sort differential");
    }
    for (const auto seed : {0U, 1U, 42U}) {
        auto actual = input;
        Quicksort(actual, seed);
        require(actual == expected, "quick seed differential");
    }
}

void enumerate_arrays(std::vector<int>& a, std::size_t n,
                      void (*visit)(const std::vector<int>&)) {
    if (a.size() == n) { visit(a); return; }
    for (int value = -1; value <= 1; ++value) {
        a.push_back(value);
        enumerate_arrays(a, n, visit);
        a.pop_back();
    }
}

void sorting_tests() {
    std::vector<int> a;
    for (std::size_t n = 0; n <= 7; ++n) enumerate_arrays(a, n, check_sort);
    check_sort({std::numeric_limits<int>::min(), 0, std::numeric_limits<int>::max(),
                std::numeric_limits<int>::min(), -1});
    std::mt19937 rng(20260911U);
    for (int t = 0; t < 1000; ++t) {
        a.resize(rng() % 97);
        for (auto& v : a) v = static_cast<int>(rng() % 201) - 100;
        check_sort(a);
    }
    for (const int n : {1, 2, 31, 512, 1500}) {
        a.resize(static_cast<std::size_t>(n));
        std::iota(a.begin(), a.end(), -1000);
        check_sort(a);
        std::reverse(a.begin(), a.end());
        check_sort(a);
        std::fill(a.begin(), a.end(), 7);
        check_sort(a);
        require(Quicksort(a) == a.size(), "equal keys have linear logical depth");
    }
    a.clear();
    require(Quicksort(a) == 0, "empty logical depth");
    const std::array<std::vector<std::size_t>, 3> expected = {{
        {1, 2, 4, 8, 16}, {1, 3, 7, 15}, {1, 4, 13}
    }};
    for (int mode = 1; mode <= 3; ++mode) {
        require(shell_gaps(20, mode) == expected[static_cast<std::size_t>(mode - 1)],
                "Shell recurrence");
        require(shell_gaps(0, mode).empty(), "empty Shell gaps");
        require(shell_gaps(1, mode).empty(), "singleton Shell gaps");
        const auto maximum = std::numeric_limits<std::size_t>::max();
        const auto gaps = shell_gaps(maximum, mode);
        require(!gaps.empty() && gaps.front() == 1 && gaps.back() < maximum,
                "Shell SIZE_MAX boundary");
        const std::size_t mul = mode == 3 ? 3 : 2;
        const std::size_t add = mode == 1 ? 0 : 1;
        for (std::size_t i = 1; i < gaps.size(); ++i)
            require(gaps[i] == mul * gaps[i - 1] + add && gaps[i] > gaps[i - 1],
                    "Shell monotone recurrence");
        require(gaps.back() > (maximum - add) / mul ||
                mul * gaps.back() + add >= maximum, "Shell no missed gap");
    }
    rejects([&] { Shell(a, 0); }, "reject invalid Shell mode");
}

std::optional<std::int64_t> brute_closest(const std::vector<Point>& points) {
    if (points.size() < 2) return std::nullopt;
    std::int64_t best = std::numeric_limits<std::int64_t>::max();
    for (std::size_t i = 0; i < points.size(); ++i) {
        for (std::size_t j = i + 1; j < points.size(); ++j) {
            const std::int64_t x = points[i].x, y = points[i].y;
            const std::int64_t u = points[j].x, v = points[j].y;
            best = std::min(best, (x - u) * (x - u) + (y - v) * (y - v));
        }
    }
    return best;
}

void check_closest(const std::vector<Point>& points) {
    ++closest_inputs;
    require(closest_squared(points) == brute_closest(points), "closest differential");
}

void closest_tests() {
    check_closest({});
    check_closest({{1, 2}});
    check_closest({{-10000000, -10000000}, {10000000, 10000000}});
    require(closest_squared({{-10000000, -10000000}, {10000000, 10000000}}) ==
            800000000000000LL, "largest legal squared distance");
    check_closest({{3, 4}, {3, 4}});
    check_closest({{0, 0}, {3, 4}});
    for (unsigned mask = 0; mask < (1U << 9); ++mask) {
        std::vector<Point> points;
        for (unsigned bit = 0; bit < 9; ++bit)
            if (mask & (1U << bit))
                points.push_back({static_cast<int>(bit / 3) - 1,
                                  static_cast<int>(bit % 3) - 1});
        check_closest(points);
    }
    std::mt19937 rng(498U);
    for (int t = 0; t < 1500; ++t) {
        std::vector<Point> points(rng() % 121);
        for (auto& p : points) {
            p.x = static_cast<int>(rng() % 20000001) - 10000000;
            p.y = static_cast<int>(rng() % 20000001) - 10000000;
            if (t % 3 == 0) p.x = 0;
            if (t % 5 == 0) p.y = 0;
            if (t % 7 == 0) { p.x %= 3; p.y %= 3; }
        }
        std::shuffle(points.begin(), points.end(), rng);
        check_closest(points);
    }
    std::vector<Point> largest(400000);
    for (std::size_t i = 0; i < largest.size(); ++i)
        largest[i] = {static_cast<std::int32_t>(i) - 200000, 0};
    require(closest_squared(largest) == 1, "400000 points boundary");
    ++closest_inputs;
    largest.push_back({0, 0});
    rejects([&] { closest_squared(largest); }, "reject too many points");
    rejects([] { closest_squared({{10000001, 0}, {0, 0}}); }, "coordinate upper");
    rejects([] { closest_squared({{0, -10000001}, {0, 0}}); }, "coordinate lower");
    rejects([] { closest_squared({{std::numeric_limits<int>::min(), 0}}); },
            "validate before arithmetic");
}

// No same-type comparison operators exist on these opaque test wrappers.
struct Nut { int key; };
struct Bolt { int key; };
struct CrossCompare {
    int operator()(const Nut& nut, const Bolt& bolt) const {
        return nut.key > bolt.key ? 1 : nut.key < bolt.key ? -1 : 0;
    }
};

void check_match(const std::vector<int>& a, const std::vector<int>& b,
                 std::uint32_t seed = 20260911U) {
    ++match_inputs;
    auto sorted_a = a, sorted_b = b;
    std::sort(sorted_a.begin(), sorted_a.end());
    std::sort(sorted_b.begin(), sorted_b.end());
    const bool valid = sorted_a == sorted_b &&
        std::adjacent_find(sorted_a.begin(), sorted_a.end()) == sorted_a.end();
    std::vector<Nut> nuts;
    std::vector<Bolt> bolts;
    for (const auto v : a) nuts.push_back({v});
    for (const auto v : b) bolts.push_back({v});
    bool rejected = false;
    try { MatchNutsBolts(nuts, bolts, CrossCompare{}, seed); }
    catch (const std::invalid_argument&) { rejected = true; }
    require(rejected == !valid, "match contract detection");
    if (rejected) { ++rejected_matches; return; }
    require(nuts.size() == a.size() && bolts.size() == b.size(), "match counts");
    for (std::size_t i = 0; i < nuts.size(); ++i)
        require(nuts[i].key == sorted_a[i] && bolts[i].key == sorted_b[i],
                "match bijection differential");
}

void matching_tests() {
    for (int n = 0; n <= 5; ++n) {
        std::vector<int> a(static_cast<std::size_t>(n));
        std::iota(a.begin(), a.end(), -2);
        do {
            auto b = a;
            std::sort(b.begin(), b.end());
            do { check_match(a, b); } while (std::next_permutation(b.begin(), b.end()));
        } while (std::next_permutation(a.begin(), a.end()));
    }
    for (unsigned n = 0; n <= 3; ++n) {
        unsigned count = 1;
        for (unsigned i = 0; i < n; ++i) count *= 3;
        for (unsigned x = 0; x < count; ++x) {
            std::vector<int> a(n), b(n);
            auto code = x;
            for (auto& value : a) { value = static_cast<int>(code % 3) - 1; code /= 3; }
            for (unsigned y = 0; y < count; ++y) {
                code = y;
                for (auto& value : b) { value = static_cast<int>(code % 3) - 1; code /= 3; }
                check_match(a, b);
            }
        }
    }
    check_match({}, {1});
    check_match({1, 2}, {1});
    check_match({std::numeric_limits<int>::min(), std::numeric_limits<int>::max(), 0},
                {0, std::numeric_limits<int>::min(), std::numeric_limits<int>::max()});
    std::mt19937 rng(20260911U);
    for (unsigned t = 0; t < 1000; ++t) {
        std::vector<int> a(rng() % 101);
        std::iota(a.begin(), a.end(), -50);
        auto b = a;
        std::shuffle(a.begin(), a.end(), rng);
        std::shuffle(b.begin(), b.end(), rng);
        check_match(a, b, t);
    }
}
} // namespace

int main() {
    try {
        sorting_tests();
        closest_tests();
        matching_tests();
        std::cout << "PASS checks=" << checks << " sorting_inputs=" << sorting_inputs
                  << " closest_inputs=" << closest_inputs
                  << " match_inputs=" << match_inputs
                  << " rejected_matches=" << rejected_matches << '\n';
        return 0;
    } catch (const std::exception& error) {
        std::cerr << "FAIL after " << checks << " checks: " << error.what() << '\n';
        return 1;
    }
}