hpcombi.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2025 James D. Mitchell
//
// 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 specializations of the class adapters in adapters.hpp
// for the element types in HPCombi.
 
#ifndef LIBSEMIGROUPS_HPCOMBI_HPP_
#define LIBSEMIGROUPS_HPCOMBI_HPP_
 
// Must include config.hpp so that LIBSEMIGROUPS_HPCOMBI_ENABLED
// is defined, if so specified at during configure.
#include "config.hpp"  // for LIBSEMIGROUPS_HPCOMBI_ENABLED
 
#if defined(LIBSEMIGROUPS_HPCOMBI_ENABLED)
#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
#pragma GCC diagnostic ignored "-Wswitch-default"
#endif
#include "hpcombi/hpcombi.hpp"  // for HPCombi::Perm16, ...
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
 
#include <type_traits>    // for decay_t etc
#include <unordered_map>  // for unordered_map
 
#include "adapters.hpp"   // for Complexity, Degree, ...
#include "constants.hpp"  // for UNDEFINED
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "types.hpp"      // for enable_if_is_same
#else
#include <type_traits>    // for decay_t etc
#include <unordered_map>  // for unordered_map
 
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#endif
 
namespace libsemigroups {
  namespace detail {
    // TODO(1) to tpp
    template <typename Iterator>
    void throw_if_duplicates(
        Iterator                                                    first,
        Iterator                                                    last,
        std::unordered_map<std::decay_t<decltype(*first)>, size_t>& seen) {
      seen.clear();
      for (auto it = first; it != last; ++it) {
        if (*it != UNDEFINED) {
          auto [pos, inserted] = seen.emplace(*it, seen.size());
          if (!inserted) {
            LIBSEMIGROUPS_EXCEPTION(
                "duplicate value, found {} in position {}, first "
                "occurrence in position {}",
                *it,
                std::distance(first, it),
                pos->second);
          }
        }
      }
    }

    template <typename Iterator>
    void throw_if_duplicates(Iterator first, Iterator last) {
      std::unordered_map<std::decay_t<decltype(*first)>, size_t> seen;
      throw_if_duplicates(first, last, seen);
    }
  }  // namespace detail
 
#if defined(LIBSEMIGROUPS_HPCOMBI_ENABLED) \
    || defined(LIBSEMIGROUPS_PARSED_BY_DOXYGEN)

  template <typename TPTransf16Subclass>
  struct Complexity<TPTransf16Subclass,
                    std::enable_if_t<std::is_base_of_v<HPCombi::PTransf16,
                                                       TPTransf16Subclass>>> {
    constexpr size_t operator()(TPTransf16Subclass const&) const noexcept {
      return 0;
    }
  };

  template <typename TPTransf16Subclass>
  struct Degree<TPTransf16Subclass,
                std::enable_if_t<std::is_base_of_v<HPCombi::PTransf16,
                                                   TPTransf16Subclass>>> {
    constexpr size_t operator()(TPTransf16Subclass const&) const noexcept {
      return 16;
    }
  };

  template <typename TPTransf16Subclass>
  struct One<TPTransf16Subclass,
             std::enable_if_t<
                 std::is_base_of_v<HPCombi::PTransf16, TPTransf16Subclass>>> {
    TPTransf16Subclass operator()(size_t = 0) const noexcept {
      return TPTransf16Subclass::one();
    }

    TPTransf16Subclass operator()(TPTransf16Subclass const&) const noexcept {
      return TPTransf16Subclass::one();
    }
  };

  template <typename TPTransf16Subclass>
  struct Product<TPTransf16Subclass,
                 std::enable_if_t<std::is_base_of_v<HPCombi::PTransf16,
                                                    TPTransf16Subclass>>> {
    void operator()(TPTransf16Subclass&       xy,
                    TPTransf16Subclass const& x,
                    TPTransf16Subclass const& y,
                    size_t = 0) const noexcept {
      xy = y * x;
    }
  };

  template <typename TPTransf16Subclass>
  struct Swap<TPTransf16Subclass,
              std::enable_if_t<
                  std::is_base_of_v<HPCombi::PTransf16, TPTransf16Subclass>>> {
    void operator()(TPTransf16Subclass& x,
                    TPTransf16Subclass& y) const noexcept {
      std::swap(x, y);
    }
  };

  template <>
  struct Inverse<HPCombi::Perm16> {
    HPCombi::Perm16 operator()(HPCombi::Perm16 const& x) const noexcept {
      return x.inverse();
    }
  };

  template <typename TIntType>
  struct ImageRightAction<HPCombi::Perm16,
                          TIntType,
                          std::enable_if_t<std::is_integral_v<TIntType>>> {
    void operator()(TIntType&              res,
                    TIntType const&        pt,
                    HPCombi::Perm16 const& p) const noexcept {
      LIBSEMIGROUPS_ASSERT(pt < 16);
      res = static_cast<TIntType>(p[pt]);
    }

    TIntType operator()(TIntType const&        pt,
                        HPCombi::Perm16 const& p) const noexcept {
      LIBSEMIGROUPS_ASSERT(pt < 16);
      return p[pt];
    }
  };

