matrix-helpers.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2026 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/>.
//
 
#ifndef LIBSEMIGROUPS_MATRIX_HELPERS_HPP_
#define LIBSEMIGROUPS_MATRIX_HELPERS_HPP_
 
#include <algorithm>      // for sort, fill, min
#include <bitset>         // for bitset
#include <cstddef>        // for size_t
#include <type_traits>    // for enable_if_t
#include <unordered_map>  // for unordered_map
#include <unordered_set>  // for unordered_set
#include <utility>        // for move, forward
#include <vector>         // for vector
 
#include "bitset.hpp"        // for BitSet, IsBitSet
#include "constants.hpp"     // for UNDEFINED
#include "debug.hpp"         // for LIBSEMIGROUPS_...
#include "exception.hpp"     // for LIBSEMIGROUPS_...
#include "is-matrix.hpp"     // for IsBMat, IsStat...
#include "matrix-class.hpp"  // for DynamicNTPMatW...
 
#include "detail/containers.hpp"         // for StaticVector1
#include "detail/matrix-exceptions.hpp"  // for throw_if_not_s...
 
namespace libsemigroups {
  namespace detail {
    template <typename T>
    struct IsStdBitSetHelper : std::false_type {};
 
    template <size_t N>
    struct IsStdBitSetHelper<std::bitset<N>> : std::true_type {};
 
    template <typename T>
    static constexpr bool IsStdBitSet = IsStdBitSetHelper<T>::value;
 
    template <typename T>
    struct BitSetCapacity {
      static constexpr size_t value = BitSet<1>::max_size();
    };
 
    template <size_t R, size_t C>
    struct BitSetCapacity<StaticBMat<R, C>> {
      static_assert(R == C, "the number of rows and columns must be equal");
      static constexpr size_t value = R;
    };
 
  }  // namespace detail

  namespace matrix {

    template <typename Mat>
    [[nodiscard]] constexpr auto threshold(Mat const&) noexcept
        -> std::enable_if_t<!detail::IsTruncMat<Mat>,
                            typename Mat::scalar_type> {
      return UNDEFINED;
    }

    template <typename Mat>
    [[nodiscard]] constexpr auto threshold(Mat const&) noexcept
        -> std::enable_if_t<detail::IsTruncMat<Mat> && !IsMatWithSemiring<Mat>,
                            typename Mat::scalar_type> {
      return detail::IsTruncMatHelper<Mat>::threshold;
    }

    template <typename Mat>
    [[nodiscard]] auto threshold(Mat const& x) noexcept
        -> std::enable_if_t<detail::IsTruncMat<Mat> && IsMatWithSemiring<Mat>,
                            typename Mat::scalar_type> {
      return x.semiring()->threshold();
    }

    template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
    [[nodiscard]] constexpr Scalar
    period(StaticNTPMat<T, P, R, C, Scalar> const&) noexcept {
      return P;
    }

    template <size_t T, size_t P, typename Scalar>
    [[nodiscard]] constexpr Scalar
    period(DynamicNTPMatWithoutSemiring<T, P, Scalar> const&) noexcept {
      return P;
    }

    template <typename Scalar>
    [[nodiscard]] Scalar
    period(DynamicNTPMatWithSemiring<Scalar> const& x) noexcept {
      return x.semiring()->period();
    }

    // Matrix helpers - pow

    // TODO(1) pow_no_checks
    // TODO(2) version that changes x in-place
    template <typename Mat>
    [[nodiscard]] Mat pow(Mat const& x, typename Mat::scalar_type e);

    // Matrix helpers - rows

    template <typename Mat, typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
    [[nodiscard]] std::vector<typename Mat::RowView> rows(Mat const& x) {
      std::vector<typename Mat::RowView> container;
      x.rows(container);
      return container;
    }

    template <typename Mat, typename = std::enable_if_t<IsStaticMatrix<Mat>>>
    [[nodiscard]] detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
    rows(Mat const& x) {
      detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
      x.rows(container);
      return container;
    }

    // Matrix helpers - bitset_rows

    template <typename Mat, size_t R, size_t C, typename Container>
    void bitset_rows(Container&&                          views,
                     detail::StaticVector1<BitSet<C>, R>& result);

    template <typename Mat, size_t R, size_t C, typename Container>
    [[nodiscard]] auto bitset_rows(Container&& views);

    template <typename Mat, size_t R, size_t C>
    void bitset_rows(Mat const& x, detail::StaticVector1<BitSet<C>, R>& result);

