#include <algorithm>
#include <functional>
#include <cstdint>
#include <string>
#include <utility>
#include <vector>

#include "tree_successor.h"

using namespace std;

// If the condition is not true, report an error and halt.
#define EXPECT(condition, message) do { if (!(condition)) expect_failed(message); } while (0)
void expect_failed(const string& message);

void test(const vector<int>& sequence, Tree &tree) {
    Node* node = tree.successor(nullptr);
    for (const auto& element : sequence) {
        EXPECT(node, "Expected successor " + to_string(element) + ", got nullptr");
        EXPECT(node->key == element,
               "Expected successor " + to_string(element) + ", got " + to_string(node->key));
        node = tree.successor(node);
    }
    EXPECT(!node, "Expected no successor, got " + to_string(node->key));
}

vector<int> get_linear_sequence() {
    vector<int> numbers;
    for (int i = 0; i < 10000000; i++)
        numbers.push_back((int)(7.13*i));
    return numbers;
}

void test_path(bool right) {
    vector<int> numbers = get_linear_sequence();
    Tree tree;
    Node *node = nullptr;
    if (right)
        for (int key : numbers)
            node = tree.insert(key, node);
    else
        for (int index = numbers.size() - 1; index >= 0; --index)
            node = tree.insert(numbers[index], node);

    test(numbers, tree);
}

void test_two_paths() {
    vector<int> numbers = get_linear_sequence();
    Tree tree;
    Node *node = nullptr;
    for(size_t i = numbers.size()/2; i < numbers.size(); i++)
        node = tree.insert(numbers[i], node);
    node = nullptr;
    for(int i = numbers.size()/2 - 1; i >= 0; i--)
        node = tree.insert(numbers[i], node);

    test(numbers, tree);
}

void test_sequence(vector<int> &&sequence) {
    Tree tree;
    for (const auto& element : sequence)
        tree.insert(element);

    sort(sequence.begin(), sequence.end());
    test(sequence, tree);
}

void test_random() {
    vector<int> sequence = {997};
    for (int i = 2; i < 199999; i++)
        sequence.push_back((sequence.back() * int64_t(997)) % 199999);
    test_sequence(move(sequence));
}

void test_trivial() {
    test_sequence({5});
    test_sequence({7,9});
    test_sequence({7,3});
    test_sequence({5,3,7});
}

void test_comb() {
    vector<int> numbers = get_linear_sequence();
    Tree tree;
    Node *node = nullptr;
    for(size_t i = numbers.size()/2; i < numbers.size(); i++)
        node = tree.insert(numbers[i], node);
    node = nullptr;
    for(int i = numbers.size()/2 - 1; i >= 0; i-=2) {
        node = tree.insert(numbers[i-1], node);
        tree.insert(numbers[i], node);
    }
    test(numbers, tree);
}

vector<pair<string, function<void()>>> tests = {
    { "trivial", test_trivial },
    { "right_path", []{ test_path(true); } },
    { "left_path", []{ test_path(false); } },
    { "random_tree", test_random },
    { "two_paths", test_two_paths },
    { "comb", test_comb }
};