  template <>
  struct ImageRightAction<HPCombi::PPerm16, HPCombi::PPerm16> {
    void operator()(HPCombi::PPerm16&       res,
                    HPCombi::PPerm16 const& x,
                    HPCombi::PPerm16 const& y) const noexcept {
      res = (y * x).left_one();
    }
  };

  template <>
  struct ImageLeftAction<HPCombi::PPerm16, HPCombi::PPerm16> {
    void operator()(HPCombi::PPerm16&       res,
                    HPCombi::PPerm16 const& x,
                    HPCombi::PPerm16 const& y) const noexcept {
      res = (x * y).right_one();
    }
  };

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

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

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

  template <>
  struct One<HPCombi::BMat8> {
    inline HPCombi::BMat8 operator()(HPCombi::BMat8 const& x) const noexcept {
      return x.one();
    }

    inline HPCombi::BMat8 operator()(size_t = 0) const noexcept {
      return HPCombi::BMat8::one();
    }
  };

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

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

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

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

  // Konieczny adapters - HPCombi::BMat8

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

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

  template <>
  struct Lambda<HPCombi::BMat8, HPCombi::BMat8> {
    void operator()(HPCombi::BMat8&       res,
                    HPCombi::BMat8 const& x) const noexcept {
      res = x.row_space_basis();
    }
  };

  template <>
  struct Rho<HPCombi::BMat8, HPCombi::BMat8> {
    void operator()(HPCombi::BMat8&       res,
                    HPCombi::BMat8 const& x) const noexcept {
      res = x.col_space_basis();
    }
  };

  template <>
  struct Rank<HPCombi::BMat8> {
    inline size_t operator()(HPCombi::BMat8 const& x) const noexcept {
      return x.row_space_size();
    }
  };

  // Konieczny adapters - HPCombi::PPerm16

  template <>
  struct LambdaValue<HPCombi::PPerm16> {
    using type = HPCombi::PPerm16;
  };

  template <>
  struct RhoValue<HPCombi::PPerm16> {
    using type = HPCombi::PPerm16;
  };

  template <>
  struct Lambda<HPCombi::PPerm16, HPCombi::PPerm16> {
    void operator()(HPCombi::PPerm16&       res,
                    HPCombi::PPerm16 const& x) const noexcept {
      res = x.left_one();
    }
  };

  template <>
  struct Rho<HPCombi::PPerm16, HPCombi::PPerm16> {
    void operator()(HPCombi::PPerm16&       res,
                    HPCombi::PPerm16 const& x) const noexcept {
      res = x.right_one();
    }
  };

  // Konieczny adapters - Transf16

  template <>
  struct ImageRightAction<HPCombi::Transf16, HPCombi::PTransf16> {
    void operator()(HPCombi::PTransf16&       res,
                    HPCombi::Transf16 const&  x,
                    HPCombi::PTransf16 const& y) const noexcept {
      res = (y * static_cast<HPCombi::PTransf16>(static_cast<HPCombi::epu8>(x)))
                .left_one();
    }
  };

  template <>
  struct ImageLeftAction<HPCombi::Transf16, HPCombi::Vect16> {
    void operator()(HPCombi::Vect16&         res,
                    HPCombi::Transf16 const& x,
                    HPCombi::Vect16 const&   y) const noexcept {
      HPCombi::Vect16 buf  = {0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff};
      size_t          next = 0;
      for (size_t i = 0; i < 16; ++i) {
        if (buf[x[y[i]]] == 0xff) {
          buf[x[y[i]]] = next++;
        }
        res[i] = buf[x[y[i]]];
      }
    }
  };

  template <>
  struct LambdaValue<HPCombi::Transf16> {
    using type = HPCombi::PTransf16;
  };

  template <>
  struct RhoValue<HPCombi::Transf16> {
    using type = HPCombi::Vect16;
  };

  template <>
  struct Lambda<HPCombi::Transf16, HPCombi::PTransf16> {
    void operator()(HPCombi::PTransf16&      res,
                    HPCombi::Transf16 const& x) const noexcept {
      res = x.left_one();
    }
  };

  template <>
  struct Rho<HPCombi::Transf16, HPCombi::Vect16> {
    void operator()(HPCombi::Vect16&         res,
                    HPCombi::Transf16 const& x) const noexcept {
      HPCombi::Vect16 buf  = {0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff,
                              0xff};
      size_t          next = 0;
      for (size_t i = 0; i < 16; ++i) {
        if (buf[x[i]] == 0xff) {
          buf[x[i]] = next++;
        }
        res[i] = buf[x[i]];
      }
    }
  };

  // Konieczny adapters - generic

  template <typename T>
  struct Rank<T,
              std::enable_if_t<std::is_base_of_v<HPCombi::PTransf16, T>,
                               RankState<T>>> {
    inline size_t operator()(T const& x) const noexcept {
      return x.rank();
    }
  };


