#include <iostream>
#include <cstdint>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <fstream>
#include <string>
#include <algorithm>

#include "al_function.hpp"
#include "al_bool_matrix.hpp"

using namespace std;

typedef uint32_t Storage;
const size_t ARGS_COUNT = 4;
const size_t FUNCTION_LEN = 1ll << ARGS_COUNT;
const size_t FUNCTIONS_COUNT = 1ll << FUNCTION_LEN;
const bool ONLY_CREATE_CLASSES = false;
const bool GENERATE_ALL_REPRESENTATIONS = true;
typedef Function<Storage, FUNCTION_LEN> MyFunction;
typedef BoolSquareMatrix<Storage, ARGS_COUNT> MyMatrix;

static_assert(
    GENERATE_ALL_REPRESENTATIONS || !ONLY_CREATE_CLASSES,
    "representations required NOT ONLY_CREATE_CLASSES"
);

map<Storage, string> function_formulas;

void test_function() {
    Function<uint16_t, 8> f_8(16);
    assert(("sizeof(sizeof(Function<uint16_t, 8>)", sizeof(Function<uint16_t, 8>)==2));
    assert(("f_8(16) = 00010000", "00010000" == f_8.string()));
    assert(("f_8(15) = 00001111", "00001111" == Function<uint16_t, 8>(15).string()));

    assert(("converting 01001001", Function<uint16_t, 8>("01001001").string() == "01001001"));
    assert(("converting 00000000", Function<uint16_t, 8>("00000000").string() == "00000000"));
    assert(("converting 11111111", Function<uint16_t, 8>("11111111").string() == "11111111"));
    assert((Function<uint16_t, 16>("0010101111110001").string() == "0010101111110001"));

    Function<uint16_t, 8> a(12);
    Function<uint16_t, 8> b(5);
    assert(("a = 00001100", a.string() == "00001100"));
    assert(("b = 00000101", b.string() == "00000101"));
    assert(("a ^ b = 00001001", (a xor b).string() == "00001001"));
    assert(("a | b = 00001101", (a or b).string() == "00001101"));
    assert(("a & b = 00000100", (a and b).string() == "00000100"));
    // no changed in this objects
    assert(("a = 00001100", a.string() == "00001100"));
    assert(("b = 00000101", b.string() == "00000101"));

    Function<uint16_t, 8> negation(107);
    assert(("f(x_1 + 1 + 1, x_2, x_3) == f", negation == negation.var_negation(1).var_negation(1)));
    assert(("f(x_1, x_2 + 1 + 1, x_3) == f", negation == negation.var_negation(2).var_negation(2)));
    assert(("f(x_1, x_2, x_3 + 1 + 1) == f", negation == negation.var_negation(3).var_negation(3)));
    assert((Function<uint16_t, 16>("0000000100010111").var_negation(1).string() == "0000001000101011"));
    assert((Function<uint16_t, 16>("0000000100010111").var_negation(4).string() == "0001011100000001"));
    /*
    cout << "f(x_1, x_2, x_3)         = " << negation.string() << endl;
    cout << "f(x_1 + 1, x_2, x_3)     = " << negation.var_negation(1).string() << endl;
    cout << "f(x_1 + 1 + 1, x_2, x_3) = " << negation.var_negation(1).var_negation(1).string() << endl;
    cout << "f(x_1, x_2 + 1, x_3)     = " << negation.var_negation(2).string() << endl;
    cout << "f(x_1, x_2 + 1 + 1, x_3) = " << negation.var_negation(2).var_negation(2).string() << endl;
    cout << "f(x_1, x_2, x_3 + 1)     = " << negation.var_negation(3).string() << endl;
    */

    BoolSquareMatrix<uint16_t, 3> ones_matrix((1 << 10) - 1), i_matrix(0b100010001), minus_i_matrix(0b001010100);
    assert(ones_matrix.string("") == "111111111");
    assert(ones_matrix.get_determinant() == 0);
    assert(i_matrix.string("") == "100010001");
    assert(i_matrix.get_determinant() == 1);
    assert(minus_i_matrix.string("") == "001010100");
    assert(minus_i_matrix.get_determinant() != 0); // == uint16_t(-1)

    assert((BoolSquareMatrix<uint16_t, 3>(0b001001010).get_determinant() == 0));
    assert((BoolSquareMatrix<uint16_t, 3>(0b101000010).get_determinant() == 0));
    assert((BoolSquareMatrix<uint16_t, 3>(0b110101110).get_determinant() == 0));
    assert((BoolSquareMatrix<uint16_t, 3>(0b110101011).get_determinant() %2 == 0));
    assert((BoolSquareMatrix<uint16_t, 3>(0b001011111).get_determinant() != 0)); // == uint16_t(-1)

    BoolSquareMatrix<uint16_t, 4> ones_matrix_4(0b1111111111111111),
        i_matrix_4(0b1000010000100001),
        minus_i_matrix_4(0b0001001001001000);
    assert(ones_matrix_4.string("") == "1111111111111111");
    assert(ones_matrix_4.get_determinant() == 0);
    assert(i_matrix_4.string("") == "1000010000100001");
    assert(i_matrix_4.get_determinant() == 1);
    assert(minus_i_matrix_4.string("") == "0001001001001000");
    assert(minus_i_matrix_4.get_determinant() == 1);

    assert((BoolSquareMatrix<uint16_t, 4>(0b0001100000011010).get_determinant() == 0));
    assert((BoolSquareMatrix<uint16_t, 4>(0b0100011110111001).get_determinant() != 0));
    assert((BoolSquareMatrix<uint16_t, 4>(0b0000110100001101).get_determinant() == 0));
    assert((BoolSquareMatrix<uint16_t, 4>(0b0010101111110001).get_determinant() != 0));

    cout << "self-test passed" << endl;
}

