libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
matrix.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2020-2025 James D. Mitchell
4//
5// This program is free software: you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program. If not, see <http://www.gnu.org/licenses/>.
17//
18
19// TODO(1) tpp file
20// TODO(1) put the detail stuff into detail/matrix-common.hpp
21// TODO(1) there're no complete set of init methods for matrices
22
23#ifndef LIBSEMIGROUPS_MATRIX_HPP_
24#define LIBSEMIGROUPS_MATRIX_HPP_
25
26#include <algorithm> // for min
27#include <array> // for array
28#include <bitset> // for bitset
29#include <cstddef> // for size_t
30#include <cstdint> // for uint64_t
31#include <initializer_list> // for initializer_list
32#include <iosfwd> // for ostringstream
33#include <iterator> // for distance
34#include <numeric> // for inner_product
35#include <ostream> // for operator<<, basic_ostream
36#include <string> // for string
37#include <tuple> // for tie
38#include <type_traits> // for false_type, is_signed, true_type
39#include <unordered_map> // for unordered_map
40#include <unordered_set> // for unordered_set
41#include <utility> // for forward, make_pair, pair
42#include <vector> // for vector
43
44#include "adapters.hpp" // for Degree
45#include "bitset.hpp" // for BitSet
46#include "config.hpp" // for LIBSEMIGROUPS_PARSED_BY_DOXYGEN
47#include "constants.hpp" // for POSITIVE_INFINITY
48#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
49#include "exception.hpp" // for LIBSEMIGROUPS_EXCEPTION
50
51#include "detail/containers.hpp" // for StaticVector1
52#include "detail/formatters.hpp" // for formatter of POSITIVE_INFINITY ...
53#include "detail/string.hpp" // for detail::to_string
54
55namespace libsemigroups {
56
128
130 // Detail
132
133 namespace detail {
134
135 template <typename T>
136 struct IsStdBitSetHelper : std::false_type {};
137
138 template <size_t N>
139 struct IsStdBitSetHelper<std::bitset<N>> : std::true_type {};
140
141 template <typename T>
142 static constexpr bool IsStdBitSet = IsStdBitSetHelper<T>::value;
143
144 struct MatrixPolymorphicBase {};
145
146 template <typename T>
147 struct IsMatrixHelper {
148 static constexpr bool value
149 = std::is_base_of<detail::MatrixPolymorphicBase, T>::value;
150 };
151 } // namespace detail
152
167 template <typename T>
168 constexpr bool IsMatrix = detail::IsMatrixHelper<T>::value;
169
170 namespace matrix {
171
183 template <typename Mat>
184 auto throw_if_not_square(Mat const& x) -> std::enable_if_t<IsMatrix<Mat>> {
185 if (x.number_of_rows() != x.number_of_cols()) {
186 LIBSEMIGROUPS_EXCEPTION("expected a square matrix, but found {}x{}",
187 x.number_of_rows(),
188 x.number_of_cols());
189 }
190 }
191
205 template <typename Mat>
206 auto throw_if_bad_dim(Mat const& x, Mat const& y)
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",
213 x.number_of_rows(),
214 x.number_of_cols(),
215 y.number_of_rows(),
216 y.number_of_cols());
217 }
218 }
219
234 template <typename Mat>
235 auto throw_if_bad_coords(Mat const& x, size_t r, size_t c)
236 -> std::enable_if_t<IsMatrix<Mat>> {
237 if (r >= x.number_of_rows()) {
238 LIBSEMIGROUPS_EXCEPTION("invalid row index in ({}, {}), expected "
239 "values in [0, {}) x [0, {})",
240 r,
241 c,
242 x.number_of_rows(),
243 x.number_of_cols(),
244 r);
245 }
246 if (c >= x.number_of_cols()) {
247 LIBSEMIGROUPS_EXCEPTION("invalid column index in ({}, {}), expected "
248 "values in [0, {}) x [0, {})",
249 r,
250 c,
251 x.number_of_rows(),
252 x.number_of_cols(),
253 r);
254 }
255 }
256 } // namespace matrix
257
259 // Detail
261 namespace detail {
262 template <typename Container,
263 typename Subclass,
264 typename TRowView,
265 typename Semiring = void>
266 class MatrixCommon : MatrixPolymorphicBase {
267 public:
269 // MatrixCommon - Aliases - public
271
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;
276
277 using container_type = Container;
278 using iterator = typename Container::iterator;
279 using const_iterator = typename Container::const_iterator;
280
281 using RowView = TRowView;
282
283 scalar_type scalar_one() const noexcept {
284 return static_cast<Subclass const*>(this)->one_impl();
285 }
286
287 scalar_type scalar_zero() const noexcept {
288 return static_cast<Subclass const*>(this)->zero_impl();
289 }
290
291 Semiring const* semiring() const noexcept {
292 return static_cast<Subclass const*>(this)->semiring_impl();
293 }
294
295 private:
297 // MatrixCommon - Semiring arithmetic - private
299
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);
302 }
303
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);
307 }
308
309 protected:
311 // MatrixCommon - Container functions - protected
313
314 // TODO(1) use constexpr-if, not SFINAE
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);
319 }
320
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> {}
324
325 public:
327 // MatrixCommon - Constructors + destructor - public
329
330 // none of the constructors are noexcept because they allocate
331 MatrixCommon() = default;
332 MatrixCommon(MatrixCommon const&) = default;
333 MatrixCommon(MatrixCommon&&) = default;
334 MatrixCommon& operator=(MatrixCommon const&) = default;
335 MatrixCommon& operator=(MatrixCommon&&) = default;
336
337 explicit MatrixCommon(std::initializer_list<scalar_type> const& c)
338 : MatrixCommon() {
339 resize(1, c.size());
340 std::copy(c.begin(), c.end(), _container.begin());
341 }
342
343 explicit MatrixCommon(std::vector<std::vector<scalar_type>> const& m)
344 : MatrixCommon() {
345 init(m);
346 }
347
348 MatrixCommon(
349 std::initializer_list<std::initializer_list<scalar_type>> const& m)
350 : MatrixCommon() {
351 init(m);
352 }
353
354 private:
355 // not noexcept because resize isn't
356 template <typename T>
357 void init(T const& m) {
358 size_t const R = m.size();
359 if (R == 0) {
360 return;
361 }
362 size_t const C = m.begin()->size();
363 resize(R, C);
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);
368 }
369 }
370 }
371
372 // not noexcept because init isn't
373 void
374 init(std::initializer_list<std::initializer_list<scalar_type>> const& m) {
375 init<std::initializer_list<std::initializer_list<scalar_type>>>(m);
376 }
377
378 public:
379 explicit MatrixCommon(RowView const& rv) : MatrixCommon() {
380 resize(1, rv.size());
381 std::copy(rv.cbegin(), rv.cend(), _container.begin());
382 }
383
384 ~MatrixCommon() = default;
385
386 // not noexcept because mem allocate is required
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();
393 }
394 return x;
395 }
396
398 // Comparison operators
400
401 // not noexcept because apparently vector::operator== isn't
402 bool operator==(MatrixCommon const& that) const {
403 return _container == that._container;
404 }
405
406 // not noexcept because apparently vector::operator== isn't
407 bool operator==(RowView const& that) const {
408 return number_of_rows() == 1
409 && static_cast<RowView>(*static_cast<Subclass const*>(this))
410 == that;
411 }
412
413 // not noexcept because apparently vector::operator< isn't
414 bool operator<(MatrixCommon const& that) const {
415 return _container < that._container;
416 }
417
418 // not noexcept because apparently vector::operator< isn't
419 bool operator<(RowView const& that) const {
420 return number_of_rows() == 1
421 && static_cast<RowView>(*static_cast<Subclass const*>(this))
422 < that;
423 }
424
425 // not noexcept because operator== isn't
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);
430 }
431
432 // not noexcept because operator< isn't
433 template <typename T>
434 bool operator>(T const& that) const {
435 static_assert(IsMatrix<T> || std::is_same_v<T, RowView>);
436 return that < *this;
437 }
438
439 // not noexcept because operator< isn't
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;
444 }
445
446 // not noexcept because operator< isn't
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;
451 }
452
454 // Attributes
456
457 // not noexcept because vector::operator[] isn't, and neither is
458 // array::operator[]
459 scalar_reference operator()(size_t r, size_t c) {
460 return this->_container[r * number_of_cols() + c];
461 }
462
463 scalar_reference at(size_t r, size_t c) {
464 matrix::throw_if_bad_coords(static_cast<Subclass const&>(*this), r, c);
465 return this->operator()(r, c);
466 }
467
468 // not noexcept because vector::operator[] isn't, and neither is
469 // array::operator[]
470 scalar_const_reference operator()(size_t r, size_t c) const {
471 return this->_container[r * number_of_cols() + c];
472 }
473
474 scalar_const_reference at(size_t r, size_t c) const {
475 matrix::throw_if_bad_coords(static_cast<Subclass const&>(*this), r, c);
476 return this->operator()(r, c);
477 }
478
479 // noexcept because number_of_rows_impl is noexcept
480 size_t number_of_rows() const noexcept {
481 return static_cast<Subclass const*>(this)->number_of_rows_impl();
482 }
483
484 // noexcept because number_of_cols_impl is noexcept
485 size_t number_of_cols() const noexcept {
486 return static_cast<Subclass const*>(this)->number_of_cols_impl();
487 }
488
489 // not noexcept because Hash<T>::operator() isn't
490 size_t hash_value() const {
491 return Hash<Container>()(_container);
492 }
493
495 // Arithmetic operators - in-place
497
498 // not noexcept because memory is allocated
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);
507
508 // Benchmarking boolean matrix multiplication reveals that using a
509 // non-static container_type gives the best performance, when compared
510 // to static container_type the performance is more or less the same
511 // (but not thread-safe), and there appears to be a performance
512 // penalty of about 50% when using static thread_local container_type
513 // (when compiling with clang).
514 size_t const N = A.number_of_rows();
515 std::vector<scalar_type> tmp(N, 0);
516
517 for (size_t c = 0; c < N; c++) {
518 for (size_t i = 0; i < N; i++) {
519 tmp[i] = B(i, c);
520 }
521 for (size_t r = 0; r < N; r++) {
522 (*this)(r, c) = std::inner_product(
523 A._container.begin() + r * N,
524 A._container.begin() + (r + 1) * N,
525 tmp.begin(),
526 scalar_zero(),
527 [this](scalar_type x, scalar_type y) {
528 return this->plus_no_checks(x, y);
529 },
530 [this](scalar_type x, scalar_type y) {
531 return this->product_no_checks(x, y);
532 });
533 }
534 }
535 }
536
537 // not noexcept because iterator increment isn't
538 void operator*=(scalar_type a) {
539 for (auto it = _container.begin(); it < _container.end(); ++it) {
540 *it = product_no_checks(*it, a);
541 }
542 }
543
544 // not noexcept because vector::operator[] and array::operator[] aren't
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]);
550 }
551 }
552
553 void operator+=(RowView const& that) {
554 LIBSEMIGROUPS_ASSERT(number_of_rows() == 1);
555 RowView(*static_cast<Subclass const*>(this)) += that;
556 }
557
558 void operator+=(scalar_type a) {
559 for (auto it = _container.begin(); it < _container.end(); ++it) {
560 *it = plus_no_checks(*it, a);
561 }
562 }
563
564 // TODO(2) implement operator*=(Subclass const&)
565
567 // Arithmetic operators - not in-place
569
570 // not noexcept because operator+= isn't
571 Subclass operator+(Subclass const& y) const {
572 Subclass result(*static_cast<Subclass const*>(this));
573 result += y;
574 return result;
575 }
576
577 // not noexcept because product_inplace_no_checks isn't
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),
581 y);
582 return result;
583 }
584
585 Subclass operator*(scalar_type a) const {
586 Subclass result(*static_cast<Subclass const*>(this));
587 result *= a;
588 return result;
589 }
590
591 Subclass operator+(scalar_type a) const {
592 Subclass result(*static_cast<Subclass const*>(this));
593 result += a;
594 return result;
595 }
596
598 // Iterators
600
601 // noexcept because vector::begin and array::begin are noexcept
602 iterator begin() noexcept {
603 return _container.begin();
604 }
605
606 // noexcept because vector::end and array::end are noexcept
607 iterator end() noexcept {
608 return _container.end();
609 }
610
611 // noexcept because vector::begin and array::begin are noexcept
612 const_iterator begin() const noexcept {
613 return _container.begin();
614 }
615
616 // noexcept because vector::end and array::end are noexcept
617 const_iterator end() const noexcept {
618 return _container.end();
619 }
620
621 // noexcept because vector::cbegin and array::cbegin are noexcept
622 const_iterator cbegin() const noexcept {
623 return _container.cbegin();
624 }
625
626 // noexcept because vector::cend and array::cend are noexcept
627 const_iterator cend() const noexcept {
628 return _container.cend();
629 }
630
631 template <typename U>
632 std::pair<scalar_type, scalar_type> coords(U const& it) const {
633 static_assert(
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");
637 scalar_type const v = std::distance(_container.begin(), it);
638 return std::make_pair(v / number_of_cols(), v % number_of_cols());
639 }
640
642 // Modifiers
644
645 // noexcept because vector::swap and array::swap are noexcept
646 void swap(MatrixCommon& that) noexcept {
647 std::swap(_container, that._container);
648 }
649
650 // noexcept because swap is noexcept, and so too are number_of_rows and
651 // number_of_cols
652 void transpose_no_checks() noexcept {
653 LIBSEMIGROUPS_ASSERT(number_of_rows() == number_of_cols());
654 if (number_of_rows() == 0) {
655 return;
656 }
657 auto& x = *this;
658 for (size_t r = 0; r < number_of_rows() - 1; ++r) {
659 for (size_t c = r + 1; c < number_of_cols(); ++c) {
660 std::swap(x(r, c), x(c, r));
661 }
662 }
663 }
664
665 void transpose() {
666 matrix::throw_if_not_square(static_cast<Subclass&>(*this));
667 transpose_no_checks();
668 }
669
671 // Rows
673
674 // not noexcept because there's an allocation
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(),
679 number_of_cols());
680 }
681
682 RowView row(size_t i) const {
683 if (i >= number_of_rows()) {
685 "index out of range, expected value in [{}, {}), found {}",
686 0,
687 number_of_rows(),
688 i);
689 }
690 return row_no_checks(i);
691 }
692
693 // not noexcept because there's an allocation
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()) {
699 x.emplace_back(
700 static_cast<Subclass const*>(this), itc, number_of_cols());
701 }
702 LIBSEMIGROUPS_ASSERT(x.size() == number_of_rows());
703 }
704
706 // Friend functions
708
709 friend std::ostream& operator<<(std::ostream& os, MatrixCommon const& x) {
710 os << detail::to_string(x);
711 return os;
712 }
713
714 private:
716 // Private data
718 container_type _container;
719 };
720
721 template <typename Scalar>
722 class MatrixDynamicDim {
723 public:
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;
729
730 MatrixDynamicDim(size_t r, size_t c)
731 : _number_of_cols(c), _number_of_rows(r) {}
732
733 ~MatrixDynamicDim() = default;
734
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);
738 }
739
740 protected:
741 size_t number_of_rows_impl() const noexcept {
742 return _number_of_rows;
743 }
744
745 size_t number_of_cols_impl() const noexcept {
746 return _number_of_cols;
747 }
748
749 private:
750 size_t _number_of_cols;
751 size_t _number_of_rows;
752 };
753
754 template <typename PlusOp,
755 typename ProdOp,
756 typename ZeroOp,
757 typename OneOp,
758 typename Scalar>
759 struct MatrixStaticArithmetic {
760 MatrixStaticArithmetic() = default;
761 MatrixStaticArithmetic(MatrixStaticArithmetic const&) = default;
762 MatrixStaticArithmetic(MatrixStaticArithmetic&&) = default;
763 MatrixStaticArithmetic& operator=(MatrixStaticArithmetic const&)
764 = default;
765 MatrixStaticArithmetic& operator=(MatrixStaticArithmetic&&) = default;
766
767 // TODO(2) from here to the end of MatrixStaticArithmetic should be
768 // private or protected
769 using scalar_type = Scalar;
770
771 static constexpr scalar_type plus_no_checks_impl(scalar_type x,
772 scalar_type y) noexcept {
773 return PlusOp()(x, y);
774 }
775
776 static constexpr scalar_type
777 product_no_checks_impl(scalar_type x, scalar_type y) noexcept {
778 return ProdOp()(x, y);
779 }
780
781 static constexpr scalar_type one_impl() noexcept {
782 return OneOp()();
783 }
784
785 static constexpr scalar_type zero_impl() noexcept {
786 return ZeroOp()();
787 }
788
789 static constexpr void const* semiring_impl() noexcept {
790 return nullptr;
791 }
792 };
793
795 // RowViews - class for cheaply storing iterators to rows
797
798 template <typename Mat, typename Subclass>
799 class RowViewCommon {
800 static_assert(IsMatrix<Mat>,
801 "the template parameter Mat must be derived from "
802 "MatrixPolymorphicBase");
803
804 public:
805 using const_iterator = typename Mat::const_iterator;
806 using iterator = typename Mat::iterator;
807
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;
811
812 using Row = typename Mat::Row;
813 using matrix_type = Mat;
814
815 size_t size() const noexcept {
816 return static_cast<Subclass const*>(this)->length_impl();
817 }
818
819 private:
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);
822 }
823
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);
827 }
828
829 public:
830 RowViewCommon() = default;
831 RowViewCommon(RowViewCommon const&) = default;
832 RowViewCommon(RowViewCommon&&) = default;
833 RowViewCommon& operator=(RowViewCommon const&) = default;
834 RowViewCommon& operator=(RowViewCommon&&) = default;
835
836 explicit RowViewCommon(Row const& r)
837 : RowViewCommon(const_cast<Row&>(r).begin()) {}
838
839 // Not noexcept because iterator::operator[] isn't
840 scalar_const_reference operator[](size_t i) const {
841 return _begin[i];
842 }
843
844 // Not noexcept because iterator::operator[] isn't
845 scalar_reference operator[](size_t i) {
846 return _begin[i];
847 }
848
849 // Not noexcept because iterator::operator[] isn't
850 scalar_const_reference operator()(size_t i) const {
851 return (*this)[i];
852 }
853
854 // Not noexcept because iterator::operator[] isn't
855 scalar_reference operator()(size_t i) {
856 return (*this)[i];
857 }
858
859 // noexcept because begin() is
860 const_iterator cbegin() const noexcept {
861 return _begin;
862 }
863
864 // not noexcept because iterator arithmetic isn't
865 const_iterator cend() const {
866 return _begin + size();
867 }
868
869 // noexcept because begin() is
870 const_iterator begin() const noexcept {
871 return _begin;
872 }
873
874 // not noexcept because iterator arithmetic isn't
875 const_iterator end() const {
876 return _begin + size();
877 }
878
879 // noexcept because begin() is
880 iterator begin() noexcept {
881 return _begin;
882 }
883
884 // not noexcept because iterator arithmetic isn't
885 iterator end() noexcept {
886 return _begin + size();
887 }
888
890 // Arithmetic operators
892
893 // not noexcept because operator[] isn't
894 void operator+=(RowViewCommon const& x) {
895 auto& this_ = *this;
896 for (size_t i = 0; i < size(); ++i) {
897 this_[i] = plus_no_checks(this_[i], x[i]);
898 }
899 }
900
901 // not noexcept because iterator arithmeic isn't
902 void operator+=(scalar_type a) {
903 for (auto& x : *this) {
904 x = plus_no_checks(x, a);
905 }
906 }
907
908 // not noexcept because iterator arithmeic isn't
909 void operator*=(scalar_type a) {
910 for (auto& x : *this) {
911 x = product_no_checks(x, a);
912 }
913 }
914
915 // not noexcept because operator*= isn't
916 Row operator*(scalar_type a) const {
917 Row result(*static_cast<Subclass const*>(this));
918 result *= a;
919 return result;
920 }
921
922 // not noexcept because operator+= isn't
923 Row operator+(RowViewCommon const& that) const {
924 Row result(*static_cast<Subclass const*>(this));
925 result += static_cast<Subclass const&>(that);
926 return result;
927 }
928
929 template <typename U>
930 bool operator==(U const& that) const {
931 // TODO(1) static assert that U is Row or RowView
932 return std::equal(begin(), end(), that.begin());
933 }
934
935 template <typename U>
936 bool operator!=(U const& that) const {
937 return !(*this == that);
938 }
939
940 template <typename U>
941 bool operator<(U const& that) const {
943 cbegin(), cend(), that.cbegin(), that.cend());
944 }
945
946 template <typename U>
947 bool operator>(U const& that) const {
948 return that < *this;
949 }
950
951 void swap(RowViewCommon& that) noexcept {
952 std::swap(that._begin, _begin);
953 }
954
955 friend std::ostream& operator<<(std::ostream& os,
956 RowViewCommon const& x) {
957 os << detail::to_string(x);
958 return os;
959 }
960
961 protected:
962 explicit RowViewCommon(iterator first) : _begin(first) {}
963
964 private:
965 iterator _begin;
966 };
967
968 template <typename Container>
969 void throw_if_any_row_wrong_size(Container const& m) {
970 if (m.size() <= 1) {
971 return;
972 }
973 uint64_t const C = m.begin()->size();
974 auto it = std::find_if_not(
975 m.begin() + 1, m.end(), [&C](typename Container::const_reference r) {
976 return r.size() == C;
977 });
978 if (it != m.end()) {
979 LIBSEMIGROUPS_EXCEPTION("invalid argument, expected every item to "
980 "have length {}, found {} in entry {}",
981 C,
982 it->size(),
983 std::distance(m.begin(), it));
984 }
985 }
986
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);
992 }
993
994 } // namespace detail
995
997 // Matrix forward declarations
999
1000#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1001 template <typename PlusOp,
1002 typename ProdOp,
1003 typename ZeroOp,
1004 typename OneOp,
1005 size_t R,
1006 size_t C,
1007 typename Scalar>
1008 class StaticMatrix;
1009
1010 template <typename... Args>
1011 class DynamicMatrix;
1012
1013 template <typename PlusOp,
1014 typename ProdOp,
1015 typename ZeroOp,
1016 typename OneOp,
1017 typename Scalar>
1018 class DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
1019
1020 template <typename Semiring, typename Scalar>
1021 class DynamicMatrix<Semiring, Scalar>;
1022#endif
1023
1028
1030 // StaticRowViews - static arithmetic
1032
1069 template <typename PlusOp,
1070 typename ProdOp,
1071 typename ZeroOp,
1072 typename OneOp,
1073 size_t C,
1074 typename Scalar>
1076 : public detail::RowViewCommon<
1077 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, 1, C, Scalar>,
1078 StaticRowView<PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar>>,
1079 public detail::
1080 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
1081 private:
1082 using RowViewCommon = detail::RowViewCommon<
1085 friend RowViewCommon;
1086
1087 template <size_t R>
1088 using StaticMatrix_ = ::libsemigroups::
1089 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>;
1090
1091 public:
1093 using const_iterator = typename RowViewCommon::const_iterator;
1094
1096 using iterator = typename RowViewCommon::iterator;
1097
1099 using scalar_type = Scalar;
1100
1102 using scalar_reference = typename RowViewCommon::scalar_reference;
1103
1105 // clang-format off
1106 // NOLINTNEXTLINE(whitespace/line_length)
1107 using scalar_const_reference = typename RowViewCommon::scalar_const_reference;
1108 // clang-format on
1109
1111 using matrix_type = typename RowViewCommon::matrix_type;
1112
1114 using Row = typename matrix_type::Row;
1115
1117 StaticRowView() = default;
1118
1120 StaticRowView(StaticRowView const&) = default;
1121
1124
1127
1130
1131#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1132 using RowViewCommon::RowViewCommon;
1133
1134 // TODO(2) This constructor should be private
1135 template <size_t R>
1136 StaticRowView(StaticMatrix_<R> const*,
1137 typename RowViewCommon::iterator it,
1138 size_t)
1139 : RowViewCommon(it) {}
1140
1141 using RowViewCommon::size;
1142#else
1154 explicit StaticRowView(Row const& r);
1155
1168 static constexpr size_t size() const noexcept;
1169
1182 iterator begin() noexcept;
1183
1198
1211 const_iterator cbegin() const noexcept;
1212
1227
1245 scalar_reference operator()(size_t i);
1246
1264 scalar_const_reference operator()(size_t i) const;
1265
1267 scalar_reference operator[](size_t i);
1268
1270 scalar_const_reference operator[](size_t i) const;
1271
1292 template <typename U>
1293 bool operator==(U const& that) const;
1294
1315 template <typename U>
1316 bool operator!=(U const& that) const;
1317
1323 // clang-format off
1326 // clang-format on
1339 template <typename U>
1340 bool operator<(U const& that) const;
1341
1363 template <typename U>
1364 bool operator<(U const& that) const;
1365
1385 Row operator+(StaticRowView const& that);
1386
1405 void operator+=(StaticRowView const& that);
1406
1420 void operator+=(scalar_type a);
1421
1439 Row operator*(scalar_type a) const;
1440
1454 void operator*=(scalar_type a);
1455#endif
1456
1457 private:
1458 static constexpr size_t length_impl() noexcept {
1459 return C;
1460 }
1461 };
1462
1464 // DynamicRowViews - static arithmetic
1466
1467 template <typename... Args>
1468 class DynamicRowView;
1469
1507 template <typename PlusOp,
1508 typename ProdOp,
1509 typename ZeroOp,
1510 typename OneOp,
1511 typename Scalar>
1512 class DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>
1513 : public detail::RowViewCommon<
1514 DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
1515 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>,
1516 public detail::
1517 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
1518 private:
1519 using DynamicMatrix_ = DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
1520 using RowViewCommon = detail::RowViewCommon<
1521 DynamicMatrix_,
1522 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>;
1523 friend RowViewCommon;
1524
1525 public:
1527 using const_iterator = typename RowViewCommon::const_iterator;
1528
1530 using iterator = typename RowViewCommon::iterator;
1531
1533 using scalar_type = Scalar;
1534
1536 using scalar_reference = typename RowViewCommon::scalar_reference;
1537
1539 // clang-format off
1540 // NOLINTNEXTLINE(whitespace/line_length)
1541 using scalar_const_reference = typename RowViewCommon::scalar_const_reference;
1542 // clang-format on
1543
1545 using matrix_type = typename RowViewCommon::matrix_type;
1546
1548 using Row = typename matrix_type::Row;
1549
1551 DynamicRowView() = default;
1552
1554 DynamicRowView(DynamicRowView const&) = default;
1555
1557 DynamicRowView(DynamicRowView&&) = default;
1558
1560 DynamicRowView& operator=(DynamicRowView const&) = default;
1561
1563 DynamicRowView& operator=(DynamicRowView&&) = default;
1564
1566 explicit DynamicRowView(Row const& r)
1567 : RowViewCommon(r), _length(r.number_of_cols()) {}
1568
1569#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1570 using RowViewCommon::RowViewCommon;
1571
1572 // TODO(2) This constructor should be private
1573 DynamicRowView(DynamicMatrix_ const*, iterator const& it, size_t N)
1574 : RowViewCommon(it), _length(N) {}
1575
1576 using RowViewCommon::size;
1577#else
1579 size_t size() const noexcept;
1580
1582 iterator begin() noexcept;
1583
1585 iterator end();
1586
1588 const_iterator cbegin() const noexcept;
1589
1591 iterator cend();
1592
1594 scalar_reference operator()(size_t i);
1595
1597 scalar_const_reference operator()(size_t i) const;
1598
1600 scalar_reference operator[](size_t i);
1601
1603 scalar_const_reference operator[](size_t i) const;
1604
1606 template <typename U>
1607 bool operator==(U const& that) const;
1608
1610 template <typename U>
1611 bool operator!=(U const& that) const;
1612
1614 template <typename U>
1615 bool operator<(U const& that) const;
1616
1618 template <typename U>
1619 bool operator<(U const& that) const;
1620
1622 Row operator+(DynamicRowView const& that);
1623
1625 void operator+=(DynamicRowView const& that);
1626
1628 void operator+=(scalar_type a);
1629
1631 Row operator*(scalar_type a) const;
1632
1634 void operator*=(scalar_type a);
1635#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1636
1637 private:
1638 size_t length_impl() const noexcept {
1639 return _length;
1640 }
1641 size_t _length;
1642 };
1643
1645 // DynamicRowViews - dynamic arithmetic
1647
1668 template <typename Semiring, typename Scalar>
1669 class DynamicRowView<Semiring, Scalar>
1670 : public detail::RowViewCommon<DynamicMatrix<Semiring, Scalar>,
1671 DynamicRowView<Semiring, Scalar>> {
1672 private:
1673 using DynamicMatrix_ = DynamicMatrix<Semiring, Scalar>;
1674 friend DynamicMatrix_;
1675 using RowViewCommon
1676 = detail::RowViewCommon<DynamicMatrix_,
1677 DynamicRowView<Semiring, Scalar>>;
1678 friend RowViewCommon;
1679
1680 public:
1682 using const_iterator = typename RowViewCommon::const_iterator;
1683
1685 using iterator = typename RowViewCommon::iterator;
1686
1688 using scalar_type = Scalar;
1689
1691 using scalar_reference = typename RowViewCommon::scalar_reference;
1692
1694 // clang-format off
1695 // NOLINTNEXTLINE(whitespace/line_length)
1696 using scalar_const_reference = typename RowViewCommon::scalar_const_reference;
1697 // clang-format on
1698
1700 using matrix_type = typename RowViewCommon::matrix_type;
1701
1703 using Row = typename matrix_type::Row;
1704
1706 DynamicRowView() = default;
1707
1709 DynamicRowView(DynamicRowView const&) = default;
1710
1712 DynamicRowView(DynamicRowView&&) = default;
1713
1715 DynamicRowView& operator=(DynamicRowView const&) = default;
1716
1718 DynamicRowView& operator=(DynamicRowView&&) = default;
1719
1721 explicit DynamicRowView(Row const& r) : RowViewCommon(r), _matrix(&r) {}
1722
1723#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1724 using RowViewCommon::RowViewCommon;
1725
1726 // TODO(2) This constructor should be private
1727 DynamicRowView(DynamicMatrix_ const* mat, iterator const& it, size_t)
1728 : RowViewCommon(it), _matrix(mat) {}
1729
1730 using RowViewCommon::size;
1731#else
1733 size_t size() const noexcept;
1734
1736 iterator begin() noexcept;
1737
1739 iterator end();
1740
1742 const_iterator cbegin() const noexcept;
1743
1745 iterator cend();
1746
1748 scalar_reference operator()(size_t i);
1749
1751 scalar_const_reference operator()(size_t i) const;
1752
1754 scalar_reference operator[](size_t i);
1755
1757 scalar_const_reference operator[](size_t i) const;
1758
1760 template <typename U>
1761 bool operator==(U const& that) const;
1762
1764 template <typename U>
1765 bool operator!=(U const& that) const;
1766
1768 template <typename U>
1769 bool operator<(U const& that) const;
1770
1772 template <typename U>
1773 bool operator<(U const& that) const;
1774
1776 Row operator+(DynamicRowView const& that);
1777
1779 void operator+=(DynamicRowView const& that);
1780
1782 void operator+=(scalar_type a);
1783
1785 Row operator*(scalar_type a) const;
1786
1788 void operator*=(scalar_type a);
1789#endif
1790
1791 private:
1792 size_t length_impl() const noexcept {
1793 return _matrix->number_of_cols();
1794 }
1795
1796 scalar_type plus_no_checks_impl(scalar_type x,
1797 scalar_type y) const noexcept {
1798 return _matrix->plus_no_checks_impl(x, y);
1799 }
1800
1801 scalar_type product_no_checks_impl(scalar_type x,
1802 scalar_type y) const noexcept {
1803 return _matrix->product_no_checks_impl(x, y);
1804 }
1805
1806 DynamicMatrix_ const* _matrix;
1807 };
1808
1810 // StaticMatrix with compile time semiring arithmetic
1812
1846 template <typename PlusOp,
1847 typename ProdOp,
1848 typename ZeroOp,
1849 typename OneOp,
1850 size_t R,
1851 size_t C,
1852 typename Scalar>
1854 : public detail::
1855 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
1856 public detail::MatrixCommon<
1857 std::array<Scalar, R * C>,
1858 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>,
1859 StaticRowView<PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar>> {
1861 // StaticMatrix - Aliases - private
1863
1864 using MatrixCommon = ::libsemigroups::detail::MatrixCommon<
1868 friend MatrixCommon;
1869
1870 public:
1872 // StaticMatrix - Aliases - public
1874
1876 using scalar_type = typename MatrixCommon::scalar_type;
1877
1879 using scalar_reference = typename MatrixCommon::scalar_reference;
1880
1882 // clang-format off
1883 // NOLINTNEXTLINE(whitespace/line_length)
1884 using scalar_const_reference = typename MatrixCommon::scalar_const_reference;
1885 // clang-format on
1886
1889
1892
1894 using Plus = PlusOp;
1895
1897 using Prod = ProdOp;
1898
1900 using Zero = ZeroOp;
1901
1903 using One = OneOp;
1904
1906 using iterator = typename MatrixCommon::iterator;
1907
1909 using const_iterator = typename MatrixCommon::const_iterator;
1910
1911 static constexpr size_t nr_rows = R;
1912 static constexpr size_t nr_cols = C;
1913
1915 // StaticMatrix - Constructors + destructor - public
1917
1935 : MatrixCommon(c) {
1936 static_assert(R == 1,
1937 "cannot construct Matrix from the given initializer list, "
1938 "incompatible dimensions");
1939 LIBSEMIGROUPS_ASSERT(c.size() == C);
1940 }
1941
1962 : MatrixCommon(m) {}
1963
1977 : MatrixCommon(m) {}
1978
1996 explicit StaticMatrix(RowView const& rv) : MatrixCommon(rv) {
1997 static_assert(
1998 R == 1,
1999 "cannot construct Matrix with more than one row from RowView!");
2000 }
2001
2005 StaticMatrix() = default;
2006
2010 StaticMatrix(StaticMatrix const&) = default;
2011
2016
2021
2026
2027#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2028 // For uniformity of interface, the args do nothing
2029 StaticMatrix(size_t r, size_t c) : StaticMatrix() {
2030 (void) r;
2031 (void) c;
2032 LIBSEMIGROUPS_ASSERT(r == number_of_rows());
2033 LIBSEMIGROUPS_ASSERT(c == number_of_cols());
2034 }
2035
2036 // For uniformity of interface, the first arg does nothing
2037 StaticMatrix(void const* ptr, std::initializer_list<scalar_type> const& c)
2038 : StaticMatrix(c) {
2039 (void) ptr;
2040 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2041 }
2042
2043 // For uniformity of interface, the first arg does nothing
2045 void const* ptr,
2047 : StaticMatrix(m) {
2048 (void) ptr;
2049 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2050 }
2051
2052 // For uniformity of interface, the first arg does nothing
2053 explicit StaticMatrix(void const* ptr, RowView const& rv)
2054 : StaticMatrix(rv) {
2055 (void) ptr;
2056 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2057 }
2058
2059 // For uniformity of interface, no arg used for anything
2060 StaticMatrix(void const* ptr, size_t r, size_t c) : StaticMatrix(r, c) {
2061 (void) ptr;
2062 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2063 }
2064#endif
2065
2066 ~StaticMatrix() = default;
2067
2068#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2069 static StaticMatrix one(size_t n) {
2070 // If specified the value of n must equal R or otherwise weirdness will
2071 // ensue...
2072 LIBSEMIGROUPS_ASSERT(n == 0 || n == R);
2073 (void) n;
2074#if defined(__APPLE__) && defined(__clang__) \
2075 && (__clang_major__ == 13 || __clang_major__ == 14)
2076 // With Apple clang version 13.1.6 (clang-1316.0.21.2.5) something goes
2077 // wrong and the value R is optimized away somehow, meaning that the
2078 // values on the diagonal aren't actually set. This only occurs when
2079 // libsemigroups is compiled with -O2 or higher.
2080 size_t volatile const m = R;
2081#else
2082 size_t const m = R;
2083#endif
2084 StaticMatrix x(m, m);
2085 std::fill(x.begin(), x.end(), ZeroOp()());
2086 for (size_t r = 0; r < m; ++r) {
2087 x(r, r) = OneOp()();
2088 }
2089 return x;
2090 }
2091
2092 static StaticMatrix one(void const* ptr, size_t n = 0) {
2093 (void) ptr;
2094 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2095 LIBSEMIGROUPS_ASSERT(n == 0 || n == R);
2096 return one(n);
2097 }
2098#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2099
2101 // StaticMatrix - member function aliases - public
2103#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2122 scalar_reference operator()(size_t r, size_t c);
2123
2137 scalar_reference at(size_t r, size_t c);
2138
2157 scalar_const_reference operator()(size_t r, size_t c) const;
2158
2172 scalar_const_reference at(size_t r, size_t c) const;
2173
2190 iterator begin() noexcept;
2191
2207
2225 const_iterator cbegin() const noexcept;
2226
2246
2260 bool operator==(StaticMatrix const& that) const;
2261
2263 bool operator==(RowView const& that) const;
2264
2276 bool operator!=(StaticMatrix const& that) const;
2277
2279 bool operator!=(RowView const& that) const;
2280
2294 bool operator<(StaticMatrix const& that) const;
2295
2297 bool operator<(RowView const& that) const;
2298
2312 bool operator>(StaticMatrix const& that) const;
2313
2330
2342 size_t number_of_rows() const noexcept;
2343
2355 size_t number_of_cols() const noexcept;
2356
2374 StaticMatrix operator+(StaticMatrix const& that);
2375
2392 void operator+=(StaticMatrix const& that);
2393
2395 void operator+=(RowView const& that);
2396
2408 void operator+=(scalar_type a);
2409
2427 StaticMatrix operator*(StaticMatrix const& that);
2428
2440 void operator*=(scalar_type a);
2441
2459 StaticMatrix const& y);
2460
2476 RowView row_no_checks(size_t i) const;
2477
2488 RowView row(size_t i) const;
2489
2503 template <typename T>
2504 void rows(T& x) const;
2505
2518 void swap(StaticMatrix& that) noexcept;
2519
2533
2549
2561 static StaticMatrix one() const;
2562
2576 size_t hash_value() const;
2577
2592 template <typename U>
2593 bool operator<=(U const& that) const;
2594
2609 template <typename U>
2610 bool operator>=(U const& that) const;
2611
2625
2640
2651 scalar_type scalar_zero() const noexcept;
2652
2663 scalar_type scalar_one() const noexcept;
2664
2676 semiring_type const* semiring() const noexcept;
2677
2678#else
2679 using MatrixCommon::at;
2680 using MatrixCommon::begin;
2681 using MatrixCommon::cbegin;
2682 using MatrixCommon::cend;
2683 using MatrixCommon::coords;
2684 using MatrixCommon::end;
2685 using MatrixCommon::hash_value;
2686 using MatrixCommon::number_of_cols;
2687 using MatrixCommon::number_of_rows;
2688 using MatrixCommon::one;
2689 using MatrixCommon::operator!=;
2690 using MatrixCommon::operator();
2691 using MatrixCommon::operator*;
2692 using MatrixCommon::operator*=;
2693 using MatrixCommon::operator+;
2694 using MatrixCommon::operator+=;
2695 using MatrixCommon::operator<; // NOLINT(whitespace/operators)
2696 using MatrixCommon::operator<=;
2697 using MatrixCommon::operator==;
2698 using MatrixCommon::operator>; // NOLINT(whitespace/operators)
2699 using MatrixCommon::operator>=;
2700 using MatrixCommon::product_inplace_no_checks;
2701 using MatrixCommon::row;
2702 using MatrixCommon::row_no_checks;
2703 using MatrixCommon::rows;
2704 using MatrixCommon::scalar_one;
2705 using MatrixCommon::scalar_zero;
2706 using MatrixCommon::semiring;
2707 using MatrixCommon::swap;
2708 using MatrixCommon::transpose;
2709 using MatrixCommon::transpose_no_checks;
2710#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2711
2712 private:
2714 // StaticMatrix - implementation of MatrixCommon requirements - private
2716
2717 static constexpr size_t number_of_rows_impl() noexcept {
2718 return R;
2719 }
2720 static constexpr size_t number_of_cols_impl() noexcept {
2721 return C;
2722 }
2723 };
2724
2726 // DynamicMatrix with compile time semiring arithmetic
2728
2762 template <typename PlusOp,
2763 typename ProdOp,
2764 typename ZeroOp,
2765 typename OneOp,
2766 typename Scalar>
2767 class DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>
2768 : public detail::MatrixDynamicDim<Scalar>,
2769 public detail::MatrixCommon<
2770 std::vector<Scalar>,
2771 DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
2772 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>,
2773 public detail::
2774 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
2775 using MatrixDynamicDim = ::libsemigroups::detail::MatrixDynamicDim<Scalar>;
2776 using MatrixCommon = ::libsemigroups::detail::MatrixCommon<
2779 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>;
2780 friend MatrixCommon;
2781
2782 public:
2784 using scalar_type = typename MatrixCommon::scalar_type;
2785
2787 using scalar_reference = typename MatrixCommon::scalar_reference;
2788
2790 // clang-format off
2791 // NOLINTNEXTLINE(whitespace/line_length)
2792 using scalar_const_reference = typename MatrixCommon::scalar_const_reference;
2793 // clang-format on
2794
2797
2799 using RowView = DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
2800
2802 using Plus = PlusOp;
2803
2805 using Prod = ProdOp;
2806
2808 using Zero = ZeroOp;
2809
2811 using One = OneOp;
2812
2818 using semiring_type = void;
2819
2823 DynamicMatrix() = default;
2824
2828 DynamicMatrix(DynamicMatrix const&) = default;
2829
2834
2839
2844
2862 DynamicMatrix(size_t r, size_t c) : MatrixDynamicDim(r, c), MatrixCommon() {
2863 resize(number_of_rows(), number_of_cols());
2864 }
2865
2885 : MatrixDynamicDim(1, c.size()), MatrixCommon(c) {}
2886
2908 : MatrixDynamicDim(m.size(), std::empty(m) ? 0 : m.begin()->size()),
2909 MatrixCommon(m) {}
2910
2926 : MatrixDynamicDim(m.size(), std::empty(m) ? 0 : m.begin()->size()),
2927 MatrixCommon(m) {}
2928
2940 explicit DynamicMatrix(RowView const& rv)
2941 : MatrixDynamicDim(1, rv.size()), MatrixCommon(rv) {}
2942
2943#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2944 // For uniformity of interface, the first arg does nothing
2945 DynamicMatrix(void const* ptr, size_t r, size_t c) : DynamicMatrix(r, c) {
2946 (void) ptr;
2947 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2948 }
2949
2950 // For uniformity of interface, the first arg does nothing
2951 DynamicMatrix(void const* ptr, std::initializer_list<scalar_type> const& c)
2952 : DynamicMatrix(c) {
2953 (void) ptr;
2954 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2955 }
2956
2957 // For uniformity of interface, the first arg does nothing
2958 DynamicMatrix(
2959 void const* ptr,
2960 std::initializer_list<std::initializer_list<scalar_type>> const& m)
2961 : DynamicMatrix(m) {
2962 (void) ptr;
2963 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2964 }
2965
2966 static DynamicMatrix one(void const* ptr, size_t n) {
2967 (void) ptr;
2968 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2969 return one(n);
2970 }
2971#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2972
2973 ~DynamicMatrix() = default;
2974
2987 static DynamicMatrix one(size_t n) {
2988 DynamicMatrix x(n, n);
2989 std::fill(x.begin(), x.end(), ZeroOp()());
2990 for (size_t r = 0; r < n; ++r) {
2991 x(r, r) = OneOp()();
2992 }
2993 return x;
2994 }
2995
2996#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2998 scalar_reference at(size_t r, size_t c);
2999
3001 scalar_reference at(size_t r, size_t c) const;
3002
3004 iterator begin() noexcept;
3005
3007 const_iterator cbegin() noexcept;
3008
3010 const_iterator cend() noexcept;
3011
3013 std::pair<scalar_type, scalar_type> coords(const_iterator it) const;
3014
3016 iterator end() noexcept;
3017
3019 size_t hash_value() const;
3020
3022 size_t number_of_cols() const noexcept;
3023
3025 size_t number_of_rows() const noexcept;
3026
3028 bool operator!=(DynamicMatrix const& that) const;
3029
3031 bool operator!=(RowView const& that) const;
3032
3034 scalar_reference operator()(size_t r, size_t c);
3035
3037 scalar_const_reference operator()(size_t r, size_t c) const;
3050
3052 DynamicMatrix operator*(DynamicMatrix const& that);
3053
3055 void operator*=(scalar_type a);
3056
3058 DynamicMatrix operator+(DynamicMatrix const& that);
3059
3061 void operator+=(DynamicMatrix const& that);
3062
3064 void operator+=(RowView const& that);
3065
3077 void operator+=(scalar_type a);
3078
3080 bool operator<(DynamicMatrix const& that) const;
3081
3083 bool operator<(RowView const& that) const;
3084
3086 template <typename T>
3087 bool operator<=(T const& that) const;
3088
3090 bool operator==(DynamicMatrix const& that) const;
3091
3093 bool operator==(RowView const& that) const;
3094
3096 bool operator>(DynamicMatrix const& that) const;
3097
3099 template <typename T>
3100 bool operator>=(T const& that) const;
3101
3104 DynamicMatrix const& y);
3105
3107 RowView row(size_t i) const;
3108
3110 RowView row_no_checks(size_t i) const;
3111
3113 template <typename T>
3114 void rows(T& x) const;
3115
3117 scalar_type scalar_one() const noexcept;
3118
3120 scalar_type scalar_zero() const noexcept;
3121
3123 semiring_type const* semiring() const noexcept;
3124
3127
3130#else
3131 using MatrixCommon::at;
3132 using MatrixCommon::begin;
3133 using MatrixCommon::cbegin;
3134 using MatrixCommon::cend;
3135 using MatrixCommon::coords;
3136 using MatrixCommon::end;
3137 using MatrixCommon::hash_value;
3138 using MatrixCommon::number_of_cols;
3139 using MatrixCommon::number_of_rows;
3140 using MatrixCommon::one;
3141 using MatrixCommon::operator!=;
3142 using MatrixCommon::operator();
3143 using MatrixCommon::operator*;
3144 using MatrixCommon::operator*=;
3145 using MatrixCommon::operator+;
3146 using MatrixCommon::operator+=;
3147 using MatrixCommon::operator<; // NOLINT(whitespace/operators)
3148 using MatrixCommon::operator<=;
3149 using MatrixCommon::operator==;
3150 using MatrixCommon::operator>; // NOLINT(whitespace/operators)
3151 using MatrixCommon::operator>=;
3152 using MatrixCommon::product_inplace_no_checks;
3153 using MatrixCommon::row;
3154 using MatrixCommon::row_no_checks;
3155 using MatrixCommon::rows;
3156 using MatrixCommon::scalar_one;
3157 using MatrixCommon::scalar_zero;
3158 using MatrixCommon::semiring;
3159 // using MatrixCommon::swap; // Don't want this use the one below.
3160 using MatrixCommon::transpose;
3161 using MatrixCommon::transpose_no_checks;
3162#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3163
3165 void swap(DynamicMatrix& that) noexcept {
3166 static_cast<MatrixDynamicDim&>(*this).swap(
3167 static_cast<MatrixDynamicDim&>(that));
3168 static_cast<MatrixCommon&>(*this).swap(static_cast<MatrixCommon&>(that));
3169 }
3170
3171 private:
3172 using MatrixCommon::resize;
3173 };
3174
3176 // DynamicMatrix with runtime semiring arithmetic
3178
3213 template <typename Semiring, typename Scalar>
3214 class DynamicMatrix<Semiring, Scalar>
3215 : public detail::MatrixDynamicDim<Scalar>,
3216 public detail::MatrixCommon<std::vector<Scalar>,
3217 DynamicMatrix<Semiring, Scalar>,
3218 DynamicRowView<Semiring, Scalar>,
3219 Semiring> {
3220 using MatrixCommon = detail::MatrixCommon<std::vector<Scalar>,
3222 DynamicRowView<Semiring, Scalar>,
3223 Semiring>;
3224 friend MatrixCommon;
3225 using MatrixDynamicDim = ::libsemigroups::detail::MatrixDynamicDim<Scalar>;
3226
3227 public:
3229 using scalar_type = typename MatrixCommon::scalar_type;
3230
3232 using scalar_reference = typename MatrixCommon::scalar_reference;
3233
3235 // clang-format off
3236 // NOLINTNEXTLINE(whitespace/line_length)
3237 using scalar_const_reference = typename MatrixCommon::scalar_const_reference;
3238 // clang-format on
3239
3242
3244 using RowView = DynamicRowView<Semiring, Scalar>;
3245
3246 friend RowView;
3247
3249 using semiring_type = Semiring;
3250
3256 DynamicMatrix() = delete;
3257
3259 DynamicMatrix(DynamicMatrix const&) = default;
3260
3263
3266
3269
3284 DynamicMatrix(Semiring const* sr, size_t r, size_t c)
3285 : MatrixDynamicDim(r, c), MatrixCommon(), _semiring(sr) {
3286 resize(number_of_rows(), number_of_cols());
3287 }
3288
3305 Semiring const* sr,
3307 : MatrixDynamicDim(rws.size(),
3308 std::empty(rws) ? 0 : rws.begin()->size()),
3309 MatrixCommon(rws),
3310 _semiring(sr) {}
3311
3327 explicit DynamicMatrix(Semiring const* sr,
3329 : MatrixDynamicDim(rws.size(), (rws.empty() ? 0 : rws.begin()->size())),
3330 MatrixCommon(rws),
3331 _semiring(sr) {}
3332
3346 explicit DynamicMatrix(Semiring const* sr,
3348 : MatrixDynamicDim(1, rw.size()), MatrixCommon(rw), _semiring(sr) {}
3349
3361 explicit DynamicMatrix(RowView const& rv)
3362 : MatrixDynamicDim(1, rv.size()),
3363 MatrixCommon(rv),
3364 _semiring(rv._matrix->semiring()) {}
3365
3380 // No static DynamicMatrix::one(size_t n) because we need a semiring!
3381 static DynamicMatrix one(Semiring const* semiring, size_t n) {
3382 DynamicMatrix x(semiring, n, n);
3383 std::fill(x.begin(), x.end(), x.scalar_zero());
3384 for (size_t r = 0; r < n; ++r) {
3385 x(r, r) = x.scalar_one();
3386 }
3387 return x;
3388 }
3389
3390 ~DynamicMatrix() = default;
3391
3392#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3394 scalar_reference at(size_t r, size_t c);
3395
3397 scalar_reference at(size_t r, size_t c) const;
3398
3400 iterator begin() noexcept;
3401
3403 const_iterator cbegin() noexcept;
3404
3406 const_iterator cend() noexcept;
3407
3409 std::pair<scalar_type, scalar_type> coords(const_iterator it) const;
3410
3412 iterator end() noexcept;
3413
3415 size_t hash_value() const;
3416
3418 size_t number_of_cols() const noexcept;
3419
3421 size_t number_of_rows() const noexcept;
3422
3424 bool operator!=(DynamicMatrix const& that) const;
3425
3427 bool operator!=(RowView const& that) const;
3428
3430 scalar_reference operator()(size_t r, size_t c);
3431
3433 scalar_const_reference operator()(size_t r, size_t c) const;
3446
3448 DynamicMatrix operator*(DynamicMatrix const& that);
3449
3451 void operator*=(scalar_type a);
3452
3454 DynamicMatrix operator+(DynamicMatrix const& that);
3455
3457 void operator+=(DynamicMatrix const& that);
3458
3460 void operator+=(RowView const& that);
3461
3473 void operator+=(scalar_type a);
3474
3476 bool operator<(DynamicMatrix const& that) const;
3477
3479 bool operator<(RowView const& that) const;
3480
3482 template <typename T>
3483 bool operator<=(T const& that) const;
3484
3486 bool operator==(DynamicMatrix const& that) const;
3487
3489 bool operator==(RowView const& that) const;
3490
3492 bool operator>(DynamicMatrix const& that) const;
3493
3495 template <typename T>
3496 bool operator>=(T const& that) const;
3497
3500 DynamicMatrix const& y);
3501
3503 RowView row(size_t i) const;
3504
3506 RowView row_no_checks(size_t i) const;
3507
3509 template <typename T>
3510 void rows(T& x) const;
3511
3513 scalar_type scalar_one() const noexcept;
3514
3516 scalar_type scalar_zero() const noexcept;
3517
3519 semiring_type const* semiring() const noexcept;
3520
3523
3526#else
3527 using MatrixCommon::at;
3528 using MatrixCommon::begin;
3529 using MatrixCommon::cbegin;
3530 using MatrixCommon::cend;
3531 using MatrixCommon::coords;
3532 using MatrixCommon::end;
3533 using MatrixCommon::hash_value;
3534 using MatrixCommon::number_of_cols;
3535 using MatrixCommon::number_of_rows;
3536 using MatrixCommon::one;
3537 using MatrixCommon::operator!=;
3538 using MatrixCommon::operator();
3539 using MatrixCommon::operator*;
3540 using MatrixCommon::operator*=;
3541 using MatrixCommon::operator+;
3542 using MatrixCommon::operator+=;
3543 using MatrixCommon::operator<; // NOLINT(whitespace/operators)
3544 using MatrixCommon::operator<=;
3545 using MatrixCommon::operator==;
3546 using MatrixCommon::operator>; // NOLINT(whitespace/operators)
3547 using MatrixCommon::operator>=;
3548 using MatrixCommon::product_inplace_no_checks;
3549 using MatrixCommon::row;
3550 using MatrixCommon::row_no_checks;
3551 using MatrixCommon::rows;
3552 using MatrixCommon::scalar_one;
3553 using MatrixCommon::scalar_zero;
3554 using MatrixCommon::semiring;
3555 // using MatrixCommon::swap; // Don't want this use the one below.
3556 using MatrixCommon::transpose;
3557 using MatrixCommon::transpose_no_checks;
3558#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3559
3561 void swap(DynamicMatrix& that) noexcept {
3562 static_cast<MatrixDynamicDim&>(*this).swap(
3563 static_cast<MatrixDynamicDim&>(that));
3564 static_cast<MatrixCommon&>(*this).swap(static_cast<MatrixCommon&>(that));
3565 std::swap(_semiring, that._semiring);
3566 }
3567
3568 private:
3569 using MatrixCommon::resize;
3570
3571 scalar_type plus_no_checks_impl(scalar_type x,
3572 scalar_type y) const noexcept {
3573 return _semiring->plus_no_checks(x, y);
3574 }
3575
3576 scalar_type product_no_checks_impl(scalar_type x,
3577 scalar_type y) const noexcept {
3578 return _semiring->product_no_checks(x, y);
3579 }
3580
3581 scalar_type one_impl() const noexcept {
3582 return _semiring->scalar_one();
3583 }
3584
3585 scalar_type zero_impl() const noexcept {
3586 return _semiring->scalar_zero();
3587 }
3588
3589 Semiring const* semiring_impl() const noexcept {
3590 return _semiring;
3591 }
3592
3593 Semiring const* _semiring;
3594 };
3595
3597 // Helper structs to check if matrix is static, or has a pointer to a
3598 // semiring
3600
3601 namespace detail {
3602 template <typename T>
3603 struct IsStaticMatrixHelper : std::false_type {};
3604
3605 template <typename PlusOp,
3606 typename ProdOp,
3607 typename ZeroOp,
3608 typename OneOp,
3609 size_t R,
3610 size_t C,
3611 typename Scalar>
3612 struct IsStaticMatrixHelper<
3613 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>>
3614 : std::true_type {};
3615
3616 template <typename T>
3617 struct IsMatWithSemiringHelper : std::false_type {};
3618
3619 template <typename Semiring, typename Scalar>
3620 struct IsMatWithSemiringHelper<DynamicMatrix<Semiring, Scalar>>
3621 : std::true_type {};
3622
3623 template <typename S, typename T = void>
3624 struct IsTruncMatHelper : std::false_type {};
3625
3626 } // namespace detail
3627
3638 template <typename T>
3639 constexpr bool IsStaticMatrix = detail::IsStaticMatrixHelper<T>::value;
3640
3651 template <typename T>
3653
3664 template <typename T>
3665 static constexpr bool IsMatWithSemiring
3666 = detail::IsMatWithSemiringHelper<T>::value;
3667
3668 namespace detail {
3669
3670 template <typename T>
3671 static constexpr bool IsTruncMat = IsTruncMatHelper<T>::value;
3672
3673 template <typename Mat>
3674 void throw_if_semiring_nullptr(Mat const& m) {
3675 if (IsMatWithSemiring<Mat> && m.semiring() == nullptr) {
3677 "the matrix's pointer to a semiring is nullptr!")
3678 }
3679 }
3680
3681 template <typename Mat, typename Container>
3682 auto throw_if_bad_dim(Container const& m)
3683 -> std::enable_if_t<IsStaticMatrix<Mat>> {
3684 // Only call this if you've already called throw_if_any_row_wrong_size
3685 uint64_t const R = m.size();
3686 uint64_t const C = std::empty(m) ? 0 : m.begin()->size();
3687 if (R != Mat::nr_rows || C != Mat::nr_cols) {
3689 "invalid argument, cannot initialize an {}x{} matrix with compile "
3690 "time dimension, with an {}x{} container",
3691 Mat::nr_rows,
3692 Mat::nr_cols,
3693 R,
3694 C);
3695 }
3696 }
3697
3698 template <typename Mat, typename Container>
3699 auto throw_if_bad_dim(Container const&)
3700 -> std::enable_if_t<IsDynamicMatrix<Mat>> {}
3701 } // namespace detail
3702
3711 namespace matrix {
3712
3726 template <typename Mat>
3727 constexpr auto threshold(Mat const&) noexcept
3728 -> std::enable_if_t<!detail::IsTruncMat<Mat>,
3729 typename Mat::scalar_type> {
3730 return UNDEFINED;
3731 }
3732
3746 template <typename Mat>
3747 constexpr auto threshold(Mat const&) noexcept
3748 -> std::enable_if_t<detail::IsTruncMat<Mat> && !IsMatWithSemiring<Mat>,
3749 typename Mat::scalar_type> {
3750 return detail::IsTruncMatHelper<Mat>::threshold;
3751 }
3752
3768 template <typename Mat>
3769 auto threshold(Mat const& x) noexcept
3770 -> std::enable_if_t<detail::IsTruncMat<Mat> && IsMatWithSemiring<Mat>,
3771 typename Mat::scalar_type> {
3772 return x.semiring()->threshold();
3773 }
3774 } // namespace matrix
3775
3777 // Boolean matrices - compile time semiring arithmetic
3779
3813
3836 constexpr bool operator()(bool x, bool y) const noexcept {
3837 return x || y;
3838 }
3839 };
3840
3863 constexpr bool operator()(bool x, bool y) const noexcept {
3864 return x & y;
3865 }
3866 };
3867
3877 struct BooleanOne {
3888 constexpr bool operator()() const noexcept {
3889 return true;
3890 }
3891 };
3892
3913 constexpr bool operator()() const noexcept {
3914 return false;
3915 }
3916 };
3917
3926 // The use of `int` rather than `bool` as the scalar type for dynamic
3927 // boolean matrices is intentional, because the bit iterators implemented in
3928 // std::vector<bool> entail a significant performance penalty.
3930 = DynamicMatrix<BooleanPlus, BooleanProd, BooleanZero, BooleanOne, int>;
3931
3943 template <size_t R, size_t C>
3947 BooleanOne,
3948 R,
3949 C,
3950 int>;
3951
3965 // FLS + JDM considered adding BMat8 and decided it wasn't a good idea.
3966 template <size_t R = 0, size_t C = R>
3967 using BMat
3968 = std::conditional_t<R == 0 || C == 0, DynamicBMat, StaticBMat<R, C>>;
3969
3970 namespace detail {
3971 template <typename T>
3972 struct IsBMatHelper : std::false_type {};
3973
3974 template <size_t R, size_t C>
3975 struct IsBMatHelper<StaticBMat<R, C>> : std::true_type {};
3976
3977 template <>
3978 struct IsBMatHelper<DynamicBMat> : std::true_type {};
3979
3980 template <typename T>
3981 struct BitSetCapacity {
3982 static constexpr size_t value = BitSet<1>::max_size();
3983 };
3984
3985 template <size_t R, size_t C>
3986 struct BitSetCapacity<StaticBMat<R, C>> {
3987 static_assert(R == C, "the number of rows and columns must be equal");
3988 static constexpr size_t value = R;
3989 };
3990 } // namespace detail
3991
4002 template <typename T>
4003 static constexpr bool IsBMat = detail::IsBMatHelper<T>::value;
4004
4005 namespace detail {
4006 // This function is required for exceptions and to_human_readable_repr, so
4007 // that if we encounter an entry of a matrix (Scalar type), then it can be
4008 // printed correctly. If we just did fmt::format("{}", val) and val ==
4009 // POSITIVE_INFINITY, but the type of val is, say, size_t, then this
4010 // wouldn't use the formatter for PositiveInfinity.
4011 //
4012 // Also in fmt v11.1.4 the custom formatter for POSITIVE_INFINITY and
4013 // NEGATIVE_INFINITY stopped working (and I wasn't able to figure out why)
4014 template <typename Scalar>
4015 std::string entry_repr(Scalar a) {
4016 if constexpr (std::is_same_v<Scalar, NegativeInfinity>
4017 || std::is_signed_v<Scalar>) {
4018 if (a == NEGATIVE_INFINITY) {
4019 return u8"-\u221E";
4020 }
4021 }
4022 if (a == POSITIVE_INFINITY) {
4023 return u8"+\u221E";
4024 }
4025 return fmt::format("{}", a);
4026 }
4027 } // namespace detail
4028
4029 namespace matrix {
4030
4046 //! but a matrix shouldn't contain values except \c 0 and \c 1.
4047 template <typename Mat>
4048 std::enable_if_t<IsBMat<Mat>> throw_if_bad_entry(Mat const& m) {
4049 using scalar_type = typename Mat::scalar_type;
4050 auto it = std::find_if_not(
4051 m.cbegin(), m.cend(), [](scalar_type x) { return x == 0 || x == 1; });
4052 if (it != m.cend()) {
4053 auto [r, c] = m.coords(it);
4055 "invalid entry, expected 0 or 1 but found {} in entry ({}, {})",
4056 detail::entry_repr(*it),
4057 r,
4058 c);
4059 }
4060 }
4061
4079 template <typename Mat>
4080 std::enable_if_t<IsBMat<Mat>>
4081 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4082 if (val != 0 && val != 1) {
4083 LIBSEMIGROUPS_EXCEPTION("invalid entry, expected 0 or 1 but found {}",
4084 detail::entry_repr(val));
4085 }
4086 }
4087 } // namespace matrix
4088
4090 // Integer matrices - compile time semiring arithmetic
4092
4120
4132 //! \tparam Scalar the type of the entries in the matrix.
4133 template <typename Scalar>
4134 struct IntegerPlus {
4145 //! \exceptions
4146 //! \noexcept
4147 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
4148 return x + y;
4149 }
4150 };
4151
4163 //! \tparam Scalar the type of the entries in the matrix.
4164 template <typename Scalar>
4165 struct IntegerProd {
4176 //! \exceptions
4177 //! \noexcept
4178 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
4179 return x * y;
4180 }
4181 };
4182
4191 //! the additive identity of the integer semiring.
4192 template <typename Scalar>
4193 struct IntegerZero {
4201 //! \exceptions
4202 //! \noexcept
4203 constexpr Scalar operator()() const noexcept {
4204 return 0;
4205 }
4206 };
4207
4216 //! the multiplicative identity of the integer semiring.
4217 template <typename Scalar>
4218 struct IntegerOne {
4226 //! \exceptions
4227 //! \noexcept
4228 constexpr Scalar operator()() const noexcept {
4229 return 1;
4230 }
4231 };
4232
4243 template <typename Scalar>
4244 using DynamicIntMat = DynamicMatrix<IntegerPlus<Scalar>,
4248 Scalar>;
4249
4266 template <size_t R, size_t C, typename Scalar>
4271 R,
4272 C,
4273 Scalar>;
4274
4291 template <size_t R = 0, size_t C = R, typename Scalar = int>
4292 using IntMat = std::conditional_t<R == 0 || C == 0,
4295 namespace detail {
4296 template <typename T>
4297 struct IsIntMatHelper : std::false_type {};
4298
4299 template <size_t R, size_t C, typename Scalar>
4300 struct IsIntMatHelper<StaticIntMat<R, C, Scalar>> : std::true_type {};
4301
4302 template <typename Scalar>
4303 struct IsIntMatHelper<DynamicIntMat<Scalar>> : std::true_type {};
4304 } // namespace detail
4305
4316 template <typename T>
4317 static constexpr bool IsIntMat = detail::IsIntMatHelper<T>::value;
4318
4319 namespace matrix {
4333 //! \param x the matrix to check.
4334 template <typename Mat>
4335 std::enable_if_t<IsIntMat<Mat>> throw_if_bad_entry(Mat const& x) {
4336 using scalar_type = typename Mat::scalar_type;
4337 auto it = std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4338 return val == POSITIVE_INFINITY || val == NEGATIVE_INFINITY;
4339 });
4340 if (it != x.cend()) {
4341 auto [r, c] = x.coords(it);
4343 "invalid entry, expected entries to be integers, "
4344 "but found {} in entry ({}, {})",
4345 detail::entry_repr(*it),
4346 r,
4347 c);
4348 }
4349 }
4350
4367 template <typename Mat>
4368 std::enable_if_t<IsIntMat<Mat>>
4369 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4370 if (val == POSITIVE_INFINITY || val == NEGATIVE_INFINITY) {
4372 "invalid entry, expected entries to be integers, "
4373 "but found {}",
4374 detail::entry_repr(val));
4375 }
4376 }
4377 } // namespace matrix
4378
4380 // Max-plus matrices
4410
4434 // Static arithmetic
4435 template <typename Scalar>
4436 struct MaxPlusPlus {
4437 static_assert(std::is_signed<Scalar>::value,
4438 "MaxPlus requires a signed integer type as parameter!");
4449 //! \exceptions
4450 //! \noexcept
4451 Scalar operator()(Scalar x, Scalar y) const noexcept {
4452 if (x == NEGATIVE_INFINITY) {
4453 return y;
4454 } else if (y == NEGATIVE_INFINITY) {
4455 return x;
4456 }
4457 return std::max(x, y);
4458 }
4459 };
4460
4481 //! integer type).
4482 template <typename Scalar>
4483 struct MaxPlusProd {
4484 static_assert(std::is_signed<Scalar>::value,
4485 "MaxPlus requires a signed integer type as parameter!");
4496 //! \exceptions
4497 //! \noexcept
4498 Scalar operator()(Scalar x, Scalar y) const noexcept {
4499 if (x == NEGATIVE_INFINITY || y == NEGATIVE_INFINITY) {
4500 return NEGATIVE_INFINITY;
4501 }
4502 return x + y;
4503 }
4504 };
4505
4518 //! integer type).
4519 template <typename Scalar>
4520 struct MaxPlusZero {
4521 static_assert(std::is_signed<Scalar>::value,
4522 "MaxPlus requires a signed integer type as parameter!");
4530 //! \exceptions
4531 //! \noexcept
4532 constexpr Scalar operator()() const noexcept {
4533 return NEGATIVE_INFINITY;
4534 }
4535 };
4536
4547 template <typename Scalar>
4548 using DynamicMaxPlusMat = DynamicMatrix<MaxPlusPlus<Scalar>,
4552 Scalar>;
4553
4566 template <size_t R, size_t C, typename Scalar>
4571 R,
4572 C,
4573 Scalar>;
4574
4590 template <size_t R = 0, size_t C = R, typename Scalar = int>
4591 using MaxPlusMat = std::conditional_t<R == 0 || C == 0,
4594
4595 namespace detail {
4596 template <typename T>
4597 struct IsMaxPlusMatHelper : std::false_type {};
4598
4599 template <size_t R, size_t C, typename Scalar>
4600 struct IsMaxPlusMatHelper<StaticMaxPlusMat<R, C, Scalar>> : std::true_type {
4601 };
4602
4603 template <typename Scalar>
4604 struct IsMaxPlusMatHelper<DynamicMaxPlusMat<Scalar>> : std::true_type {};
4605 } // namespace detail
4606
4617 template <typename T>
4618 static constexpr bool IsMaxPlusMat = detail::IsMaxPlusMatHelper<T>::value;
4619
4620 namespace matrix {
4635 //! \ref POSITIVE_INFINITY.
4636 template <typename Mat>
4637 auto throw_if_bad_entry(Mat const& x)
4638 -> std::enable_if_t<IsMaxPlusMat<Mat>> {
4639 using scalar_type = typename Mat::scalar_type;
4640 auto it = std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4641 return val == POSITIVE_INFINITY;
4642 });
4643 if (it != x.cend()) {
4644 auto [r, c] = x.coords(it);
4646 "invalid entry, expected entries to be integers or {} (= {}), "
4647 "but found {} (= {}) in entry ({}, {})",
4648 entry_repr(NEGATIVE_INFINITY),
4649 static_cast<scalar_type>(NEGATIVE_INFINITY),
4650 entry_repr(POSITIVE_INFINITY),
4651 static_cast<scalar_type>(POSITIVE_INFINITY),
4652 r,
4653 c);
4654 }
4655 }
4656
4672 template <typename Mat>
4673 std::enable_if_t<IsMaxPlusMat<Mat>>
4674 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4675 if (val == POSITIVE_INFINITY) {
4676 using scalar_type = typename Mat::scalar_type;
4677 LIBSEMIGROUPS_EXCEPTION("invalid entry, expected entries to be "
4678 "integers or {} (= {}) but found {} (= {})",
4679 entry_repr(NEGATIVE_INFINITY),
4680 static_cast<scalar_type>(NEGATIVE_INFINITY),
4681 entry_repr(POSITIVE_INFINITY),
4682 static_cast<scalar_type>(POSITIVE_INFINITY));
4683 }
4684 }
4685 } // namespace matrix
4686
4688 // Min-plus matrices
4690
4719
4742 // Static arithmetic
4743 template <typename Scalar>
4744 struct MinPlusPlus {
4745 static_assert(std::is_signed<Scalar>::value,
4746 "MinPlus requires a signed integer type as parameter!");
4757 //! \exceptions
4758 //! \noexcept
4759 Scalar operator()(Scalar x, Scalar y) const noexcept {
4760 if (x == POSITIVE_INFINITY) {
4761 return y;
4762 } else if (y == POSITIVE_INFINITY) {
4763 return x;
4764 }
4765 return std::min(x, y);
4766 }
4767 };
4768
4789 //! integer type).
4790 template <typename Scalar>
4791 struct MinPlusProd {
4792 static_assert(std::is_signed<Scalar>::value,
4793 "MinPlus requires a signed integer type as parameter!");
4804 //! \exceptions
4805 //! \noexcept
4806 Scalar operator()(Scalar x, Scalar y) const noexcept {
4807 if (x == POSITIVE_INFINITY || y == POSITIVE_INFINITY) {
4808 return POSITIVE_INFINITY;
4809 }
4810 return x + y;
4811 }
4812 };
4813
4826 //! integer type).
4827 template <typename Scalar>
4828 struct MinPlusZero {
4829 static_assert(std::is_signed<Scalar>::value,
4830 "MinPlus requires a signed integer type as parameter!");
4838 //! \exceptions
4839 //! \noexcept
4840 constexpr Scalar operator()() const noexcept {
4841 return POSITIVE_INFINITY;
4842 }
4843 };
4844
4855 template <typename Scalar>
4856 using DynamicMinPlusMat = DynamicMatrix<MinPlusPlus<Scalar>,
4860 Scalar>;
4861
4874 template <size_t R, size_t C, typename Scalar>
4879 R,
4880 C,
4881 Scalar>;
4898 template <size_t R = 0, size_t C = R, typename Scalar = int>
4899 using MinPlusMat = std::conditional_t<R == 0 || C == 0,
4902
4903 namespace detail {
4904 template <typename T>
4905 struct IsMinPlusMatHelper : std::false_type {};
4906
4907 template <size_t R, size_t C, typename Scalar>
4908 struct IsMinPlusMatHelper<StaticMinPlusMat<R, C, Scalar>> : std::true_type {
4909 };
4910
4911 template <typename Scalar>
4912 struct IsMinPlusMatHelper<DynamicMinPlusMat<Scalar>> : std::true_type {};
4913 } // namespace detail
4914
4925 template <typename T>
4926 static constexpr bool IsMinPlusMat = detail::IsMinPlusMatHelper<T>::value;
4927
4928 namespace matrix {
4943 //! \ref NEGATIVE_INFINITY.
4944 template <typename Mat>
4945 std::enable_if_t<IsMinPlusMat<Mat>> throw_if_bad_entry(Mat const& x) {
4946 using scalar_type = typename Mat::scalar_type;
4947 auto it = std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4948 return val == NEGATIVE_INFINITY;
4949 });
4950 if (it != x.cend()) {
4951 auto [r, c] = x.coords(it);
4953 "invalid entry, expected entries to be integers or {} (= {}), "
4954 "but found {} (= {}) in entry ({}, {})",
4955 entry_repr(POSITIVE_INFINITY),
4956 static_cast<scalar_type>(POSITIVE_INFINITY),
4957 entry_repr(NEGATIVE_INFINITY),
4958 static_cast<scalar_type>(NEGATIVE_INFINITY),
4959 r,
4960 c);
4961 }
4962 }
4963
4979 template <typename Mat>
4980 std::enable_if_t<IsMinPlusMat<Mat>>
4981 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4982 if (val == NEGATIVE_INFINITY) {
4983 using scalar_type = typename Mat::scalar_type;
4984 LIBSEMIGROUPS_EXCEPTION("invalid entry, expected entries to be "
4985 "integers or {} (= {}) but found {} (= {})",
4986 entry_repr(POSITIVE_INFINITY),
4987 static_cast<scalar_type>(POSITIVE_INFINITY),
4988 entry_repr(NEGATIVE_INFINITY),
4989 static_cast<scalar_type>(NEGATIVE_INFINITY));
4990 }
4991 }
4992 } // namespace matrix
4993
4995 // Max-plus matrices with threshold
4997
5043
5068 //! integer type).
5069 template <size_t T, typename Scalar>
5070 struct MaxPlusTruncProd {
5071 static_assert(std::is_signed<Scalar>::value,
5072 "MaxPlus requires a signed integer type as parameter!");
5083 //! \exceptions
5084 //! \noexcept
5085 Scalar operator()(Scalar x, Scalar y) const noexcept {
5086 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= static_cast<Scalar>(T))
5087 || x == NEGATIVE_INFINITY);
5088 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= static_cast<Scalar>(T))
5089 || y == NEGATIVE_INFINITY);
5090 if (x == NEGATIVE_INFINITY || y == NEGATIVE_INFINITY) {
5091 return NEGATIVE_INFINITY;
5092 }
5093 return std::min(x + y, static_cast<Scalar>(T));
5094 }
5095 };
5096
5110 //! signed integer type (defaults to \c int).
5111 template <typename Scalar = int>
5112 class MaxPlusTruncSemiring {
5113 static_assert(std::is_signed<Scalar>::value,
5114 "MaxPlus requires a signed integer type as parameter!");
5115
5116 public:
5120 MaxPlusTruncSemiring() = delete;
5121
5125 MaxPlusTruncSemiring(MaxPlusTruncSemiring const&) noexcept = default;
5126
5130 MaxPlusTruncSemiring(MaxPlusTruncSemiring&&) noexcept = default;
5131
5135 MaxPlusTruncSemiring& operator=(MaxPlusTruncSemiring const&) noexcept
5136 = default;
5137
5141 MaxPlusTruncSemiring& operator=(MaxPlusTruncSemiring&&) noexcept = default;
5142
5143 ~MaxPlusTruncSemiring() = default;
5144
5153 //! \complexity
5154 //! Constant.
5155 explicit MaxPlusTruncSemiring(Scalar threshold) : _threshold(threshold) {
5156 if (threshold < 0) {
5157 LIBSEMIGROUPS_EXCEPTION("expected non-negative value, found {}",
5158 threshold);
5159 }
5160 }
5161
5170 //! \exceptions
5171 //! \noexcept
5172 static constexpr Scalar scalar_one() noexcept {
5173 return 0;
5174 }
5175
5184 //! \exceptions
5185 //! \noexcept
5186 static constexpr Scalar scalar_zero() noexcept {
5187 return NEGATIVE_INFINITY;
5188 }
5189
5212 //! \complexity
5213 //! Constant.
5214 Scalar product_no_checks(Scalar x, Scalar y) const noexcept {
5215 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5216 || x == NEGATIVE_INFINITY);
5217 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5218 || y == NEGATIVE_INFINITY);
5219 if (x == NEGATIVE_INFINITY || y == NEGATIVE_INFINITY) {
5220 return NEGATIVE_INFINITY;
5221 }
5222 return std::min(x + y, _threshold);
5223 }
5224
5247 //! \complexity
5248 //! Constant.
5249 Scalar plus_no_checks(Scalar x, Scalar y) const noexcept {
5250 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5251 || x == NEGATIVE_INFINITY);
5252 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5253 || y == NEGATIVE_INFINITY);
5254 if (x == NEGATIVE_INFINITY) {
5255 return y;
5256 } else if (y == NEGATIVE_INFINITY) {
5257 return x;
5258 }
5259 return std::max(x, y);
5260 }
5261
5272 //! \complexity
5273 //! Constant.
5274 Scalar threshold() const noexcept {
5275 return _threshold;
5276 }
5277
5278 public:
5279 Scalar const _threshold;
5280 };
5281
5294 template <size_t T, typename Scalar>
5295 using DynamicMaxPlusTruncMat = DynamicMatrix<MaxPlusPlus<Scalar>,
5299 Scalar>;
5300
5314 template <size_t T, size_t R, size_t C, typename Scalar>
5319 R,
5320 C,
5321 Scalar>;
5340 template <size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
5341 using MaxPlusTruncMat = std::conditional_t<
5342 R == 0 || C == 0,
5343 std::conditional_t<T == 0,
5344 DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>,
5347
5348 namespace detail {
5349 template <typename T>
5350 struct IsMaxPlusTruncMatHelper : std::false_type {};
5351
5352 template <size_t T, size_t R, size_t C, typename Scalar>
5353 struct IsMaxPlusTruncMatHelper<StaticMaxPlusTruncMat<T, R, C, Scalar>>
5354 : std::true_type {
5355 static constexpr Scalar threshold = T;
5356 };
5357
5358 template <size_t T, typename Scalar>
5359 struct IsMaxPlusTruncMatHelper<DynamicMaxPlusTruncMat<T, Scalar>>
5360 : std::true_type {
5361 static constexpr Scalar threshold = T;
5362 };
5363
5364 template <typename Scalar>
5365 struct IsMaxPlusTruncMatHelper<
5366 DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>> : std::true_type {
5367 static constexpr Scalar threshold = UNDEFINED;
5368 };
5369 } // namespace detail
5370
5382 template <typename T>
5383 static constexpr bool IsMaxPlusTruncMat
5384 = detail::IsMaxPlusTruncMatHelper<T>::value;
5385
5386 namespace detail {
5387 template <typename T>
5388 struct IsTruncMatHelper<T, std::enable_if_t<IsMaxPlusTruncMat<T>>>
5389 : std::true_type {
5390 static constexpr typename T::scalar_type threshold
5391 = IsMaxPlusTruncMatHelper<T>::threshold;
5392 };
5393 } // namespace detail
5394
5395 namespace matrix {
5413 //! (only applies to matrices with run time arithmetic).
5414 template <typename Mat>
5415 std::enable_if_t<IsMaxPlusTruncMat<Mat>> throw_if_bad_entry(Mat const& m) {
5416 // TODO(1) to tpp
5417 detail::throw_if_semiring_nullptr(m);
5418
5419 using scalar_type = typename Mat::scalar_type;
5420 scalar_type const t = matrix::threshold(m);
5421 auto it = std::find_if_not(m.cbegin(), m.cend(), [t](scalar_type x) {
5422 return x == NEGATIVE_INFINITY || (0 <= x && x <= t);
5423 });
5424 if (it != m.cend()) {
5425 auto [r, c] = m.coords(it);
5427 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5428 "but found {} in entry ({}, {})",
5429 t,
5430 entry_repr(NEGATIVE_INFINITY),
5431 static_cast<scalar_type>(NEGATIVE_INFINITY),
5432 detail::entry_repr(*it),
5433 r,
5434 c);
5435 }
5436 }
5437
5457 template <typename Mat>
5458 std::enable_if_t<IsMaxPlusTruncMat<Mat>>
5459 throw_if_bad_entry(Mat const& m, typename Mat::scalar_type val) {
5460 detail::throw_if_semiring_nullptr(m);
5461 using scalar_type = typename Mat::scalar_type;
5462 scalar_type const t = matrix::threshold(m);
5463 if (val == POSITIVE_INFINITY || 0 > val || val > t) {
5465 "invalid entry, expected values in {{0, 1, ..., {}, -{} (= {})}} "
5466 "but found {}",
5467 t,
5468 entry_repr(NEGATIVE_INFINITY),
5469 static_cast<scalar_type>(NEGATIVE_INFINITY),
5470 detail::entry_repr(val));
5471 }
5472 }
5473 } // namespace matrix
5474
5476 // Min-plus matrices with threshold
5478
5524
5548 //! \tparam Scalar the type of the values in the semiring.
5549 template <size_t T, typename Scalar>
5550 struct MinPlusTruncProd {
5561 //! \exceptions
5562 //! \noexcept
5563 Scalar operator()(Scalar x, Scalar y) const noexcept {
5564 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= static_cast<Scalar>(T))
5565 || x == POSITIVE_INFINITY);
5566 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= static_cast<Scalar>(T))
5567 || y == POSITIVE_INFINITY);
5568 if (x == POSITIVE_INFINITY || y == POSITIVE_INFINITY) {
5569 return POSITIVE_INFINITY;
5570 }
5571 return std::min(x + y, static_cast<Scalar>(T));
5572 }
5573 };
5574
5587 //! integral type.
5588 template <typename Scalar = int>
5589 class MinPlusTruncSemiring {
5590 static_assert(std::is_integral<Scalar>::value,
5591 "MinPlus requires an integral type as parameter!");
5592
5593 public:
5597 MinPlusTruncSemiring() = delete;
5598
5602 MinPlusTruncSemiring(MinPlusTruncSemiring const&) noexcept = default;
5603
5607 MinPlusTruncSemiring(MinPlusTruncSemiring&&) noexcept = default;
5608
5612 MinPlusTruncSemiring& operator=(MinPlusTruncSemiring const&) noexcept
5613 = default;
5614
5618 MinPlusTruncSemiring& operator=(MinPlusTruncSemiring&&) noexcept = default;
5619
5628 //! \complexity
5629 //! Constant.
5630 explicit MinPlusTruncSemiring(Scalar threshold) : _threshold(threshold) {
5632 LIBSEMIGROUPS_EXCEPTION("expected non-negative value, found {}",
5633 threshold);
5634 }
5635 }
5636
5645 //! \exceptions
5646 //! \noexcept
5647 static constexpr Scalar scalar_one() noexcept {
5648 return 0;
5649 }
5650
5660 //! \noexcept
5661 // TODO(1) These mem fns (one and zero) aren't needed?
5662 static constexpr Scalar scalar_zero() noexcept {
5663 return POSITIVE_INFINITY;
5664 }
5665
5688 //! \complexity
5689 //! Constant.
5690 Scalar product_no_checks(Scalar x, Scalar y) const noexcept {
5691 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5692 || x == POSITIVE_INFINITY);
5693 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5694 || y == POSITIVE_INFINITY);
5695 if (x == POSITIVE_INFINITY || y == POSITIVE_INFINITY) {
5696 return POSITIVE_INFINITY;
5697 }
5698 return std::min(x + y, _threshold);
5699 }
5700
5723 //! \complexity
5724 //! Constant.
5725 Scalar plus_no_checks(Scalar x, Scalar y) const noexcept {
5726 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5727 || x == POSITIVE_INFINITY);
5728 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5729 || y == POSITIVE_INFINITY);
5730 if (x == POSITIVE_INFINITY) {
5731 return y;
5732 } else if (y == POSITIVE_INFINITY) {
5733 return x;
5734 }
5735 return std::min(x, y);
5736 }
5737
5748 //! \complexity
5749 //! Constant.
5750 Scalar threshold() const noexcept {
5751 return _threshold;
5752 }
5753
5754 public:
5755 Scalar const _threshold;
5756 };
5757
5770 template <size_t T, typename Scalar>
5771 using DynamicMinPlusTruncMat = DynamicMatrix<MinPlusPlus<Scalar>,
5775 Scalar>;
5776
5790 template <size_t T, size_t R, size_t C, typename Scalar>
5795 R,
5796 C,
5797 Scalar>;
5798
5817 template <size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
5818 using MinPlusTruncMat = std::conditional_t<
5819 R == 0 || C == 0,
5820 std::conditional_t<T == 0,
5821 DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>,
5824
5825 namespace detail {
5826 template <typename T>
5827 struct IsMinPlusTruncMatHelper : std::false_type {};
5828
5829 template <size_t T, size_t R, size_t C, typename Scalar>
5830 struct IsMinPlusTruncMatHelper<StaticMinPlusTruncMat<T, R, C, Scalar>>
5831 : std::true_type {
5832 static constexpr Scalar threshold = T;
5833 };
5834
5835 template <size_t T, typename Scalar>
5836 struct IsMinPlusTruncMatHelper<DynamicMinPlusTruncMat<T, Scalar>>
5837 : std::true_type {
5838 static constexpr Scalar threshold = T;
5839 };
5840
5841 template <typename Scalar>
5842 struct IsMinPlusTruncMatHelper<
5843 DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>> : std::true_type {
5844 static constexpr Scalar threshold = UNDEFINED;
5845 };
5846 } // namespace detail
5847
5859 template <typename T>
5860 static constexpr bool IsMinPlusTruncMat
5861 = detail::IsMinPlusTruncMatHelper<T>::value;
5862
5863 namespace detail {
5864 template <typename T>
5865 struct IsTruncMatHelper<T, std::enable_if_t<IsMinPlusTruncMat<T>>>
5866 : std::true_type {
5867 static constexpr typename T::scalar_type threshold
5868 = IsMinPlusTruncMatHelper<T>::threshold;
5869 };
5870 } // namespace detail
5871
5872 namespace matrix {
5891 // TODO(1) to tpp
5892 template <typename Mat>
5893 std::enable_if_t<IsMinPlusTruncMat<Mat>> throw_if_bad_entry(Mat const& m) {
5894 // Check that the semiring pointer isn't the nullptr if it shouldn't be
5895 detail::throw_if_semiring_nullptr(m);
5896
5897 using scalar_type = typename Mat::scalar_type;
5898 scalar_type const t = matrix::threshold(m);
5899 auto it = std::find_if_not(m.cbegin(), m.cend(), [t](scalar_type x) {
5900 return x == POSITIVE_INFINITY || (0 <= x && x <= t);
5901 });
5902 if (it != m.cend()) {
5903 uint64_t r, c;
5904 std::tie(r, c) = m.coords(it);
5905
5907 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5908 "but found {} in entry ({}, {})",
5909 t,
5910 detail::entry_repr(POSITIVE_INFINITY),
5911 static_cast<scalar_type>(POSITIVE_INFINITY),
5912 detail::entry_repr(*it),
5913 r,
5914 c);
5915 }
5916 }
5917
5937 template <typename Mat>
5938 std::enable_if_t<IsMinPlusTruncMat<Mat>>
5939 throw_if_bad_entry(Mat const& m, typename Mat::scalar_type val) {
5940 detail::throw_if_semiring_nullptr(m);
5941
5942 using scalar_type = typename Mat::scalar_type;
5943 scalar_type const t = matrix::threshold(m);
5944 if (!(val == POSITIVE_INFINITY || (0 <= val && val <= t))) {
5946 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5947 "but found {}",
5948 t,
5949 detail::entry_repr(POSITIVE_INFINITY),
5950 static_cast<scalar_type>(POSITIVE_INFINITY),
5951 detail::entry_repr(val));
5952 }
5953 }
5954 } // namespace matrix
5955
5957 // NTP matrices
5959
6012
6013 namespace detail {
6014 template <size_t T, size_t P, typename Scalar>
6015 constexpr Scalar thresholdperiod(Scalar x) noexcept {
6016 if (x > T) {
6017 return T + (x - T) % P;
6018 }
6019 return x;
6020 }
6021
6022 template <typename Scalar>
6023 inline Scalar thresholdperiod(Scalar x,
6024 Scalar threshold,
6025 Scalar period) noexcept {
6026 if (x > threshold) {
6027 return threshold + (x - threshold) % period;
6028 }
6029 return x;
6030 }
6031 } // namespace detail
6032
6055 // Static arithmetic
6056 template <size_t T, size_t P, typename Scalar>
6057 struct NTPPlus {
6067 //! \exceptions
6068 //! \noexcept
6069 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
6070 return detail::thresholdperiod<T, P>(x + y);
6071 }
6072 };
6073
6096 //! \tparam Scalar the type of the values in the semiring.
6097 template <size_t T, size_t P, typename Scalar>
6098 struct NTPProd {
6110 //! \exceptions
6111 //! \noexcept
6112 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
6113 return detail::thresholdperiod<T, P>(x * y);
6114 }
6115 };
6116
6130 // Dynamic arithmetic
6131 template <typename Scalar = size_t>
6132 class NTPSemiring {
6133 public:
6137 // Deleted to avoid uninitialised values of period and threshold.
6138 NTPSemiring() = delete;
6139
6143 NTPSemiring(NTPSemiring const&) = default;
6144
6148 NTPSemiring(NTPSemiring&&) = default;
6149
6153 NTPSemiring& operator=(NTPSemiring const&) = default;
6154
6158 NTPSemiring& operator=(NTPSemiring&&) = default;
6159
6160 ~NTPSemiring() = default;
6161
6172 //! \complexity
6173 //! Constant.
6174 NTPSemiring(Scalar t, Scalar p) : _period(p), _threshold(t) {
6175 if constexpr (std::is_signed<Scalar>::value) {
6176 if (t < 0) {
6178 "expected non-negative value for 1st argument, found {}", t);
6179 }
6180 }
6181 if (p <= 0) {
6183 "expected positive value for 2nd argument, found {}", p);
6184 }
6185 }
6186
6195 //! \exceptions
6196 //! \noexcept
6197 static constexpr Scalar scalar_one() noexcept {
6198 return 1;
6199 }
6200
6211 //! \complexity
6212 //! Constant.
6213 static constexpr Scalar scalar_zero() noexcept {
6214 return 0;
6215 }
6216
6239 //! \complexity
6240 //! Constant.
6241 Scalar product_no_checks(Scalar x, Scalar y) const noexcept {
6242 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + _threshold - 1);
6243 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + _threshold - 1);
6244 return detail::thresholdperiod(x * y, _threshold, _period);
6245 }
6246
6269 //! \complexity
6270 //! Constant.
6271 Scalar plus_no_checks(Scalar x, Scalar y) const noexcept {
6272 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + _threshold - 1);
6273 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + _threshold - 1);
6274 return detail::thresholdperiod(x + y, _threshold, _period);
6275 }
6276
6287 //! \complexity
6288 //! Constant.
6289 Scalar threshold() const noexcept {
6290 return _threshold;
6291 }
6292
6303 //! \complexity
6304 //! Constant.
6305 Scalar period() const noexcept {
6306 return _period;
6307 }
6308
6309 private:
6310 Scalar _period;
6311 Scalar _threshold;
6312 };
6313
6324 template <typename Scalar>
6325 using DynamicNTPMatWithSemiring = DynamicMatrix<NTPSemiring<Scalar>, Scalar>;
6326
6340 template <size_t T, size_t P, typename Scalar>
6341 using DynamicNTPMatWithoutSemiring = DynamicMatrix<NTPPlus<T, P, Scalar>,
6345 Scalar>;
6346
6366 template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
6371 R,
6372 C,
6373 Scalar>;
6374
6397 template <size_t T = 0,
6398 size_t P = 0,
6399 size_t R = 0,
6400 size_t C = R,
6401 typename Scalar = size_t>
6402 using NTPMat = std::conditional_t<
6403 R == 0 || C == 0,
6404 std::conditional_t<T == 0 && P == 0,
6408
6409 namespace detail {
6410 template <typename T>
6411 struct IsNTPMatHelper : std::false_type {};
6412
6413 template <typename Scalar>
6414 struct IsNTPMatHelper<DynamicNTPMatWithSemiring<Scalar>> : std::true_type {
6415 static constexpr Scalar threshold = UNDEFINED;
6416 static constexpr Scalar period = UNDEFINED;
6417 };
6418
6419 template <size_t T, size_t P, typename Scalar>
6420 struct IsNTPMatHelper<DynamicNTPMatWithoutSemiring<T, P, Scalar>>
6421 : std::true_type {
6422 static constexpr Scalar threshold = T;
6423 static constexpr Scalar period = P;
6424 };
6425
6426 template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
6427 struct IsNTPMatHelper<StaticNTPMat<T, P, R, C, Scalar>> : std::true_type {
6428 static constexpr Scalar threshold = T;
6429 static constexpr Scalar period = P;
6430 };
6431 } // namespace detail
6432
6444 template <typename U>
6445 static constexpr bool IsNTPMat = detail::IsNTPMatHelper<U>::value;
6446
6447 namespace detail {
6448 template <typename T>
6449 struct IsTruncMatHelper<T, std::enable_if_t<IsNTPMat<T>>> : std::true_type {
6450 static constexpr typename T::scalar_type threshold
6451 = IsNTPMatHelper<T>::threshold;
6452 static constexpr typename T::scalar_type period
6453 = IsNTPMatHelper<T>::period;
6454 };
6455
6456 } // namespace detail
6457
6458 namespace matrix {
6479 //! \noexcept
6480 template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
6481 constexpr Scalar period(StaticNTPMat<T, P, R, C, Scalar> const&) noexcept {
6482 return P;
6483 }
6484
6502 template <size_t T, size_t P, typename Scalar>
6503 constexpr Scalar
6505 return P;
6506 }
6507
6522 //! \noexcept
6523 template <typename Scalar>
6524 Scalar period(DynamicNTPMatWithSemiring<Scalar> const& x) noexcept {
6525 return x.semiring()->period();
6526 }
6527 } // namespace matrix
6528
6529 namespace matrix {
6549 //! defined (only applies to matrices with run time arithmetic).
6550 template <typename Mat>
6551 std::enable_if_t<IsNTPMat<Mat>> throw_if_bad_entry(Mat const& m) {
6552 detail::throw_if_semiring_nullptr(m);
6553
6554 using scalar_type = typename Mat::scalar_type;
6555 scalar_type const t = matrix::threshold(m);
6556 scalar_type const p = matrix::period(m);
6557 auto it = std::find_if_not(m.cbegin(), m.cend(), [t, p](scalar_type x) {
6558 return (0 <= x && x < p + t);
6559 });
6560 if (it != m.cend()) {
6561 uint64_t r, c;
6562 std::tie(r, c) = m.coords(it);
6563
6565 "invalid entry, expected values in {{0, 1, ..., {}}}, but "
6566 "found {} in entry ({}, {})",
6567 p + t,
6568 detail::entry_repr(*it),
6569 r,
6570 c);
6571 }
6572 }
6573
6595 template <typename Mat>
6596 std::enable_if_t<IsNTPMat<Mat>>
6597 throw_if_bad_entry(Mat const& m, typename Mat::scalar_type val) {
6598 detail::throw_if_semiring_nullptr(m);
6599 using scalar_type = typename Mat::scalar_type;
6600 scalar_type const t = matrix::threshold(m);
6601 scalar_type const p = matrix::period(m);
6602 if (val < 0 || val >= p + t) {
6604 "invalid entry, expected values in {{0, 1, ..., {}}}, but "
6605 "found {}",
6606 p + t,
6607 detail::entry_repr(val));
6608 }
6609 }
6610 } // namespace matrix
6611
6613 // Projective max-plus matrices
6615
6616 namespace detail {
6617 template <typename T>
6618 class ProjMaxPlusMat : MatrixPolymorphicBase {
6619 public:
6620 using scalar_type = typename T::scalar_type;
6621 using scalar_reference = typename T::scalar_reference;
6622 using scalar_const_reference = typename T::scalar_const_reference;
6623 using semiring_type = void;
6624
6625 using container_type = typename T::container_type;
6626 using iterator = typename T::iterator;
6627 using const_iterator = typename T::const_iterator;
6628
6629 using underlying_matrix_type = T;
6630
6631 using RowView = typename T::RowView;
6632
6633 // Note that Rows are never normalised, and that's why we use the
6634 // underlying matrix Row type and not 1 x n ProjMaxPlusMat's instead
6635 // (since these will be normalised according to their entries, and
6636 // this might not correspond to the normalised entries of the matrix).
6637 using Row = typename T::Row;
6638
6639 scalar_type scalar_one() const noexcept {
6640 return _underlying_mat.scalar_one();
6641 }
6642
6643 scalar_type scalar_zero() const noexcept {
6644 return _underlying_mat.scalar_zero();
6645 }
6646
6648 // ProjMaxPlusMat - Constructors + destructor - public
6650
6651 ProjMaxPlusMat() : _is_normalized(false), _underlying_mat() {}
6652 ProjMaxPlusMat(ProjMaxPlusMat const&) = default;
6653 ProjMaxPlusMat(ProjMaxPlusMat&&) = default;
6654 ProjMaxPlusMat& operator=(ProjMaxPlusMat const&) = default;
6655 ProjMaxPlusMat& operator=(ProjMaxPlusMat&&) = default;
6656
6657 ProjMaxPlusMat(size_t r, size_t c)
6658 : _is_normalized(false), _underlying_mat(r, c) {}
6659
6660 // TODO(1) other missing constructors
6661 ProjMaxPlusMat(
6662 typename underlying_matrix_type::semiring_type const* semiring,
6663 size_t r,
6664 size_t c)
6665 : _is_normalized(false), _underlying_mat(semiring, r, c) {}
6666
6667 explicit ProjMaxPlusMat(std::vector<std::vector<scalar_type>> const& m)
6668 : _is_normalized(false), _underlying_mat(m) {
6669 normalize();
6670 }
6671
6672 ProjMaxPlusMat(
6673 std::initializer_list<std::initializer_list<scalar_type>> const& m)
6674 : ProjMaxPlusMat(
6675 std::vector<std::vector<scalar_type>>(m.begin(), m.end())) {}
6676
6677 ~ProjMaxPlusMat() = default;
6678
6679 ProjMaxPlusMat one() const {
6680 auto result = ProjMaxPlusMat(_underlying_mat.one());
6681 return result;
6682 }
6683
6684 static ProjMaxPlusMat one(size_t n) {
6685 return ProjMaxPlusMat(T::one(n));
6686 }
6687
6689 // Comparison operators
6691
6692 bool operator==(ProjMaxPlusMat const& that) const {
6693 normalize();
6694 that.normalize();
6695 return _underlying_mat == that._underlying_mat;
6696 }
6697
6698 bool operator!=(ProjMaxPlusMat const& that) const {
6699 return !(_underlying_mat == that._underlying_mat);
6700 }
6701
6702 bool operator<(ProjMaxPlusMat const& that) const {
6703 normalize();
6704 that.normalize();
6705 return _underlying_mat < that._underlying_mat;
6706 }
6707
6708 bool operator>(ProjMaxPlusMat const& that) const {
6709 return that < *this;
6710 }
6711
6712 template <typename Thing>
6713 bool operator>=(Thing const& that) const {
6714 static_assert(IsMatrix<Thing> || std::is_same_v<Thing, RowView>);
6715 return that < *this || that == *this;
6716 }
6717
6718 // not noexcept because operator< isn't
6719 template <typename Thing>
6720 bool operator<=(Thing const& that) const {
6721 static_assert(IsMatrix<Thing> || std::is_same_v<Thing, RowView>);
6722 return *this < that || that == *this;
6723 }
6724
6726 // Attributes
6728
6729 scalar_reference operator()(size_t r, size_t c) {
6730 // to ensure the returned value is normalised
6731 normalize();
6732 // to ensure that the matrix is renormalised if the returned scalar is
6733 // assigned.
6734 _is_normalized = false;
6735 return _underlying_mat(r, c);
6736 }
6737
6738 scalar_reference at(size_t r, size_t c) {
6739 matrix::throw_if_bad_coords(*this, r, c);
6740 return this->operator()(r, c);
6741 }
6742
6743 scalar_const_reference operator()(size_t r, size_t c) const {
6744 normalize();
6745 return _underlying_mat(r, c);
6746 }
6747
6748 scalar_const_reference at(size_t r, size_t c) const {
6749 matrix::throw_if_bad_coords(*this, r, c);
6750 return this->operator()(r, c);
6751 }
6752
6753 size_t number_of_rows() const noexcept {
6754 return _underlying_mat.number_of_rows();
6755 }
6756
6757 size_t number_of_cols() const noexcept {
6758 return _underlying_mat.number_of_cols();
6759 }
6760
6761 size_t hash_value() const {
6762 normalize();
6763 return Hash<T>()(_underlying_mat);
6764 }
6765
6767 // Arithmetic operators - in-place
6769
6770 void product_inplace_no_checks(ProjMaxPlusMat const& A,
6771 ProjMaxPlusMat const& B) {
6772 _underlying_mat.product_inplace_no_checks(A._underlying_mat,
6773 B._underlying_mat);
6774 normalize(true); // force normalize
6775 }
6776
6777 void operator+=(ProjMaxPlusMat const& that) {
6778 _underlying_mat += that._underlying_mat;
6779 normalize(true); // force normalize
6780 }
6781
6782 void operator*=(scalar_type a) {
6783 _underlying_mat *= a;
6784 normalize(true); // force normalize
6785 }
6786
6787 void operator+=(scalar_type a) {
6788 _underlying_mat += a;
6789 normalize(true); // force normalize
6790 }
6791
6792 ProjMaxPlusMat operator*(scalar_type a) const {
6793 ProjMaxPlusMat result(*this);
6794 result *= a;
6795 return result;
6796 }
6797
6798 ProjMaxPlusMat operator+(scalar_type a) const {
6799 ProjMaxPlusMat result(*this);
6800 result += a;
6801 return result;
6802 }
6803
6805 // Arithmetic operators - not in-place
6807
6808 ProjMaxPlusMat operator+(ProjMaxPlusMat const& that) const {
6809 return ProjMaxPlusMat(_underlying_mat + that._underlying_mat);
6810 }
6811
6812 ProjMaxPlusMat operator*(ProjMaxPlusMat const& that) const {
6813 return ProjMaxPlusMat(_underlying_mat * that._underlying_mat);
6814 }
6815
6817 // Iterators
6819
6820 // The following should probably be commented out because I can't
6821 // currently think how to ensure that the matrix is normalised if it's
6822 // changed this way.
6823
6824 iterator begin() noexcept {
6825 // to ensure the returned value is normalised
6826 normalize();
6827 // to ensure that the matrix is renormalised if the returned scalar is
6828 // assigned.
6829 _is_normalized = false;
6830 return _underlying_mat.begin();
6831 }
6832
6833 iterator end() noexcept {
6834 // to ensure the returned value is normalised
6835 normalize();
6836 // to ensure that the matrix is renormalised if the returned scalar is
6837 // assigned.
6838 _is_normalized = false;
6839 return _underlying_mat.end();
6840 }
6841
6842 const_iterator begin() const noexcept {
6843 normalize();
6844 return _underlying_mat.begin();
6845 }
6846
6847 const_iterator end() const noexcept {
6848 normalize();
6849 return _underlying_mat.end();
6850 }
6851
6852 const_iterator cbegin() const noexcept {
6853 normalize();
6854 return _underlying_mat.cbegin();
6855 }
6856
6857 const_iterator cend() const noexcept {
6858 normalize();
6859 return _underlying_mat.cend();
6860 }
6861
6863 // Modifiers
6865
6866 void swap(ProjMaxPlusMat& that) noexcept {
6867 std::swap(_underlying_mat, that._underlying_mat);
6868 }
6869
6870 void transpose() noexcept {
6871 _underlying_mat.transpose();
6872 }
6873
6874 void transpose_no_checks() noexcept {
6875 _underlying_mat.transpose_no_checks();
6876 }
6877
6879 // Rows
6881
6882 RowView row(size_t i) const {
6883 normalize();
6884 return _underlying_mat.row(i);
6885 }
6886
6887 template <typename C>
6888 void rows(C& x) const {
6889 normalize();
6890 return _underlying_mat.rows(x);
6891 }
6892
6894 // Friend functions
6896
6897 friend std::ostream& operator<<(std::ostream& os,
6898 ProjMaxPlusMat const& x) {
6899 x.normalize();
6900 os << detail::to_string(x._underlying_mat);
6901 return os;
6902 }
6903
6904 T const& underlying_matrix() const noexcept {
6905 normalize();
6906 return _underlying_mat;
6907 }
6908
6909 private:
6910 explicit ProjMaxPlusMat(T&& mat)
6911 : _is_normalized(false), _underlying_mat(std::move(mat)) {
6912 normalize();
6913 }
6914
6915 void normalize(bool force = false) const {
6916 if ((_is_normalized && !force)
6917 || (_underlying_mat.number_of_rows() == 0)
6918 || (_underlying_mat.number_of_cols() == 0)) {
6919 _is_normalized = true;
6920 return;
6921 }
6922 scalar_type const n = *std::max_element(_underlying_mat.cbegin(),
6923 _underlying_mat.cend());
6924 std::for_each(_underlying_mat.begin(),
6925 _underlying_mat.end(),
6926 [&n](scalar_type& s) {
6927 if (s != NEGATIVE_INFINITY) {
6928 s -= n;
6929 }
6930 });
6931 _is_normalized = true;
6932 }
6933
6934 mutable bool _is_normalized;
6935 mutable T _underlying_mat;
6936 };
6937 } // namespace detail
6938
6983
6997 template <size_t R, size_t C, typename Scalar>
6999 = detail::ProjMaxPlusMat<StaticMaxPlusMat<R, C, Scalar>>;
7000
7012 template <typename Scalar>
7014 = detail::ProjMaxPlusMat<DynamicMaxPlusMat<Scalar>>;
7015
7030 template <size_t R = 0, size_t C = R, typename Scalar = int>
7031 using ProjMaxPlusMat = std::conditional_t<R == 0 || C == 0,
7034
7035 namespace detail {
7036 template <typename T>
7037 struct IsProjMaxPlusMatHelper : std::false_type {};
7038
7039 template <size_t R, size_t C, typename Scalar>
7040 struct IsProjMaxPlusMatHelper<StaticProjMaxPlusMat<R, C, Scalar>>
7041 : std::true_type {};
7042
7043 template <typename Scalar>
7044 struct IsProjMaxPlusMatHelper<DynamicProjMaxPlusMat<Scalar>>
7045 : std::true_type {};
7046 } // namespace detail
7047
7059 template <typename T>
7060 static constexpr bool IsProjMaxPlusMat
7061 = detail::IsProjMaxPlusMatHelper<T>::value;
7062
7063 namespace matrix {
7064 // \ingroup projmaxplus_group
7065 //
7079 //! \throws LibsemigroupsException if
7080 //! `throw_if_bad_entry(x.underlying_matrix())` throws.
7081 template <typename Mat>
7082 constexpr std::enable_if_t<IsProjMaxPlusMat<Mat>>
7083 throw_if_bad_entry(Mat const& x) {
7084 throw_if_bad_entry(x.underlying_matrix());
7085 }
7086
7087 // \ingroup projmaxplus_group
7088 //
7102 //! \throws LibsemigroupsException if
7103 //! `throw_if_bad_entry(x.underlying_matrix(), val)` throws.
7104 template <typename Mat>
7105 constexpr std::enable_if_t<IsProjMaxPlusMat<Mat>>
7106 throw_if_bad_entry(Mat const& x, typename Mat::scalar_type val) {
7107 throw_if_bad_entry(x.underlying_matrix(), val);
7108 }
7109
7111 // Matrix helpers - pow
7113
7147 //! \endcode
7148 // TODO(1) pow_no_checks
7149 // TODO(2) version that changes x in-place
7150 template <typename Mat>
7151 Mat pow(Mat const& x, typename Mat::scalar_type e) {
7152 using scalar_type = typename Mat::scalar_type;
7153
7154 if constexpr (std::is_signed<scalar_type>::value) {
7155 if (e < 0) {
7157 "negative exponent, expected value >= 0, found {}", e);
7158 }
7159 }
7160
7162
7163 typename Mat::semiring_type const* sr = nullptr;
7164
7165 if constexpr (IsMatWithSemiring<Mat>) {
7166 sr = x.semiring();
7167 }
7168
7169 if (e == 0) {
7170 return x.one();
7171 }
7172
7173 auto y = Mat(x);
7174 if (e == 1) {
7175 return y;
7176 }
7177 auto z = (e % 2 == 0 ? x.one() : y);
7178
7179 Mat tmp(sr, x.number_of_rows(), x.number_of_cols());
7180 while (e > 1) {
7181 tmp.product_inplace_no_checks(y, y);
7182 std::swap(y, tmp);
7183 e /= 2;
7184 if (e % 2 == 1) {
7185 tmp.product_inplace_no_checks(z, y);
7186 std::swap(z, tmp);
7187 }
7188 }
7189 return z;
7190 }
7191
7193 // Matrix helpers - rows
7195
7212 //!
7213 //! \complexity
7214 //! \f$O(m)\f$ where \f$m\f$ is the number of rows in the matrix \p x.
7215 template <typename Mat, typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
7218 x.rows(container);
7219 return container;
7220 }
7221
7240 //! \complexity
7241 //! \f$O(m)\f$ where \f$m\f$ is the number of rows in the matrix \p x.
7242 template <typename Mat, typename = std::enable_if_t<IsStaticMatrix<Mat>>>
7243 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
7244 rows(Mat const& x) {
7245 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
7246 x.rows(container);
7247 return container;
7248 }
7249
7251 // Matrix helpers - bitset_rows
7253
7254 // The main function
7283 //! \complexity
7284 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in `views` and
7285 //! and \f$n\f$ is the number of columns in any vector in `views`.
7286 template <typename Mat, size_t R, size_t C, typename Container>
7287 void bitset_rows(Container&& views,
7288 detail::StaticVector1<BitSet<C>, R>& result) {
7289 using RowView = typename Mat::RowView;
7290 using value_type = typename std::decay_t<Container>::value_type;
7291 // std::vector<bool> is used as value_type in the benchmarks
7292 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7295 "Container::value_type must equal Mat::RowView or "
7296 "std::vector<bool>!!");
7297 static_assert(R <= BitSet<1>::max_size(),
7298 "R must be at most BitSet<1>::max_size()!");
7299 static_assert(C <= BitSet<1>::max_size(),
7300 "C must be at most BitSet<1>::max_size()!");
7301 LIBSEMIGROUPS_ASSERT(views.size() <= R);
7302 LIBSEMIGROUPS_ASSERT(views.empty() || views[0].size() <= C);
7303 for (auto const& v : views) {
7304 result.emplace_back(v.cbegin(), v.cend());
7305 }
7306 }
7307
7337 //! \complexity
7338 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in \p views and
7339 //! and \f$n\f$ is the number of columns in any vector in \p views.
7340 template <typename Mat, size_t R, size_t C, typename Container>
7341 auto bitset_rows(Container&& views) {
7342 using RowView = typename Mat::RowView;
7343 using value_type = typename std::decay_t<Container>::value_type;
7344 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7347 "Container::value_type must equal Mat::RowView or "
7348 "std::vector<bool>!!");
7349 static_assert(R <= BitSet<1>::max_size(),
7350 "R must be at most BitSet<1>::max_size()!");
7351 static_assert(C <= BitSet<1>::max_size(),
7352 "C must be at most BitSet<1>::max_size()!");
7353 LIBSEMIGROUPS_ASSERT(views.size() <= R);
7354 LIBSEMIGROUPS_ASSERT(views.empty() || views[0].size() <= C);
7355 detail::StaticVector1<BitSet<C>, R> result;
7357 return result;
7358 }
7359
7360 // Helper
7386 //! \complexity
7387 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in \p x and and
7388 //! \f$n\f$ is the number of columns in \p x.
7389 template <typename Mat, size_t R, size_t C>
7390 void bitset_rows(Mat const& x,
7391 detail::StaticVector1<BitSet<C>, R>& result) {
7392 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7393 static_assert(R <= BitSet<1>::max_size(),
7394 "R must be at most BitSet<1>::max_size()!");
7395 static_assert(C <= BitSet<1>::max_size(),
7396 "C must be at most BitSet<1>::max_size()!");
7397 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= C);
7398 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= R);
7399 bitset_rows<Mat>(std::move(rows(x)), result);
7400 }
7401
7402 // Helper
7418 //! \complexity
7419 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in \p x and
7420 //! and \f$n\f$ is the number of columns in \p x.
7421 template <typename Mat>
7422 auto bitset_rows(Mat const& x) {
7423 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7424 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7425 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7426 size_t const M = detail::BitSetCapacity<Mat>::value;
7428 }
7429
7431 // Matrix helpers - bitset_row_basis
7433
7455 //! \f$c\f$ is the size of each bitset in `rows`.
7456 // This works with std::vector and StaticVector1, with value_type equal
7457 // to std::bitset and BitSet.
7458 template <typename Mat, typename Container>
7459 void bitset_row_basis(Container&& rows, std::decay_t<Container>& result) {
7460 using value_type = typename std::decay_t<Container>::value_type;
7461 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7462 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7463 "Container::value_type must be BitSet or std::bitset");
7464 LIBSEMIGROUPS_ASSERT(rows.size() <= BitSet<1>::max_size());
7465 LIBSEMIGROUPS_ASSERT(rows.empty()
7466 || rows[0].size() <= BitSet<1>::max_size());
7467
7468 std::sort(rows.begin(), rows.end(), detail::LessBitSet());
7469 // Remove duplicates
7470 rows.erase(std::unique(rows.begin(), rows.end()), rows.end());
7471 for (size_t i = 0; i < rows.size(); ++i) {
7472 value_type cup;
7473 cup.reset();
7474 for (size_t j = 0; j < i; ++j) {
7475 if ((rows[i] & rows[j]) == rows[j]) {
7476 cup |= rows[j];
7477 }
7478 }
7479 for (size_t j = i + 1; j < rows.size(); ++j) {
7480 if ((rows[i] & rows[j]) == rows[j]) {
7481 cup |= rows[j];
7482 }
7483 }
7484 if (cup != rows[i]) {
7485 result.push_back(std::move(rows[i]));
7486 }
7487 }
7488 }
7489
7510 //! \complexity
7511 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the size of \p rows and
7512 //! \f$c\f$ is the size of each bitset in \p rows.
7513 template <typename Mat, typename Container>
7514 std::decay_t<Container> bitset_row_basis(Container&& rows) {
7515 using value_type = typename std::decay_t<Container>::value_type;
7516 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7517 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7518 "Container::value_type must be BitSet or std::bitset");
7519 LIBSEMIGROUPS_ASSERT(rows.size() <= BitSet<1>::max_size());
7520 LIBSEMIGROUPS_ASSERT(rows.empty()
7521 || rows[0].size() <= BitSet<1>::max_size());
7522 std::decay_t<Container> result;
7524 return result;
7525 }
7526
7551 //! \complexity
7552 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x and
7553 //! \f$c\f$ is the number of columns in \p x.
7554 template <typename Mat, size_t M = detail::BitSetCapacity<Mat>::value>
7555 detail::StaticVector1<BitSet<M>, M> bitset_row_basis(Mat const& x) {
7556 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7557 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7558 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7559 detail::StaticVector1<BitSet<M>, M> result;
7561 return result;
7562 }
7563
7584 //! \complexity
7585 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x
7586 //! and \f$c\f$ is the number of columns in \p x.
7587 template <typename Mat, typename Container>
7588 void bitset_row_basis(Mat const& x, Container& result) {
7589 using value_type = typename Container::value_type;
7590 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7591 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7592 "Container::value_type must be BitSet or std::bitset");
7593 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7594 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7596 }
7597
7599 // Matrix helpers - row_basis - MaxPlusTruncMat
7601
7627 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the size of \p views and
7628 //! \f$c\f$ is the size of each row view or bit set in \p views.
7629 template <typename Mat, typename Container>
7630 std::enable_if_t<IsMaxPlusTruncMat<Mat>>
7631 row_basis(Container&& views, std::decay_t<Container>& result) {
7632 using value_type = typename std::decay_t<Container>::value_type;
7634 "Container::value_type must be Mat::RowView");
7635 using scalar_type = typename Mat::scalar_type;
7636 using Row = typename Mat::Row;
7637
7638 if (views.empty()) {
7639 return;
7640 }
7641
7642 LIBSEMIGROUPS_ASSERT(result.empty());
7643
7644 std::sort(views.begin(), views.end());
7645 Row tmp1(views[0]);
7646
7647 for (size_t r1 = 0; r1 < views.size(); ++r1) {
7648 if (r1 == 0 || views[r1] != views[r1 - 1]) {
7649 std::fill(tmp1.begin(), tmp1.end(), tmp1.scalar_zero());
7650 for (size_t r2 = 0; r2 < r1; ++r2) {
7651 scalar_type max_scalar = matrix::threshold(tmp1);
7652 for (size_t c = 0; c < tmp1.number_of_cols(); ++c) {
7653 if (views[r2][c] == tmp1.scalar_zero()) {
7654 continue;
7655 }
7656 if (views[r1][c] >= views[r2][c]) {
7657 if (views[r1][c] != matrix::threshold(tmp1)) {
7658 max_scalar
7659 = std::min(max_scalar, views[r1][c] - views[r2][c]);
7660 }
7661 } else {
7662 max_scalar = tmp1.scalar_zero();
7663 break;
7664 }
7665 }
7666 if (max_scalar != tmp1.scalar_zero()) {
7667 tmp1 += views[r2] * max_scalar;
7668 }
7669 }
7670 if (tmp1 != views[r1]) {
7671 result.push_back(views[r1]);
7672 }
7673 }
7674 }
7675 }
7676
7678 // Matrix helpers - row_basis - BMat
7680
7681 // This version of row_basis for BMat's is for used for compatibility
7682 // with the MatrixCommon framework, i.e. so that BMat's exhibit the same
7683 // interface/behaviour as other matrices.
7684 //
7685 // This version takes a container of row views of BMat, converts it to a
7686 // container of BitSets, computes the row basis using the BitSets, then
7687 // selects those row views in views that belong to the computed basis.
7688
7704 //! \exceptions
7705 //! \no_libsemigroups_except
7706 // TODO(2) complexity
7707 template <typename Mat, typename Container>
7708 std::enable_if_t<IsBMat<Mat>> row_basis(Container&& views,
7709 std::decay_t<Container>& result) {
7710 using RowView = typename Mat::RowView;
7711 using value_type = typename std::decay_t<Container>::value_type;
7712 // std::vector<bool> is used as value_type in the benchmarks
7715 "Container::value_type must equal Mat::RowView or "
7716 "std::vector<bool>!!");
7717
7718 if (views.empty()) {
7719 return;
7720 }
7721
7722 // Convert RowViews to BitSets
7723 size_t const M = detail::BitSetCapacity<Mat>::value;
7725 using bitset_type = typename decltype(br)::value_type;
7726
7727 // Map for converting bitsets back to row views
7729 LIBSEMIGROUPS_ASSERT(br.size() == views.size());
7730 for (size_t i = 0; i < br.size(); ++i) {
7731 lookup.insert({br[i], i});
7732 }
7733
7734 // Compute rowbasis using bitsets + convert back to rowviews
7735 for (auto const& bs : bitset_row_basis<Mat>(br)) {
7736 auto it = lookup.find(bs);
7737 LIBSEMIGROUPS_ASSERT(it != lookup.end());
7738 result.push_back(views[it->second]);
7739 }
7740 }
7741
7743 // Matrix helpers - row_basis - generic helpers
7745
7767 // Row basis of rowspace of matrix <x> appended to <result>
7768 template <typename Mat,
7769 typename Container,
7770 typename = std::enable_if_t<IsMatrix<Mat>>>
7771 void row_basis(Mat const& x, Container& result) {
7772 row_basis<Mat>(std::move(rows(x)), result);
7773 }
7774
7792 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x
7793 //! and \f$c\f$ is the number of columns in \p x.
7794 // Row basis of rowspace of matrix <x>
7795 template <typename Mat, typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
7798 row_basis(x, container);
7799 return container;
7800 }
7801
7819 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x
7820 //! and \f$c\f$ is the number of columns in \p x.
7821 template <typename Mat, typename = std::enable_if_t<IsStaticMatrix<Mat>>>
7822 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
7823 row_basis(Mat const& x) {
7824 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
7825 row_basis(x, container);
7826 return container;
7827 }
7828
7845 //! \exceptions
7846 //! \no_libsemigroups_except
7847 // TODO(2) complexity
7848 template <typename Mat, typename Container>
7849 std::decay_t<Container> row_basis(Container&& rows) {
7850 using value_type = typename std::decay_t<Container>::value_type;
7851 static_assert(IsMatrix<Mat>, "IsMatrix<Mat> must be true!");
7853 "Container::value_type must be Mat::RowView");
7854
7855 std::decay_t<Container> result;
7857 return result;
7858 }
7859
7861 // Matrix helpers - row_space_size
7863
7891 //! auto x = make<BMat<>>({{1, 0, 0}, {0, 0, 1}, {0, 1, 0}});
7892 //! matrix::row_space_size(x); // returns 7
7893 //! \endcode
7894 template <typename Mat, typename = std::enable_if_t<IsBMat<Mat>>>
7895 size_t row_space_size(Mat const& x) {
7896 size_t const M = detail::BitSetCapacity<Mat>::value;
7897 auto bitset_row_basis_ = bitset_row_basis<Mat>(
7899
7901 st.insert(bitset_row_basis_.cbegin(), bitset_row_basis_.cend());
7902 std::vector<BitSet<M>> orb(bitset_row_basis_.cbegin(),
7903 bitset_row_basis_.cend());
7904 for (size_t i = 0; i < orb.size(); ++i) {
7905 for (auto& row : bitset_row_basis_) {
7906 auto cup = orb[i];
7907 for (size_t j = 0; j < x.number_of_rows(); ++j) {
7908 cup.set(j, cup[j] || row[j]);
7909 }
7910 if (st.insert(cup).second) {
7911 orb.push_back(std::move(cup));
7912 }
7913 }
7914 }
7915 return orb.size();
7916 }
7917
7918 } // namespace matrix
7919
7936 //! \no_libsemigroups_except
7937 //!
7938 //! \warning This function does not detect overflows of `Mat::scalar_type`.
7939 template <typename Mat>
7940 auto operator+(typename Mat::scalar_type a, Mat const& x)
7941 -> std::enable_if_t<IsMatrix<Mat>, Mat> {
7942 return x + a;
7943 }
7944
7961 //! \no_libsemigroups_except
7962 //!
7963 //! \warning This function does not detect overflows of `Mat::scalar_type`.
7964 template <typename Mat>
7965 auto operator*(typename Mat::scalar_type a, Mat const& x)
7966 -> std::enable_if_t<IsMatrix<Mat>, Mat> {
7967 return x * a;
7968 }
7969
7980
8005 //! \f$n\f$ is the number of columns of the matrix.
8006 template <typename Mat,
8007 typename
8008 = std::enable_if_t<IsMatrix<Mat> && !IsMatWithSemiring<Mat>>>
8010 detail::throw_if_any_row_wrong_size(rows);
8011 detail::throw_if_bad_dim<Mat>(rows);
8012 Mat m(rows);
8014 return m;
8015 }
8016
8041 //! \f$n\f$ is the number of columns of the matrix.
8042 template <typename Mat,
8043 typename
8044 = std::enable_if_t<IsMatrix<Mat> && !IsMatWithSemiring<Mat>>>
8046 rows) {
8048 }
8049
8075 //! parameter \c R is \c 1.
8076 template <typename Mat,
8077 typename
8078 = std::enable_if_t<IsMatrix<Mat> && !IsMatWithSemiring<Mat>>>
8080 // TODO(0) Add row dimension checking for compile-time size matrices
8081 Mat m(row);
8083 return m;
8084 }
8085 // TODO(1) vector version of above
8086
8118 template <typename Mat,
8119 typename Semiring,
8120 typename = std::enable_if_t<IsMatrix<Mat>>>
8121 // TODO(1) pass Semiring by reference, this is hard mostly due to the way
8122 // the tests are written, which is not optimal.
8123 Mat make(Semiring const* semiring,
8126 detail::throw_if_any_row_wrong_size(rows);
8127 detail::throw_if_bad_dim<Mat>(rows);
8128 Mat m(semiring, rows);
8130 return m;
8131 }
8132
8163 //! \f$n\f$ is the number of columns of the matrix.
8164 template <typename Mat,
8165 typename Semiring,
8166 typename = std::enable_if_t<IsMatrix<Mat>>>
8167 Mat make(Semiring const* semiring,
8169 detail::throw_if_any_row_wrong_size(rows);
8170 detail::throw_if_bad_dim<Mat>(rows);
8171 Mat m(semiring, rows);
8173 return m;
8174 }
8175
8197 //! \f$O(n)\f$ where \f$n\f$ is the number of columns of the matrix.
8198 template <typename Mat,
8199 typename Semiring,
8200 typename = std::enable_if_t<IsMatrix<Mat>>>
8201 Mat make(Semiring const* semiring,
8203 // TODO(0) Add row dimension checking for compile-time size matrices
8204 Mat m(semiring, row);
8206 return m;
8207 }
8208
8234 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows and \f$n\f$ is the
8235 //! number of columns of the matrix.
8236 template <size_t R, size_t C, typename Scalar>
8241 }
8242
8244 // Printing etc...
8246
8256 //!
8257 //! \exceptions
8258 //! \no_libsemigroups_except
8259 template <typename S, typename T>
8261 detail::RowViewCommon<S, T> const& x) {
8262 os << "{";
8263 for (auto it = x.cbegin(); it != x.cend(); ++it) {
8264 os << *it;
8265 if (it != x.cend() - 1) {
8266 os << ", ";
8267 }
8268 }
8269 os << "}";
8270 return os;
8271 }
8272
8286 //!
8287 //! \exceptions
8288 //! \no_libsemigroups_except
8289 template <typename Mat>
8290 auto operator<<(std::ostringstream& os, Mat const& x)
8291 -> std::enable_if_t<IsMatrix<Mat>, std::ostringstream&> {
8292 size_t n = 0;
8293 if (x.number_of_rows() != 1) {
8294 os << "{";
8295 }
8296 for (auto&& r : matrix::rows(x)) {
8297 os << r;
8298 if (n != x.number_of_rows() - 1) {
8299 os << ", ";
8300 }
8301 n++;
8302 }
8303 if (x.number_of_rows() != 1) {
8304 os << "}";
8305 }
8306 return os;
8307 }
8308
8322 //! (default: \c 72).
8323 //!
8324 //! \throws LibsemigroupsException if \p braces does not have size \c 2.
8325 template <typename Mat>
8326 auto to_human_readable_repr(Mat const& x,
8327 std::string const& prefix,
8328 std::string const& short_name = "",
8329 std::string const& braces = "{}",
8330 size_t max_width = 72)
8331 -> std::enable_if_t<IsMatrix<Mat>, std::string> {
8332 if (braces.size() != 2) {
8334 "the 4th argument (braces) must have size 2, found {}",
8335 braces.size());
8336 }
8337
8338 size_t const R = x.number_of_rows();
8339 size_t const C = x.number_of_cols();
8340
8341 std::vector<size_t> max_col_widths(C, 0);
8342 std::vector<size_t> row_widths(C, prefix.size() + 1);
8343 for (size_t r = 0; r < R; ++r) {
8344 for (size_t c = 0; c < C; ++c) {
8345 size_t width
8346 = detail::unicode_string_length(detail::entry_repr(x(r, c)));
8347 row_widths[r] += width;
8348 if (width > max_col_widths[c]) {
8349 max_col_widths[c] = width;
8350 }
8351 }
8352 }
8353 auto col_width
8354 = *std::max_element(max_col_widths.begin(), max_col_widths.end());
8355 // The total width if we pad the entries according to the widest column.
8356 auto const total_width = col_width * C + prefix.size() + 1;
8357 if (total_width > max_width) {
8358 // Padding according to the widest column is too wide!
8359 if (*std::max_element(row_widths.begin(), row_widths.end()) > max_width) {
8360 // If the widest row is too wide, then use the short name
8361 return fmt::format(
8362 "<{}x{} {}>", x.number_of_rows(), x.number_of_cols(), short_name);
8363 }
8364 // If the widest row is not too wide, then just don't pad the entries
8365 col_width = 0;
8366 }
8367
8368 std::string result = fmt::format("{}", prefix);
8369 std::string rindent;
8370 auto const lbrace = braces[0], rbrace = braces[1];
8371 if (R != 0 && C != 0) {
8372 result += lbrace;
8373 for (size_t r = 0; r < R; ++r) {
8374 result += fmt::format("{}{}", rindent, lbrace);
8375 rindent = std::string(prefix.size() + 1, ' ');
8376 std::string csep = "";
8377 for (size_t c = 0; c < C; ++c) {
8378 result += fmt::format(
8379 "{}{:>{}}", csep, detail::entry_repr(x(r, c)), col_width);
8380 csep = ", ";
8381 }
8382 result += fmt::format("{}", rbrace);
8383 if (r != R - 1) {
8384 result += ",\n";
8385 }
8386 }
8387 result += rbrace;
8388 }
8389 result += ")";
8390 return result;
8391 }
8392
8394 // Adapters
8396
8411
8419 //! satisfying \ref IsMatrix<Mat>.
8420 //!
8421 //! \tparam Mat the type of matrices.
8422 template <typename Mat>
8423 struct Complexity<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8433 //! \noexcept
8434 //!
8435 //! \complexity
8436 //! Constant.
8437 constexpr size_t operator()(Mat const& x) const noexcept {
8438 return x.number_of_rows() * x.number_of_rows() * x.number_of_rows();
8439 }
8440 };
8441
8449 //! \ref IsMatrix<Mat>.
8450 //!
8451 //! \tparam Mat the type of matrices.
8452 template <typename Mat>
8453 struct Degree<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8462 //! \noexcept
8463 //!
8464 //! \complexity
8465 //! Constant.
8466 constexpr size_t operator()(Mat const& x) const noexcept {
8467 return x.number_of_rows();
8468 }
8469 };
8470
8478 //! \ref IsMatrix<Mat>.
8479 //!
8480 //! \tparam Mat the type of matrices.
8481 template <typename Mat>
8482 struct Hash<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8491 //! \no_libsemigroups_except
8492 //!
8493 //! \complexity
8494 //! Constant.
8495 constexpr size_t operator()(Mat const& x) const {
8496 return x.hash_value();
8497 }
8498 };
8499
8512 //! It is not possible to increase the degree of any of the types
8513 //! satisfying \ref IsMatrix, and as such the call operator of this type
8514 //! does nothing.
8515 template <typename Mat>
8516 struct IncreaseDegree<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8520 constexpr void operator()(Mat&, size_t) const noexcept {
8521 // static_assert(false, "Cannot increase degree for Matrix");
8522 LIBSEMIGROUPS_ASSERT(false);
8523 }
8524 };
8525
8533 //! \ref IsMatrix.
8534 //!
8535 //! \tparam Mat the type of matrices.
8536 template <typename Mat>
8537 struct One<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8547 //!
8548 //! \complexity
8549 //! \f$O(m ^ 2)\f$ where \f$m\f$ is the number of rows of the
8550 //! matrix \p x.
8551 inline Mat operator()(Mat const& x) const {
8552 return x.one();
8553 }
8554 };
8555
8563 //! \ref IsMatrix<Mat>.
8564 //!
8565 //! \tparam Mat the type of matrices.
8566 template <typename Mat>
8567 struct Product<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8583 //!
8584 //! \warning
8585 //! This function only works for square matrices.
8586 inline void
8587 operator()(Mat& xy, Mat const& x, Mat const& y, size_t = 0) const {
8588 xy.product_inplace_no_checks(x, y);
8589 }
8590 };
8591} // namespace libsemigroups
8592
8593namespace std {
8594 template <size_t N,
8595 typename Mat,
8596 std::enable_if_t<libsemigroups::IsMatrix<Mat>>>
8597 inline void swap(Mat& x, Mat& y) noexcept {
8598 x.swap(y);
8599 }
8600} // namespace std
8601
8602#endif // LIBSEMIGROUPS_MATRIX_HPP_
DynamicMatrix(std::initializer_list< scalar_type > const &c)
Construct a vector from a std::initializer_list.
Definition matrix.hpp:2884
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:2906
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:2805
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:2796
PlusOp Plus
Alias for the template parameter PlusOp.
Definition matrix.hpp:2802
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:2792
void swap(DynamicMatrix &that) noexcept
Swaps the contents of *this with the contents of that.
Definition matrix.hpp:3165
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:2987
DynamicMatrix(size_t r, size_t c)
Construct a matrix with given dimensions.
Definition matrix.hpp:2862
ZeroOp Zero
Alias for the template parameter ZeroOp.
Definition matrix.hpp:2808
scalar_type scalar_zero() const noexcept
Returns the additive identity of the underlying semiring.
semiring_type const * semiring() const noexcept
Returns the underlying semiring.
OneOp One
Alias for the template parameter OneOp.
Definition matrix.hpp:2811
void semiring_type
Alias for the semiring type (void).
Definition matrix.hpp:2818
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:2940
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:2799
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:2925
typename MatrixCommon::scalar_reference scalar_reference
The type of references to the entries in the matrix.
Definition matrix.hpp:2787
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:2784
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
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:3304
DynamicMatrix & operator=(DynamicMatrix &&)=default
Default move assignment operator.
static DynamicMatrix one(Semiring const *semiring, size_t n)
Construct the identity matrix.
Definition matrix.hpp:3381
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:3327
DynamicMatrix(Semiring const *sr, size_t r, size_t c)
Construct a matrix over a given semiring with given dimensions.
Definition matrix.hpp:3284
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:3241
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:3237
void swap(DynamicMatrix &that) noexcept
Swaps the contents of *this with the contents of that.
Definition matrix.hpp:3561
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.
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:3361
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:3346
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:3232
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:3229
DynamicRowView< Semiring, Scalar > RowView
Alias for the type of row views of a DynamicMatrix.
Definition matrix.hpp:3244
Semiring semiring_type
Alias for the template parameter Semiring.
Definition matrix.hpp:3249
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.
Class representing a truncated max-plus semiring.
Definition matrix.hpp:5110
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:5184
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in a truncated max-plus semiring.
Definition matrix.hpp:5247
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in a truncated max-plus semiring.
Definition matrix.hpp:5212
MaxPlusTruncSemiring()=delete
Deleted default constructor.
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:5272
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:5170
Class representing a truncated min-plus semiring.
Definition matrix.hpp:5587
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:5660
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in a truncated min-plus semiring.
Definition matrix.hpp:5723
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in a truncated min-plus semiring.
Definition matrix.hpp:5688
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:5748
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:5645
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:6211
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in an ntp semiring.
Definition matrix.hpp:6269
NTPSemiring()=delete
Deleted default constructor.
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in an ntp semiring.
Definition matrix.hpp:6239
Scalar period() const noexcept
Get the period.
Definition matrix.hpp:6303
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:6287
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:6195
Static matrix class.
Definition matrix.hpp:1859
typename MatrixCommon::iterator iterator
Definition matrix.hpp:1906
StaticMatrix(std::initializer_list< scalar_type > const &c)
Construct a row (from std::initializer_list).
Definition matrix.hpp:1934
typename MatrixCommon::const_iterator const_iterator
Definition matrix.hpp:1909
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.
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:1884
scalar_reference operator()(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
void product_inplace_no_checks(StaticMatrix const &x, StaticMatrix const &y)
StaticMatrix(std::initializer_list< std::initializer_list< scalar_type > > const &m)
Construct a matrix.
Definition matrix.hpp:1960
StaticRowView< PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar > RowView
Definition matrix.hpp:1891
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:1996
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:1976
StaticMatrix< PlusOp, ProdOp, ZeroOp, OneOp, 1, C, Scalar > Row
Alias for the type of the rows of a StaticMatrix.
Definition matrix.hpp:1888
StaticMatrix()=default
Default constructor.
typename MatrixCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1879
typename MatrixCommon::scalar_type scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1876
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.
T copy(T... args)
T distance(T... args)
T equal(T... args)
T fill(T... args)
T find_if_not(T... args)
T for_each(T... args)
T forward(T... args)
std::string to_human_readable_repr(AhoCorasick const &ac)
Return a string representation.
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:3943
static constexpr bool IsBMat
Helper to check if a type is BMat.
Definition matrix.hpp:4001
DynamicMatrix< BooleanPlus, BooleanProd, BooleanZero, BooleanOne, int > DynamicBMat
Alias for dynamic boolean matrices.
Definition matrix.hpp:3929
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:4046
std::conditional_t< R==0||C==0, DynamicBMat, StaticBMat< R, C > > BMat
Alias template for boolean matrices.
Definition matrix.hpp:3966
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:4290
DynamicMatrix< IntegerPlus< Scalar >, IntegerProd< Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, Scalar > DynamicIntMat
Alias for dynamic integer matrices.
Definition matrix.hpp:4242
StaticMatrix< IntegerPlus< Scalar >, IntegerProd< Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, R, C, Scalar > StaticIntMat
Alias for static integer matrices.
Definition matrix.hpp:4265
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:798
static constexpr bool IsMaxPlusMat
Helper variable template.
Definition matrix.hpp:4616
constexpr bool IsStaticMatrix
Helper variable template.
Definition matrix.hpp:3639
constexpr bool IsDynamicMatrix
Helper variable template.
Definition matrix.hpp:3652
static constexpr bool IsIntMat
Helper variable template.
Definition matrix.hpp:4315
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:7936
static constexpr bool IsMatWithSemiring
Helper variable template.
Definition matrix.hpp:3666
static constexpr bool IsMinPlusMat
Helper variable template.
Definition matrix.hpp:4924
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:4565
DynamicMatrix< MaxPlusPlus< Scalar >, MaxPlusProd< Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMaxPlusMat
Alias for dynamic max-plus matrices.
Definition matrix.hpp:4546
std::conditional_t< R==0||C==0, DynamicMaxPlusMat< Scalar >, StaticMaxPlusMat< R, C, Scalar > > MaxPlusMat
Alias template for max-plus matrices.
Definition matrix.hpp:4589
DynamicMatrix< MaxPlusPlus< Scalar >, MaxPlusTruncProd< T, Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMaxPlusTruncMat
Alias for dynamic truncated max-plus matrices.
Definition matrix.hpp:5293
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:5339
StaticMatrix< MaxPlusPlus< Scalar >, MaxPlusTruncProd< T, Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMaxPlusTruncMat
Alias for static truncated max-plus matrices.
Definition matrix.hpp:5313
static constexpr bool IsMaxPlusTruncMat
Helper to check if a type is MaxPlusTruncMat.
Definition matrix.hpp:5382
DynamicMatrix< MinPlusPlus< Scalar >, MinPlusProd< Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMinPlusMat
Alias for dynamic min-plus matrices.
Definition matrix.hpp:4854
StaticMatrix< MinPlusPlus< Scalar >, MinPlusProd< Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMinPlusMat
Alias for static min-plus matrices.
Definition matrix.hpp:4873
std::conditional_t< R==0||C==0, DynamicMinPlusMat< Scalar >, StaticMinPlusMat< R, C, Scalar > > MinPlusMat
Alias template for min-plus matrices.
Definition matrix.hpp:4897
DynamicMatrix< MinPlusPlus< Scalar >, MinPlusTruncProd< T, Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMinPlusTruncMat
Alias for dynamic truncated min-plus matrices.
Definition matrix.hpp:5769
StaticMatrix< MinPlusPlus< Scalar >, MinPlusTruncProd< T, Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMinPlusTruncMat
Alias for static truncated min-plus matrices.
Definition matrix.hpp:5789
static constexpr bool IsMinPlusTruncMat
Helper to check if a type is MinPlusTruncMat.
Definition matrix.hpp:5859
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:5816
DynamicMatrix< NTPSemiring< Scalar >, Scalar > DynamicNTPMatWithSemiring
Alias for ntp matrices with dynamic threshold and period.
Definition matrix.hpp:6323
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:6339
static constexpr bool IsNTPMat
Helper to check if a type is NTPMat.
Definition matrix.hpp:6443
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:6400
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:6365
std::conditional_t< R==0||C==0, DynamicProjMaxPlusMat< Scalar >, StaticProjMaxPlusMat< R, C, Scalar > > ProjMaxPlusMat
Alias template for projective max-plus matrices.
Definition matrix.hpp:7027
detail::ProjMaxPlusMat< DynamicMaxPlusMat< Scalar > > DynamicProjMaxPlusMat
Alias for dynamic projective max-plus matrices with run-time dimensions.
Definition matrix.hpp:7010
static constexpr bool IsProjMaxPlusMat
Helper to check if a type is ProjMaxPlusMat.
Definition matrix.hpp:7057
detail::ProjMaxPlusMat< StaticMaxPlusMat< R, C, Scalar > > StaticProjMaxPlusMat
Alias for static projective max-plus matrices with compile-time arithmetic and dimensions.
Definition matrix.hpp:6996
T inner_product(T... args)
T insert(T... args)
T lexicographical_compare(T... args)
T make_pair(T... args)
T max_element(T... args)
T max(T... args)
T min(T... args)
T move(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:7455
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:7283
constexpr Scalar period(StaticNTPMat< T, P, R, C, Scalar > const &) noexcept
Returns the period of a static ntp matrix.
Definition matrix.hpp:6479
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:3727
size_t row_space_size(Mat const &x)
Returns the size of the row space of a boolean matrix.
Definition matrix.hpp:7891
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:7212
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:7147
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:7627
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T push_back(T... args)
T sort(T... args)
Function object for returning the multiplicative identity.
Definition matrix.hpp:3877
constexpr bool operator()() const noexcept
Call operator returning the multiplication identity true of the boolean semiring.
Definition matrix.hpp:3888
Function object for addition in the boolean semiring.
Definition matrix.hpp:3823
constexpr bool operator()(bool x, bool y) const noexcept
Call operator for addition.
Definition matrix.hpp:3836
Function object for multiplication in the boolean semiring.
Definition matrix.hpp:3850
constexpr bool operator()(bool x, bool y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:3863
Function object for returning the additive identity.
Definition matrix.hpp:3902
constexpr bool operator()() const noexcept
Call operator returning the additive identity false of the boolean semiring.
Definition matrix.hpp:3913
constexpr size_t operator()(Mat const &x) const noexcept
Call operator.
Definition matrix.hpp:8433
Adapter for the complexity of multiplication.
Definition adapters.hpp:121
constexpr size_t operator()(Mat const &x) const noexcept
Call operator.
Definition matrix.hpp:8462
Adapter for the degree of an element.
Definition adapters.hpp:159
constexpr size_t operator()(Mat const &x) const
Call operator.
Definition matrix.hpp:8491
Adapter for hashing.
Definition adapters.hpp:446
constexpr void operator()(Mat &, size_t) const noexcept
Call operator.
Definition matrix.hpp:8516
Adapter for increasing the degree of an element.
Definition adapters.hpp:199
Function object for returning the multiplicative identity.
Definition matrix.hpp:4216
constexpr Scalar operator()() const noexcept
Call operator returning the integer 1.
Definition matrix.hpp:4226
Function object for addition in the ring of integers.
Definition matrix.hpp:4132
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4145
Function object for multiplication in the ring of integers.
Definition matrix.hpp:4163
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4176
Function object for returning the additive identity.
Definition matrix.hpp:4191
constexpr Scalar operator()() const noexcept
Call operator returning the integer 0.
Definition matrix.hpp:4201
Function object for addition in the max-plus semiring.
Definition matrix.hpp:4434
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4449
Function object for multiplication in the max-plus semiring.
Definition matrix.hpp:4481
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4496
Function object for multiplication in truncated max-plus semirings.
Definition matrix.hpp:5068
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:5083
Function object for returning the additive identity of the max-plus semiring.
Definition matrix.hpp:4518
constexpr Scalar operator()() const noexcept
Call operator for additive identity.
Definition matrix.hpp:4530
Function object for addition in the min-plus semiring.
Definition matrix.hpp:4742
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4757
Function object for multiplication in the min-plus semiring.
Definition matrix.hpp:4789
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4804
Function object for multiplication in min-plus truncated semirings.
Definition matrix.hpp:5548
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:5561
Function object for returning the additive identity of the min-plus semiring.
Definition matrix.hpp:4826
constexpr Scalar operator()() const noexcept
Call operator for additive identity.
Definition matrix.hpp:4838
Function object for addition in ntp semirings.
Definition matrix.hpp:6055
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:6067
Function object for multiplication in an ntp semirings.
Definition matrix.hpp:6096
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:6110
Mat operator()(Mat const &x) const
Call operator.
Definition matrix.hpp:8547
Adapter for the identity element of the given type.
Definition adapters.hpp:246
void operator()(Mat &xy, Mat const &x, Mat const &y, size_t=0) const
Call operator.
Definition matrix.hpp:8583
Adapter for the product of two elements.
Definition adapters.hpp:284
T swap(T... args)
T tie(T... args)
T unique(T... args)