  template <typename Return, typename Container>
  [[nodiscard]] enable_if_is_same<Return, HPCombi::Transf16>
  make(Container&& cont) {
    if (cont.size() > 16) {
      LIBSEMIGROUPS_EXCEPTION("the 1st argument (container) must have size at "
                              "most 16, but found {}",
                              cont.size());
    }
    auto result = HPCombi::Transf16(cont);
    if (!result.validate()) {
      auto it = std::find_if(std::begin(cont),
                             std::begin(cont),
                             [](auto const& val) { return val > 15; });
      LIBSEMIGROUPS_EXCEPTION("image value out of bounds, expected value in "
                              "[0, 16), found {} in position {}",
                              *it,
                              std::distance(std::begin(cont), it));
    }
    return result;
  }

  template <typename Return, typename Container>
  [[nodiscard]] enable_if_is_same<Return, HPCombi::Perm16>
  make(Container&& cont) {
    if (cont.size() > 16) {
      LIBSEMIGROUPS_EXCEPTION("the 1st argument (container) must have size at "
                              "most 16, but found {}",
                              cont.size());
    }
    auto result = HPCombi::Perm16(cont);
    if (!result.HPCombi::Transf16::validate()) {
      auto it = std::find_if(std::begin(cont),
                             std::begin(cont),
                             [](auto const& val) { return val > 15; });
      LIBSEMIGROUPS_EXCEPTION("image value out of bounds, expected value in "
                              "[0, 16), found {} in position {}",
                              *it,
                              std::distance(std::begin(cont), it));
    }
    if (!result.validate()) {
      detail::throw_if_duplicates(std::begin(cont), std::end(cont));
      // TODO(1) check if result contains UNDEFINED
    }
    return result;
  }

  template <typename Return, typename Container>
  [[nodiscard]] enable_if_is_same<Return, HPCombi::PPerm16>
  make(Container&& cont) {
    if (cont.size() > 16) {
      LIBSEMIGROUPS_EXCEPTION("the 1st argument (container) must have size at "
                              "most 16, but found {}",
                              cont.size());
    }
    auto result = HPCombi::PPerm16(cont);
    if (!result.HPCombi::PTransf16::validate()) {
      auto it = std::find_if(
          std::begin(cont), std::begin(cont), [](auto const& val) {
            return val != 0xFF && val > 15;
          });
      LIBSEMIGROUPS_EXCEPTION("image value out of bounds, expected value in "
                              "[0, 16) or 0xFF (= {}), found {} in position {}",
                              0xFF,
                              *it,
                              std::distance(std::begin(cont), it));
    }
    if (!result.validate()) {
      detail::throw_if_duplicates(std::begin(cont), std::end(cont));
    }
    return result;
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, HPCombi::PPerm16>
  make(std::vector<uint8_t> const& dom,
       std::vector<uint8_t> const& ran,
       size_t                      deg = 16) {
    if (deg > 16) {
      LIBSEMIGROUPS_EXCEPTION(
          "the 3rd argument is not valid, expected <=16, found {}", deg);
    } else if (dom.size() != ran.size()) {
      LIBSEMIGROUPS_EXCEPTION("domain and range size mismatch, domain has "
                              "size {} but range has size {}",
                              dom.size(),
                              ran.size());
    } else if (!(dom.empty()
                 || deg > *std::max_element(dom.cbegin(), dom.cend()))) {
      LIBSEMIGROUPS_EXCEPTION(
          "domain value out of bounds, found {}, must be less than {}",
          *std::max_element(dom.cbegin(), dom.cend()),
          deg);
    }
    // TODO(1) check ran for out of bounds values too
    std::unordered_map<uint8_t, size_t> seen;
    detail::throw_if_duplicates(dom.cbegin(), dom.cend(), seen);
    detail::throw_if_duplicates(ran.cbegin(), ran.cend(), seen);
    HPCombi::PPerm16 result(dom, ran, deg);
    LIBSEMIGROUPS_ASSERT(result.validate());
    return result;
  }

  template <typename Return, typename Int>
  [[nodiscard]] enable_if_is_same<Return, HPCombi::PPerm16>
  make(std::initializer_list<Int> dom,
       std::initializer_list<Int> ran,
       size_t                     M) {
    return make<Return>(std::vector<uint8_t>(dom.begin(), dom.end()),
                        std::vector<uint8_t>(ran.begin(), ran.end()),
                        M);
  }

  template <typename Return>
  [[nodiscard]] std::enable_if_t<std::is_base_of_v<HPCombi::PTransf16, Return>,
                                 Return>
  make(std::initializer_list<uint8_t>&& cont) {
    return make<Return, std::initializer_list<uint8_t>>(std::move(cont));
  }
#endif  // LIBSEMIGROUPS_HPCOMBI_ENABLED
 
}  // namespace libsemigroups
 
#endif  // LIBSEMIGROUPS_HPCOMBI_HPP_