// Pruebas de lo que los apuntes afirman sobre la franja del par más cercano.
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <random>
#include <vector>

#include "strip.h"

static void test_notes_examples() {
    std::vector<Point> example = {{1, 9}, {2, 3}, {3, 7}, {4, 1}, {5, 5}, {6, 4}, {7, 10}, {8, 8}, {9, 2}, {10, 6}};
    RootStep root = analyze_root(example);
    assert(root.line == 6);
    assert(root.left_best == 8);
    assert(root.right_best == 5);
    assert(root.delta2 == 5);
    assert(root.strip.size() == 5);
    assert(root.best_in_strip == 2);
    assert(brute_force(example) == 2);

    std::vector<Point> near_line = {{-2, 0}, {-1, 100}, {1, -100}, {2, 0}};
    RootStep second = analyze_root(near_line);
    assert(brute_force(near_line) == 16);
    assert(second.best_in_strip == 16);
    assert(dist2({-1, 100}, {1, -100}) == 40004);

    std::vector<Point> next_only = {{-9, 50}, {-1, 0}, {0, 2}, {8, 1}};
    RootStep third = analyze_root(next_only);
    assert(third.delta2 == 65);
    assert(best_with_window(third, 1) == 65);
    assert(best_with_window(third, 7) == 5);
    assert(brute_force(next_only) == 5);

    std::vector<Point> three_apart = {{-99, 50}, {0, 0}, {1, 99}, {99, 51}};
    RootStep fourth = analyze_root(three_apart);
    assert(fourth.max_gap == 3);
    assert(best_with_window(fourth, 2) == 11908);
    assert(best_with_window(fourth, 3) == 9802);
    assert(brute_force(three_apart) == 9802);

    // Un par por debajo de δ² a 5 posiciones, aunque la respuesta sea otro par.
    std::vector<Point> far_apart = {{-99, 15}, {-20, 98}, {0, 0}, {1, 99}, {25, 1}, {99, 70}};
    RootStep fifth = analyze_root(far_apart);
    assert(fifth.max_gap == 5);
    assert(dist2({0, 0}, {1, 99}) == 9802 && fifth.delta2 == 10004);
    assert(brute_force(far_apart) == 442);
}

// Todos sobre una vertical, con dos desempates en el orden por x: la respuesta no cambia.
static void test_vertical_ties() {
    std::vector<Point> mixed = {{5, 0}, {5, 10}, {5, 20}, {5, 30}, {5, 3}, {5, 13}, {5, 23}, {5, 33}};
    RootStep first = analyze_root(mixed);
    assert(first.line == 5);
    assert(first.delta2 == 100);
    assert(first.strip.size() == 8);
    assert(first.best_in_strip == 9);
    assert(first.max_gap == 1);

    std::vector<Point> by_height = {{5, 0}, {5, 3}, {5, 10}, {5, 13}, {5, 20}, {5, 23}, {5, 30}, {5, 33}};
    RootStep second = analyze_root(by_height);
    assert(second.delta2 == 9);
    assert(second.strip.size() == 8);
    assert(second.best_in_strip == 9);
}

// Puntos repetidos a los dos lados de la línea: δ > 0 y aun así la respuesta es 0.
static void test_duplicate_across_line() {
    std::vector<Point> points = {{0, 0}, {5, 5}, {5, 5}, {9, 9}};
    RootStep step = analyze_root(points);
    assert(step.delta2 == 32);
    assert(step.best_in_strip == 0);
    assert(step.max_gap <= 7);
}

// Un punto repetido dentro de una mitad da δ = 0, y la franja queda vacía.
static void test_duplicate_inside_half() {
    std::vector<Point> points = {{1, 1}, {1, 1}, {4, 2}, {7, 3}};
    RootStep step = analyze_root(points);
    assert(step.delta2 == 0);
    assert(step.strip.empty());
    assert(step.best_in_strip == 0);
}

// El lema: para toda entrada y todo desempate, un par de la franja con distancia menor que δ está a
// lo sumo a 7 posiciones. Además, ese par siempre cruza, y con 7 vecinos se halla la respuesta correcta.
static long long test_lemma(unsigned seed, int rounds, int max_n, long long range, bool vertical) {
    std::mt19937 rng(seed);
    long long largest_gap = 0;
    for (int round = 0; round < rounds; round++) {
        int n = 4 + static_cast<int>(rng() % static_cast<unsigned>(max_n - 3));
        std::vector<Point> points(n);
        for (Point& p : points) {
            p.x = vertical ? 0 : static_cast<long long>(rng() % range);
            p.y = static_cast<long long>(rng() % range);
        }
        std::shuffle(points.begin(), points.end(), rng);
        sort_by_x(points);
        RootStep step = analyze_root(points);
        assert(step.max_gap <= 7);
        assert(step.all_crossing);
        assert(best_with_window(step, 7) == brute_force(points));
        largest_gap = std::max(largest_gap, step.max_gap);
    }
    return largest_gap;
}

int main() {
    test_notes_examples();
    test_vertical_ties();
    test_duplicate_across_line();
    test_duplicate_inside_half();
    long long largest = 0;
    for (long long range : {4LL, 8LL, 16LL, 64LL, 1000LL, 2000000000LL}) {
        largest = std::max(largest, test_lemma(1, 4000, 40, range, false));
        largest = std::max(largest, test_lemma(2, 2000, 40, range, true));
    }
    std::printf("test_strip: ok (mayor salto observado: %lld)\n", largest);
}