23#ifndef LIBSEMIGROUPS_MATRIX_HPP_
24#define LIBSEMIGROUPS_MATRIX_HPP_
31#include <initializer_list>
39#include <unordered_map>
40#include <unordered_set>
44#include "adapters.hpp"
47#include "constants.hpp"
49#include "exception.hpp"
51#include "detail/containers.hpp"
52#include "detail/formatters.hpp"
53#include "detail/string.hpp"
135 template <
typename T>
136 struct IsStdBitSetHelper : std::false_type {};
139 struct IsStdBitSetHelper<std::bitset<N>> : std::true_type {};
141 template <
typename T>
142 static constexpr bool IsStdBitSet = IsStdBitSetHelper<T>::value;
144 struct MatrixPolymorphicBase {};
146 template <
typename T>
147 struct IsMatrixHelper {
148 static constexpr bool value
149 = std::is_base_of<detail::MatrixPolymorphicBase, T>::value;
167 template <
typename T>
168 constexpr bool IsMatrix = detail::IsMatrixHelper<T>::value;
183 template <
typename Mat>
185 if (x.number_of_rows() != x.number_of_cols()) {
205 template <
typename Mat>
207 -> std::enable_if_t<IsMatrix<Mat>> {
208 if (x.number_of_rows() != y.number_of_rows()
209 || x.number_of_cols() != y.number_of_cols()) {
211 "expected matrices with the same dimensions, the 1st argument is a "
212 "{}x{} matrix, and the 2nd is a {}x{} matrix",
234 template <
typename Mat>
236 -> std::enable_if_t<IsMatrix<Mat>> {
237 if (r >= x.number_of_rows()) {
239 "values in [0, {}) x [0, {})",
246 if (c >= x.number_of_cols()) {
248 "values in [0, {}) x [0, {})",
262 template <
typename Container,
265 typename Semiring =
void>
266 class MatrixCommon : MatrixPolymorphicBase {
272 using scalar_type =
typename Container::value_type;
273 using scalar_reference =
typename Container::reference;
274 using scalar_const_reference =
typename Container::const_reference;
275 using semiring_type = Semiring;
277 using container_type = Container;
278 using iterator =
typename Container::iterator;
279 using const_iterator =
typename Container::const_iterator;
281 using RowView = TRowView;
283 scalar_type scalar_one() const noexcept {
284 return static_cast<Subclass const*
>(
this)->one_impl();
287 scalar_type scalar_zero() const noexcept {
288 return static_cast<Subclass const*
>(
this)->zero_impl();
291 Semiring
const* semiring() const noexcept {
292 return static_cast<Subclass const*
>(
this)->semiring_impl();
300 scalar_type plus_no_checks(scalar_type x, scalar_type y)
const noexcept {
301 return static_cast<Subclass const*
>(
this)->plus_no_checks_impl(y, x);
304 scalar_type product_no_checks(scalar_type x,
305 scalar_type y)
const noexcept {
306 return static_cast<Subclass const*
>(
this)->product_no_checks_impl(y, x);
315 template <
typename SFINAE = container_type>
316 auto resize(
size_t r,
size_t c) -> std::enable_if_t<
317 std::is_same<SFINAE, std::vector<scalar_type>>::value> {
318 _container.resize(r * c);
321 template <
typename SFINAE = container_type>
322 auto resize(
size_t,
size_t) -> std::enable_if_t<
323 !std::is_same<SFINAE, std::vector<scalar_type>>::value> {}
331 MatrixCommon() =
default;
332 MatrixCommon(MatrixCommon
const&) =
default;
333 MatrixCommon(MatrixCommon&&) =
default;
334 MatrixCommon& operator=(MatrixCommon
const&) =
default;
335 MatrixCommon& operator=(MatrixCommon&&) =
default;
337 explicit MatrixCommon(std::initializer_list<scalar_type>
const& c)
343 explicit MatrixCommon(std::vector<std::vector<scalar_type>>
const& m)
349 std::initializer_list<std::initializer_list<scalar_type>>
const& m)
356 template <
typename T>
357 void init(T
const& m) {
358 size_t const R = m.size();
362 size_t const C = m.begin()->size();
364 for (
size_t r = 0; r < R; ++r) {
365 auto row = m.begin() + r;
366 for (
size_t c = 0; c < C; ++c) {
367 _container[r * C + c] = *(row->begin() + c);
374 init(std::initializer_list<std::initializer_list<scalar_type>>
const& m) {
375 init<std::initializer_list<std::initializer_list<scalar_type>>>(m);
379 explicit MatrixCommon(RowView
const& rv) : MatrixCommon() {
380 resize(1, rv.size());
381 std::copy(rv.cbegin(), rv.cend(), _container.begin());
384 ~MatrixCommon() =
default;
387 Subclass one()
const {
388 size_t const n = number_of_rows();
389 Subclass x(semiring(), n, n);
390 std::fill(x.begin(), x.end(), scalar_zero());
391 for (
size_t r = 0; r < n; ++r) {
392 x(r, r) = scalar_one();
402 bool operator==(MatrixCommon
const& that)
const {
403 return _container == that._container;
407 bool operator==(RowView
const& that)
const {
408 return number_of_rows() == 1
409 &&
static_cast<RowView
>(*
static_cast<Subclass const*
>(
this))
414 bool operator<(MatrixCommon
const& that)
const {
415 return _container < that._container;
419 bool operator<(RowView
const& that)
const {
420 return number_of_rows() == 1
421 &&
static_cast<RowView
>(*
static_cast<Subclass const*
>(
this))
426 template <
typename T>
427 bool operator!=(T
const& that)
const {
428 static_assert(
IsMatrix<T> || std::is_same_v<T, RowView>);
429 return !(*
this == that);
433 template <
typename T>
434 bool operator>(T
const& that)
const {
435 static_assert(
IsMatrix<T> || std::is_same_v<T, RowView>);
440 template <
typename T>
441 bool operator>=(T
const& that)
const {
442 static_assert(
IsMatrix<T> || std::is_same_v<T, RowView>);
443 return that < *
this || that == *
this;
447 template <
typename T>
448 bool operator<=(T
const& that)
const {
449 static_assert(
IsMatrix<T> || std::is_same_v<T, RowView>);
450 return *
this < that || that == *
this;
459 scalar_reference operator()(
size_t r,
size_t c) {
460 return this->_container[r * number_of_cols() + c];
463 scalar_reference at(
size_t r,
size_t c) {
465 return this->operator()(r, c);
470 scalar_const_reference operator()(
size_t r,
size_t c)
const {
471 return this->_container[r * number_of_cols() + c];
474 scalar_const_reference at(
size_t r,
size_t c)
const {
476 return this->operator()(r, c);
480 size_t number_of_rows() const noexcept {
481 return static_cast<Subclass const*
>(
this)->number_of_rows_impl();
485 size_t number_of_cols() const noexcept {
486 return static_cast<Subclass const*
>(
this)->number_of_cols_impl();
490 size_t hash_value()
const {
491 return Hash<Container>()(_container);
499 void product_inplace_no_checks(Subclass
const& A, Subclass
const& B) {
500 LIBSEMIGROUPS_ASSERT(number_of_rows() == number_of_cols());
501 LIBSEMIGROUPS_ASSERT(A.number_of_rows() == number_of_rows());
502 LIBSEMIGROUPS_ASSERT(B.number_of_rows() == number_of_rows());
503 LIBSEMIGROUPS_ASSERT(A.number_of_cols() == number_of_cols());
504 LIBSEMIGROUPS_ASSERT(B.number_of_cols() == number_of_cols());
505 LIBSEMIGROUPS_ASSERT(&A !=
this);
506 LIBSEMIGROUPS_ASSERT(&B !=
this);
514 size_t const N = A.number_of_rows();
515 std::vector<scalar_type> tmp(N, 0);
517 for (
size_t c = 0; c < N; c++) {
518 for (
size_t i = 0; i < N; i++) {
521 for (
size_t r = 0; r < N; r++) {
523 A._container.begin() + r * N,
524 A._container.begin() + (r + 1) * N,
527 [
this](scalar_type x, scalar_type y) {
528 return this->plus_no_checks(x, y);
530 [
this](scalar_type x, scalar_type y) {
531 return this->product_no_checks(x, y);
538 void operator*=(scalar_type a) {
539 for (
auto it = _container.begin(); it < _container.end(); ++it) {
540 *it = product_no_checks(*it, a);
545 void operator+=(Subclass
const& that) {
546 LIBSEMIGROUPS_ASSERT(that.number_of_rows() == number_of_rows());
547 LIBSEMIGROUPS_ASSERT(that.number_of_cols() == number_of_cols());
548 for (
size_t i = 0; i < _container.size(); ++i) {
549 _container[i] = plus_no_checks(_container[i], that._container[i]);
553 void operator+=(RowView
const& that) {
554 LIBSEMIGROUPS_ASSERT(number_of_rows() == 1);
555 RowView(*
static_cast<Subclass const*
>(
this)) += that;
558 void operator+=(scalar_type a) {
559 for (
auto it = _container.begin(); it < _container.end(); ++it) {
560 *it = plus_no_checks(*it, a);
571 Subclass operator+(Subclass
const& y)
const {
572 Subclass result(*
static_cast<Subclass const*
>(
this));
578 Subclass operator*(Subclass
const& y)
const {
579 Subclass result(*
static_cast<Subclass const*
>(
this));
580 result.product_inplace_no_checks(*
static_cast<Subclass const*
>(
this),
585 Subclass operator*(scalar_type a)
const {
586 Subclass result(*
static_cast<Subclass const*
>(
this));
591 Subclass operator+(scalar_type a)
const {
592 Subclass result(*
static_cast<Subclass const*
>(
this));
602 iterator begin() noexcept {
603 return _container.begin();
607 iterator end() noexcept {
608 return _container.end();
612 const_iterator begin() const noexcept {
613 return _container.begin();
617 const_iterator end() const noexcept {
618 return _container.end();
622 const_iterator cbegin() const noexcept {
623 return _container.cbegin();
627 const_iterator cend() const noexcept {
628 return _container.cend();
631 template <
typename U>
632 std::pair<scalar_type, scalar_type> coords(U
const& it)
const {
634 std::is_same<U, iterator>::value
635 || std::is_same<U, const_iterator>::value,
636 "the parameter it must be of type iterator or const_iterator");
638 return std::make_pair(v / number_of_cols(), v % number_of_cols());
646 void swap(MatrixCommon& that)
noexcept {
652 void transpose_no_checks() noexcept {
653 LIBSEMIGROUPS_ASSERT(number_of_rows() == number_of_cols());
654 if (number_of_rows() == 0) {
658 for (
size_t r = 0; r < number_of_rows() - 1; ++r) {
659 for (
size_t c = r + 1; c < number_of_cols(); ++c) {
667 transpose_no_checks();
675 RowView row_no_checks(
size_t i)
const {
676 auto& container =
const_cast<Container&
>(_container);
677 return RowView(
static_cast<Subclass const*
>(
this),
678 container.begin() + i * number_of_cols(),
682 RowView row(
size_t i)
const {
683 if (i >= number_of_rows()) {
685 "index out of range, expected value in [{}, {}), found {}",
690 return row_no_checks(i);
694 template <
typename T>
695 void rows(T& x)
const {
696 auto& container =
const_cast<Container&
>(_container);
697 for (
auto itc = container.begin(); itc != container.end();
698 itc += number_of_cols()) {
700 static_cast<Subclass const*
>(
this), itc, number_of_cols());
702 LIBSEMIGROUPS_ASSERT(x.size() == number_of_rows());
709 friend std::ostream& operator<<(std::ostream& os, MatrixCommon
const& x) {
710 os << detail::to_string(x);
718 container_type _container;
721 template <
typename Scalar>
722 class MatrixDynamicDim {
724 MatrixDynamicDim() : _number_of_cols(0), _number_of_rows(0) {}
725 MatrixDynamicDim(MatrixDynamicDim
const&) =
default;
726 MatrixDynamicDim(MatrixDynamicDim&&) =
default;
727 MatrixDynamicDim& operator=(MatrixDynamicDim
const&) =
default;
728 MatrixDynamicDim& operator=(MatrixDynamicDim&&) =
default;
730 MatrixDynamicDim(
size_t r,
size_t c)
731 : _number_of_cols(c), _number_of_rows(r) {}
733 ~MatrixDynamicDim() =
default;
735 void swap(MatrixDynamicDim& that)
noexcept {
736 std::swap(_number_of_cols, that._number_of_cols);
737 std::swap(_number_of_rows, that._number_of_rows);
741 size_t number_of_rows_impl() const noexcept {
742 return _number_of_rows;
745 size_t number_of_cols_impl() const noexcept {
746 return _number_of_cols;
750 size_t _number_of_cols;
751 size_t _number_of_rows;
754 template <
typename PlusOp,
759 struct MatrixStaticArithmetic {
760 MatrixStaticArithmetic() =
default;
761 MatrixStaticArithmetic(MatrixStaticArithmetic
const&) =
default;
762 MatrixStaticArithmetic(MatrixStaticArithmetic&&) =
default;
763 MatrixStaticArithmetic& operator=(MatrixStaticArithmetic
const&)
765 MatrixStaticArithmetic& operator=(MatrixStaticArithmetic&&) =
default;
769 using scalar_type = Scalar;
771 static constexpr scalar_type plus_no_checks_impl(scalar_type x,
772 scalar_type y)
noexcept {
773 return PlusOp()(x, y);
776 static constexpr scalar_type
777 product_no_checks_impl(scalar_type x, scalar_type y)
noexcept {
778 return ProdOp()(x, y);
781 static constexpr scalar_type one_impl() noexcept {
785 static constexpr scalar_type zero_impl() noexcept {
789 static constexpr void const* semiring_impl() noexcept {
798 template <
typename Mat,
typename Sub
class>
799 class RowViewCommon {
801 "the template parameter Mat must be derived from "
802 "MatrixPolymorphicBase");
805 using const_iterator =
typename Mat::const_iterator;
806 using iterator =
typename Mat::iterator;
808 using scalar_type =
typename Mat::scalar_type;
809 using scalar_reference =
typename Mat::scalar_reference;
810 using scalar_const_reference =
typename Mat::scalar_const_reference;
812 using Row =
typename Mat::Row;
813 using matrix_type = Mat;
815 size_t size() const noexcept {
816 return static_cast<Subclass const*
>(
this)->length_impl();
820 scalar_type plus_no_checks(scalar_type x, scalar_type y)
const noexcept {
821 return static_cast<Subclass const*
>(
this)->plus_no_checks_impl(y, x);
824 scalar_type product_no_checks(scalar_type x,
825 scalar_type y)
const noexcept {
826 return static_cast<Subclass const*
>(
this)->product_no_checks_impl(y, x);
830 RowViewCommon() =
default;
831 RowViewCommon(RowViewCommon
const&) =
default;
832 RowViewCommon(RowViewCommon&&) =
default;
833 RowViewCommon& operator=(RowViewCommon
const&) =
default;
834 RowViewCommon& operator=(RowViewCommon&&) =
default;
836 explicit RowViewCommon(Row
const& r)
837 : RowViewCommon(const_cast<Row&>(r).begin()) {}
840 scalar_const_reference operator[](
size_t i)
const {
845 scalar_reference operator[](
size_t i) {
850 scalar_const_reference operator()(
size_t i)
const {
855 scalar_reference operator()(
size_t i) {
860 const_iterator cbegin() const noexcept {
865 const_iterator cend()
const {
866 return _begin + size();
870 const_iterator begin() const noexcept {
875 const_iterator end()
const {
876 return _begin + size();
880 iterator begin() noexcept {
885 iterator end() noexcept {
886 return _begin + size();
894 void operator+=(RowViewCommon
const& x) {
896 for (
size_t i = 0; i < size(); ++i) {
897 this_[i] = plus_no_checks(this_[i], x[i]);
902 void operator+=(scalar_type a) {
903 for (
auto& x : *
this) {
904 x = plus_no_checks(x, a);
909 void operator*=(scalar_type a) {
910 for (
auto& x : *
this) {
911 x = product_no_checks(x, a);
916 Row operator*(scalar_type a)
const {
917 Row result(*
static_cast<Subclass const*
>(
this));
923 Row operator+(RowViewCommon
const& that)
const {
924 Row result(*
static_cast<Subclass const*
>(
this));
925 result +=
static_cast<Subclass const&
>(that);
929 template <
typename U>
930 bool operator==(U
const& that)
const {
932 return std::equal(begin(), end(), that.begin());
935 template <
typename U>
936 bool operator!=(U
const& that)
const {
937 return !(*
this == that);
940 template <
typename U>
941 bool operator<(U
const& that)
const {
943 cbegin(), cend(), that.cbegin(), that.cend());
946 template <
typename U>
947 bool operator>(U
const& that)
const {
951 void swap(RowViewCommon& that)
noexcept {
955 friend std::ostream& operator<<(std::ostream& os,
956 RowViewCommon
const& x) {
957 os << detail::to_string(x);
962 explicit RowViewCommon(iterator first) : _begin(first) {}
968 template <
typename Container>
969 void throw_if_any_row_wrong_size(Container
const& m) {
973 uint64_t
const C = m.begin()->size();
975 m.begin() + 1, m.end(), [&C](
typename Container::const_reference r) {
976 return r.size() == C;
980 "have length {}, found {} in entry {}",
987 template <
typename Scalar>
988 void throw_if_any_row_wrong_size(
989 std::initializer_list<std::initializer_list<Scalar>> m) {
990 throw_if_any_row_wrong_size<
991 std::initializer_list<std::initializer_list<Scalar>>>(m);
1000#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1001 template <
typename PlusOp,
1010 template <
typename... Args>
1011 class DynamicMatrix;
1013 template <
typename PlusOp,
1018 class DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
1020 template <
typename Semiring,
typename Scalar>
1021 class DynamicMatrix<Semiring, Scalar>;
1069 template <
typename PlusOp,
1076 :
public detail::RowViewCommon<
1077 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, 1, C, Scalar>,
1078 StaticRowView<PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar>>,
1080 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
1082 using RowViewCommon = detail::RowViewCommon<
1085 friend RowViewCommon;
1088 using StaticMatrix_ = ::libsemigroups::
1089 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>;
1114 using Row =
typename matrix_type::Row;
1131#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1132 using RowViewCommon::RowViewCommon;
1137 typename RowViewCommon::iterator it,
1139 : RowViewCommon(it) {}
1141 using RowViewCommon::size;
1168 static constexpr size_t size() const noexcept;
1292 template <typename U>
1293 bool operator==(U const& that) const;
1315 template <typename U>
1316 bool operator!=(U const& that) const;
1341 template <typename U>
1342 bool operator<(U const& that) const;
1365 template <typename U>
1366 bool operator<(U const& that) const;
1460 static constexpr size_t length_impl() noexcept {
1469#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1472 template <
typename... Args>
1473 class DynamicRowView;
1513 template <
typename PlusOp,
1519 :
public detail::RowViewCommon<
1520 DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
1521 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>,
1523 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
1525 using DynamicMatrix_ = DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
1526 using RowViewCommon = detail::RowViewCommon<
1529 friend RowViewCommon;
1554 using Row =
typename matrix_type::Row;
1573 : RowViewCommon(r), _length(r.number_of_cols()) {}
1575#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1576 using RowViewCommon::RowViewCommon;
1579 DynamicRowView(DynamicMatrix_
const*, iterator
const& it,
size_t N)
1580 : RowViewCommon(it), _length(N) {}
1582 using RowViewCommon::size;
1612 template <typename U>
1613 bool operator==(U const& that) const;
1616 template <typename U>
1617 bool operator!=(U const& that) const;
1620 template <typename U>
1621 bool operator<(U const& that) const;
1624 template <typename U>
1625 bool operator<(U const& that) const;
1644 size_t length_impl() const noexcept {
1674 template <
typename Semiring,
typename Scalar>
1676 :
public detail::RowViewCommon<DynamicMatrix<Semiring, Scalar>,
1677 DynamicRowView<Semiring, Scalar>> {
1679 using DynamicMatrix_ = DynamicMatrix<Semiring, Scalar>;
1680 friend DynamicMatrix_;
1682 = detail::RowViewCommon<DynamicMatrix_,
1684 friend RowViewCommon;
1691 using iterator =
typename RowViewCommon::iterator;
1706 using matrix_type =
typename RowViewCommon::matrix_type;
1709 using Row =
typename matrix_type::Row;
1729#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1730 using RowViewCommon::RowViewCommon;
1733 DynamicRowView(DynamicMatrix_
const* mat, iterator
const& it,
size_t)
1734 : RowViewCommon(it), _matrix(mat) {}
1736 using RowViewCommon::size;
1739 size_t size() const noexcept;
1766 template <typename U>
1767 bool operator==(U const& that) const;
1770 template <typename U>
1771 bool operator!=(U const& that) const;
1774 template <typename U>
1775 bool operator<(U const& that) const;
1778 template <typename U>
1779 bool operator<(U const& that) const;
1798 size_t length_impl() const noexcept {
1799 return _matrix->number_of_cols();
1802 scalar_type plus_no_checks_impl(scalar_type x,
1803 scalar_type y)
const noexcept {
1804 return _matrix->plus_no_checks_impl(x, y);
1807 scalar_type product_no_checks_impl(scalar_type x,
1808 scalar_type y)
const noexcept {
1809 return _matrix->product_no_checks_impl(x, y);
1812 DynamicMatrix_
const* _matrix;
1852 template <
typename PlusOp,
1861 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
1862 public detail::MatrixCommon<
1863 std::array<Scalar, R * C>,
1864 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>,
1865 StaticRowView<PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar>> {
1870 using MatrixCommon = ::libsemigroups::detail::MatrixCommon<
1874 friend MatrixCommon;
1917 static constexpr size_t nr_rows = R;
1918 static constexpr size_t nr_cols = C;
1942 static_assert(R == 1,
1943 "cannot construct Matrix from the given initializer list, "
1944 "incompatible dimensions");
1945 LIBSEMIGROUPS_ASSERT(c.
size() == C);
1968 : MatrixCommon(m) {}
1983 : MatrixCommon(m) {}
2005 "cannot construct Matrix with more than one row from RowView!");
2033#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2046 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2055 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2062 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2068 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2074#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2078 LIBSEMIGROUPS_ASSERT(n == 0 || n == R);
2080#if defined(__APPLE__) && defined(__clang__) \
2081 && (__clang_major__ == 13 || __clang_major__ == 14)
2086 size_t volatile const m = R;
2091 std::fill(x.begin(), x.end(), ZeroOp()());
2092 for (
size_t r = 0; r < m; ++r) {
2093 x(r, r) = OneOp()();
2100 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2101 LIBSEMIGROUPS_ASSERT(n == 0 || n == R);
2109#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2509 template <typename T>
2598 template <typename U>
2599 bool operator<=(U const& that) const;
2615 template <typename U>
2616 bool operator>=(U const& that) const;
2685 using MatrixCommon::at;
2686 using MatrixCommon::begin;
2687 using MatrixCommon::cbegin;
2688 using MatrixCommon::cend;
2689 using MatrixCommon::coords;
2690 using MatrixCommon::end;
2691 using MatrixCommon::hash_value;
2692 using MatrixCommon::number_of_cols;
2693 using MatrixCommon::number_of_rows;
2694 using MatrixCommon::one;
2695 using MatrixCommon::operator!=;
2696 using MatrixCommon::operator();
2697 using MatrixCommon::operator*;
2698 using MatrixCommon::operator*=;
2699 using MatrixCommon::operator+;
2700 using MatrixCommon::operator+=;
2701 using MatrixCommon::operator<;
2702 using MatrixCommon::operator<=;
2703 using MatrixCommon::operator==;
2704 using MatrixCommon::operator>;
2705 using MatrixCommon::operator>=;
2706 using MatrixCommon::product_inplace_no_checks;
2707 using MatrixCommon::row;
2708 using MatrixCommon::row_no_checks;
2709 using MatrixCommon::rows;
2710 using MatrixCommon::scalar_one;
2711 using MatrixCommon::scalar_zero;
2712 using MatrixCommon::semiring;
2713 using MatrixCommon::swap;
2714 using MatrixCommon::transpose;
2715 using MatrixCommon::transpose_no_checks;
2723 static constexpr size_t number_of_rows_impl() noexcept {
2726 static constexpr size_t number_of_cols_impl() noexcept {
2768 template <
typename PlusOp,
2774 :
public detail::MatrixDynamicDim<Scalar>,
2775 public detail::MatrixCommon<
2776 std::vector<Scalar>,
2777 DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
2778 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>,
2780 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
2781 using MatrixDynamicDim = ::libsemigroups::detail::MatrixDynamicDim<Scalar>;
2782 using MatrixCommon = ::libsemigroups::detail::MatrixCommon<
2785 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>;
2786 friend MatrixCommon;
2805 using RowView = DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
2891 : MatrixDynamicDim(1, c.size()), MatrixCommon(c) {}
2914 : MatrixDynamicDim(m.size(),
std::empty(m) ? 0 : m.
begin()->size()),
2932 : MatrixDynamicDim(m.size(),
std::empty(m) ? 0 : m.
begin()->size()),
2947 : MatrixDynamicDim(1, rv.size()), MatrixCommon(rv) {}
2949#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2951 DynamicMatrix(
void const* ptr,
size_t r,
size_t c) : DynamicMatrix(r, c) {
2953 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2958 : DynamicMatrix(c) {
2960 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2966 std::initializer_list<std::initializer_list<scalar_type>>
const& m)
2967 : DynamicMatrix(m) {
2969 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2972 static DynamicMatrix
one(
void const* ptr,
size_t n) {
2974 LIBSEMIGROUPS_ASSERT(ptr ==
nullptr);
2979 ~DynamicMatrix() =
default;
2995 std::fill(x.begin(), x.end(), ZeroOp()());
2996 for (
size_t r = 0; r < n; ++r) {
2997 x(r, r) = OneOp()();
3002#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3092 template <typename T>
3093 bool operator<=(T const& that) const;
3105 template <typename T>
3106 bool operator>=(T const& that) const;
3119 template <typename T>
3137 using MatrixCommon::at;
3138 using MatrixCommon::begin;
3139 using MatrixCommon::cbegin;
3140 using MatrixCommon::cend;
3141 using MatrixCommon::coords;
3142 using MatrixCommon::end;
3143 using MatrixCommon::hash_value;
3144 using MatrixCommon::number_of_cols;
3145 using MatrixCommon::number_of_rows;
3146 using MatrixCommon::one;
3147 using MatrixCommon::operator!=;
3148 using MatrixCommon::operator();
3149 using MatrixCommon::operator*;
3150 using MatrixCommon::operator*=;
3151 using MatrixCommon::operator+;
3152 using MatrixCommon::operator+=;
3153 using MatrixCommon::operator<;
3154 using MatrixCommon::operator<=;
3155 using MatrixCommon::operator==;
3156 using MatrixCommon::operator>;
3157 using MatrixCommon::operator>=;
3158 using MatrixCommon::product_inplace_no_checks;
3159 using MatrixCommon::row;
3160 using MatrixCommon::row_no_checks;
3161 using MatrixCommon::rows;
3162 using MatrixCommon::scalar_one;
3163 using MatrixCommon::scalar_zero;
3164 using MatrixCommon::semiring;
3166 using MatrixCommon::transpose;
3167 using MatrixCommon::transpose_no_checks;
3172 static_cast<MatrixDynamicDim&
>(*this).swap(
3173 static_cast<MatrixDynamicDim&
>(that));
3174 static_cast<MatrixCommon&
>(*this).swap(
static_cast<MatrixCommon&
>(that));
3178 using MatrixCommon::resize;
3219 template <
typename Semiring,
typename Scalar>
3221 :
public detail::MatrixDynamicDim<Scalar>,
3222 public detail::MatrixCommon<std::vector<Scalar>,
3223 DynamicMatrix<Semiring, Scalar>,
3224 DynamicRowView<Semiring, Scalar>,
3226 using MatrixCommon = detail::MatrixCommon<std::vector<Scalar>,
3228 DynamicRowView<Semiring, Scalar>,
3230 friend MatrixCommon;
3231 using MatrixDynamicDim = ::libsemigroups::detail::MatrixDynamicDim<Scalar>;
3291 : MatrixDynamicDim(r, c), MatrixCommon(), _semiring(sr) {
3313 : MatrixDynamicDim(rws.size(),
3314 std::empty(rws) ? 0 : rws.
begin()->size()),
3335 : MatrixDynamicDim(rws.size(), (rws.empty() ? 0 : rws.
begin()->size())),
3354 : MatrixDynamicDim(1, rw.size()), MatrixCommon(rw), _semiring(sr) {}
3368 : MatrixDynamicDim(1, rv.size()),
3370 _semiring(rv._matrix->
semiring()) {}
3389 std::fill(x.begin(), x.end(), x.scalar_zero());
3390 for (
size_t r = 0; r < n; ++r) {
3391 x(r, r) = x.scalar_one();
3396 ~DynamicMatrix() =
default;
3398#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3488 template <typename T>
3489 bool operator<=(T const& that) const;
3501 template <typename T>
3502 bool operator>=(T const& that) const;
3515 template <typename T>
3533 using MatrixCommon::at;
3534 using MatrixCommon::begin;
3535 using MatrixCommon::cbegin;
3536 using MatrixCommon::cend;
3537 using MatrixCommon::coords;
3538 using MatrixCommon::end;
3539 using MatrixCommon::hash_value;
3540 using MatrixCommon::number_of_cols;
3541 using MatrixCommon::number_of_rows;
3542 using MatrixCommon::one;
3543 using MatrixCommon::operator!=;
3544 using MatrixCommon::operator();
3545 using MatrixCommon::operator*;
3546 using MatrixCommon::operator*=;
3547 using MatrixCommon::operator+;
3548 using MatrixCommon::operator+=;
3549 using MatrixCommon::operator<;
3550 using MatrixCommon::operator<=;
3551 using MatrixCommon::operator==;
3552 using MatrixCommon::operator>;
3553 using MatrixCommon::operator>=;
3554 using MatrixCommon::product_inplace_no_checks;
3555 using MatrixCommon::row;
3556 using MatrixCommon::row_no_checks;
3557 using MatrixCommon::rows;
3558 using MatrixCommon::scalar_one;
3559 using MatrixCommon::scalar_zero;
3560 using MatrixCommon::semiring;
3562 using MatrixCommon::transpose;
3563 using MatrixCommon::transpose_no_checks;
3568 static_cast<MatrixDynamicDim&
>(*this).swap(
3569 static_cast<MatrixDynamicDim&
>(that));
3570 static_cast<MatrixCommon&
>(*this).swap(
static_cast<MatrixCommon&
>(that));
3575 using MatrixCommon::resize;
3577 scalar_type plus_no_checks_impl(scalar_type x,
3578 scalar_type y)
const noexcept {
3579 return _semiring->plus_no_checks(x, y);
3582 scalar_type product_no_checks_impl(scalar_type x,
3583 scalar_type y)
const noexcept {
3584 return _semiring->product_no_checks(x, y);
3587 scalar_type one_impl() const noexcept {
3588 return _semiring->scalar_one();
3591 scalar_type zero_impl() const noexcept {
3592 return _semiring->scalar_zero();
3595 Semiring
const* semiring_impl() const noexcept {
3599 Semiring
const* _semiring;
3608 template <
typename T>
3609 struct IsStaticMatrixHelper : std::false_type {};
3611 template <
typename PlusOp,
3618 struct IsStaticMatrixHelper<
3619 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>>
3620 : std::true_type {};
3622 template <
typename T>
3623 struct IsMatWithSemiringHelper : std::false_type {};
3625 template <
typename Semiring,
typename Scalar>
3626 struct IsMatWithSemiringHelper<DynamicMatrix<Semiring, Scalar>>
3627 : std::true_type {};
3629 template <
typename S,
typename T =
void>
3630 struct IsTruncMatHelper : std::false_type {};
3644 template <
typename T>
3657 template <
typename T>
3670 template <
typename T>
3672 = detail::IsMatWithSemiringHelper<T>::value;
3676 template <
typename T>
3677 static constexpr bool IsTruncMat = IsTruncMatHelper<T>::value;
3679 template <
typename Mat>
3680 void throw_if_semiring_nullptr(Mat
const& m) {
3683 "the matrix's pointer to a semiring is nullptr!")
3687 template <
typename Mat,
typename Container>
3688 auto throw_if_bad_dim(Container
const& m)
3689 -> std::enable_if_t<IsStaticMatrix<Mat>> {
3691 uint64_t
const R = m.size();
3692 uint64_t
const C = std::empty(m) ? 0 : m.begin()->size();
3693 if (R != Mat::nr_rows || C != Mat::nr_cols) {
3695 "invalid argument, cannot initialize an {}x{} matrix with compile "
3696 "time dimension, with an {}x{} container",
3704 template <
typename Mat,
typename Container>
3705 auto throw_if_bad_dim(Container
const&)
3706 -> std::enable_if_t<IsDynamicMatrix<Mat>> {}
3732 template <
typename Mat>
3734 -> std::enable_if_t<!detail::IsTruncMat<Mat>,
3735 typename Mat::scalar_type> {
3752 template <
typename Mat>
3753 constexpr auto threshold(Mat
const&)
noexcept
3755 typename Mat::scalar_type> {
3756 return detail::IsTruncMatHelper<Mat>::threshold;
3774 template <
typename Mat>
3777 typename Mat::scalar_type> {
3778 return x.semiring()->threshold();
3936 = DynamicMatrix<BooleanPlus, BooleanProd, BooleanZero, BooleanOne, int>;
3949 template <
size_t R,
size_t C>
3972 template <
size_t R = 0,
size_t C = R>
3974 = std::conditional_t<R == 0 || C == 0, DynamicBMat, StaticBMat<R, C>>;
3977 template <
typename T>
3980 template <
size_t R,
size_t C>
3986 template <
typename T>
3987 struct BitSetCapacity {
3988 static constexpr size_t value = BitSet<1>::max_size();
3991 template <
size_t R,
size_t C>
3993 static_assert(R == C,
"the number of rows and columns must be equal");
3994 static constexpr size_t value = R;
4008 template <
typename T>
4009 static constexpr bool IsBMat = detail::IsBMatHelper<T>::value;
4020 template <
typename Scalar>
4022 if constexpr (std::is_same_v<Scalar, NegativeInfinity>
4023 || std::is_signed_v<Scalar>) {
4031 return fmt::format(
"{}", a);
4053 template <
typename Mat>
4055 using scalar_type =
typename Mat::scalar_type;
4057 m.cbegin(), m.cend(), [](scalar_type x) { return x == 0 || x == 1; });
4058 if (it != m.cend()) {
4059 auto [r, c] = m.coords(it);
4061 "invalid entry, expected 0 or 1 but found {} in entry ({}, {})",
4062 detail::entry_repr(*it),
4085 template <
typename Mat>
4086 std::enable_if_t<IsBMat<Mat>>
4088 if (val != 0 && val != 1) {
4090 detail::entry_repr(val));
4139 template <
typename Scalar>
4153 constexpr Scalar
operator()(Scalar x, Scalar y)
const noexcept {
4170 template <
typename Scalar>
4184 constexpr Scalar
operator()(Scalar x, Scalar y)
const noexcept {
4198 template <
typename Scalar>
4209 constexpr Scalar
operator()() const noexcept {
4223 template <
typename Scalar>
4234 constexpr Scalar
operator()() const noexcept {
4249 template <
typename Scalar>
4272 template <
size_t R,
size_t C,
typename Scalar>
4297 template <
size_t R = 0,
size_t C = R,
typename Scalar =
int>
4298 using IntMat = std::conditional_t<R == 0 || C == 0,
4302 template <
typename T>
4305 template <
size_t R,
size_t C,
typename Scalar>
4308 template <
typename Scalar>
4322 template <
typename T>
4323 static constexpr bool IsIntMat = detail::IsIntMatHelper<T>::value;
4340 template <
typename Mat>
4342 using scalar_type =
typename Mat::scalar_type;
4343 auto it =
std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4344 return val == POSITIVE_INFINITY || val == NEGATIVE_INFINITY;
4346 if (it != x.cend()) {
4347 auto [r, c] = x.coords(it);
4349 "invalid entry, expected entries to be integers, "
4350 "but found {} in entry ({}, {})",
4351 detail::entry_repr(*it),
4373 template <
typename Mat>
4374 std::enable_if_t<IsIntMat<Mat>>
4378 "invalid entry, expected entries to be integers, "
4380 detail::entry_repr(val));
4441 template <
typename Scalar>
4444 "MaxPlus requires a signed integer type as parameter!");
4457 Scalar
operator()(Scalar x, Scalar y)
const noexcept {
4488 template <
typename Scalar>
4491 "MaxPlus requires a signed integer type as parameter!");
4504 Scalar
operator()(Scalar x, Scalar y)
const noexcept {
4525 template <
typename Scalar>
4528 "MaxPlus requires a signed integer type as parameter!");
4538 constexpr Scalar
operator()() const noexcept {
4553 template <
typename Scalar>
4572 template <
size_t R,
size_t C,
typename Scalar>
4596 template <
size_t R = 0,
size_t C = R,
typename Scalar =
int>
4597 using MaxPlusMat = std::conditional_t<R == 0 || C == 0,
4602 template <
typename T>
4605 template <
size_t R,
size_t C,
typename Scalar>
4609 template <
typename Scalar>
4623 template <
typename T>
4624 static constexpr bool IsMaxPlusMat = detail::IsMaxPlusMatHelper<T>::value;
4642 template <
typename Mat>
4644 -> std::enable_if_t<IsMaxPlusMat<Mat>> {
4645 using scalar_type =
typename Mat::scalar_type;
4646 auto it =
std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4647 return val == POSITIVE_INFINITY;
4649 if (it != x.cend()) {
4650 auto [r, c] = x.coords(it);
4652 "invalid entry, expected entries to be integers or {} (= {}), "
4653 "but found {} (= {}) in entry ({}, {})",
4678 template <
typename Mat>
4679 std::enable_if_t<IsMaxPlusMat<Mat>>
4682 using scalar_type =
typename Mat::scalar_type;
4684 "integers or {} (= {}) but found {} (= {})",
4749 template <
typename Scalar>
4752 "MinPlus requires a signed integer type as parameter!");
4765 Scalar
operator()(Scalar x, Scalar y)
const noexcept {
4796 template <
typename Scalar>
4799 "MinPlus requires a signed integer type as parameter!");
4812 Scalar
operator()(Scalar x, Scalar y)
const noexcept {
4833 template <
typename Scalar>
4836 "MinPlus requires a signed integer type as parameter!");
4846 constexpr Scalar
operator()() const noexcept {
4861 template <
typename Scalar>
4880 template <
size_t R,
size_t C,
typename Scalar>
4904 template <
size_t R = 0,
size_t C = R,
typename Scalar =
int>
4905 using MinPlusMat = std::conditional_t<R == 0 || C == 0,
4910 template <
typename T>
4913 template <
size_t R,
size_t C,
typename Scalar>
4917 template <
typename Scalar>
4931 template <
typename T>
4932 static constexpr bool IsMinPlusMat = detail::IsMinPlusMatHelper<T>::value;
4950 template <
typename Mat>
4952 using scalar_type =
typename Mat::scalar_type;
4953 auto it =
std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4954 return val == NEGATIVE_INFINITY;
4956 if (it != x.cend()) {
4957 auto [r, c] = x.coords(it);
4959 "invalid entry, expected entries to be integers or {} (= {}), "
4960 "but found {} (= {}) in entry ({}, {})",
4985 template <
typename Mat>
4986 std::enable_if_t<IsMinPlusMat<Mat>>
4989 using scalar_type =
typename Mat::scalar_type;
4991 "integers or {} (= {}) but found {} (= {})",
5075 template <
size_t T,
typename Scalar>
5078 "MaxPlus requires a signed integer type as parameter!");
5091 Scalar
operator()(Scalar x, Scalar y)
const noexcept {
5092 LIBSEMIGROUPS_ASSERT((x >= 0 && x <=
static_cast<Scalar
>(T))
5094 LIBSEMIGROUPS_ASSERT((y >= 0 && y <=
static_cast<Scalar
>(T))
5099 return std::min(x + y,
static_cast<Scalar
>(T));
5117 template <
typename Scalar =
int>
5120 "MaxPlus requires a signed integer type as parameter!");
5178 static constexpr Scalar
scalar_one() noexcept {
5221 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5223 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5228 return std::min(x + y, _threshold);
5256 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5258 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5285 Scalar
const _threshold;
5300 template <
size_t T,
typename Scalar>
5320 template <
size_t T,
size_t R,
size_t C,
typename Scalar>
5346 template <
size_t T = 0,
size_t R = 0,
size_t C = R,
typename Scalar =
int>
5349 std::conditional_t<T == 0,
5350 DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>,
5355 template <
typename T>
5358 template <
size_t T,
size_t R,
size_t C,
typename Scalar>
5361 static constexpr Scalar threshold = T;
5364 template <
size_t T,
typename Scalar>
5367 static constexpr Scalar threshold = T;
5370 template <
typename Scalar>
5371 struct IsMaxPlusTruncMatHelper<
5373 static constexpr Scalar threshold =
UNDEFINED;
5388 template <
typename T>
5390 = detail::IsMaxPlusTruncMatHelper<T>::value;
5393 template <
typename T>
5394 struct IsTruncMatHelper<T,
std::enable_if_t<IsMaxPlusTruncMat<T>>>
5396 static constexpr typename T::scalar_type threshold
5397 = IsMaxPlusTruncMatHelper<T>::threshold;
5420 template <
typename Mat>
5423 detail::throw_if_semiring_nullptr(m);
5425 using scalar_type =
typename Mat::scalar_type;
5428 return x == NEGATIVE_INFINITY || (0 <= x && x <= t);
5430 if (it != m.cend()) {
5431 auto [r, c] = m.coords(it);
5433 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5434 "but found {} in entry ({}, {})",
5438 detail::entry_repr(*it),
5463 template <
typename Mat>
5464 std::enable_if_t<IsMaxPlusTruncMat<Mat>>
5466 detail::throw_if_semiring_nullptr(m);
5467 using scalar_type =
typename Mat::scalar_type;
5471 "invalid entry, expected values in {{0, 1, ..., {}, -{} (= {})}} "
5476 detail::entry_repr(val));
5555 template <
size_t T,
typename Scalar>
5569 Scalar
operator()(Scalar x, Scalar y)
const noexcept {
5570 LIBSEMIGROUPS_ASSERT((x >= 0 && x <=
static_cast<Scalar
>(T))
5572 LIBSEMIGROUPS_ASSERT((y >= 0 && y <=
static_cast<Scalar
>(T))
5577 return std::min(x + y,
static_cast<Scalar
>(T));
5594 template <
typename Scalar =
int>
5597 "MinPlus requires an integral type as parameter!");
5653 static constexpr Scalar
scalar_one() noexcept {
5697 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5699 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5704 return std::min(x + y, _threshold);
5732 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5734 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5761 Scalar
const _threshold;
5776 template <
size_t T,
typename Scalar>
5796 template <
size_t T,
size_t R,
size_t C,
typename Scalar>
5823 template <
size_t T = 0,
size_t R = 0,
size_t C = R,
typename Scalar =
int>
5826 std::conditional_t<T == 0,
5827 DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>,
5832 template <
typename T>
5835 template <
size_t T,
size_t R,
size_t C,
typename Scalar>
5838 static constexpr Scalar threshold = T;
5841 template <
size_t T,
typename Scalar>
5844 static constexpr Scalar threshold = T;
5847 template <
typename Scalar>
5848 struct IsMinPlusTruncMatHelper<
5850 static constexpr Scalar threshold =
UNDEFINED;
5865 template <
typename T>
5867 = detail::IsMinPlusTruncMatHelper<T>::value;
5870 template <
typename T>
5871 struct IsTruncMatHelper<T,
std::enable_if_t<IsMinPlusTruncMat<T>>>
5873 static constexpr typename T::scalar_type threshold
5874 = IsMinPlusTruncMatHelper<T>::threshold;
5898 template <
typename Mat>
5901 detail::throw_if_semiring_nullptr(m);
5903 using scalar_type =
typename Mat::scalar_type;
5906 return x == POSITIVE_INFINITY || (0 <= x && x <= t);
5908 if (it != m.cend()) {
5913 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5914 "but found {} in entry ({}, {})",
5918 detail::entry_repr(*it),
5943 template <
typename Mat>
5944 std::enable_if_t<IsMinPlusTruncMat<Mat>>
5946 detail::throw_if_semiring_nullptr(m);
5948 using scalar_type =
typename Mat::scalar_type;
5952 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5957 detail::entry_repr(val));
6020 template <
size_t T,
size_t P,
typename Scalar>
6021 constexpr Scalar thresholdperiod(Scalar x)
noexcept {
6023 return T + (x - T) % P;
6028 template <
typename Scalar>
6029 inline Scalar thresholdperiod(Scalar x,
6031 Scalar period)
noexcept {
6032 if (x > threshold) {
6062 template <
size_t T,
size_t P,
typename Scalar>
6075 constexpr Scalar
operator()(Scalar x, Scalar y)
const noexcept {
6076 return detail::thresholdperiod<T, P>(x + y);
6103 template <
size_t T,
size_t P,
typename Scalar>
6118 constexpr Scalar
operator()(Scalar x, Scalar y)
const noexcept {
6119 return detail::thresholdperiod<T, P>(x * y);
6137 template <
typename Scalar =
size_t>
6180 NTPSemiring(Scalar t, Scalar p) : _period(p), _threshold(t) {
6184 "expected non-negative value for 1st argument, found {}", t);
6189 "expected positive value for 2nd argument, found {}", p);
6203 static constexpr Scalar
scalar_one() noexcept {
6248 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + _threshold - 1);
6249 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + _threshold - 1);
6250 return detail::thresholdperiod(x * y, _threshold, _period);
6278 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + _threshold - 1);
6279 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + _threshold - 1);
6280 return detail::thresholdperiod(x + y, _threshold, _period);
6311 Scalar
period() const noexcept {
6330 template <
typename Scalar>
6346 template <
size_t T,
size_t P,
typename Scalar>
6372 template <
size_t T,
size_t P,
size_t R,
size_t C,
typename Scalar>
6403 template <
size_t T = 0,
6407 typename Scalar =
size_t>
6408 using NTPMat = std::conditional_t<
6410 std::conditional_t<T == 0 && P == 0,
6416 template <
typename T>
6419 template <
typename Scalar>
6421 static constexpr Scalar threshold =
UNDEFINED;
6422 static constexpr Scalar period =
UNDEFINED;
6425 template <
size_t T,
size_t P,
typename Scalar>
6428 static constexpr Scalar threshold = T;
6429 static constexpr Scalar period = P;
6432 template <
size_t T,
size_t P,
size_t R,
size_t C,
typename Scalar>
6434 static constexpr Scalar threshold = T;
6435 static constexpr Scalar period = P;
6450 template <
typename U>
6451 static constexpr bool IsNTPMat = detail::IsNTPMatHelper<U>::value;
6454 template <
typename T>
6456 static constexpr typename T::scalar_type threshold
6457 = IsNTPMatHelper<T>::threshold;
6458 static constexpr typename T::scalar_type period
6459 = IsNTPMatHelper<T>::period;
6486 template <
size_t T,
size_t P,
size_t R,
size_t C,
typename Scalar>
6508 template <
size_t T,
size_t P,
typename Scalar>
6529 template <
typename Scalar>
6531 return x.semiring()->period();
6556 template <
typename Mat>
6558 detail::throw_if_semiring_nullptr(m);
6560 using scalar_type =
typename Mat::scalar_type;
6564 return (0 <= x && x < p + t);
6566 if (it != m.cend()) {
6571 "invalid entry, expected values in {{0, 1, ..., {}}}, but "
6572 "found {} in entry ({}, {})",
6574 detail::entry_repr(*it),
6601 template <
typename Mat>
6602 std::enable_if_t<IsNTPMat<Mat>>
6604 detail::throw_if_semiring_nullptr(m);
6605 using scalar_type =
typename Mat::scalar_type;
6608 if (val < 0 || val >= p + t) {
6610 "invalid entry, expected values in {{0, 1, ..., {}}}, but "
6613 detail::entry_repr(val));
6623 template <
typename T>
6626 using scalar_type =
typename T::scalar_type;
6627 using scalar_reference =
typename T::scalar_reference;
6628 using scalar_const_reference =
typename T::scalar_const_reference;
6629 using semiring_type = void;
6631 using container_type =
typename T::container_type;
6632 using iterator =
typename T::iterator;
6633 using const_iterator =
typename T::const_iterator;
6635 using underlying_matrix_type = T;
6637 using RowView =
typename T::RowView;
6643 using Row =
typename T::Row;
6645 scalar_type scalar_one() const noexcept {
6646 return _underlying_mat.scalar_one();
6649 scalar_type scalar_zero() const noexcept {
6650 return _underlying_mat.scalar_zero();
6657 ProjMaxPlusMat() : _is_normalized(false), _underlying_mat() {}
6658 ProjMaxPlusMat(ProjMaxPlusMat
const&) =
default;
6659 ProjMaxPlusMat(ProjMaxPlusMat&&) =
default;
6660 ProjMaxPlusMat& operator=(ProjMaxPlusMat
const&) =
default;
6661 ProjMaxPlusMat& operator=(ProjMaxPlusMat&&) =
default;
6663 ProjMaxPlusMat(
size_t r,
size_t c)
6664 : _is_normalized(false), _underlying_mat(r, c) {}
6668 typename underlying_matrix_type::semiring_type
const* semiring,
6671 : _is_normalized(false), _underlying_mat(semiring, r, c) {}
6673 explicit ProjMaxPlusMat(std::vector<std::vector<scalar_type>>
const& m)
6674 : _is_normalized(false), _underlying_mat(m) {
6679 std::initializer_list<std::initializer_list<scalar_type>>
const& m)
6681 std::vector<std::vector<scalar_type>>(m.begin(), m.
end())) {}
6683 ~ProjMaxPlusMat() =
default;
6685 ProjMaxPlusMat one()
const {
6686 auto result = ProjMaxPlusMat(_underlying_mat.one());
6690 static ProjMaxPlusMat one(
size_t n) {
6691 return ProjMaxPlusMat(T::one(n));
6698 bool operator==(ProjMaxPlusMat
const& that)
const {
6701 return _underlying_mat == that._underlying_mat;
6704 bool operator!=(ProjMaxPlusMat
const& that)
const {
6705 return !(_underlying_mat == that._underlying_mat);
6708 bool operator<(ProjMaxPlusMat
const& that)
const {
6711 return _underlying_mat < that._underlying_mat;
6714 bool operator>(ProjMaxPlusMat
const& that)
const {
6715 return that < *
this;
6718 template <
typename Thing>
6719 bool operator>=(Thing
const& that)
const {
6721 return that < *
this || that == *
this;
6725 template <
typename Thing>
6726 bool operator<=(Thing
const& that)
const {
6728 return *
this < that || that == *
this;
6735 scalar_reference operator()(
size_t r,
size_t c) {
6740 _is_normalized =
false;
6741 return _underlying_mat(r, c);
6744 scalar_reference at(
size_t r,
size_t c) {
6746 return this->operator()(r, c);
6749 scalar_const_reference operator()(
size_t r,
size_t c)
const {
6751 return _underlying_mat(r, c);
6754 scalar_const_reference at(
size_t r,
size_t c)
const {
6756 return this->operator()(r, c);
6759 size_t number_of_rows() const noexcept {
6760 return _underlying_mat.number_of_rows();
6763 size_t number_of_cols() const noexcept {
6764 return _underlying_mat.number_of_cols();
6767 size_t hash_value()
const {
6769 return Hash<T>()(_underlying_mat);
6776 void product_inplace_no_checks(ProjMaxPlusMat
const& A,
6777 ProjMaxPlusMat
const& B) {
6778 _underlying_mat.product_inplace_no_checks(A._underlying_mat,
6783 void operator+=(ProjMaxPlusMat
const& that) {
6784 _underlying_mat += that._underlying_mat;
6788 void operator*=(scalar_type a) {
6789 _underlying_mat *= a;
6793 void operator+=(scalar_type a) {
6794 _underlying_mat += a;
6798 ProjMaxPlusMat operator*(scalar_type a)
const {
6799 ProjMaxPlusMat result(*
this);
6804 ProjMaxPlusMat operator+(scalar_type a)
const {
6805 ProjMaxPlusMat result(*
this);
6814 ProjMaxPlusMat operator+(ProjMaxPlusMat
const& that)
const {
6815 return ProjMaxPlusMat(_underlying_mat + that._underlying_mat);
6818 ProjMaxPlusMat operator*(ProjMaxPlusMat
const& that)
const {
6819 return ProjMaxPlusMat(_underlying_mat * that._underlying_mat);
6830 iterator begin() noexcept {
6835 _is_normalized =
false;
6836 return _underlying_mat.begin();
6839 iterator
end() noexcept {
6844 _is_normalized =
false;
6845 return _underlying_mat.end();
6848 const_iterator begin() const noexcept {
6850 return _underlying_mat.begin();
6853 const_iterator
end() const noexcept {
6855 return _underlying_mat.end();
6858 const_iterator cbegin() const noexcept {
6860 return _underlying_mat.cbegin();
6863 const_iterator cend() const noexcept {
6865 return _underlying_mat.cend();
6872 void swap(ProjMaxPlusMat& that)
noexcept {
6873 std::swap(_underlying_mat, that._underlying_mat);
6877 _underlying_mat.transpose();
6880 void transpose_no_checks() noexcept {
6881 _underlying_mat.transpose_no_checks();
6888 RowView row(
size_t i)
const {
6890 return _underlying_mat.row(i);
6893 template <
typename C>
6894 void rows(C& x)
const {
6896 return _underlying_mat.rows(x);
6903 friend std::ostream& operator<<(std::ostream& os,
6904 ProjMaxPlusMat
const& x) {
6906 os << detail::to_string(x._underlying_mat);
6910 T
const& underlying_matrix() const noexcept {
6912 return _underlying_mat;
6916 explicit ProjMaxPlusMat(T&& mat)
6917 : _is_normalized(false), _underlying_mat(std::
move(mat)) {
6921 void normalize(
bool force =
false)
const {
6922 if ((_is_normalized && !force)
6923 || (_underlying_mat.number_of_rows() == 0)
6924 || (_underlying_mat.number_of_cols() == 0)) {
6925 _is_normalized =
true;
6929 _underlying_mat.cend());
6931 _underlying_mat.end(),
6932 [&n](scalar_type& s) {
6933 if (s != NEGATIVE_INFINITY) {
6937 _is_normalized =
true;
6940 mutable bool _is_normalized;
6941 mutable T _underlying_mat;
7003 template <
size_t R,
size_t C,
typename Scalar>
7005 = detail::ProjMaxPlusMat<StaticMaxPlusMat<R, C, Scalar>>;
7018 template <
typename Scalar>
7020 = detail::ProjMaxPlusMat<DynamicMaxPlusMat<Scalar>>;
7036 template <
size_t R = 0,
size_t C = R,
typename Scalar =
int>
7042 template <
typename T>
7045 template <
size_t R,
size_t C,
typename Scalar>
7049 template <
typename Scalar>
7065 template <
typename T>
7067 = detail::IsProjMaxPlusMatHelper<T>::value;
7087 template <
typename Mat>
7088 constexpr std::enable_if_t<IsProjMaxPlusMat<Mat>>
7110 template <
typename Mat>
7111 constexpr std::enable_if_t<IsProjMaxPlusMat<Mat>>
7156 template <
typename Mat>
7157 Mat
pow(Mat
const& x,
typename Mat::scalar_type e) {
7158 using scalar_type =
typename Mat::scalar_type;
7163 "negative exponent, expected value >= 0, found {}", e);
7169 typename Mat::semiring_type
const* sr =
nullptr;
7183 auto z = (e % 2 == 0 ? x.one() : y);
7185 Mat tmp(sr, x.number_of_rows(), x.number_of_cols());
7187 tmp.product_inplace_no_checks(y, y);
7191 tmp.product_inplace_no_checks(z, y);
7221 template <
typename Mat,
typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
7248 template <
typename Mat,
typename = std::enable_if_t<IsStaticMatrix<Mat>>>
7249 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
7250 rows(Mat
const& x) {
7251 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
7292 template <
typename Mat,
size_t R,
size_t C,
typename Container>
7294 detail::StaticVector1<BitSet<C>, R>& result) {
7295 using RowView =
typename Mat::RowView;
7296 using value_type =
typename std::decay_t<Container>::value_type;
7298 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7301 "Container::value_type must equal Mat::RowView or "
7302 "std::vector<bool>!!");
7303 static_assert(R <= BitSet<1>::max_size(),
7304 "R must be at most BitSet<1>::max_size()!");
7305 static_assert(C <= BitSet<1>::max_size(),
7306 "C must be at most BitSet<1>::max_size()!");
7307 LIBSEMIGROUPS_ASSERT(views.size() <= R);
7308 LIBSEMIGROUPS_ASSERT(views.empty() || views[0].size() <= C);
7309 for (
auto const& v : views) {
7310 result.emplace_back(v.cbegin(), v.cend());
7346 template <
typename Mat,
size_t R,
size_t C,
typename Container>
7348 using RowView =
typename Mat::RowView;
7349 using value_type =
typename std::decay_t<Container>::value_type;
7350 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7353 "Container::value_type must equal Mat::RowView or "
7354 "std::vector<bool>!!");
7355 static_assert(R <= BitSet<1>::max_size(),
7356 "R must be at most BitSet<1>::max_size()!");
7357 static_assert(C <= BitSet<1>::max_size(),
7358 "C must be at most BitSet<1>::max_size()!");
7359 LIBSEMIGROUPS_ASSERT(views.size() <= R);
7360 LIBSEMIGROUPS_ASSERT(views.empty() || views[0].size() <= C);
7361 detail::StaticVector1<BitSet<C>, R> result;
7395 template <
typename Mat,
size_t R,
size_t C>
7397 detail::StaticVector1<BitSet<C>, R>& result) {
7398 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7399 static_assert(R <= BitSet<1>::max_size(),
7400 "R must be at most BitSet<1>::max_size()!");
7401 static_assert(C <= BitSet<1>::max_size(),
7402 "C must be at most BitSet<1>::max_size()!");
7403 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= C);
7404 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= R);
7427 template <
typename Mat>
7429 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7430 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7431 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7432 size_t const M = detail::BitSetCapacity<Mat>::value;
7464 template <
typename Mat,
typename Container>
7466 using value_type =
typename std::decay_t<Container>::value_type;
7467 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7468 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7469 "Container::value_type must be BitSet or std::bitset");
7470 LIBSEMIGROUPS_ASSERT(
rows.size() <= BitSet<1>::max_size());
7471 LIBSEMIGROUPS_ASSERT(
rows.empty()
7472 ||
rows[0].size() <= BitSet<1>::max_size());
7477 for (
size_t i = 0; i <
rows.size(); ++i) {
7480 for (
size_t j = 0; j < i; ++j) {
7485 for (
size_t j = i + 1; j <
rows.size(); ++j) {
7490 if (cup !=
rows[i]) {
7519 template <
typename Mat,
typename Container>
7521 using value_type =
typename std::decay_t<Container>::value_type;
7522 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7523 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7524 "Container::value_type must be BitSet or std::bitset");
7525 LIBSEMIGROUPS_ASSERT(
rows.size() <= BitSet<1>::max_size());
7526 LIBSEMIGROUPS_ASSERT(
rows.empty()
7527 ||
rows[0].size() <= BitSet<1>::max_size());
7528 std::decay_t<Container> result;
7560 template <typename Mat, size_t M = detail::BitSetCapacity<Mat>::value>
7562 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7563 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7564 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7565 detail::StaticVector1<BitSet<M>, M> result;
7593 template <
typename Mat,
typename Container>
7595 using value_type =
typename Container::value_type;
7596 static_assert(
IsBMat<Mat>,
"IsBMat<Mat> must be true!");
7597 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7598 "Container::value_type must be BitSet or std::bitset");
7599 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7600 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7635 template <
typename Mat,
typename Container>
7636 std::enable_if_t<IsMaxPlusTruncMat<Mat>>
7637 row_basis(Container&& views, std::decay_t<Container>& result) {
7638 using value_type =
typename std::decay_t<Container>::value_type;
7640 "Container::value_type must be Mat::RowView");
7641 using scalar_type =
typename Mat::scalar_type;
7642 using Row =
typename Mat::Row;
7644 if (views.empty()) {
7648 LIBSEMIGROUPS_ASSERT(result.empty());
7653 for (
size_t r1 = 0; r1 < views.size(); ++r1) {
7654 if (r1 == 0 || views[r1] != views[r1 - 1]) {
7655 std::fill(tmp1.begin(), tmp1.end(), tmp1.scalar_zero());
7656 for (
size_t r2 = 0; r2 < r1; ++r2) {
7658 for (
size_t c = 0; c < tmp1.number_of_cols(); ++c) {
7659 if (views[r2][c] == tmp1.scalar_zero()) {
7662 if (views[r1][c] >= views[r2][c]) {
7665 =
std::min(max_scalar, views[r1][c] - views[r2][c]);
7668 max_scalar = tmp1.scalar_zero();
7672 if (max_scalar != tmp1.scalar_zero()) {
7673 tmp1 += views[r2] * max_scalar;
7676 if (tmp1 != views[r1]) {
7677 result.push_back(views[r1]);
7713 template <
typename Mat,
typename Container>
7714 std::enable_if_t<IsBMat<Mat>>
row_basis(Container&& views,
7715 std::decay_t<Container>& result) {
7716 using RowView =
typename Mat::RowView;
7717 using value_type =
typename std::decay_t<Container>::value_type;
7721 "Container::value_type must equal Mat::RowView or "
7722 "std::vector<bool>!!");
7724 if (views.empty()) {
7729 size_t const M = detail::BitSetCapacity<Mat>::value;
7731 using bitset_type =
typename decltype(br)::value_type;
7735 LIBSEMIGROUPS_ASSERT(br.size() == views.size());
7736 for (
size_t i = 0; i < br.size(); ++i) {
7737 lookup.
insert({br[i], i});
7742 auto it = lookup.
find(bs);
7743 LIBSEMIGROUPS_ASSERT(it != lookup.
end());
7744 result.push_back(views[it->second]);
7774 template <
typename Mat,
7776 typename = std::enable_if_t<IsMatrix<Mat>>>
7777 void row_basis(Mat
const& x, Container& result) {
7801 template <
typename Mat,
typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
7827 template <
typename Mat,
typename = std::enable_if_t<IsStaticMatrix<Mat>>>
7828 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
7830 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
7854 template <
typename Mat,
typename Container>
7856 using value_type =
typename std::decay_t<Container>::value_type;
7857 static_assert(
IsMatrix<Mat>,
"IsMatrix<Mat> must be true!");
7859 "Container::value_type must be Mat::RowView");
7861 std::decay_t<Container> result;
7900 template <
typename Mat,
typename = std::enable_if_t<IsBMat<Mat>>>
7902 size_t const M = detail::BitSetCapacity<Mat>::value;
7907 st.
insert(bitset_row_basis_.cbegin(), bitset_row_basis_.cend());
7909 bitset_row_basis_.cend());
7910 for (
size_t i = 0; i < orb.
size(); ++i) {
7911 for (
auto& row : bitset_row_basis_) {
7913 for (
size_t j = 0; j < x.number_of_rows(); ++j) {
7914 cup.set(j, cup[j] || row[j]);
7916 if (st.
insert(cup).second) {
7945 template <
typename Mat>
7946 auto operator+(
typename Mat::scalar_type a, Mat
const& x)
7947 -> std::enable_if_t<IsMatrix<Mat>, Mat> {
7970 template <
typename Mat>
7971 auto operator*(
typename Mat::scalar_type a, Mat
const& x)
7972 -> std::enable_if_t<IsMatrix<Mat>, Mat> {
8012 template <
typename Mat,
8016 detail::throw_if_any_row_wrong_size(rows);
8017 detail::throw_if_bad_dim<Mat>(rows);
8048 template <
typename Mat,
8082 template <
typename Mat,
8124 template <
typename Mat,
8126 typename = std::enable_if_t<IsMatrix<Mat>>>
8129 Mat
make(Semiring
const* semiring,
8132 detail::throw_if_any_row_wrong_size(rows);
8133 detail::throw_if_bad_dim<Mat>(rows);
8134 Mat m(semiring, rows);
8170 template <
typename Mat,
8172 typename = std::enable_if_t<IsMatrix<Mat>>>
8173 Mat
make(Semiring
const* semiring,
8175 detail::throw_if_any_row_wrong_size(rows);
8176 detail::throw_if_bad_dim<Mat>(rows);
8177 Mat m(semiring, rows);
8204 template <
typename Mat,
8206 typename = std::enable_if_t<IsMatrix<Mat>>>
8207 Mat
make(Semiring
const* semiring,
8210 Mat m(semiring, row);
8242 template <
size_t R,
size_t C,
typename Scalar>
8265 template <
typename S,
typename T>
8267 detail::RowViewCommon<S, T>
const& x) {
8269 for (
auto it = x.cbegin(); it != x.cend(); ++it) {
8271 if (it != x.cend() - 1) {
8295 template <
typename Mat>
8299 if (x.number_of_rows() != 1) {
8304 if (n != x.number_of_rows() - 1) {
8309 if (x.number_of_rows() != 1) {
8331 template <
typename Mat>
8336 size_t max_width = 72)
8338 if (braces.size() != 2) {
8340 "the 4th argument (braces) must have size 2, found {}",
8344 size_t const R = x.number_of_rows();
8345 size_t const C = x.number_of_cols();
8349 for (
size_t r = 0; r < R; ++r) {
8350 for (
size_t c = 0; c < C; ++c) {
8352 = detail::unicode_string_length(detail::entry_repr(x(r, c)));
8353 row_widths[r] += width;
8354 if (width > max_col_widths[c]) {
8355 max_col_widths[c] = width;
8362 auto const total_width = col_width * C + prefix.size() + 1;
8363 if (total_width > max_width) {
8368 "<{}x{} {}>", x.number_of_rows(), x.number_of_cols(), short_name);
8376 auto const lbrace = braces[0], rbrace = braces[1];
8377 if (R != 0 && C != 0) {
8379 for (
size_t r = 0; r < R; ++r) {
8380 result += fmt::format(
"{}{}", rindent, lbrace);
8383 for (
size_t c = 0; c < C; ++c) {
8384 result += fmt::format(
8385 "{}{:>{}}", csep, detail::entry_repr(x(r, c)), col_width);
8388 result += fmt::format(
"{}", rbrace);
8428 template <
typename Mat>
8443 constexpr size_t operator()(Mat
const& x)
const noexcept {
8444 return x.number_of_rows() * x.number_of_rows() * x.number_of_rows();
8458 template <
typename Mat>
8459 struct Degree<Mat,
std::enable_if_t<IsMatrix<Mat>>> {
8472 constexpr size_t operator()(Mat
const& x)
const noexcept {
8473 return x.number_of_rows();
8487 template <
typename Mat>
8488 struct Hash<Mat,
std::enable_if_t<IsMatrix<Mat>>> {
8501 constexpr size_t operator()(Mat
const& x)
const {
8502 return x.hash_value();
8521 template <
typename Mat>
8526 constexpr void operator()(Mat&,
size_t)
const noexcept {
8528 LIBSEMIGROUPS_ASSERT(
false);
8542 template <
typename Mat>
8543 struct One<Mat,
std::enable_if_t<IsMatrix<Mat>>> {
8572 template <
typename Mat>
8573 struct Product<Mat,
std::enable_if_t<IsMatrix<Mat>>> {
8593 operator()(Mat& xy, Mat
const& x, Mat
const& y,
size_t = 0)
const {
8594 xy.product_inplace_no_checks(x, y);
8602 std::enable_if_t<libsemigroups::IsMatrix<Mat>>>
8603 inline void swap(Mat& x, Mat& y)
noexcept {
DynamicMatrix(std::initializer_list< scalar_type > const &c)
Construct a vector from a std::initializer_list.
Definition matrix.hpp:2890
DynamicMatrix(std::initializer_list< std::initializer_list< scalar_type > > const &m)
Construct a matrix from std::initializer_list of std::initializer_list of scalars.
Definition matrix.hpp:2912
DynamicMatrix()=default
Default constructor.
DynamicMatrix & operator=(DynamicMatrix &&)=default
Default move assignment operator.
scalar_reference at(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
ProdOp Prod
Alias for the template parameter ProdOp.
Definition matrix.hpp:2811
void product_inplace_no_checks(DynamicMatrix const &x, DynamicMatrix const &y)
Multiplies x and y and stores the result in this.
DynamicMatrix & operator=(DynamicMatrix const &)=default
Default copy assignment operator.
DynamicMatrix Row
The type of a row of a DynamicMatrix.
Definition matrix.hpp:2802
PlusOp Plus
Alias for the template parameter PlusOp.
Definition matrix.hpp:2808
void rows(T &x) const
Add row views for every row in the matrix to a container.
scalar_type scalar_one() const noexcept
Returns the multiplicative identity of the underlying semiring.
typename MatrixCommon::scalar_const_reference scalar_const_reference
The type of const references to the entries in the matrix.
Definition matrix.hpp:2798
void swap(DynamicMatrix &that) noexcept
Swaps the contents of *this with the contents of that.
Definition matrix.hpp:3171
const_iterator cend() noexcept
Returns a const iterator pointing one beyond the last entry in the matrix.
static DynamicMatrix one(size_t n)
Construct the identity matrix.
Definition matrix.hpp:2993
DynamicMatrix(size_t r, size_t c)
Construct a matrix with given dimensions.
Definition matrix.hpp:2868
ZeroOp Zero
Alias for the template parameter ZeroOp.
Definition matrix.hpp:2814
scalar_type scalar_zero() const noexcept
Returns the additive identity of the underlying semiring.
void transpose_no_checks()
Transpose a matrix in-place.
semiring_type const * semiring() const noexcept
Returns the underlying semiring.
OneOp One
Alias for the template parameter OneOp.
Definition matrix.hpp:2817
void semiring_type
Alias for the semiring type (void).
Definition matrix.hpp:2824
RowView row(size_t i) const
Returns a view into a row.
DynamicMatrix(RowView const &rv)
Construct a row from a row view.
Definition matrix.hpp:2946
iterator begin() noexcept
Returns an iterator pointing at the first entry.
size_t number_of_rows() const noexcept
Returns the number of rows of the matrix.
DynamicRowView< PlusOp, ProdOp, ZeroOp, OneOp, Scalar > RowView
The type of a row view into a DynamicMatrix.
Definition matrix.hpp:2805
RowView row_no_checks(size_t i) const
Returns a view into a row.
DynamicMatrix(std::vector< std::vector< scalar_type > > const &m)
Construct a matrix from std::vector of std::vector of scalars.
Definition matrix.hpp:2931
typename MatrixCommon::scalar_reference scalar_reference
The type of references to the entries in the matrix.
Definition matrix.hpp:2793
scalar_reference at(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
DynamicMatrix(DynamicMatrix const &)=default
Default copy constructor.
size_t hash_value() const
Return a hash value of a matrix.
const_iterator cbegin() noexcept
Returns a const iterator pointing at the first entry.
DynamicMatrix(DynamicMatrix &&)=default
Default move constructor.
typename MatrixCommon::scalar_type scalar_type
The type of the entries in the matrix.
Definition matrix.hpp:2790
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
void transpose()
Transpose a matrix in-place.
std::pair< scalar_type, scalar_type > coords(const_iterator it) const
Get the coordinates of an iterator.
iterator end() noexcept
Returns an iterator pointing one beyond the last entry in the matrix.
DynamicMatrix(Semiring const *sr, std::initializer_list< std::initializer_list< scalar_type > > const &rws)
Construct a matrix over a given semiring (std::initializer_list of std::initializer_list).
Definition matrix.hpp:3310
DynamicMatrix & operator=(DynamicMatrix &&)=default
Default move assignment operator.
static DynamicMatrix one(Semiring const *semiring, size_t n)
Construct the identity matrix.
Definition matrix.hpp:3387
scalar_reference at(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
DynamicMatrix(Semiring const *sr, std::vector< std::vector< scalar_type > > const &rws)
Construct a matrix over a given semiring (std::vector of std::vector).
Definition matrix.hpp:3333
DynamicMatrix(Semiring const *sr, size_t r, size_t c)
Construct a matrix over a given semiring with given dimensions.
Definition matrix.hpp:3290
void product_inplace_no_checks(DynamicMatrix const &x, DynamicMatrix const &y)
Multiplies x and y and stores the result in this.
DynamicMatrix & operator=(DynamicMatrix const &)=default
Default copy assignment operator.
DynamicMatrix Row
Alias for the type of the rows of a DynamicMatrix.
Definition matrix.hpp:3247
void rows(T &x) const
Add row views for every row in the matrix to a container.
scalar_type scalar_one() const noexcept
Returns the multiplicative identity of the underlying semiring.
typename MatrixCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:3243
void swap(DynamicMatrix &that) noexcept
Swaps the contents of *this with the contents of that.
Definition matrix.hpp:3567
const_iterator cend() noexcept
Returns a const iterator pointing one beyond the last entry in the matrix.
scalar_type scalar_zero() const noexcept
Returns the additive identity of the underlying semiring.
void transpose_no_checks()
Transpose a matrix in-place.
DynamicMatrix()=delete
Deleted.
semiring_type const * semiring() const noexcept
Returns the underlying semiring.
RowView row(size_t i) const
Returns a view into a row.
DynamicMatrix(RowView const &rv)
Construct a row over a given semiring (RowView).
Definition matrix.hpp:3367
iterator begin() noexcept
Returns an iterator pointing at the first entry.
size_t number_of_rows() const noexcept
Returns the number of rows of the matrix.
DynamicMatrix(Semiring const *sr, std::initializer_list< scalar_type > const &rw)
Construct a row over a given semiring (std::initializer_list).
Definition matrix.hpp:3352
RowView row_no_checks(size_t i) const
Returns a view into a row.
typename MatrixCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:3238
scalar_reference at(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
DynamicMatrix(DynamicMatrix const &)=default
Default copy constructor.
size_t hash_value() const
Return a hash value of a matrix.
const_iterator cbegin() noexcept
Returns a const iterator pointing at the first entry.
DynamicMatrix(DynamicMatrix &&)=default
Default move constructor.
typename MatrixCommon::scalar_type scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:3235
DynamicRowView< Semiring, Scalar > RowView
Alias for the type of row views of a DynamicMatrix.
Definition matrix.hpp:3250
Semiring semiring_type
Alias for the template parameter Semiring.
Definition matrix.hpp:3255
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
void transpose()
Transpose a matrix in-place.
std::pair< scalar_type, scalar_type > coords(const_iterator it) const
Get the coordinates of an iterator.
iterator end() noexcept
Returns an iterator pointing one beyond the last entry in the matrix.
DynamicRowView & operator=(DynamicRowView &&)=default
Default move assignment operator.
size_t size() const noexcept
Returns the size of the row.
DynamicRowView & operator=(DynamicRowView const &)=default
Default copy assignment operator.
DynamicRowView(DynamicRowView const &)=default
Default copy constructor.
DynamicRowView(DynamicRowView &&)=default
Default move constructor.
DynamicRowView(Row const &r)
Construct a row view from a Row.
Definition matrix.hpp:1572
typename RowViewCommon::iterator iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1536
typename RowViewCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1547
typename RowViewCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1542
iterator begin() noexcept
Returns a iterator pointing at the first entry.
iterator cend()
Returns a const iterator pointing one beyond the last entry of the row.
typename matrix_type::Row Row
Alias for the type of a row in the underlying matrix.
Definition matrix.hpp:1554
typename RowViewCommon::const_iterator const_iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1533
const_iterator cbegin() const noexcept
Returns a const iterator pointing at the first entry.
iterator end()
Returns a iterator pointing one beyond the last entry of the row.
Scalar scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1539
typename RowViewCommon::matrix_type matrix_type
Alias for the type of the underlying matrix.
Definition matrix.hpp:1551
DynamicRowView()=default
Default constructor.
size_t size() const noexcept
Returns the size of the row.
DynamicRowView & operator=(DynamicRowView const &)=default
Default copy assignment operator.
typename RowViewCommon::iterator iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1690
typename RowViewCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1701
typename RowViewCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1696
iterator begin() noexcept
Returns a iterator pointing at the first entry.
iterator cend()
Returns a const iterator pointing one beyond the last entry of the row.
typename matrix_type::Row Row
Alias for the type of a row in the underlying matrix.
Definition matrix.hpp:1708
typename RowViewCommon::const_iterator const_iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1687
const_iterator cbegin() const noexcept
Returns a const iterator pointing at the first entry.
iterator end()
Returns a iterator pointing one beyond the last entry of the row.
Scalar scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1693
typename RowViewCommon::matrix_type matrix_type
Alias for the type of the underlying matrix.
Definition matrix.hpp:1705
DynamicRowView()=default
Default constructor.
Class representing a truncated max-plus semiring.
Definition matrix.hpp:5116
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:5190
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in a truncated max-plus semiring.
Definition matrix.hpp:5253
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in a truncated max-plus semiring.
Definition matrix.hpp:5218
MaxPlusTruncSemiring()=delete
Deleted default constructor.
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:5278
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:5176
Class representing a truncated min-plus semiring.
Definition matrix.hpp:5593
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:5666
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in a truncated min-plus semiring.
Definition matrix.hpp:5729
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in a truncated min-plus semiring.
Definition matrix.hpp:5694
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:5754
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:5651
MinPlusTruncSemiring()=delete
Deleted default constructor.
NTPSemiring & operator=(NTPSemiring const &)=default
Default copy assignment operator.
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:6217
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in an ntp semiring.
Definition matrix.hpp:6275
NTPSemiring()=delete
Deleted default constructor.
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in an ntp semiring.
Definition matrix.hpp:6245
Scalar period() const noexcept
Get the period.
Definition matrix.hpp:6309
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:6293
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:6201
Static matrix class.
Definition matrix.hpp:1865
typename MatrixCommon::iterator iterator
Definition matrix.hpp:1912
StaticMatrix(std::initializer_list< scalar_type > const &c)
Construct a row (from std::initializer_list).
Definition matrix.hpp:1940
typename MatrixCommon::const_iterator const_iterator
Definition matrix.hpp:1915
scalar_const_reference at(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
scalar_reference at(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
ProdOp Prod
Definition matrix.hpp:1903
PlusOp Plus
Definition matrix.hpp:1900
scalar_type scalar_one() const noexcept
StaticMatrix(StaticMatrix &&)=default
Default move constructor.
typename MatrixCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1890
scalar_reference operator()(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
ZeroOp Zero
Definition matrix.hpp:1906
scalar_type scalar_zero() const noexcept
void transpose_no_checks()
semiring_type const * semiring() const noexcept
void product_inplace_no_checks(StaticMatrix const &x, StaticMatrix const &y)
OneOp One
Definition matrix.hpp:1909
StaticMatrix(std::initializer_list< std::initializer_list< scalar_type > > const &m)
Construct a matrix.
Definition matrix.hpp:1966
StaticRowView< PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar > RowView
Definition matrix.hpp:1897
RowView row(size_t i) const
void swap(StaticMatrix &that) noexcept
static StaticMatrix one() const
Returns an identity matrix.
StaticMatrix(StaticMatrix const &)=default
Default copy constructor.
iterator begin() noexcept
Returns an iterator pointing at the first entry.
StaticMatrix(RowView const &rv)
Construct a row from a row view.
Definition matrix.hpp:2002
size_t number_of_rows() const noexcept
Returns the number of rows of the matrix.
StaticMatrix(std::vector< std::vector< scalar_type > > const &m)
Construct a matrix.
Definition matrix.hpp:1982
StaticMatrix< PlusOp, ProdOp, ZeroOp, OneOp, 1, C, Scalar > Row
Alias for the type of the rows of a StaticMatrix.
Definition matrix.hpp:1894
const_iterator cbegin() const noexcept
RowView row_no_checks(size_t i) const
StaticMatrix()=default
Default constructor.
typename MatrixCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1885
size_t hash_value() const
typename MatrixCommon::scalar_type scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1882
scalar_const_reference operator()(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
StaticMatrix & operator=(StaticMatrix &&)=default
Default move assignment operator.
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
StaticMatrix & operator=(StaticMatrix const &)=default
Default copy assignment operator.
std::pair< scalar_type, scalar_type > coords(const_iterator it) const
Class for views into a row of a matrix over a semiring.
Definition matrix.hpp:1080
typename RowViewCommon::iterator iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1096
typename RowViewCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1107
StaticRowView & operator=(StaticRowView &&)=default
Default move assignment operator.
typename RowViewCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1102
iterator begin() noexcept
Returns a iterator pointing at the first entry.
iterator cend()
Returns a const iterator pointing one beyond the last entry of the row.
StaticRowView()=default
Default constructor.
typename matrix_type::Row Row
Alias for the type of a row in the underlying matrix.
Definition matrix.hpp:1114
typename RowViewCommon::const_iterator const_iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1093
const_iterator cbegin() const noexcept
Returns a const iterator pointing at the first entry.
iterator end()
Returns a iterator pointing one beyond the last entry of the row.
Scalar scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1099
StaticRowView(StaticRowView &&)=default
Default move constructor.
typename RowViewCommon::matrix_type matrix_type
Alias for the type of the underlying matrix.
Definition matrix.hpp:1111
StaticRowView(StaticRowView const &)=default
Default copy constructor.
static constexpr size_t size() const noexcept
Returns the size of the row.
StaticRowView & operator=(StaticRowView const &)=default
Default copy assignment operator.
StaticRowView(Row const &r)
Construct a row view from a Row.
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
Bipartition operator*(Bipartition const &x, Bipartition const &y)
Multiply two bipartitions.
std::ostringstream & operator<<(std::ostringstream &os, BMat8 const &x)
Insertion operator.
StaticMatrix< BooleanPlus, BooleanProd, BooleanZero, BooleanOne, R, C, int > StaticBMat
Alias for static boolean matrices.
Definition matrix.hpp:3949
static constexpr bool IsBMat
Helper to check if a type is BMat.
Definition matrix.hpp:4007
DynamicMatrix< BooleanPlus, BooleanProd, BooleanZero, BooleanOne, int > DynamicBMat
Alias for dynamic boolean matrices.
Definition matrix.hpp:3935
std::enable_if_t< IsBMat< Mat > > throw_if_bad_entry(Mat const &m)
Check the entries in a boolean matrix are valid.
Definition matrix.hpp:4052
std::conditional_t< R==0||C==0, DynamicBMat, StaticBMat< R, C > > BMat
Alias template for boolean matrices.
Definition matrix.hpp:3972
NegativeInfinity const NEGATIVE_INFINITY
Value for negative infinity.
Undefined const UNDEFINED
Value for something undefined.
PositiveInfinity const POSITIVE_INFINITY
Value for positive infinity.
#define LIBSEMIGROUPS_EXCEPTION(...)
Throw a LibsemigroupsException.
Definition exception.hpp:99
std::conditional_t< R==0||C==0, DynamicIntMat< Scalar >, StaticIntMat< R, C, Scalar > > IntMat
Alias template for integer matrices.
Definition matrix.hpp:4296
DynamicMatrix< IntegerPlus< Scalar >, IntegerProd< Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, Scalar > DynamicIntMat
Alias for dynamic integer matrices.
Definition matrix.hpp:4248
StaticMatrix< IntegerPlus< Scalar >, IntegerProd< Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, R, C, Scalar > StaticIntMat
Alias for static integer matrices.
Definition matrix.hpp:4271
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:855
static constexpr bool IsMaxPlusMat
Helper variable template.
Definition matrix.hpp:4622
constexpr bool IsStaticMatrix
Helper variable template.
Definition matrix.hpp:3645
constexpr bool IsDynamicMatrix
Helper variable template.
Definition matrix.hpp:3658
static constexpr bool IsIntMat
Helper variable template.
Definition matrix.hpp:4321
auto operator+(typename Mat::scalar_type a, Mat const &x) -> std::enable_if_t< IsMatrix< Mat >, Mat >
Add a scalar to a matrix.
Definition matrix.hpp:7942
static constexpr bool IsMatWithSemiring
Helper variable template.
Definition matrix.hpp:3672
static constexpr bool IsMinPlusMat
Helper variable template.
Definition matrix.hpp:4930
constexpr bool IsMatrix
Helper variable template.
Definition matrix.hpp:168
StaticMatrix< MaxPlusPlus< Scalar >, MaxPlusProd< Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMaxPlusMat
Alias for static max-plus matrices.
Definition matrix.hpp:4571
DynamicMatrix< MaxPlusPlus< Scalar >, MaxPlusProd< Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMaxPlusMat
Alias for dynamic max-plus matrices.
Definition matrix.hpp:4552
std::conditional_t< R==0||C==0, DynamicMaxPlusMat< Scalar >, StaticMaxPlusMat< R, C, Scalar > > MaxPlusMat
Alias template for max-plus matrices.
Definition matrix.hpp:4595
DynamicMatrix< MaxPlusPlus< Scalar >, MaxPlusTruncProd< T, Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMaxPlusTruncMat
Alias for dynamic truncated max-plus matrices.
Definition matrix.hpp:5299
std::conditional_t< R==0||C==0, std::conditional_t< T==0, DynamicMatrix< MaxPlusTruncSemiring< Scalar >, Scalar >, DynamicMaxPlusTruncMat< T, Scalar > >, StaticMaxPlusTruncMat< T, R, C, Scalar > > MaxPlusTruncMat
Alias template for truncated max-plus matrices.
Definition matrix.hpp:5345
StaticMatrix< MaxPlusPlus< Scalar >, MaxPlusTruncProd< T, Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMaxPlusTruncMat
Alias for static truncated max-plus matrices.
Definition matrix.hpp:5319
static constexpr bool IsMaxPlusTruncMat
Helper to check if a type is MaxPlusTruncMat.
Definition matrix.hpp:5388
DynamicMatrix< MinPlusPlus< Scalar >, MinPlusProd< Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMinPlusMat
Alias for dynamic min-plus matrices.
Definition matrix.hpp:4860
StaticMatrix< MinPlusPlus< Scalar >, MinPlusProd< Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMinPlusMat
Alias for static min-plus matrices.
Definition matrix.hpp:4879
std::conditional_t< R==0||C==0, DynamicMinPlusMat< Scalar >, StaticMinPlusMat< R, C, Scalar > > MinPlusMat
Alias template for min-plus matrices.
Definition matrix.hpp:4903
DynamicMatrix< MinPlusPlus< Scalar >, MinPlusTruncProd< T, Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMinPlusTruncMat
Alias for dynamic truncated min-plus matrices.
Definition matrix.hpp:5775
StaticMatrix< MinPlusPlus< Scalar >, MinPlusTruncProd< T, Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMinPlusTruncMat
Alias for static truncated min-plus matrices.
Definition matrix.hpp:5795
static constexpr bool IsMinPlusTruncMat
Helper to check if a type is MinPlusTruncMat.
Definition matrix.hpp:5865
std::conditional_t< R==0||C==0, std::conditional_t< T==0, DynamicMatrix< MinPlusTruncSemiring< Scalar >, Scalar >, DynamicMinPlusTruncMat< T, Scalar > >, StaticMinPlusTruncMat< T, R, C, Scalar > > MinPlusTruncMat
Alias template for truncated min-plus matrices.
Definition matrix.hpp:5822
DynamicMatrix< NTPSemiring< Scalar >, Scalar > DynamicNTPMatWithSemiring
Alias for ntp matrices with dynamic threshold and period.
Definition matrix.hpp:6329
DynamicMatrix< NTPPlus< T, P, Scalar >, NTPProd< T, P, Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, Scalar > DynamicNTPMatWithoutSemiring
Alias for ntp matrices with static threshold and period.
Definition matrix.hpp:6345
static constexpr bool IsNTPMat
Helper to check if a type is NTPMat.
Definition matrix.hpp:6449
std::conditional_t< R==0||C==0, std::conditional_t< T==0 &&P==0, DynamicNTPMatWithSemiring< Scalar >, DynamicNTPMatWithoutSemiring< T, P, Scalar > >, StaticNTPMat< T, P, R, C, Scalar > > NTPMat
Alias template for ntp matrices.
Definition matrix.hpp:6406
StaticMatrix< NTPPlus< T, P, Scalar >, NTPProd< T, P, Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, R, C, Scalar > StaticNTPMat
Alias for ntp matrices with static threshold and period, and dimensions.
Definition matrix.hpp:6371
std::conditional_t< R==0||C==0, DynamicProjMaxPlusMat< Scalar >, StaticProjMaxPlusMat< R, C, Scalar > > ProjMaxPlusMat
Alias template for projective max-plus matrices.
Definition matrix.hpp:7033
detail::ProjMaxPlusMat< DynamicMaxPlusMat< Scalar > > DynamicProjMaxPlusMat
Alias for dynamic projective max-plus matrices with run-time dimensions.
Definition matrix.hpp:7016
static constexpr bool IsProjMaxPlusMat
Helper to check if a type is ProjMaxPlusMat.
Definition matrix.hpp:7063
detail::ProjMaxPlusMat< StaticMaxPlusMat< R, C, Scalar > > StaticProjMaxPlusMat
Alias for static projective max-plus matrices with compile-time arithmetic and dimensions.
Definition matrix.hpp:7002
T inner_product(T... args)
T lexicographical_compare(T... args)
Bipartition one(Bipartition const &f)
Return the identity bipartition with the same degree as the given bipartition.
constexpr BMat8 transpose(BMat8 const &x) noexcept
Returns the transpose of a BMat8.
Definition bmat8.hpp:704
Namespace for helper functions for matrices.
Definition matrix.hpp:170
void bitset_row_basis(Container &&rows, std::decay_t< Container > &result)
Appends a basis for the space spanned by some bitsets to a container.
Definition matrix.hpp:7461
void bitset_rows(Container &&views, detail::StaticVector1< BitSet< C >, R > &result)
Converts a container of row views of a boolean matrix to bit sets, and append them to another contain...
Definition matrix.hpp:7289
constexpr Scalar period(StaticNTPMat< T, P, R, C, Scalar > const &) noexcept
Returns the period of a static ntp matrix.
Definition matrix.hpp:6485
auto throw_if_bad_coords(Mat const &x, size_t r, size_t c) -> std::enable_if_t< IsMatrix< Mat > >
Throws the arguments do not index an entry of a matrix.
Definition matrix.hpp:235
constexpr auto threshold(Mat const &) noexcept -> std::enable_if_t<!detail::IsTruncMat< Mat >, typename Mat::scalar_type >
Returns the threshold of a matrix.
Definition matrix.hpp:3733
size_t row_space_size(Mat const &x)
Returns the size of the row space of a boolean matrix.
Definition matrix.hpp:7897
std::vector< typename Mat::RowView > rows(Mat const &x)
Returns a std::vector of row views into the rows of a dynamic matrix.
Definition matrix.hpp:7218
auto throw_if_bad_dim(Mat const &x, Mat const &y) -> std::enable_if_t< IsMatrix< Mat > >
Throws if two matrices do not have the same dimensions.
Definition matrix.hpp:206
Mat pow(Mat const &x, typename Mat::scalar_type e)
Returns a power of a matrix.
Definition matrix.hpp:7153
auto throw_if_not_square(Mat const &x) -> std::enable_if_t< IsMatrix< Mat > >
Throws if a matrix is not square.
Definition matrix.hpp:184
std::enable_if_t< IsMaxPlusTruncMat< Mat > > row_basis(Container &&views, std::decay_t< Container > &result)
Appends a basis for a space spanned by row views or bit sets to a container.
Definition matrix.hpp:7633
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
Function object for returning the multiplicative identity.
Definition matrix.hpp:3883
constexpr bool operator()() const noexcept
Call operator returning the multiplication identity true of the boolean semiring.
Definition matrix.hpp:3894
Function object for addition in the boolean semiring.
Definition matrix.hpp:3829
constexpr bool operator()(bool x, bool y) const noexcept
Call operator for addition.
Definition matrix.hpp:3842
Function object for multiplication in the boolean semiring.
Definition matrix.hpp:3856
constexpr bool operator()(bool x, bool y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:3869
Function object for returning the additive identity.
Definition matrix.hpp:3908
constexpr bool operator()() const noexcept
Call operator returning the additive identity false of the boolean semiring.
Definition matrix.hpp:3919
constexpr size_t operator()(Mat const &x) const noexcept
Call operator.
Definition matrix.hpp:8439
Adapter for the complexity of multiplication.
Definition adapters.hpp:128
constexpr size_t operator()(Mat const &x) const noexcept
Call operator.
Definition matrix.hpp:8468
Adapter for the degree of an element.
Definition adapters.hpp:166
constexpr size_t operator()(Mat const &x) const
Call operator.
Definition matrix.hpp:8497
Adapter for hashing.
Definition adapters.hpp:453
constexpr void operator()(Mat &, size_t) const noexcept
Call operator.
Definition matrix.hpp:8522
Adapter for increasing the degree of an element.
Definition adapters.hpp:206
Function object for returning the multiplicative identity.
Definition matrix.hpp:4222
constexpr Scalar operator()() const noexcept
Call operator returning the integer 1.
Definition matrix.hpp:4232
Function object for addition in the ring of integers.
Definition matrix.hpp:4138
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4151
Function object for multiplication in the ring of integers.
Definition matrix.hpp:4169
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4182
Function object for returning the additive identity.
Definition matrix.hpp:4197
constexpr Scalar operator()() const noexcept
Call operator returning the integer 0.
Definition matrix.hpp:4207
Function object for addition in the max-plus semiring.
Definition matrix.hpp:4440
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4455
Function object for multiplication in the max-plus semiring.
Definition matrix.hpp:4487
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4502
Function object for multiplication in truncated max-plus semirings.
Definition matrix.hpp:5074
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:5089
Function object for returning the additive identity of the max-plus semiring.
Definition matrix.hpp:4524
constexpr Scalar operator()() const noexcept
Call operator for additive identity.
Definition matrix.hpp:4536
Function object for addition in the min-plus semiring.
Definition matrix.hpp:4748
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4763
Function object for multiplication in the min-plus semiring.
Definition matrix.hpp:4795
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4810
Function object for multiplication in min-plus truncated semirings.
Definition matrix.hpp:5554
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:5567
Function object for returning the additive identity of the min-plus semiring.
Definition matrix.hpp:4832
constexpr Scalar operator()() const noexcept
Call operator for additive identity.
Definition matrix.hpp:4844
Function object for addition in ntp semirings.
Definition matrix.hpp:6061
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:6073
Function object for multiplication in an ntp semirings.
Definition matrix.hpp:6102
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:6116
Mat operator()(Mat const &x) const
Call operator.
Definition matrix.hpp:8553
Adapter for the identity element of the given type.
Definition adapters.hpp:253
void operator()(Mat &xy, Mat const &x, Mat const &y, size_t=0) const
Call operator.
Definition matrix.hpp:8589
Adapter for the product of two elements.
Definition adapters.hpp:291