bmat8.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2026 Finn Smith
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
 
// This file contains a declaration of fast boolean matrices up to dimension 8.
 
// TODO(1)
// * is it better to pass BMat8 by value rather than by const&?
 
#ifndef LIBSEMIGROUPS_BMAT8_HPP_
#define LIBSEMIGROUPS_BMAT8_HPP_
 
#include <array>        // for array
#include <cstddef>      // for size_t
#include <cstdint>      // for uint64_t
#include <functional>   // for hash
#include <iosfwd>       // for ostream, ostringstream
#include <memory>       // for hash
#include <string>       // for string
#include <type_traits>  // for is_trivial
#include <utility>      // for swap
#include <vector>       // for vector
 
#include "adapters.hpp"   // for Complexity, Degree, etc . . .
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
 
#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
namespace HPCombi {
  class BMat8;
}
#endif  // LIBSEMIGROUPS_HPCOMBI_ENABLED
 
namespace libsemigroups {



  class BMat8 {
    uint64_t _data;
    // Proxy class for reference to bits in the matrix
    class BitRef {
     private:
      uint64_t& _data;
      uint64_t  _mask;
 
     public:
      // Constructor: takes a reference to a byte and the index of the bit in
      // that byte
      constexpr BitRef(uint64_t& data, size_t index) noexcept
          : _data(data), _mask(static_cast<uint64_t>(1) << (63 - index)) {}
 
      // Assignment operator to allow setting the bit through the proxy
      constexpr BitRef& operator=(bool val) noexcept {
        _data ^= (-val ^ _data) & _mask;
        return *this;
      }
 
      // Conversion operator to read the value of the bit as a boolean
      [[nodiscard]] constexpr operator bool() const {
        return _data & _mask;
      }
    };
 
   public:
    BMat8() noexcept = default;

    constexpr explicit BMat8(uint64_t mat) noexcept : _data(mat) {}

    explicit BMat8(std::vector<std::vector<bool>> const& mat);

    constexpr BMat8(BMat8 const&) noexcept = default;

    constexpr BMat8(BMat8&&) noexcept = default;

    constexpr BMat8& operator=(BMat8 const&) noexcept = default;

    constexpr BMat8& operator=(BMat8&&) noexcept = default;
 
    ~BMat8() = default;

    [[nodiscard]] constexpr bool operator==(BMat8 const& that) const noexcept {
      return _data == that._data;
    }

    [[nodiscard]] constexpr bool operator!=(BMat8 const& that) const noexcept {
      return _data != that._data;
    }

    [[nodiscard]] constexpr bool operator<(BMat8 const& that) const noexcept {
      return _data < that._data;
    }

    [[nodiscard]] constexpr bool operator<=(BMat8 const& that) const noexcept {
      return *this < that || *this == that;
    }

    [[nodiscard]] constexpr bool operator>(BMat8 const& that) const noexcept {
      return _data > that._data;
    }

    [[nodiscard]] constexpr bool operator>=(BMat8 const& that) const noexcept {
      return *this > that || *this == that;
    }

    [[nodiscard]] constexpr bool operator()(size_t r, size_t c) const noexcept {
      LIBSEMIGROUPS_ASSERT(r < 8);
      LIBSEMIGROUPS_ASSERT(c < 8);
      return (_data << (8 * r + c)) >> 63;
    }

    [[nodiscard]] constexpr uint8_t operator()(size_t r) const noexcept {
      LIBSEMIGROUPS_ASSERT(r < 8);
      return static_cast<uint8_t>(to_int() << 8 * r >> 56);
    }

    [[nodiscard]] uint8_t at(size_t r) const;

    [[nodiscard]] constexpr BitRef operator()(size_t r, size_t c) {
      return BitRef(_data, 8 * r + c);
    }

    [[nodiscard]] bool at(size_t r, size_t c) const;

    [[nodiscard]] BitRef at(size_t r, size_t c);

    [[nodiscard]] constexpr inline uint64_t to_int() const noexcept {
      return _data;
    }