template<class STORAGE, size_t ARGUMENTS_COUNT, class Callable>
Function<STORAGE, 1ll << ARGUMENTS_COUNT > get_function_from_callable(Callable INPUT_FUNCTION) {
    const STORAGE values_count = 1ll << ARGUMENTS_COUNT;
    STORAGE function_values(0);
    for (STORAGE cur_vec_value = values_count; cur_vec_value != 0; --cur_vec_value) {
        BoolVector<STORAGE, ARGUMENTS_COUNT> vec(cur_vec_value - 1);
        function_values *= 2;
        function_values += INPUT_FUNCTION(vec);
    }
    return Function<STORAGE, values_count >(function_values);
}

template<class CONTAINER>
void print_lens(CONTAINER len_map) {
    map<int, size_t> counter;
    for (const auto el: len_map) {
        if ( counter.find(el) == counter.end() )
            counter[el] = 0;
        ++counter[el];
    }
    for (auto&& el: counter)
        cout << "len " << el.first << " count " << el.second << endl;
}

vector< MyMatrix > get_good_matrices() {
    vector< MyMatrix > res;
    for (size_t cur_val = 1ll << (ARGS_COUNT * ARGS_COUNT); cur_val != 0; --cur_val) {
        MyMatrix cur_matrix(cur_val);
        Storage det = cur_matrix.get_determinant();
        // if ( det %2 != 0 )
        if ( det == 1 or det == Storage(-1) )
            res.push_back(cur_matrix);
    }
    return res;
}


vector<MyFunction> get_function_class(MyFunction f, const vector< MyMatrix >& tranformations, ostream& out) {
    set<MyFunction> cur_res;
    if constexpr ( GENERATE_ALL_REPRESENTATIONS ) {
        // Тут достаточно использовать функциональный класс из одной функции.
        // Хорошо работает для k=4 и меньше
        return vector<MyFunction>{f};
    }
    for (Storage i = 0; i < FUNCTION_LEN; ++i) {
        MyFunction cur_f = f;
        for (Storage arg_ind = 0; arg_ind < ARGS_COUNT; ++arg_ind)
            if ( (i >> arg_ind) % 2 == 1 )
                cur_f = cur_f.var_negation(arg_ind + 1);
        cur_res.insert(cur_f);
    }

    set<MyFunction> transformed_res(cur_res.begin(), cur_res.end());
    for (auto cur_f: cur_res) {
        for (auto transformation: tranformations) {
            MyFunction linear_transformed = get_function_from_callable<Storage, ARGS_COUNT>(
                [transformation, cur_f](const BoolVector<Storage, ARGS_COUNT> vec) -> Storage {
                    return cur_f.at((transformation * vec).get_value());
                }
            );
            bool is_inserted = transformed_res.insert(linear_transformed).second;
            if ( is_inserted ) {
                if ( function_formulas.find(linear_transformed.value()) == function_formulas.end() ) {
                    function_formulas[linear_transformed.value()] = "LT";
                }
            }
        }
    }

    return vector<MyFunction>(transformed_res.begin(), transformed_res.end());
}