    template <typename Mat>
    [[nodiscard]] auto bitset_rows(Mat const& x);

    // Matrix helpers - bitset_row_basis

    // This works with std::vector and StaticVector1, with value_type equal
    // to std::bitset and BitSet.
    template <typename Mat, typename Container>
    void bitset_row_basis(Container&& rows, std::decay_t<Container>& result);

    template <typename Mat, typename Container>
    [[nodiscard]] std::decay_t<Container> bitset_row_basis(Container&& rows);

    template <typename Mat, size_t M = detail::BitSetCapacity<Mat>::value>
    [[nodiscard]] detail::StaticVector1<BitSet<M>, M>
    bitset_row_basis(Mat const& x);

    template <typename Mat, typename Container>
    void bitset_row_basis(Mat const& x, Container& result);

    // Matrix helpers - row_basis - MaxPlusTruncMat

    template <typename Mat, typename Container>
    std::enable_if_t<IsMaxPlusTruncMat<Mat>>
    row_basis(Container&& views, std::decay_t<Container>& result);

    // Matrix helpers - row_basis - BMat
 
    // This version of row_basis for BMat's is used for compatibility
    // with the MatrixCommon framework, i.e. so that BMat's exhibit the same
    // interface/behaviour as other matrices.
    //
    // This version takes a container of row views of BMat, converts it to a
    // container of BitSets, computes the row basis using the BitSets, then
    // selects those row views in views that belong to the computed basis.

    // TODO(2) complexity
    template <typename Mat, typename Container>
    std::enable_if_t<IsBMat<Mat>> row_basis(Container&&              views,
                                            std::decay_t<Container>& result);

    // Matrix helpers - row_basis - generic helpers

    // Row basis of rowspace of matrix <x> appended to <result>
    template <typename Mat,
              typename Container,
              typename = std::enable_if_t<IsMatrix<Mat>>>
    void row_basis(Mat const& x, Container& result) {
      row_basis<Mat>(rows(x), result);
    }

    // Row basis of rowspace of matrix <x>
    template <typename Mat, typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
    [[nodiscard]] std::vector<typename Mat::RowView> row_basis(Mat const& x) {
      std::vector<typename Mat::RowView> container;
      row_basis(x, container);
      return container;
    }

    template <typename Mat, typename = std::enable_if_t<IsStaticMatrix<Mat>>>
    [[nodiscard]] detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
    row_basis(Mat const& x) {
      detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
      row_basis(x, container);
      return container;
    }

    // TODO(2) complexity
    template <typename Mat,
              typename Container,
              typename = std::enable_if_t<!IsMatrix<std::decay_t<Container>>>>
    [[nodiscard]] std::decay_t<Container> row_basis(Container&& rows);
 
    // TODO move
    template <typename T>
    struct RowSum {
      void operator()(T& res, T const& pt, T const& x) const {
        res = pt;
        res += x;
      }
    };
 
    // TODO(doc)
    template <typename Mat,
              typename Container,
              typename = std::enable_if_t<IsMatrix<Mat>>>
    void row_basis_rows(Mat const& x, Container& result);
 
    // TODO(doc)
    template <typename Mat,
              typename Container,
              typename = std::enable_if_t<IsStaticMatrix<Mat>>>
    [[nodiscard]] detail::StaticVector1<typename Mat::Row, Mat::nr_rows>
    row_basis_rows(Mat const& x);
 
    // TODO(doc)
    template <typename Mat,
              typename Container,
              typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
    [[nodiscard]] std::vector<typename Mat::Row> row_basis_rows(Mat const& x) {
      std::vector<typename Mat::Row> container;
      row_basis_rows(x, container);
      return container;
    }
 
    // This modifies the argument rows by moving out those in the basis
    template <typename Mat,
              typename Container,
              typename = std::enable_if_t<IsStaticMatrix<Mat>>>
    [[nodiscard]] detail::StaticVector1<typename Mat::Row, Mat::nr_rows>
    row_basis_rows(Container&& rows);

    // Matrix helpers - row_space_size

    template <typename Mat, typename = std::enable_if_t<IsBMat<Mat>>>
    [[nodiscard]] size_t row_space_size(Mat const& x);
  }  // namespace matrix
}  // namespace libsemigroups
 
#include "matrix-helpers.tpp"
#endif  // LIBSEMIGROUPS_MATRIX_HELPERS_HPP_