    [[nodiscard]] BMat8 operator*(BMat8 const& that) const noexcept;

    [[nodiscard]] constexpr BMat8 operator*(bool scalar) const noexcept {
      if (scalar) {
        return *this;
      } else {
        return BMat8(0);
      }
    }

    constexpr BMat8& operator*=(bool scalar) noexcept {
      if (!scalar) {
        _data = 0;
      }
      return *this;
    }

    [[nodiscard]] constexpr BMat8 operator+(BMat8 const& that) const noexcept {
      return BMat8(_data | that._data);
    }

    constexpr BMat8& operator+=(BMat8 const& that) noexcept {
      _data |= that._data;
      return *this;
    }

    BMat8& operator*=(BMat8 const& that) noexcept;

    inline void swap(BMat8& that) noexcept {
      std::swap(this->_data, that._data);
    }
  };
 
  static_assert(std::is_trivial<BMat8>(), "BMat8 is not a trivial class!");

  namespace bmat8 {
    template <typename T>
    [[nodiscard]] constexpr T one(size_t dim = 8) {
#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
      static_assert(std::is_same_v<T, BMat8>
                    || std::is_same_v<T, HPCombi::BMat8>);
#else
      static_assert(std::is_same_v<T, BMat8>);
#endif
      if (dim > 8) {
        LIBSEMIGROUPS_EXCEPTION(
            "the argument (dimension) must be at most 8, found {}", dim);
      }
      constexpr std::array<uint64_t, 9> const ones = {0x0000000000000000,
                                                      0x8000000000000000,
                                                      0x8040000000000000,
                                                      0x8040200000000000,
                                                      0x8040201000000000,
                                                      0x8040201008000000,
                                                      0x8040201008040000,
                                                      0x8040201008040200,
                                                      0x8040201008040201};
      return T(ones[dim]);
    }

    [[nodiscard]] constexpr BMat8 one(size_t dim = 8) {
      return one<BMat8>(dim);
    }

    // Not noexcept since std::uniform_int_distribution::operator() is not
    // noexcept.
    [[nodiscard]] BMat8 random();

    // Not noexcept since std::uniform_int_distribution::operator() is not
    // noexcept.
    [[nodiscard]] BMat8 random(size_t dim);

    [[nodiscard]] constexpr BMat8 transpose(BMat8 const& x) noexcept {
      uint64_t y = x.to_int();
      uint64_t z = (y ^ (y >> 7)) & 0xAA00AA00AA00AA;
      y          = y ^ z ^ (z << 7);
      z          = (y ^ (y >> 14)) & 0xCCCC0000CCCC;
      y          = y ^ z ^ (z << 14);
      z          = (y ^ (y >> 28)) & 0xF0F0F0F0;
      y          = y ^ z ^ (z << 28);
      return BMat8(y);
    }

    [[nodiscard]] BMat8 row_space_basis(BMat8 const& x) noexcept;

    [[nodiscard]] inline BMat8 col_space_basis(BMat8 const& x) noexcept {
      return transpose(row_space_basis(transpose(x)));
    }

    [[nodiscard]] constexpr size_t number_of_rows(BMat8 const& x) noexcept {
      size_t count = 0;
      for (size_t i = 0; i < 8; ++i) {
        if (x.to_int() << (8 * i) >> 56 > 0) {
          count++;
        }
      }
      return count;
    }
 
    // TODO(2) these should be templated to allow using HPCombi::BMat8's
    // here too.
    // noexcept because transpose and number_of_rows are.
    [[nodiscard]] constexpr size_t number_of_cols(BMat8 const& x) noexcept {
      return number_of_rows(transpose(x));
    }

    [[nodiscard]] size_t row_space_size(BMat8 const& x);

    // Not noexcept because row_space_size isn't.
    [[nodiscard]] inline size_t col_space_size(BMat8 const& x) {
      return row_space_size(transpose(x));
    }

    [[nodiscard]] size_t minimum_dim(BMat8 const& x) noexcept;

    [[nodiscard]] std::vector<uint8_t> rows(BMat8 const& x);