vector<MyFunction> get_linear_components() {
    vector<MyFunction> res;
    if constexpr ( ARGS_COUNT == 2 ) {
        res.push_back(MyFunction("0000"));  // f = 0
        function_formulas[res.back().value()] = "0";
        res.push_back(MyFunction("1111"));  // f = 1
        function_formulas[res.back().value()] = "1";
        res.push_back(MyFunction("0011"));  // f = x_1
        function_formulas[res.back().value()] = "x_1";
        res.push_back(MyFunction("0101"));  // f = x_2
        function_formulas[res.back().value()] = "x_2";
    } else if constexpr ( ARGS_COUNT == 3 ) {
        res.push_back(MyFunction("00000000"));  // f = 0
        function_formulas[res.back().value()] = "0";
        res.push_back(MyFunction("11111111"));  // f = 1
        function_formulas[res.back().value()] = "1";
        res.push_back(MyFunction("00001111"));  // f = x_1
        function_formulas[res.back().value()] = "x_1";
        res.push_back(MyFunction("00110011"));  // f = x_2
        function_formulas[res.back().value()] = "x_2";
        res.push_back(MyFunction("01010101"));  // f = x_3
        function_formulas[res.back().value()] = "x_3";
    } else if constexpr ( ARGS_COUNT == 4 ) {
        res.push_back(MyFunction("0000000000000000"));  // f = 0
        function_formulas[res.back().value()] = "0";
        res.push_back(MyFunction("1111111111111111"));  // f = 1
        function_formulas[res.back().value()] = "1";
        res.push_back(MyFunction("0000000011111111"));  // f = x_1
        function_formulas[res.back().value()] = "x_1";
        res.push_back(MyFunction("0000111100001111"));  // f = x_2
        function_formulas[res.back().value()] = "x_2";
        res.push_back(MyFunction("0011001100110011"));  // f = x_3
        function_formulas[res.back().value()] = "x_3";
        res.push_back(MyFunction("0101010101010101"));  // f = x_4
        function_formulas[res.back().value()] = "x_4";
    } else if constexpr ( ARGS_COUNT == 5 ) {
        res.push_back(MyFunction("11111111111111111111111111111111"));  // f = 1
        res.push_back(MyFunction("00000000000000001111111111111111"));  // f = x_1
        res.push_back(MyFunction("00000000111111110000000011111111"));  // f = x_2
        res.push_back(MyFunction("00001111000011110000111100001111"));  // f = x_3
        res.push_back(MyFunction("00110011001100110011001100110011"));  // f = x_4
        res.push_back(MyFunction("01010101010101010101010101010101"));  // f = x_5
    } else {
        assert (("bad args_count", false));
    }
    return res;
}

vector<MyFunction> get_linear_combinations(const vector<MyFunction> &linear_components) {
    set<MyFunction> res(linear_components.begin(), linear_components.end());
    bool is_added = true;
    while ( is_added ) {
        is_added = false;
        for (auto el_first: res)
            for (auto el_second: res) {
                bool is_added_now = res.insert(el_first xor el_second).second;
                if ( is_added_now ) {
                    Storage cur_value = (el_first xor el_second).value();
                    function_formulas[cur_value] = function_formulas[el_first.value()] + " + " + function_formulas[el_second.value()];
                }
                is_added = is_added or is_added_now;
            }
    }
    return vector<MyFunction>(res.begin(), res.end());
}

string preprocess_factor(string factor) {
    if ( factor.find("+") != string::npos and factor.find("*") == string::npos and factor[0] !='(' and factor[factor.size() - 1] != ')')
        return "(" + factor + ")";
    return factor;
}

vector<MyFunction> get_all_monomials(const vector<MyFunction> &linear_combinations) {
    set<MyFunction> res(linear_combinations.begin(), linear_combinations.end());
    bool is_added = true;
    while ( is_added ) {
        is_added = false;
        for (auto el_first: res)
            for (auto el_second: res) {
                bool is_added_now = res.insert(el_first and el_second).second;
                if ( is_added_now ) {
                    Storage cur_value = (el_first and el_second).value();
                    function_formulas[cur_value] = preprocess_factor(function_formulas[el_first.value()])
                        + " " + preprocess_factor(function_formulas[el_second.value()]);
                        // no symbol for multiplication needed
                }
                is_added = is_added or is_added_now;
            }
    }
    return vector<MyFunction>(res.begin(), res.end());
}

string preprocess_monom(string monom) {
    return monom;
}

inline bool exists_test0 (const std::string& name) {
    ifstream f(name.c_str());
    return f.good();
}


string get_out_file_name(size_t rank_ind) {
    return string("base_" + to_string(ARGS_COUNT) + "_rank_" + to_string(rank_ind) + ".txt");
}

