cmc-finite-functions/finite_function.hpp

#include <array>
#include <string>
#include <utility>
#include <iostream>
typedef uint8_t CellType;

// Пока положим, что только два аргумента, чтобы упростить реализацию
template <CellType BASE>
class FiniteFunction {
    public:
        FiniteFunction() {}

        // Устанавливает результат функции, использую другую функцию как
        // инициализатор
        template <class Callable>
        FiniteFunction(Callable initer) : _num(0) {
            for (auto && el: _results)
                el = 0;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    auto inited_result = initer(first, second);
                    set_result(first, second, inited_result);
                }
            update_num();
        }

        explicit FiniteFunction(std::string text_repr) {
            for (auto && el: _results)
                el = 0;
            size_t cur_ind = 0;
            for (auto ch: text_repr) {
                if ( !isdigit(ch) )
                    continue;
                set_result(
                    cur_ind / BASE,
                    cur_ind % BASE,
                    std::stoi(std::string(1, ch))
                );
                ++cur_ind;
            }
            update_num();
        }
        ~FiniteFunction() {}

        //  Устанавливает результат функции по двум аргументам
        void set_result(CellType first, CellType second, CellType result) {
            //std::cout << "setting " << (int)first << "," << (int)second << " to " << (int)result << std::endl;
            
            uint8_t byte_num = get_index(first, second) / 4;
            uint8_t shift = 2*(get_index(first, second) % 4);
            //std::cout << "before: " << (int)_results[byte_num];
            _results[byte_num] = (_results[byte_num] ^ (((_results[byte_num] >> shift)
             & 0x03) << shift)) | (result <<shift);
             //std::cout << " -> " << (int)_results[byte_num] << std::endl;
        }

        int operator() (CellType first, CellType second) const {
            uint8_t byte_num = get_index(first, second) / 4;
            uint8_t shift = 2*(get_index(first, second) % 4);
            // возьмём последние два бита
            return (_results[byte_num] >> shift) & 0x03;
        }

        bool operator < (const FiniteFunction &f) const {
            return _num < f._num;
        }

        bool operator == (const FiniteFunction &f) const {
            return _num == f._num;
        }

        FiniteFunction reversed() const {
        // f(x,y) -> f(y,x)
            FiniteFunction res;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    res.set_result(first, second, (*this)(second, first));
                }
            res.update_num();
            return res;
        }

        FiniteFunction equaled() const {
        // f(x,y) -> f(x,x)
            FiniteFunction res;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    res.set_result(first, second, (*this)(first, first));
                }
            res.update_num();
            return res;
        }

        FiniteFunction apply_to_first_partial(const FiniteFunction &g) const {
            // -> this(g(x,y), x)
            FiniteFunction res;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    res.set_result(first, second, (*this)(g(first, second), first));
                }
            res.update_num();
            return res;
        }

        std::tuple<FiniteFunction, FiniteFunction> apply_to_first(const FiniteFunction &g) const {
            // -> this(g(x,y), x), this(g(x,y), y)
            FiniteFunction res_1, res_2;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    res_1.set_result(first, second, (*this)(g(first, second), first));
                    res_2.set_result(first, second, (*this)(g(first, second), second));
                }
            res_1.update_num();
            res_2.update_num();
            return std::make_tuple(res_1, res_2);
        }

        FiniteFunction apply_two(const FiniteFunction &g, const FiniteFunction &h) const {
            FiniteFunction res;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    res.set_result(
                        first,
                        second,
                        (*this)(g(first, second), h(first, second))
                    );
                }
            res.update_num();
            return res;
        }

        FiniteFunction apply_permutation(std::array<int, BASE> perm) const {
            FiniteFunction res;
            for (CellType first = 0; first < BASE; ++first)
                for (CellType second = 0; second < BASE; ++second) {
                    res.set_result(
                        first,
                        second,
                        std::find(
                            perm.begin(),
                            perm.end(),
                            (*this)(perm[first], perm[second])
                        ) - perm.begin()
                    );
                }
            res.update_num();
            return res;
        }

        uint32_t get_hash() const {
            return _num;
        }

        static size_t get_index(CellType first, CellType second) {
            return first * BASE + second;
        }
        template <CellType _BASE>
        friend std::ostream& operator << (std::ostream& os, const FiniteFunction<_BASE> &f);
    private:
        void update_num() {
            _num = 0;
            for (auto&& val: _results) {
                _num *= 256;
                _num += val;
            }
        }
        uint32_t _num;
        std::array<CellType, (BASE*BASE + 3) / 4> _results;
};


template <CellType BASE>
std::ostream& operator << (std::ostream& os, const FiniteFunction<BASE> &f){
    for (int first = 0; first < BASE; ++first) {
        for (int second = 0; second < BASE; ++second) {
            os << f(first, second);
        }
        if ( first != BASE-1 )
            os << " ";
    }
    return os;
}