    template <typename Container>
    void push_back_rows(Container& rows, BMat8 const& x) {
      static_assert(std::is_same_v<typename Container::value_type, uint8_t>);
      for (size_t i = 0; i < 8; ++i) {
        rows.push_back(x(i));
      }
    }

    [[nodiscard]] bool is_regular_element(BMat8 const& x) noexcept;

    std::vector<bool> to_vector(uint8_t row);
 
  }  // namespace bmat8

  std::ostringstream& operator<<(std::ostringstream& os, BMat8 const& x);

  std::ostream& operator<<(std::ostream& os, BMat8 const& x);

  std::string to_human_readable_repr(BMat8 const&       x,
                                     std::string const& braces = "{}");

  [[nodiscard]] constexpr BMat8 operator*(bool         scalar,
                                          BMat8 const& x) noexcept {
    if (scalar) {
      return x;
    } else {
      return BMat8(0);
    }
  }
}  // namespace libsemigroups
 
namespace std {
  template <>
  struct hash<libsemigroups::BMat8> {
    size_t operator()(libsemigroups::BMat8 const& bm) const {
      return hash<uint64_t>()(bm.to_int());
    }
  };
}  // namespace std
 
namespace libsemigroups {

  template <>
  struct Complexity<BMat8> {
    [[nodiscard]] constexpr inline size_t
    operator()(BMat8 const&) const noexcept {
      return 0;
    }
  };

  template <>
  struct Degree<BMat8> {
    [[nodiscard]] constexpr inline size_t
    operator()(BMat8 const&) const noexcept {
      return 8;
    }
  };

  template <>
  struct IncreaseDegree<BMat8> {
    inline void operator()(BMat8 const&, size_t) const noexcept {}
  };

  template <>
  struct One<BMat8> {
    [[nodiscard]] inline BMat8 operator()(BMat8 const&) const noexcept {
      return bmat8::one();
    }

    [[nodiscard]] inline BMat8 operator()(size_t dim = 8) const {
      return bmat8::one(dim);
    }
  };

  template <>
  struct Product<BMat8> {
    inline void operator()(BMat8&       xy,
                           BMat8 const& x,
                           BMat8 const& y,
                           size_t = 0) const noexcept {
      xy = x * y;
    }
  };

  template <>
  struct ImageRightAction<BMat8, BMat8> {
    void operator()(BMat8&       res,
                    BMat8 const& pt,
                    BMat8 const& x) const noexcept {
      res = bmat8::row_space_basis(pt * x);
    }
  };

  template <>
  struct ImageLeftAction<BMat8, BMat8> {
    void operator()(BMat8&       res,
                    BMat8 const& pt,
                    BMat8 const& x) const noexcept {
      res = bmat8::col_space_basis(x * pt);
    }
  };

  template <>
  struct Inverse<BMat8> {
    [[nodiscard]] inline BMat8 operator()(BMat8 const& x) const noexcept {
      LIBSEMIGROUPS_ASSERT(x * bmat8::transpose(x) == bmat8::one());
      return bmat8::transpose(x);
    }
  };

  template <>
  struct LambdaValue<BMat8> {
    using type = BMat8;
  };

  template <>
  struct RhoValue<BMat8> {
    using type = BMat8;
  };

  template <>
  struct Lambda<BMat8, BMat8> {
    // noexcept because bmat8::row_space_basis is noexcept
    inline void operator()(BMat8& res, BMat8 const& x) const noexcept {
      res = bmat8::row_space_basis(x);
    }
  };

  template <>
  struct Rho<BMat8, BMat8> {
    // noexcept because bmat8::col_space_basis is noexcept
    inline void operator()(BMat8& res, BMat8 const& x) const noexcept {
      res = bmat8::col_space_basis(x);
    }
  };

  template <>
  struct Rank<BMat8> {
    [[nodiscard]] inline size_t operator()(BMat8 const& x) const noexcept {
      return bmat8::row_space_size(x);
    }
  };
}  // namespace libsemigroups
 
#endif  // LIBSEMIGROUPS_BMAT8_HPP_