size_t recover_ranks(vector< vector<MyFunction> >& ranks, vector<int8_t>& used_map, size_t& functions_remains) {
    for (size_t rank_ind = 2; true; ++rank_ind) {
        ifstream f_in(get_out_file_name(rank_ind).c_str(), std::ios::binary);
        if ( not f_in.good() )
            return rank_ind;
        ranks.push_back(vector<MyFunction>());

        for (Storage bytes_cnt = 0; bytes_cnt < FUNCTIONS_COUNT / 8; ++bytes_cnt) {
            uint8_t buf;
            f_in.read(reinterpret_cast<char*>(&buf), 1);
            for (int8_t bits_cnt = 7; bits_cnt >= 0; --bits_cnt) {
                bool is_exists = buf % 2;
                if ( is_exists ) {
                    Storage function_value = bytes_cnt * 8 + bits_cnt;
                    MyFunction f(function_value);
                    if (used_map.at(f.value()))
                        continue;
                    used_map.at(f.value()) = rank_ind;
                    --functions_remains;
                    ranks.back().push_back(f);
                }
                buf /= 2;
            }
        }
        ranks.back().shrink_to_fit();
    }
}

void save_rank(size_t rank_ind, vector<MyFunction>& rank_items) {
    if ( not is_sorted(rank_items.begin(), rank_items.end()) )
        exit(1);
    ofstream f_out(get_out_file_name(rank_ind).c_str(), ios::binary);

    size_t fn_ptr = 0;

    for (Storage bytes_cnt = 0; bytes_cnt < FUNCTIONS_COUNT / 8; ++bytes_cnt) {
        uint8_t buf = 0;
        for (Storage bits_cnt = 0; bits_cnt < 8; ++bits_cnt) {
            buf *= 2;
            if ( fn_ptr >= rank_items.size() or rank_items[fn_ptr].value() != bytes_cnt * 8 + bits_cnt )
                continue;
            ++buf;
            ++fn_ptr;
        }
        f_out.write(reinterpret_cast<char*>(&buf), 1);
    }
}


void clean_trash_ranks(vector< vector<MyFunction> >& ranks) {
    for (size_t rank_ind = 2; rank_ind < ranks.size() - 1; ++rank_ind)
        ranks.at(rank_ind).clear();
}


