#ifndef _AL_BOOL_MATRIX_HPP
#define _AL_BOOL_MATRIX_HPP

#include <cassert>
#include <cstdint>

#include <bitset>
#include <limits>
#include <string>


template <class STORAGE, size_t SIZE>
class BoolVector {
    public:
        BoolVector(): _value(0) {
            static_assert(not std::numeric_limits<STORAGE>::is_signed);
        }
        BoolVector(STORAGE val): _value(val) {
            static_assert(not std::numeric_limits<STORAGE>::is_signed);
            assert(val < 1ll << SIZE);
        }

        BoolVector operator*(BoolVector other) const {
            return BoolVector(_value & other.get_value());
        }

        STORAGE get_value() const {
            return _value;
        }
        STORAGE at(STORAGE ind) const {
            return (_value >> ind) % 2;
        }
        std::string string() const {
            std::string res(SIZE, '0');
            for (size_t ind = 0; ind < SIZE; ++ind) {
                char cur_ch = at(ind) % 2 == 0 ? '0' : '1';
                res[ind] = cur_ch;
            }
            return res;
        }
    private:
        STORAGE _value;
};

template<class STORAGE, size_t SIZE>
class BoolSquareMatrix {
    public:
        BoolSquareMatrix(): _values(0) {
            static_assert(not std::numeric_limits<STORAGE>::is_signed);
        }
        BoolSquareMatrix(STORAGE val): _values(val) {
            static_assert(not std::numeric_limits<STORAGE>::is_signed);
        }
        STORAGE at(STORAGE row, STORAGE col) const {
            return (_values >> index(row, col)) % 2;
        }
        STORAGE get_determinant() {
            if constexpr ( SIZE == 2 ) {
                return at(0,0) * at(1,1) - at(0,1) * at(1,0);
            } else if constexpr ( SIZE == 4 or SIZE == 3 ) {
                int cur_modifier = 1;
                STORAGE res = 0;
                for (STORAGE remove_ind = 0; remove_ind < SIZE; ++remove_ind) {
                    STORAGE tmp_vector_value = 0;
                    for (STORAGE i = 1; i < SIZE; ++i) {
                        for (STORAGE j = 0; j < SIZE; ++j) {
                            if ( j == remove_ind )
                                continue;
                            tmp_vector_value *= 2;
                            tmp_vector_value += at(i, j);
                        }
                    }
                    BoolSquareMatrix<STORAGE, SIZE - 1> tmp_matix(tmp_vector_value);
                    res += cur_modifier * tmp_matix.get_determinant() * at(0, remove_ind);
                    cur_modifier *= -1;
                }
                return res;
            }
        }

        BoolVector<STORAGE, SIZE> operator * (BoolVector<STORAGE, SIZE> vec) const {
            /* a_1
             * a_2
             * a_3
             */
            STORAGE vector_value = 0;
            for (STORAGE ind = 0; ind < SIZE; ++ind) {
                BoolVector<STORAGE, SIZE> cur_vec = vec * get_row(ind);
                /* STORAGE cur_sum = 0;
                for (STORAGE vec_ind = 0; vec_ind < SIZE; ++vec_ind)
                    cur_sum += cur_vec.at(vec_ind);
                same but slow version, we just need number of bits
                */
                vector_value *= 2;
                vector_value += __builtin_popcount(cur_vec.get_value()) % 2; // cur_sum
            }
            return BoolVector<STORAGE, SIZE>(vector_value);
        }

        STORAGE get_value() const {
            return _values;
        }
        std::string string(std::string delimiter="\n") const {
            std::string res;
            for (STORAGE i = 0; i < SIZE; ++i) {
                for (STORAGE j = 0; j < SIZE; ++j) {
                    char cur_ch = at(i,j) % 2 == 0 ? '0' : '1';
                    res += cur_ch;
                }
                if ( i != SIZE - 1 )
                    res += delimiter;
            }
            return res;
        }

        bool operator < (BoolSquareMatrix other) const {
            return _values < other._values;
        }
        bool operator == (BoolSquareMatrix other) const {
            return _values == other._values;
        }
    private:
        STORAGE _values;
        STORAGE index(STORAGE row, STORAGE col) const {
            return SIZE * row + col;
        }
        BoolVector<STORAGE, SIZE> get_row(STORAGE row) const {
            STORAGE vector_value = 0;
            for (STORAGE i = 0; i < SIZE; ++i) {
                vector_value *= 2;
                vector_value += at(row, i);
            }
            return BoolVector<STORAGE, SIZE>(vector_value);
        }
};
#endif // _AL_BOOL_MATRIX_HPP