void fill_ranks(vector<MyFunction> monomials) {
    vector<int8_t> used_map(FUNCTIONS_COUNT, 0);
    size_t functions_remains = FUNCTIONS_COUNT;

    vector< vector<MyFunction> > ranks;
    ranks.push_back(vector<MyFunction>()); // empty set
    ranks.push_back(monomials); // empty set
    save_rank(1, monomials);

    cout << "rank index = " << 1 << endl;
    for (auto el: monomials) {
        --functions_remains;
        used_map.at(el.value()) = 1;
    }

    size_t total_ranks = 2;
    if constexpr ( ONLY_CREATE_CLASSES ) {
        total_ranks = recover_ranks(ranks, used_map, functions_remains);
    }

    clean_trash_ranks(ranks);
    cout << "recovered to " << total_ranks << endl;
    cout << "current ranks: " << endl;
    for (auto&& r: ranks)
        cout << r.size() << " ";
    cout << endl;
    for (; functions_remains; ++total_ranks) {
        cout << "rank index = " << total_ranks << " remains: " << functions_remains << endl;
        vector<int8_t> temp_used_map(FUNCTIONS_COUNT, 0);
        for (size_t ind_first = 0; ind_first != ranks[1].size(); ++ind_first) {
            if ( ind_first % 20 == 0 ) {
                for (auto&& r: ranks)
                    cout << r.size() << " ";
                cout << endl;
                cout << 100. * ind_first / ranks[1].size() << "% for " << ranks[1].size()
                    << " x " << ranks.back().size() << endl;
            }
            const auto el_first = ranks[1][ind_first];
            for (auto el_second: ranks.back()) {
                MyFunction res_el = el_first xor el_second;
                if constexpr ( not ONLY_CREATE_CLASSES ) {
                    if ( used_map[res_el.value()] == 0 ) {
                        function_formulas[res_el.value()] =
                            preprocess_monom(function_formulas[el_first.value()]) +
                            " + " + preprocess_monom(function_formulas[el_second.value()]);
                    }
                }
                temp_used_map[res_el.value()] = total_ranks;
            }
        }

        ranks.push_back(vector<MyFunction>());
        clean_trash_ranks(ranks);
        for (size_t func_ind = 0; func_ind < temp_used_map.size(); ++func_ind) {
            if (not temp_used_map[func_ind] or used_map[func_ind] != 0)
                continue;
            --functions_remains;
            auto cur_fn = MyFunction(func_ind);
            auto val = cur_fn.value();
            if (val >= used_map.size()) {
                cout << val << " " << cur_fn.string() << endl;
                continue;
            }
            used_map[val] = total_ranks;
            ranks.back().push_back(cur_fn);
        }
        cout << "remains: " << functions_remains << endl;
        save_rank(total_ranks, ranks.back());
        cout << "size for rank " << total_ranks << " is " << ranks.at(total_ranks).size() << endl;
    }

    if constexpr ( ONLY_CREATE_CLASSES ) {
        return;
    }

    print_lens(used_map);

    auto possible_tranformations = get_good_matrices();
    cout << "Total " << possible_tranformations.size() << " linear tranformations" << endl;

    ofstream f_out("out.tex");
    f_out << "\\begin{longtable}{| l| l | l | p{70mm} |}" << endl
        << "\\hline" << endl
        << "\\endhead" << endl
        << "\\hline \\multicolumn{4}{r}{\\textit{Продолжение на следующей странице}} \\\\" << endl
        << "\\endfoot" << endl
        << "\\hline" << endl
        << "\\endlastfoot" << endl
        << "\\hline" << endl
        << "Номер класса & Длина & Размер класса & ПСПФ\\\\" << endl
        << "\\hline" << endl;

    ranks.clear();
    for (auto i = total_ranks - 1; i != 0; --i)
        ranks.push_back(vector<MyFunction>()); // empty set
    size_t total_unique_functions = 0;
    size_t total_functions = 0;
    map<MyFunction, size_t> class_sizes;
    for (size_t fn_value = 0; fn_value < used_map.size(); ++fn_value) {
        auto cur_rank = used_map[fn_value];
        if ( not cur_rank )
            continue;
        ++total_unique_functions;
        MyFunction current_fn(fn_value);
        vector<MyFunction> function_class = get_function_class(
            current_fn, possible_tranformations, cout
        );
        // cout << "size of function class " << current_fn.string() << " is " << function_class.size() << endl;
        class_sizes[current_fn] = function_class.size();
        for (auto marked_function: function_class) {
            if ( used_map[marked_function.value()] == 0 )
                f_out << "already 0  at " << marked_function.string() << " " << function_formulas[marked_function.value()]
                    << " from class " << current_fn.string() << " " << function_formulas[current_fn.value()] << endl;
            used_map[marked_function.value()] = 0;
            ++total_functions;
        }
        ranks.at(cur_rank - 1).push_back(current_fn);
    }
    if ( total_functions != FUNCTIONS_COUNT)
        cout << "total counted functions: " << total_functions
            << " but must be " << FUNCTIONS_COUNT << endl;
    cout << "total function classes: " << total_unique_functions << endl;
    size_t function_index = 1;
    for (size_t rank_ind = 0; rank_ind < ranks.size(); ++rank_ind) {
        cout << "rank index = " << rank_ind + 1 << endl;
        f_out << "\\hline" << endl;
        for (auto f: ranks.at(rank_ind)) {
            cout << f.string() << " size: " << class_sizes[f] << " "
                << function_formulas[f.value()] << endl;
            f_out << "  " << function_index << " & " << rank_ind + 1 << " & "
                << class_sizes[f] << " & $" << function_formulas[f.value()] << "$ \\\\" << endl;
            ++function_index;
        }
    }

    f_out << "  \\hline" << endl
        << "\\end{longtable}" << endl
        << "\\captionof{figure}{Классы псевдополиномов}" << endl
        << "\\label{fig:polynoms}" << endl
        << "\\addtocounter{table}{-1}" << endl;
    f_out.close();
}

int main() {
    test_function();
    cout << "using " << sizeof(Storage) << " bytes for storage" << endl;
    cout << FUNCTIONS_COUNT << " functions with " << ARGS_COUNT
        << " arguments and " << FUNCTION_LEN << " values" << endl;

    auto linear_components = get_linear_components();
    cout << "Linear components: " << endl;
    for (auto el: linear_components)
        cout << el.string() << endl;

    auto linear_combinations = get_linear_combinations(linear_components);
    cout << "Linear combinations: " << linear_combinations.size() << endl;

    auto monomials = get_all_monomials(linear_combinations);
    cout << "Monomials: " << monomials.size() << endl;

    fill_ranks(monomials);

    if constexpr ( GENERATE_ALL_REPRESENTATIONS ) {
        ofstream f_out(("functions_strings_" + to_string(ARGS_COUNT) +  ".txt").c_str());
        for (size_t i = 0; i < FUNCTIONS_COUNT; ++i) {
            f_out << function_formulas[i] << "\n";
        }
    }
    return 0;
}