libsemigroups  v3.2.0
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
1324 // NOLINTNEXTLINE(whitespace/line_length)
1328 // clang-format on
1341 template <typename U>
1342 bool operator<(U const& that) const;
1343
1365 template <typename U>
1366 bool operator<(U const& that) const;
1367
1387 Row operator+(StaticRowView const& that);
1388
1407 void operator+=(StaticRowView const& that);
1408
1422 void operator+=(scalar_type a);
1423
1441 Row operator*(scalar_type a) const;
1442
1456 void operator*=(scalar_type a);
1457#endif
1458
1459 private:
1460 static constexpr size_t length_impl() noexcept {
1461 return C;
1462 }
1463 };
1464
1466 // DynamicRowViews - static arithmetic
1468
1469#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1470 // Doxygen needs to ignore this so that the actual implementation of
1471 // DynamicRowView gets documented.
1472 template <typename... Args>
1473 class DynamicRowView;
1474#endif
1475
1513 template <typename PlusOp,
1514 typename ProdOp,
1515 typename ZeroOp,
1516 typename OneOp,
1517 typename Scalar>
1518 class DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>
1519 : public detail::RowViewCommon<
1520 DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
1521 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>,
1522 public detail::
1523 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
1524 private:
1525 using DynamicMatrix_ = DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
1526 using RowViewCommon = detail::RowViewCommon<
1527 DynamicMatrix_,
1529 friend RowViewCommon;
1530
1531 public:
1533 using const_iterator = typename RowViewCommon::const_iterator;
1534
1536 using iterator = typename RowViewCommon::iterator;
1537
1539 using scalar_type = Scalar;
1540
1542 using scalar_reference = typename RowViewCommon::scalar_reference;
1543
1545 // clang-format off
1546 // NOLINTNEXTLINE(whitespace/line_length)
1547 using scalar_const_reference = typename RowViewCommon::scalar_const_reference;
1548 // clang-format on
1549
1551 using matrix_type = typename RowViewCommon::matrix_type;
1552
1554 using Row = typename matrix_type::Row;
1555
1557 DynamicRowView() = default;
1558
1561
1564
1567
1570
1572 explicit DynamicRowView(Row const& r)
1573 : RowViewCommon(r), _length(r.number_of_cols()) {}
1574
1575#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1576 using RowViewCommon::RowViewCommon;
1577
1578 // TODO(2) This constructor should be private
1579 DynamicRowView(DynamicMatrix_ const*, iterator const& it, size_t N)
1580 : RowViewCommon(it), _length(N) {}
1581
1582 using RowViewCommon::size;
1583#else
1585 size_t size() const noexcept;
1586
1588 iterator begin() noexcept;
1589
1592
1594 const_iterator cbegin() const noexcept;
1595
1598
1600 scalar_reference operator()(size_t i);
1601
1603 scalar_const_reference operator()(size_t i) const;
1604
1606 scalar_reference operator[](size_t i);
1607
1609 scalar_const_reference operator[](size_t i) const;
1610
1612 template <typename U>
1613 bool operator==(U const& that) const;
1614
1616 template <typename U>
1617 bool operator!=(U const& that) const;
1618
1620 template <typename U>
1621 bool operator<(U const& that) const;
1622
1624 template <typename U>
1625 bool operator<(U const& that) const;
1626
1628 Row operator+(DynamicRowView const& that);
1629
1631 void operator+=(DynamicRowView const& that);
1632
1634 void operator+=(scalar_type a);
1635
1637 Row operator*(scalar_type a) const;
1638
1640 void operator*=(scalar_type a);
1641#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1642
1643 private:
1644 size_t length_impl() const noexcept {
1645 return _length;
1646 }
1647 size_t _length;
1648 };
1649
1651 // DynamicRowViews - dynamic arithmetic
1653
1674 template <typename Semiring, typename Scalar>
1675 class DynamicRowView<Semiring, Scalar>
1676 : public detail::RowViewCommon<DynamicMatrix<Semiring, Scalar>,
1677 DynamicRowView<Semiring, Scalar>> {
1678 private:
1679 using DynamicMatrix_ = DynamicMatrix<Semiring, Scalar>;
1680 friend DynamicMatrix_;
1681 using RowViewCommon
1682 = detail::RowViewCommon<DynamicMatrix_,
1684 friend RowViewCommon;
1685
1686 public:
1688 using const_iterator = typename RowViewCommon::const_iterator;
1689
1691 using iterator = typename RowViewCommon::iterator;
1692
1694 using scalar_type = Scalar;
1695
1697 using scalar_reference = typename RowViewCommon::scalar_reference;
1698
1700 // clang-format off
1701 // NOLINTNEXTLINE(whitespace/line_length)
1702 using scalar_const_reference = typename RowViewCommon::scalar_const_reference;
1703 // clang-format on
1704
1706 using matrix_type = typename RowViewCommon::matrix_type;
1707
1709 using Row = typename matrix_type::Row;
1710
1712 DynamicRowView() = default;
1713
1715 DynamicRowView(DynamicRowView const&) = default;
1716
1718 DynamicRowView(DynamicRowView&&) = default;
1719
1721 DynamicRowView& operator=(DynamicRowView const&) = default;
1722
1725
1727 explicit DynamicRowView(Row const& r) : RowViewCommon(r), _matrix(&r) {}
1728
1729#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
1730 using RowViewCommon::RowViewCommon;
1731
1732 // TODO(2) This constructor should be private
1733 DynamicRowView(DynamicMatrix_ const* mat, iterator const& it, size_t)
1734 : RowViewCommon(it), _matrix(mat) {}
1735
1736 using RowViewCommon::size;
1737#else
1739 size_t size() const noexcept;
1740
1742 iterator begin() noexcept;
1743
1745 iterator end();
1746
1748 const_iterator cbegin() const noexcept;
1749
1751 iterator cend();
1752
1754 scalar_reference operator()(size_t i);
1755
1757 scalar_const_reference operator()(size_t i) const;
1758
1760 scalar_reference operator[](size_t i);
1761
1763 scalar_const_reference operator[](size_t i) const;
1764
1766 template <typename U>
1767 bool operator==(U const& that) const;
1768
1770 template <typename U>
1771 bool operator!=(U const& that) const;
1772
1774 template <typename U>
1775 bool operator<(U const& that) const;
1776
1778 template <typename U>
1779 bool operator<(U const& that) const;
1780
1782 Row operator+(DynamicRowView const& that);
1783
1785 void operator+=(DynamicRowView const& that);
1786
1788 void operator+=(scalar_type a);
1789
1791 Row operator*(scalar_type a) const;
1792
1794 void operator*=(scalar_type a);
1795#endif
1796
1797 private:
1798 size_t length_impl() const noexcept {
1799 return _matrix->number_of_cols();
1800 }
1801
1802 scalar_type plus_no_checks_impl(scalar_type x,
1803 scalar_type y) const noexcept {
1804 return _matrix->plus_no_checks_impl(x, y);
1805 }
1806
1807 scalar_type product_no_checks_impl(scalar_type x,
1808 scalar_type y) const noexcept {
1809 return _matrix->product_no_checks_impl(x, y);
1810 }
1811
1812 DynamicMatrix_ const* _matrix;
1813 };
1814
1816 // StaticMatrix with compile time semiring arithmetic
1818
1852 template <typename PlusOp,
1853 typename ProdOp,
1854 typename ZeroOp,
1855 typename OneOp,
1856 size_t R,
1857 size_t C,
1858 typename Scalar>
1860 : public detail::
1861 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
1862 public detail::MatrixCommon<
1863 std::array<Scalar, R * C>,
1864 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>,
1865 StaticRowView<PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar>> {
1867 // StaticMatrix - Aliases - private
1869
1870 using MatrixCommon = ::libsemigroups::detail::MatrixCommon<
1874 friend MatrixCommon;
1875
1876 public:
1878 // StaticMatrix - Aliases - public
1880
1882 using scalar_type = typename MatrixCommon::scalar_type;
1883
1885 using scalar_reference = typename MatrixCommon::scalar_reference;
1886
1888 // clang-format off
1889 // NOLINTNEXTLINE(whitespace/line_length)
1890 using scalar_const_reference = typename MatrixCommon::scalar_const_reference;
1891 // clang-format on
1892
1895
1898
1900 using Plus = PlusOp;
1901
1903 using Prod = ProdOp;
1904
1906 using Zero = ZeroOp;
1907
1909 using One = OneOp;
1910
1912 using iterator = typename MatrixCommon::iterator;
1913
1915 using const_iterator = typename MatrixCommon::const_iterator;
1916
1917 static constexpr size_t nr_rows = R;
1918 static constexpr size_t nr_cols = C;
1919
1921 // StaticMatrix - Constructors + destructor - public
1923
1941 : MatrixCommon(c) {
1942 static_assert(R == 1,
1943 "cannot construct Matrix from the given initializer list, "
1944 "incompatible dimensions");
1945 LIBSEMIGROUPS_ASSERT(c.size() == C);
1946 }
1947
1968 : MatrixCommon(m) {}
1969
1983 : MatrixCommon(m) {}
1984
2002 explicit StaticMatrix(RowView const& rv) : MatrixCommon(rv) {
2003 static_assert(
2004 R == 1,
2005 "cannot construct Matrix with more than one row from RowView!");
2006 }
2007
2011 StaticMatrix() = default;
2012
2016 StaticMatrix(StaticMatrix const&) = default;
2017
2022
2027
2032
2033#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2034 // For uniformity of interface, the args do nothing
2035 StaticMatrix(size_t r, size_t c) : StaticMatrix() {
2036 (void) r;
2037 (void) c;
2038 LIBSEMIGROUPS_ASSERT(r == number_of_rows());
2039 LIBSEMIGROUPS_ASSERT(c == number_of_cols());
2040 }
2041
2042 // For uniformity of interface, the first arg does nothing
2043 StaticMatrix(void const* ptr, std::initializer_list<scalar_type> const& c)
2044 : StaticMatrix(c) {
2045 (void) ptr;
2046 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2047 }
2048
2049 // For uniformity of interface, the first arg does nothing
2051 void const* ptr,
2053 : StaticMatrix(m) {
2054 (void) ptr;
2055 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2056 }
2057
2058 // For uniformity of interface, the first arg does nothing
2059 explicit StaticMatrix(void const* ptr, RowView const& rv)
2060 : StaticMatrix(rv) {
2061 (void) ptr;
2062 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2063 }
2064
2065 // For uniformity of interface, no arg used for anything
2066 StaticMatrix(void const* ptr, size_t r, size_t c) : StaticMatrix(r, c) {
2067 (void) ptr;
2068 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2069 }
2070#endif
2071
2072 ~StaticMatrix() = default;
2073
2074#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2075 static StaticMatrix one(size_t n) {
2076 // If specified the value of n must equal R or otherwise weirdness will
2077 // ensue...
2078 LIBSEMIGROUPS_ASSERT(n == 0 || n == R);
2079 (void) n;
2080#if defined(__APPLE__) && defined(__clang__) \
2081 && (__clang_major__ == 13 || __clang_major__ == 14)
2082 // With Apple clang version 13.1.6 (clang-1316.0.21.2.5) something goes
2083 // wrong and the value R is optimized away somehow, meaning that the
2084 // values on the diagonal aren't actually set. This only occurs when
2085 // libsemigroups is compiled with -O2 or higher.
2086 size_t volatile const m = R;
2087#else
2088 size_t const m = R;
2089#endif
2090 StaticMatrix x(m, m);
2091 std::fill(x.begin(), x.end(), ZeroOp()());
2092 for (size_t r = 0; r < m; ++r) {
2093 x(r, r) = OneOp()();
2094 }
2095 return x;
2096 }
2097
2098 static StaticMatrix one(void const* ptr, size_t n = 0) {
2099 (void) ptr;
2100 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2101 LIBSEMIGROUPS_ASSERT(n == 0 || n == R);
2102 return one(n);
2103 }
2104#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2105
2107 // StaticMatrix - member function aliases - public
2109#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2128 scalar_reference operator()(size_t r, size_t c);
2129
2143 scalar_reference at(size_t r, size_t c);
2144
2163 scalar_const_reference operator()(size_t r, size_t c) const;
2164
2178 scalar_const_reference at(size_t r, size_t c) const;
2179
2196 iterator begin() noexcept;
2197
2213
2231 const_iterator cbegin() const noexcept;
2232
2252
2266 bool operator==(StaticMatrix const& that) const;
2267
2269 bool operator==(RowView const& that) const;
2270
2282 bool operator!=(StaticMatrix const& that) const;
2283
2285 bool operator!=(RowView const& that) const;
2286
2300 bool operator<(StaticMatrix const& that) const;
2301
2303 bool operator<(RowView const& that) const;
2304
2318 bool operator>(StaticMatrix const& that) const;
2319
2336
2348 size_t number_of_rows() const noexcept;
2349
2361 size_t number_of_cols() const noexcept;
2362
2380 StaticMatrix operator+(StaticMatrix const& that);
2381
2398 void operator+=(StaticMatrix const& that);
2399
2401 void operator+=(RowView const& that);
2402
2414 void operator+=(scalar_type a);
2415
2433 StaticMatrix operator*(StaticMatrix const& that);
2434
2446 void operator*=(scalar_type a);
2447
2465 StaticMatrix const& y);
2466
2482 RowView row_no_checks(size_t i) const;
2483
2494 RowView row(size_t i) const;
2495
2509 template <typename T>
2510 void rows(T& x) const;
2511
2524 void swap(StaticMatrix& that) noexcept;
2525
2539
2555
2567 static StaticMatrix one() const;
2568
2582 size_t hash_value() const;
2583
2598 template <typename U>
2599 bool operator<=(U const& that) const;
2600
2615 template <typename U>
2616 bool operator>=(U const& that) const;
2617
2631
2646
2657 scalar_type scalar_zero() const noexcept;
2658
2669 scalar_type scalar_one() const noexcept;
2670
2682 semiring_type const* semiring() const noexcept;
2683
2684#else
2685 using MatrixCommon::at;
2686 using MatrixCommon::begin;
2687 using MatrixCommon::cbegin;
2688 using MatrixCommon::cend;
2689 using MatrixCommon::coords;
2690 using MatrixCommon::end;
2691 using MatrixCommon::hash_value;
2692 using MatrixCommon::number_of_cols;
2693 using MatrixCommon::number_of_rows;
2694 using MatrixCommon::one;
2695 using MatrixCommon::operator!=;
2696 using MatrixCommon::operator();
2697 using MatrixCommon::operator*;
2698 using MatrixCommon::operator*=;
2699 using MatrixCommon::operator+;
2700 using MatrixCommon::operator+=;
2701 using MatrixCommon::operator<; // NOLINT(whitespace/operators)
2702 using MatrixCommon::operator<=;
2703 using MatrixCommon::operator==;
2704 using MatrixCommon::operator>; // NOLINT(whitespace/operators)
2705 using MatrixCommon::operator>=;
2706 using MatrixCommon::product_inplace_no_checks;
2707 using MatrixCommon::row;
2708 using MatrixCommon::row_no_checks;
2709 using MatrixCommon::rows;
2710 using MatrixCommon::scalar_one;
2711 using MatrixCommon::scalar_zero;
2712 using MatrixCommon::semiring;
2713 using MatrixCommon::swap;
2714 using MatrixCommon::transpose;
2715 using MatrixCommon::transpose_no_checks;
2716#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2717
2718 private:
2720 // StaticMatrix - implementation of MatrixCommon requirements - private
2722
2723 static constexpr size_t number_of_rows_impl() noexcept {
2724 return R;
2725 }
2726 static constexpr size_t number_of_cols_impl() noexcept {
2727 return C;
2728 }
2729 };
2730
2732 // DynamicMatrix with compile time semiring arithmetic
2734
2768 template <typename PlusOp,
2769 typename ProdOp,
2770 typename ZeroOp,
2771 typename OneOp,
2772 typename Scalar>
2773 class DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>
2774 : public detail::MatrixDynamicDim<Scalar>,
2775 public detail::MatrixCommon<
2776 std::vector<Scalar>,
2777 DynamicMatrix<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>,
2778 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>,
2779 public detail::
2780 MatrixStaticArithmetic<PlusOp, ProdOp, ZeroOp, OneOp, Scalar> {
2781 using MatrixDynamicDim = ::libsemigroups::detail::MatrixDynamicDim<Scalar>;
2782 using MatrixCommon = ::libsemigroups::detail::MatrixCommon<
2785 DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>>;
2786 friend MatrixCommon;
2787
2788 public:
2790 using scalar_type = typename MatrixCommon::scalar_type;
2791
2793 using scalar_reference = typename MatrixCommon::scalar_reference;
2794
2796 // clang-format off
2797 // NOLINTNEXTLINE(whitespace/line_length)
2798 using scalar_const_reference = typename MatrixCommon::scalar_const_reference;
2799 // clang-format on
2800
2803
2805 using RowView = DynamicRowView<PlusOp, ProdOp, ZeroOp, OneOp, Scalar>;
2806
2808 using Plus = PlusOp;
2809
2811 using Prod = ProdOp;
2812
2814 using Zero = ZeroOp;
2815
2817 using One = OneOp;
2818
2824 using semiring_type = void;
2825
2829 DynamicMatrix() = default;
2830
2834 DynamicMatrix(DynamicMatrix const&) = default;
2835
2840
2845
2850
2868 DynamicMatrix(size_t r, size_t c) : MatrixDynamicDim(r, c), MatrixCommon() {
2869 resize(number_of_rows(), number_of_cols());
2870 }
2871
2891 : MatrixDynamicDim(1, c.size()), MatrixCommon(c) {}
2892
2914 : MatrixDynamicDim(m.size(), std::empty(m) ? 0 : m.begin()->size()),
2915 MatrixCommon(m) {}
2916
2932 : MatrixDynamicDim(m.size(), std::empty(m) ? 0 : m.begin()->size()),
2933 MatrixCommon(m) {}
2934
2946 explicit DynamicMatrix(RowView const& rv)
2947 : MatrixDynamicDim(1, rv.size()), MatrixCommon(rv) {}
2948
2949#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2950 // For uniformity of interface, the first arg does nothing
2951 DynamicMatrix(void const* ptr, size_t r, size_t c) : DynamicMatrix(r, c) {
2952 (void) ptr;
2953 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2954 }
2955
2956 // For uniformity of interface, the first arg does nothing
2957 DynamicMatrix(void const* ptr, std::initializer_list<scalar_type> const& c)
2958 : DynamicMatrix(c) {
2959 (void) ptr;
2960 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2961 }
2962
2963 // For uniformity of interface, the first arg does nothing
2964 DynamicMatrix(
2965 void const* ptr,
2966 std::initializer_list<std::initializer_list<scalar_type>> const& m)
2967 : DynamicMatrix(m) {
2968 (void) ptr;
2969 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2970 }
2971
2972 static DynamicMatrix one(void const* ptr, size_t n) {
2973 (void) ptr;
2974 LIBSEMIGROUPS_ASSERT(ptr == nullptr);
2975 return one(n);
2976 }
2977#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
2978
2979 ~DynamicMatrix() = default;
2980
2993 static DynamicMatrix one(size_t n) {
2994 DynamicMatrix x(n, n);
2995 std::fill(x.begin(), x.end(), ZeroOp()());
2996 for (size_t r = 0; r < n; ++r) {
2997 x(r, r) = OneOp()();
2998 }
2999 return x;
3000 }
3001
3002#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3004 scalar_reference at(size_t r, size_t c);
3005
3007 scalar_reference at(size_t r, size_t c) const;
3008
3010 iterator begin() noexcept;
3011
3013 const_iterator cbegin() noexcept;
3014
3016 const_iterator cend() noexcept;
3017
3019 std::pair<scalar_type, scalar_type> coords(const_iterator it) const;
3020
3022 iterator end() noexcept;
3023
3025 size_t hash_value() const;
3026
3028 size_t number_of_cols() const noexcept;
3029
3031 size_t number_of_rows() const noexcept;
3032
3034 bool operator!=(DynamicMatrix const& that) const;
3035
3037 bool operator!=(RowView const& that) const;
3038
3040 scalar_reference operator()(size_t r, size_t c);
3041
3043 scalar_const_reference operator()(size_t r, size_t c) const;
3056
3058 DynamicMatrix operator*(DynamicMatrix const& that);
3059
3061 void operator*=(scalar_type a);
3062
3064 DynamicMatrix operator+(DynamicMatrix const& that);
3065
3067 void operator+=(DynamicMatrix const& that);
3068
3070 void operator+=(RowView const& that);
3071
3083 void operator+=(scalar_type a);
3084
3086 bool operator<(DynamicMatrix const& that) const;
3087
3089 bool operator<(RowView const& that) const;
3090
3092 template <typename T>
3093 bool operator<=(T const& that) const;
3094
3096 bool operator==(DynamicMatrix const& that) const;
3097
3099 bool operator==(RowView const& that) const;
3100
3102 bool operator>(DynamicMatrix const& that) const;
3103
3105 template <typename T>
3106 bool operator>=(T const& that) const;
3107
3110 DynamicMatrix const& y);
3111
3113 RowView row(size_t i) const;
3114
3116 RowView row_no_checks(size_t i) const;
3117
3119 template <typename T>
3120 void rows(T& x) const;
3121
3123 scalar_type scalar_one() const noexcept;
3124
3126 scalar_type scalar_zero() const noexcept;
3127
3129 semiring_type const* semiring() const noexcept;
3130
3133
3136#else
3137 using MatrixCommon::at;
3138 using MatrixCommon::begin;
3139 using MatrixCommon::cbegin;
3140 using MatrixCommon::cend;
3141 using MatrixCommon::coords;
3142 using MatrixCommon::end;
3143 using MatrixCommon::hash_value;
3144 using MatrixCommon::number_of_cols;
3145 using MatrixCommon::number_of_rows;
3146 using MatrixCommon::one;
3147 using MatrixCommon::operator!=;
3148 using MatrixCommon::operator();
3149 using MatrixCommon::operator*;
3150 using MatrixCommon::operator*=;
3151 using MatrixCommon::operator+;
3152 using MatrixCommon::operator+=;
3153 using MatrixCommon::operator<; // NOLINT(whitespace/operators)
3154 using MatrixCommon::operator<=;
3155 using MatrixCommon::operator==;
3156 using MatrixCommon::operator>; // NOLINT(whitespace/operators)
3157 using MatrixCommon::operator>=;
3158 using MatrixCommon::product_inplace_no_checks;
3159 using MatrixCommon::row;
3160 using MatrixCommon::row_no_checks;
3161 using MatrixCommon::rows;
3162 using MatrixCommon::scalar_one;
3163 using MatrixCommon::scalar_zero;
3164 using MatrixCommon::semiring;
3165 // using MatrixCommon::swap; // Don't want this use the one below.
3166 using MatrixCommon::transpose;
3167 using MatrixCommon::transpose_no_checks;
3168#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3169
3171 void swap(DynamicMatrix& that) noexcept {
3172 static_cast<MatrixDynamicDim&>(*this).swap(
3173 static_cast<MatrixDynamicDim&>(that));
3174 static_cast<MatrixCommon&>(*this).swap(static_cast<MatrixCommon&>(that));
3175 }
3176
3177 private:
3178 using MatrixCommon::resize;
3179 };
3180
3182 // DynamicMatrix with runtime semiring arithmetic
3184
3219 template <typename Semiring, typename Scalar>
3220 class DynamicMatrix<Semiring, Scalar>
3221 : public detail::MatrixDynamicDim<Scalar>,
3222 public detail::MatrixCommon<std::vector<Scalar>,
3223 DynamicMatrix<Semiring, Scalar>,
3224 DynamicRowView<Semiring, Scalar>,
3225 Semiring> {
3226 using MatrixCommon = detail::MatrixCommon<std::vector<Scalar>,
3228 DynamicRowView<Semiring, Scalar>,
3229 Semiring>;
3230 friend MatrixCommon;
3231 using MatrixDynamicDim = ::libsemigroups::detail::MatrixDynamicDim<Scalar>;
3232
3233 public:
3235 using scalar_type = typename MatrixCommon::scalar_type;
3236
3238 using scalar_reference = typename MatrixCommon::scalar_reference;
3239
3241 // clang-format off
3242 // NOLINTNEXTLINE(whitespace/line_length)
3243 using scalar_const_reference = typename MatrixCommon::scalar_const_reference;
3244 // clang-format on
3245
3248
3250 using RowView = DynamicRowView<Semiring, Scalar>;
3251
3252 friend RowView;
3253
3255 using semiring_type = Semiring;
3256
3262 DynamicMatrix() = delete;
3263
3265 DynamicMatrix(DynamicMatrix const&) = default;
3266
3269
3272
3275
3290 DynamicMatrix(Semiring const* sr, size_t r, size_t c)
3291 : MatrixDynamicDim(r, c), MatrixCommon(), _semiring(sr) {
3292 resize(number_of_rows(), number_of_cols());
3293 }
3294
3311 Semiring const* sr,
3313 : MatrixDynamicDim(rws.size(),
3314 std::empty(rws) ? 0 : rws.begin()->size()),
3315 MatrixCommon(rws),
3316 _semiring(sr) {}
3317
3333 explicit DynamicMatrix(Semiring const* sr,
3335 : MatrixDynamicDim(rws.size(), (rws.empty() ? 0 : rws.begin()->size())),
3336 MatrixCommon(rws),
3337 _semiring(sr) {}
3338
3352 explicit DynamicMatrix(Semiring const* sr,
3354 : MatrixDynamicDim(1, rw.size()), MatrixCommon(rw), _semiring(sr) {}
3355
3367 explicit DynamicMatrix(RowView const& rv)
3368 : MatrixDynamicDim(1, rv.size()),
3369 MatrixCommon(rv),
3370 _semiring(rv._matrix->semiring()) {}
3371
3386 // No static DynamicMatrix::one(size_t n) because we need a semiring!
3387 static DynamicMatrix one(Semiring const* semiring, size_t n) {
3388 DynamicMatrix x(semiring, n, n);
3389 std::fill(x.begin(), x.end(), x.scalar_zero());
3390 for (size_t r = 0; r < n; ++r) {
3391 x(r, r) = x.scalar_one();
3392 }
3393 return x;
3394 }
3395
3396 ~DynamicMatrix() = default;
3397
3398#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3400 scalar_reference at(size_t r, size_t c);
3401
3403 scalar_reference at(size_t r, size_t c) const;
3404
3406 iterator begin() noexcept;
3407
3409 const_iterator cbegin() noexcept;
3410
3412 const_iterator cend() noexcept;
3413
3415 std::pair<scalar_type, scalar_type> coords(const_iterator it) const;
3416
3418 iterator end() noexcept;
3419
3421 size_t hash_value() const;
3422
3424 size_t number_of_cols() const noexcept;
3425
3427 size_t number_of_rows() const noexcept;
3428
3430 bool operator!=(DynamicMatrix const& that) const;
3431
3433 bool operator!=(RowView const& that) const;
3434
3436 scalar_reference operator()(size_t r, size_t c);
3437
3439 scalar_const_reference operator()(size_t r, size_t c) const;
3452
3454 DynamicMatrix operator*(DynamicMatrix const& that);
3455
3457 void operator*=(scalar_type a);
3458
3460 DynamicMatrix operator+(DynamicMatrix const& that);
3461
3463 void operator+=(DynamicMatrix const& that);
3464
3466 void operator+=(RowView const& that);
3467
3479 void operator+=(scalar_type a);
3480
3482 bool operator<(DynamicMatrix const& that) const;
3483
3485 bool operator<(RowView const& that) const;
3486
3488 template <typename T>
3489 bool operator<=(T const& that) const;
3490
3492 bool operator==(DynamicMatrix const& that) const;
3493
3495 bool operator==(RowView const& that) const;
3496
3498 bool operator>(DynamicMatrix const& that) const;
3499
3501 template <typename T>
3502 bool operator>=(T const& that) const;
3503
3506 DynamicMatrix const& y);
3507
3509 RowView row(size_t i) const;
3510
3512 RowView row_no_checks(size_t i) const;
3513
3515 template <typename T>
3516 void rows(T& x) const;
3517
3519 scalar_type scalar_one() const noexcept;
3520
3522 scalar_type scalar_zero() const noexcept;
3523
3525 semiring_type const* semiring() const noexcept;
3526
3529
3532#else
3533 using MatrixCommon::at;
3534 using MatrixCommon::begin;
3535 using MatrixCommon::cbegin;
3536 using MatrixCommon::cend;
3537 using MatrixCommon::coords;
3538 using MatrixCommon::end;
3539 using MatrixCommon::hash_value;
3540 using MatrixCommon::number_of_cols;
3541 using MatrixCommon::number_of_rows;
3542 using MatrixCommon::one;
3543 using MatrixCommon::operator!=;
3544 using MatrixCommon::operator();
3545 using MatrixCommon::operator*;
3546 using MatrixCommon::operator*=;
3547 using MatrixCommon::operator+;
3548 using MatrixCommon::operator+=;
3549 using MatrixCommon::operator<; // NOLINT(whitespace/operators)
3550 using MatrixCommon::operator<=;
3551 using MatrixCommon::operator==;
3552 using MatrixCommon::operator>; // NOLINT(whitespace/operators)
3553 using MatrixCommon::operator>=;
3554 using MatrixCommon::product_inplace_no_checks;
3555 using MatrixCommon::row;
3556 using MatrixCommon::row_no_checks;
3557 using MatrixCommon::rows;
3558 using MatrixCommon::scalar_one;
3559 using MatrixCommon::scalar_zero;
3560 using MatrixCommon::semiring;
3561 // using MatrixCommon::swap; // Don't want this use the one below.
3562 using MatrixCommon::transpose;
3563 using MatrixCommon::transpose_no_checks;
3564#endif // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
3565
3567 void swap(DynamicMatrix& that) noexcept {
3568 static_cast<MatrixDynamicDim&>(*this).swap(
3569 static_cast<MatrixDynamicDim&>(that));
3570 static_cast<MatrixCommon&>(*this).swap(static_cast<MatrixCommon&>(that));
3571 std::swap(_semiring, that._semiring);
3572 }
3573
3574 private:
3575 using MatrixCommon::resize;
3576
3577 scalar_type plus_no_checks_impl(scalar_type x,
3578 scalar_type y) const noexcept {
3579 return _semiring->plus_no_checks(x, y);
3580 }
3581
3582 scalar_type product_no_checks_impl(scalar_type x,
3583 scalar_type y) const noexcept {
3584 return _semiring->product_no_checks(x, y);
3585 }
3586
3587 scalar_type one_impl() const noexcept {
3588 return _semiring->scalar_one();
3589 }
3590
3591 scalar_type zero_impl() const noexcept {
3592 return _semiring->scalar_zero();
3593 }
3594
3595 Semiring const* semiring_impl() const noexcept {
3596 return _semiring;
3597 }
3598
3599 Semiring const* _semiring;
3600 };
3601
3603 // Helper structs to check if matrix is static, or has a pointer to a
3604 // semiring
3606
3607 namespace detail {
3608 template <typename T>
3609 struct IsStaticMatrixHelper : std::false_type {};
3610
3611 template <typename PlusOp,
3612 typename ProdOp,
3613 typename ZeroOp,
3614 typename OneOp,
3615 size_t R,
3616 size_t C,
3617 typename Scalar>
3618 struct IsStaticMatrixHelper<
3619 StaticMatrix<PlusOp, ProdOp, ZeroOp, OneOp, R, C, Scalar>>
3620 : std::true_type {};
3621
3622 template <typename T>
3623 struct IsMatWithSemiringHelper : std::false_type {};
3624
3625 template <typename Semiring, typename Scalar>
3626 struct IsMatWithSemiringHelper<DynamicMatrix<Semiring, Scalar>>
3627 : std::true_type {};
3628
3629 template <typename S, typename T = void>
3630 struct IsTruncMatHelper : std::false_type {};
3631
3632 } // namespace detail
3633
3644 template <typename T>
3645 constexpr bool IsStaticMatrix = detail::IsStaticMatrixHelper<T>::value;
3646
3657 template <typename T>
3659
3670 template <typename T>
3671 static constexpr bool IsMatWithSemiring
3672 = detail::IsMatWithSemiringHelper<T>::value;
3673
3674 namespace detail {
3675
3676 template <typename T>
3677 static constexpr bool IsTruncMat = IsTruncMatHelper<T>::value;
3678
3679 template <typename Mat>
3680 void throw_if_semiring_nullptr(Mat const& m) {
3681 if (IsMatWithSemiring<Mat> && m.semiring() == nullptr) {
3683 "the matrix's pointer to a semiring is nullptr!")
3684 }
3685 }
3686
3687 template <typename Mat, typename Container>
3688 auto throw_if_bad_dim(Container const& m)
3689 -> std::enable_if_t<IsStaticMatrix<Mat>> {
3690 // Only call this if you've already called throw_if_any_row_wrong_size
3691 uint64_t const R = m.size();
3692 uint64_t const C = std::empty(m) ? 0 : m.begin()->size();
3693 if (R != Mat::nr_rows || C != Mat::nr_cols) {
3695 "invalid argument, cannot initialize an {}x{} matrix with compile "
3696 "time dimension, with an {}x{} container",
3697 Mat::nr_rows,
3698 Mat::nr_cols,
3699 R,
3700 C);
3701 }
3702 }
3703
3704 template <typename Mat, typename Container>
3705 auto throw_if_bad_dim(Container const&)
3706 -> std::enable_if_t<IsDynamicMatrix<Mat>> {}
3707 } // namespace detail
3708
3717 namespace matrix {
3718
3732 template <typename Mat>
3733 constexpr auto threshold(Mat const&) noexcept
3734 -> std::enable_if_t<!detail::IsTruncMat<Mat>,
3735 typename Mat::scalar_type> {
3736 return UNDEFINED;
3737 }
3738
3752 template <typename Mat>
3753 constexpr auto threshold(Mat const&) noexcept
3754 -> std::enable_if_t<detail::IsTruncMat<Mat> && !IsMatWithSemiring<Mat>,
3755 typename Mat::scalar_type> {
3756 return detail::IsTruncMatHelper<Mat>::threshold;
3757 }
3758
3774 template <typename Mat>
3775 auto threshold(Mat const& x) noexcept
3776 -> std::enable_if_t<detail::IsTruncMat<Mat> && IsMatWithSemiring<Mat>,
3777 typename Mat::scalar_type> {
3778 return x.semiring()->threshold();
3779 }
3780 } // namespace matrix
3781
3783 // Boolean matrices - compile time semiring arithmetic
3785
3819
3842 constexpr bool operator()(bool x, bool y) const noexcept {
3843 return x || y;
3844 }
3845 };
3846
3869 constexpr bool operator()(bool x, bool y) const noexcept {
3870 return x & y;
3871 }
3872 };
3873
3883 struct BooleanOne {
3894 constexpr bool operator()() const noexcept {
3895 return true;
3896 }
3897 };
3898
3919 constexpr bool operator()() const noexcept {
3920 return false;
3921 }
3922 };
3923
3932 // The use of `int` rather than `bool` as the scalar type for dynamic
3933 // boolean matrices is intentional, because the bit iterators implemented in
3934 // std::vector<bool> entail a significant performance penalty.
3936 = DynamicMatrix<BooleanPlus, BooleanProd, BooleanZero, BooleanOne, int>;
3937
3949 template <size_t R, size_t C>
3953 BooleanOne,
3954 R,
3955 C,
3956 int>;
3957
3971 // FLS + JDM considered adding BMat8 and decided it wasn't a good idea.
3972 template <size_t R = 0, size_t C = R>
3973 using BMat
3974 = std::conditional_t<R == 0 || C == 0, DynamicBMat, StaticBMat<R, C>>;
3975
3976 namespace detail {
3977 template <typename T>
3978 struct IsBMatHelper : std::false_type {};
3979
3980 template <size_t R, size_t C>
3981 struct IsBMatHelper<StaticBMat<R, C>> : std::true_type {};
3982
3983 template <>
3984 struct IsBMatHelper<DynamicBMat> : std::true_type {};
3985
3986 template <typename T>
3987 struct BitSetCapacity {
3988 static constexpr size_t value = BitSet<1>::max_size();
3989 };
3990
3991 template <size_t R, size_t C>
3992 struct BitSetCapacity<StaticBMat<R, C>> {
3993 static_assert(R == C, "the number of rows and columns must be equal");
3994 static constexpr size_t value = R;
3995 };
3996 } // namespace detail
3997
4008 template <typename T>
4009 static constexpr bool IsBMat = detail::IsBMatHelper<T>::value;
4010
4011 namespace detail {
4012 // This function is required for exceptions and to_human_readable_repr, so
4013 // that if we encounter an entry of a matrix (Scalar type), then it can be
4014 // printed correctly. If we just did fmt::format("{}", val) and val ==
4015 // POSITIVE_INFINITY, but the type of val is, say, size_t, then this
4016 // wouldn't use the formatter for PositiveInfinity.
4017 //
4018 // Also in fmt v11.1.4 the custom formatter for POSITIVE_INFINITY and
4019 // NEGATIVE_INFINITY stopped working (and I wasn't able to figure out why)
4020 template <typename Scalar>
4021 std::string entry_repr(Scalar a) {
4022 if constexpr (std::is_same_v<Scalar, NegativeInfinity>
4023 || std::is_signed_v<Scalar>) {
4024 if (a == NEGATIVE_INFINITY) {
4025 return u8"-\u221E";
4026 }
4027 }
4028 if (a == POSITIVE_INFINITY) {
4029 return u8"+\u221E";
4030 }
4031 return fmt::format("{}", a);
4032 }
4033 } // namespace detail
4034
4035 namespace matrix {
4036
4052 //! but a matrix shouldn't contain values except \c 0 and \c 1.
4053 template <typename Mat>
4054 std::enable_if_t<IsBMat<Mat>> throw_if_bad_entry(Mat const& m) {
4055 using scalar_type = typename Mat::scalar_type;
4056 auto it = std::find_if_not(
4057 m.cbegin(), m.cend(), [](scalar_type x) { return x == 0 || x == 1; });
4058 if (it != m.cend()) {
4059 auto [r, c] = m.coords(it);
4061 "invalid entry, expected 0 or 1 but found {} in entry ({}, {})",
4062 detail::entry_repr(*it),
4063 r,
4064 c);
4065 }
4066 }
4067
4085 template <typename Mat>
4086 std::enable_if_t<IsBMat<Mat>>
4087 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4088 if (val != 0 && val != 1) {
4089 LIBSEMIGROUPS_EXCEPTION("invalid entry, expected 0 or 1 but found {}",
4090 detail::entry_repr(val));
4091 }
4092 }
4093 } // namespace matrix
4094
4096 // Integer matrices - compile time semiring arithmetic
4098
4126
4138 //! \tparam Scalar the type of the entries in the matrix.
4139 template <typename Scalar>
4140 struct IntegerPlus {
4151 //! \exceptions
4152 //! \noexcept
4153 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
4154 return x + y;
4155 }
4156 };
4157
4169 //! \tparam Scalar the type of the entries in the matrix.
4170 template <typename Scalar>
4171 struct IntegerProd {
4182 //! \exceptions
4183 //! \noexcept
4184 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
4185 return x * y;
4186 }
4187 };
4188
4197 //! the additive identity of the integer semiring.
4198 template <typename Scalar>
4199 struct IntegerZero {
4207 //! \exceptions
4208 //! \noexcept
4209 constexpr Scalar operator()() const noexcept {
4210 return 0;
4211 }
4212 };
4213
4222 //! the multiplicative identity of the integer semiring.
4223 template <typename Scalar>
4224 struct IntegerOne {
4232 //! \exceptions
4233 //! \noexcept
4234 constexpr Scalar operator()() const noexcept {
4235 return 1;
4236 }
4237 };
4238
4249 template <typename Scalar>
4250 using DynamicIntMat = DynamicMatrix<IntegerPlus<Scalar>,
4254 Scalar>;
4255
4272 template <size_t R, size_t C, typename Scalar>
4277 R,
4278 C,
4279 Scalar>;
4280
4297 template <size_t R = 0, size_t C = R, typename Scalar = int>
4298 using IntMat = std::conditional_t<R == 0 || C == 0,
4301 namespace detail {
4302 template <typename T>
4303 struct IsIntMatHelper : std::false_type {};
4304
4305 template <size_t R, size_t C, typename Scalar>
4306 struct IsIntMatHelper<StaticIntMat<R, C, Scalar>> : std::true_type {};
4307
4308 template <typename Scalar>
4309 struct IsIntMatHelper<DynamicIntMat<Scalar>> : std::true_type {};
4310 } // namespace detail
4311
4322 template <typename T>
4323 static constexpr bool IsIntMat = detail::IsIntMatHelper<T>::value;
4324
4325 namespace matrix {
4339 //! \param x the matrix to check.
4340 template <typename Mat>
4341 std::enable_if_t<IsIntMat<Mat>> throw_if_bad_entry(Mat const& x) {
4342 using scalar_type = typename Mat::scalar_type;
4343 auto it = std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4344 return val == POSITIVE_INFINITY || val == NEGATIVE_INFINITY;
4345 });
4346 if (it != x.cend()) {
4347 auto [r, c] = x.coords(it);
4349 "invalid entry, expected entries to be integers, "
4350 "but found {} in entry ({}, {})",
4351 detail::entry_repr(*it),
4352 r,
4353 c);
4354 }
4355 }
4356
4373 template <typename Mat>
4374 std::enable_if_t<IsIntMat<Mat>>
4375 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4376 if (val == POSITIVE_INFINITY || val == NEGATIVE_INFINITY) {
4378 "invalid entry, expected entries to be integers, "
4379 "but found {}",
4380 detail::entry_repr(val));
4381 }
4382 }
4383 } // namespace matrix
4384
4386 // Max-plus matrices
4416
4440 // Static arithmetic
4441 template <typename Scalar>
4442 struct MaxPlusPlus {
4443 static_assert(std::is_signed<Scalar>::value,
4444 "MaxPlus requires a signed integer type as parameter!");
4455 //! \exceptions
4456 //! \noexcept
4457 Scalar operator()(Scalar x, Scalar y) const noexcept {
4458 if (x == NEGATIVE_INFINITY) {
4459 return y;
4460 } else if (y == NEGATIVE_INFINITY) {
4461 return x;
4462 }
4463 return std::max(x, y);
4464 }
4465 };
4466
4487 //! integer type).
4488 template <typename Scalar>
4489 struct MaxPlusProd {
4490 static_assert(std::is_signed<Scalar>::value,
4491 "MaxPlus requires a signed integer type as parameter!");
4502 //! \exceptions
4503 //! \noexcept
4504 Scalar operator()(Scalar x, Scalar y) const noexcept {
4505 if (x == NEGATIVE_INFINITY || y == NEGATIVE_INFINITY) {
4506 return NEGATIVE_INFINITY;
4507 }
4508 return x + y;
4509 }
4510 };
4511
4524 //! integer type).
4525 template <typename Scalar>
4526 struct MaxPlusZero {
4527 static_assert(std::is_signed<Scalar>::value,
4528 "MaxPlus requires a signed integer type as parameter!");
4536 //! \exceptions
4537 //! \noexcept
4538 constexpr Scalar operator()() const noexcept {
4539 return NEGATIVE_INFINITY;
4540 }
4541 };
4542
4553 template <typename Scalar>
4554 using DynamicMaxPlusMat = DynamicMatrix<MaxPlusPlus<Scalar>,
4558 Scalar>;
4559
4572 template <size_t R, size_t C, typename Scalar>
4577 R,
4578 C,
4579 Scalar>;
4580
4596 template <size_t R = 0, size_t C = R, typename Scalar = int>
4597 using MaxPlusMat = std::conditional_t<R == 0 || C == 0,
4600
4601 namespace detail {
4602 template <typename T>
4603 struct IsMaxPlusMatHelper : std::false_type {};
4604
4605 template <size_t R, size_t C, typename Scalar>
4606 struct IsMaxPlusMatHelper<StaticMaxPlusMat<R, C, Scalar>> : std::true_type {
4607 };
4608
4609 template <typename Scalar>
4610 struct IsMaxPlusMatHelper<DynamicMaxPlusMat<Scalar>> : std::true_type {};
4611 } // namespace detail
4612
4623 template <typename T>
4624 static constexpr bool IsMaxPlusMat = detail::IsMaxPlusMatHelper<T>::value;
4625
4626 namespace matrix {
4641 //! \ref POSITIVE_INFINITY.
4642 template <typename Mat>
4643 auto throw_if_bad_entry(Mat const& x)
4644 -> std::enable_if_t<IsMaxPlusMat<Mat>> {
4645 using scalar_type = typename Mat::scalar_type;
4646 auto it = std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4647 return val == POSITIVE_INFINITY;
4648 });
4649 if (it != x.cend()) {
4650 auto [r, c] = x.coords(it);
4652 "invalid entry, expected entries to be integers or {} (= {}), "
4653 "but found {} (= {}) in entry ({}, {})",
4654 entry_repr(NEGATIVE_INFINITY),
4655 static_cast<scalar_type>(NEGATIVE_INFINITY),
4656 entry_repr(POSITIVE_INFINITY),
4657 static_cast<scalar_type>(POSITIVE_INFINITY),
4658 r,
4659 c);
4660 }
4661 }
4662
4678 template <typename Mat>
4679 std::enable_if_t<IsMaxPlusMat<Mat>>
4680 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4681 if (val == POSITIVE_INFINITY) {
4682 using scalar_type = typename Mat::scalar_type;
4683 LIBSEMIGROUPS_EXCEPTION("invalid entry, expected entries to be "
4684 "integers or {} (= {}) but found {} (= {})",
4685 entry_repr(NEGATIVE_INFINITY),
4686 static_cast<scalar_type>(NEGATIVE_INFINITY),
4687 entry_repr(POSITIVE_INFINITY),
4688 static_cast<scalar_type>(POSITIVE_INFINITY));
4689 }
4690 }
4691 } // namespace matrix
4692
4694 // Min-plus matrices
4696
4725
4748 // Static arithmetic
4749 template <typename Scalar>
4750 struct MinPlusPlus {
4751 static_assert(std::is_signed<Scalar>::value,
4752 "MinPlus requires a signed integer type as parameter!");
4763 //! \exceptions
4764 //! \noexcept
4765 Scalar operator()(Scalar x, Scalar y) const noexcept {
4766 if (x == POSITIVE_INFINITY) {
4767 return y;
4768 } else if (y == POSITIVE_INFINITY) {
4769 return x;
4770 }
4771 return std::min(x, y);
4772 }
4773 };
4774
4795 //! integer type).
4796 template <typename Scalar>
4797 struct MinPlusProd {
4798 static_assert(std::is_signed<Scalar>::value,
4799 "MinPlus requires a signed integer type as parameter!");
4810 //! \exceptions
4811 //! \noexcept
4812 Scalar operator()(Scalar x, Scalar y) const noexcept {
4813 if (x == POSITIVE_INFINITY || y == POSITIVE_INFINITY) {
4814 return POSITIVE_INFINITY;
4815 }
4816 return x + y;
4817 }
4818 };
4819
4832 //! integer type).
4833 template <typename Scalar>
4834 struct MinPlusZero {
4835 static_assert(std::is_signed<Scalar>::value,
4836 "MinPlus requires a signed integer type as parameter!");
4844 //! \exceptions
4845 //! \noexcept
4846 constexpr Scalar operator()() const noexcept {
4847 return POSITIVE_INFINITY;
4848 }
4849 };
4850
4861 template <typename Scalar>
4862 using DynamicMinPlusMat = DynamicMatrix<MinPlusPlus<Scalar>,
4866 Scalar>;
4867
4880 template <size_t R, size_t C, typename Scalar>
4885 R,
4886 C,
4887 Scalar>;
4904 template <size_t R = 0, size_t C = R, typename Scalar = int>
4905 using MinPlusMat = std::conditional_t<R == 0 || C == 0,
4908
4909 namespace detail {
4910 template <typename T>
4911 struct IsMinPlusMatHelper : std::false_type {};
4912
4913 template <size_t R, size_t C, typename Scalar>
4914 struct IsMinPlusMatHelper<StaticMinPlusMat<R, C, Scalar>> : std::true_type {
4915 };
4916
4917 template <typename Scalar>
4918 struct IsMinPlusMatHelper<DynamicMinPlusMat<Scalar>> : std::true_type {};
4919 } // namespace detail
4920
4931 template <typename T>
4932 static constexpr bool IsMinPlusMat = detail::IsMinPlusMatHelper<T>::value;
4933
4934 namespace matrix {
4949 //! \ref NEGATIVE_INFINITY.
4950 template <typename Mat>
4951 std::enable_if_t<IsMinPlusMat<Mat>> throw_if_bad_entry(Mat const& x) {
4952 using scalar_type = typename Mat::scalar_type;
4953 auto it = std::find_if(x.cbegin(), x.cend(), [](scalar_type val) {
4954 return val == NEGATIVE_INFINITY;
4955 });
4956 if (it != x.cend()) {
4957 auto [r, c] = x.coords(it);
4959 "invalid entry, expected entries to be integers or {} (= {}), "
4960 "but found {} (= {}) in entry ({}, {})",
4961 entry_repr(POSITIVE_INFINITY),
4962 static_cast<scalar_type>(POSITIVE_INFINITY),
4963 entry_repr(NEGATIVE_INFINITY),
4964 static_cast<scalar_type>(NEGATIVE_INFINITY),
4965 r,
4966 c);
4967 }
4968 }
4969
4985 template <typename Mat>
4986 std::enable_if_t<IsMinPlusMat<Mat>>
4987 throw_if_bad_entry(Mat const&, typename Mat::scalar_type val) {
4988 if (val == NEGATIVE_INFINITY) {
4989 using scalar_type = typename Mat::scalar_type;
4990 LIBSEMIGROUPS_EXCEPTION("invalid entry, expected entries to be "
4991 "integers or {} (= {}) but found {} (= {})",
4992 entry_repr(POSITIVE_INFINITY),
4993 static_cast<scalar_type>(POSITIVE_INFINITY),
4994 entry_repr(NEGATIVE_INFINITY),
4995 static_cast<scalar_type>(NEGATIVE_INFINITY));
4996 }
4997 }
4998 } // namespace matrix
4999
5001 // Max-plus matrices with threshold
5003
5049
5074 //! integer type).
5075 template <size_t T, typename Scalar>
5076 struct MaxPlusTruncProd {
5077 static_assert(std::is_signed<Scalar>::value,
5078 "MaxPlus requires a signed integer type as parameter!");
5089 //! \exceptions
5090 //! \noexcept
5091 Scalar operator()(Scalar x, Scalar y) const noexcept {
5092 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= static_cast<Scalar>(T))
5093 || x == NEGATIVE_INFINITY);
5094 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= static_cast<Scalar>(T))
5095 || y == NEGATIVE_INFINITY);
5096 if (x == NEGATIVE_INFINITY || y == NEGATIVE_INFINITY) {
5097 return NEGATIVE_INFINITY;
5098 }
5099 return std::min(x + y, static_cast<Scalar>(T));
5100 }
5101 };
5102
5116 //! signed integer type (defaults to \c int).
5117 template <typename Scalar = int>
5118 class MaxPlusTruncSemiring {
5119 static_assert(std::is_signed<Scalar>::value,
5120 "MaxPlus requires a signed integer type as parameter!");
5121
5122 public:
5126 MaxPlusTruncSemiring() = delete;
5127
5131 MaxPlusTruncSemiring(MaxPlusTruncSemiring const&) noexcept = default;
5132
5136 MaxPlusTruncSemiring(MaxPlusTruncSemiring&&) noexcept = default;
5137
5141 MaxPlusTruncSemiring& operator=(MaxPlusTruncSemiring const&) noexcept
5142 = default;
5143
5147 MaxPlusTruncSemiring& operator=(MaxPlusTruncSemiring&&) noexcept = default;
5148
5149 ~MaxPlusTruncSemiring() = default;
5150
5159 //! \complexity
5160 //! Constant.
5161 explicit MaxPlusTruncSemiring(Scalar threshold) : _threshold(threshold) {
5162 if (threshold < 0) {
5163 LIBSEMIGROUPS_EXCEPTION("expected non-negative value, found {}",
5164 threshold);
5165 }
5166 }
5167
5176 //! \exceptions
5177 //! \noexcept
5178 static constexpr Scalar scalar_one() noexcept {
5179 return 0;
5180 }
5181
5190 //! \exceptions
5191 //! \noexcept
5192 static constexpr Scalar scalar_zero() noexcept {
5193 return NEGATIVE_INFINITY;
5194 }
5195
5218 //! \complexity
5219 //! Constant.
5220 Scalar product_no_checks(Scalar x, Scalar y) const noexcept {
5221 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5222 || x == NEGATIVE_INFINITY);
5223 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5224 || y == NEGATIVE_INFINITY);
5225 if (x == NEGATIVE_INFINITY || y == NEGATIVE_INFINITY) {
5226 return NEGATIVE_INFINITY;
5227 }
5228 return std::min(x + y, _threshold);
5229 }
5230
5253 //! \complexity
5254 //! Constant.
5255 Scalar plus_no_checks(Scalar x, Scalar y) const noexcept {
5256 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5257 || x == NEGATIVE_INFINITY);
5258 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5259 || y == NEGATIVE_INFINITY);
5260 if (x == NEGATIVE_INFINITY) {
5261 return y;
5262 } else if (y == NEGATIVE_INFINITY) {
5263 return x;
5264 }
5265 return std::max(x, y);
5266 }
5267
5278 //! \complexity
5279 //! Constant.
5280 Scalar threshold() const noexcept {
5281 return _threshold;
5282 }
5283
5284 public:
5285 Scalar const _threshold;
5286 };
5287
5300 template <size_t T, typename Scalar>
5301 using DynamicMaxPlusTruncMat = DynamicMatrix<MaxPlusPlus<Scalar>,
5305 Scalar>;
5306
5320 template <size_t T, size_t R, size_t C, typename Scalar>
5325 R,
5326 C,
5327 Scalar>;
5346 template <size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
5347 using MaxPlusTruncMat = std::conditional_t<
5348 R == 0 || C == 0,
5349 std::conditional_t<T == 0,
5350 DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>,
5353
5354 namespace detail {
5355 template <typename T>
5356 struct IsMaxPlusTruncMatHelper : std::false_type {};
5357
5358 template <size_t T, size_t R, size_t C, typename Scalar>
5359 struct IsMaxPlusTruncMatHelper<StaticMaxPlusTruncMat<T, R, C, Scalar>>
5360 : std::true_type {
5361 static constexpr Scalar threshold = T;
5362 };
5363
5364 template <size_t T, typename Scalar>
5365 struct IsMaxPlusTruncMatHelper<DynamicMaxPlusTruncMat<T, Scalar>>
5366 : std::true_type {
5367 static constexpr Scalar threshold = T;
5368 };
5369
5370 template <typename Scalar>
5371 struct IsMaxPlusTruncMatHelper<
5372 DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>> : std::true_type {
5373 static constexpr Scalar threshold = UNDEFINED;
5374 };
5375 } // namespace detail
5376
5388 template <typename T>
5389 static constexpr bool IsMaxPlusTruncMat
5390 = detail::IsMaxPlusTruncMatHelper<T>::value;
5391
5392 namespace detail {
5393 template <typename T>
5394 struct IsTruncMatHelper<T, std::enable_if_t<IsMaxPlusTruncMat<T>>>
5395 : std::true_type {
5396 static constexpr typename T::scalar_type threshold
5397 = IsMaxPlusTruncMatHelper<T>::threshold;
5398 };
5399 } // namespace detail
5400
5401 namespace matrix {
5419 //! (only applies to matrices with run time arithmetic).
5420 template <typename Mat>
5421 std::enable_if_t<IsMaxPlusTruncMat<Mat>> throw_if_bad_entry(Mat const& m) {
5422 // TODO(1) to tpp
5423 detail::throw_if_semiring_nullptr(m);
5424
5425 using scalar_type = typename Mat::scalar_type;
5426 scalar_type const t = matrix::threshold(m);
5427 auto it = std::find_if_not(m.cbegin(), m.cend(), [t](scalar_type x) {
5428 return x == NEGATIVE_INFINITY || (0 <= x && x <= t);
5429 });
5430 if (it != m.cend()) {
5431 auto [r, c] = m.coords(it);
5433 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5434 "but found {} in entry ({}, {})",
5435 t,
5436 entry_repr(NEGATIVE_INFINITY),
5437 static_cast<scalar_type>(NEGATIVE_INFINITY),
5438 detail::entry_repr(*it),
5439 r,
5440 c);
5441 }
5442 }
5443
5463 template <typename Mat>
5464 std::enable_if_t<IsMaxPlusTruncMat<Mat>>
5465 throw_if_bad_entry(Mat const& m, typename Mat::scalar_type val) {
5466 detail::throw_if_semiring_nullptr(m);
5467 using scalar_type = typename Mat::scalar_type;
5468 scalar_type const t = matrix::threshold(m);
5469 if (val == POSITIVE_INFINITY || 0 > val || val > t) {
5471 "invalid entry, expected values in {{0, 1, ..., {}, -{} (= {})}} "
5472 "but found {}",
5473 t,
5474 entry_repr(NEGATIVE_INFINITY),
5475 static_cast<scalar_type>(NEGATIVE_INFINITY),
5476 detail::entry_repr(val));
5477 }
5478 }
5479 } // namespace matrix
5480
5482 // Min-plus matrices with threshold
5484
5530
5554 //! \tparam Scalar the type of the values in the semiring.
5555 template <size_t T, typename Scalar>
5556 struct MinPlusTruncProd {
5567 //! \exceptions
5568 //! \noexcept
5569 Scalar operator()(Scalar x, Scalar y) const noexcept {
5570 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= static_cast<Scalar>(T))
5571 || x == POSITIVE_INFINITY);
5572 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= static_cast<Scalar>(T))
5573 || y == POSITIVE_INFINITY);
5574 if (x == POSITIVE_INFINITY || y == POSITIVE_INFINITY) {
5575 return POSITIVE_INFINITY;
5576 }
5577 return std::min(x + y, static_cast<Scalar>(T));
5578 }
5579 };
5580
5593 //! integral type.
5594 template <typename Scalar = int>
5595 class MinPlusTruncSemiring {
5596 static_assert(std::is_integral<Scalar>::value,
5597 "MinPlus requires an integral type as parameter!");
5598
5599 public:
5603 MinPlusTruncSemiring() = delete;
5604
5608 MinPlusTruncSemiring(MinPlusTruncSemiring const&) noexcept = default;
5609
5613 MinPlusTruncSemiring(MinPlusTruncSemiring&&) noexcept = default;
5614
5618 MinPlusTruncSemiring& operator=(MinPlusTruncSemiring const&) noexcept
5619 = default;
5620
5624 MinPlusTruncSemiring& operator=(MinPlusTruncSemiring&&) noexcept = default;
5625
5634 //! \complexity
5635 //! Constant.
5636 explicit MinPlusTruncSemiring(Scalar threshold) : _threshold(threshold) {
5638 LIBSEMIGROUPS_EXCEPTION("expected non-negative value, found {}",
5639 threshold);
5640 }
5641 }
5642
5651 //! \exceptions
5652 //! \noexcept
5653 static constexpr Scalar scalar_one() noexcept {
5654 return 0;
5655 }
5656
5666 //! \noexcept
5667 // TODO(1) These mem fns (one and zero) aren't needed?
5668 static constexpr Scalar scalar_zero() noexcept {
5669 return POSITIVE_INFINITY;
5670 }
5671
5694 //! \complexity
5695 //! Constant.
5696 Scalar product_no_checks(Scalar x, Scalar y) const noexcept {
5697 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5698 || x == POSITIVE_INFINITY);
5699 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5700 || y == POSITIVE_INFINITY);
5701 if (x == POSITIVE_INFINITY || y == POSITIVE_INFINITY) {
5702 return POSITIVE_INFINITY;
5703 }
5704 return std::min(x + y, _threshold);
5705 }
5706
5729 //! \complexity
5730 //! Constant.
5731 Scalar plus_no_checks(Scalar x, Scalar y) const noexcept {
5732 LIBSEMIGROUPS_ASSERT((x >= 0 && x <= _threshold)
5733 || x == POSITIVE_INFINITY);
5734 LIBSEMIGROUPS_ASSERT((y >= 0 && y <= _threshold)
5735 || y == POSITIVE_INFINITY);
5736 if (x == POSITIVE_INFINITY) {
5737 return y;
5738 } else if (y == POSITIVE_INFINITY) {
5739 return x;
5740 }
5741 return std::min(x, y);
5742 }
5743
5754 //! \complexity
5755 //! Constant.
5756 Scalar threshold() const noexcept {
5757 return _threshold;
5758 }
5759
5760 public:
5761 Scalar const _threshold;
5762 };
5763
5776 template <size_t T, typename Scalar>
5777 using DynamicMinPlusTruncMat = DynamicMatrix<MinPlusPlus<Scalar>,
5781 Scalar>;
5782
5796 template <size_t T, size_t R, size_t C, typename Scalar>
5801 R,
5802 C,
5803 Scalar>;
5804
5823 template <size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
5824 using MinPlusTruncMat = std::conditional_t<
5825 R == 0 || C == 0,
5826 std::conditional_t<T == 0,
5827 DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>,
5830
5831 namespace detail {
5832 template <typename T>
5833 struct IsMinPlusTruncMatHelper : std::false_type {};
5834
5835 template <size_t T, size_t R, size_t C, typename Scalar>
5836 struct IsMinPlusTruncMatHelper<StaticMinPlusTruncMat<T, R, C, Scalar>>
5837 : std::true_type {
5838 static constexpr Scalar threshold = T;
5839 };
5840
5841 template <size_t T, typename Scalar>
5842 struct IsMinPlusTruncMatHelper<DynamicMinPlusTruncMat<T, Scalar>>
5843 : std::true_type {
5844 static constexpr Scalar threshold = T;
5845 };
5846
5847 template <typename Scalar>
5848 struct IsMinPlusTruncMatHelper<
5849 DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>> : std::true_type {
5850 static constexpr Scalar threshold = UNDEFINED;
5851 };
5852 } // namespace detail
5853
5865 template <typename T>
5866 static constexpr bool IsMinPlusTruncMat
5867 = detail::IsMinPlusTruncMatHelper<T>::value;
5868
5869 namespace detail {
5870 template <typename T>
5871 struct IsTruncMatHelper<T, std::enable_if_t<IsMinPlusTruncMat<T>>>
5872 : std::true_type {
5873 static constexpr typename T::scalar_type threshold
5874 = IsMinPlusTruncMatHelper<T>::threshold;
5875 };
5876 } // namespace detail
5877
5878 namespace matrix {
5897 // TODO(1) to tpp
5898 template <typename Mat>
5899 std::enable_if_t<IsMinPlusTruncMat<Mat>> throw_if_bad_entry(Mat const& m) {
5900 // Check that the semiring pointer isn't the nullptr if it shouldn't be
5901 detail::throw_if_semiring_nullptr(m);
5902
5903 using scalar_type = typename Mat::scalar_type;
5904 scalar_type const t = matrix::threshold(m);
5905 auto it = std::find_if_not(m.cbegin(), m.cend(), [t](scalar_type x) {
5906 return x == POSITIVE_INFINITY || (0 <= x && x <= t);
5907 });
5908 if (it != m.cend()) {
5909 uint64_t r, c;
5910 std::tie(r, c) = m.coords(it);
5911
5913 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5914 "but found {} in entry ({}, {})",
5915 t,
5916 detail::entry_repr(POSITIVE_INFINITY),
5917 static_cast<scalar_type>(POSITIVE_INFINITY),
5918 detail::entry_repr(*it),
5919 r,
5920 c);
5921 }
5922 }
5923
5943 template <typename Mat>
5944 std::enable_if_t<IsMinPlusTruncMat<Mat>>
5945 throw_if_bad_entry(Mat const& m, typename Mat::scalar_type val) {
5946 detail::throw_if_semiring_nullptr(m);
5947
5948 using scalar_type = typename Mat::scalar_type;
5949 scalar_type const t = matrix::threshold(m);
5950 if (!(val == POSITIVE_INFINITY || (0 <= val && val <= t))) {
5952 "invalid entry, expected values in {{0, 1, ..., {}, {} (= {})}} "
5953 "but found {}",
5954 t,
5955 detail::entry_repr(POSITIVE_INFINITY),
5956 static_cast<scalar_type>(POSITIVE_INFINITY),
5957 detail::entry_repr(val));
5958 }
5959 }
5960 } // namespace matrix
5961
5963 // NTP matrices
5965
6018
6019 namespace detail {
6020 template <size_t T, size_t P, typename Scalar>
6021 constexpr Scalar thresholdperiod(Scalar x) noexcept {
6022 if (x > T) {
6023 return T + (x - T) % P;
6024 }
6025 return x;
6026 }
6027
6028 template <typename Scalar>
6029 inline Scalar thresholdperiod(Scalar x,
6030 Scalar threshold,
6031 Scalar period) noexcept {
6032 if (x > threshold) {
6033 return threshold + (x - threshold) % period;
6034 }
6035 return x;
6036 }
6037 } // namespace detail
6038
6061 // Static arithmetic
6062 template <size_t T, size_t P, typename Scalar>
6063 struct NTPPlus {
6073 //! \exceptions
6074 //! \noexcept
6075 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
6076 return detail::thresholdperiod<T, P>(x + y);
6077 }
6078 };
6079
6102 //! \tparam Scalar the type of the values in the semiring.
6103 template <size_t T, size_t P, typename Scalar>
6104 struct NTPProd {
6116 //! \exceptions
6117 //! \noexcept
6118 constexpr Scalar operator()(Scalar x, Scalar y) const noexcept {
6119 return detail::thresholdperiod<T, P>(x * y);
6120 }
6121 };
6122
6136 // Dynamic arithmetic
6137 template <typename Scalar = size_t>
6138 class NTPSemiring {
6139 public:
6143 // Deleted to avoid uninitialised values of period and threshold.
6144 NTPSemiring() = delete;
6145
6149 NTPSemiring(NTPSemiring const&) = default;
6150
6154 NTPSemiring(NTPSemiring&&) = default;
6155
6159 NTPSemiring& operator=(NTPSemiring const&) = default;
6160
6164 NTPSemiring& operator=(NTPSemiring&&) = default;
6165
6166 ~NTPSemiring() = default;
6167
6178 //! \complexity
6179 //! Constant.
6180 NTPSemiring(Scalar t, Scalar p) : _period(p), _threshold(t) {
6181 if constexpr (std::is_signed<Scalar>::value) {
6182 if (t < 0) {
6184 "expected non-negative value for 1st argument, found {}", t);
6185 }
6186 }
6187 if (p <= 0) {
6189 "expected positive value for 2nd argument, found {}", p);
6190 }
6191 }
6192
6201 //! \exceptions
6202 //! \noexcept
6203 static constexpr Scalar scalar_one() noexcept {
6204 return 1;
6205 }
6206
6217 //! \complexity
6218 //! Constant.
6219 static constexpr Scalar scalar_zero() noexcept {
6220 return 0;
6221 }
6222
6245 //! \complexity
6246 //! Constant.
6247 Scalar product_no_checks(Scalar x, Scalar y) const noexcept {
6248 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + _threshold - 1);
6249 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + _threshold - 1);
6250 return detail::thresholdperiod(x * y, _threshold, _period);
6251 }
6252
6275 //! \complexity
6276 //! Constant.
6277 Scalar plus_no_checks(Scalar x, Scalar y) const noexcept {
6278 LIBSEMIGROUPS_ASSERT(x >= 0 && x <= _period + _threshold - 1);
6279 LIBSEMIGROUPS_ASSERT(y >= 0 && y <= _period + _threshold - 1);
6280 return detail::thresholdperiod(x + y, _threshold, _period);
6281 }
6282
6293 //! \complexity
6294 //! Constant.
6295 Scalar threshold() const noexcept {
6296 return _threshold;
6297 }
6298
6309 //! \complexity
6310 //! Constant.
6311 Scalar period() const noexcept {
6312 return _period;
6313 }
6314
6315 private:
6316 Scalar _period;
6317 Scalar _threshold;
6318 };
6319
6330 template <typename Scalar>
6331 using DynamicNTPMatWithSemiring = DynamicMatrix<NTPSemiring<Scalar>, Scalar>;
6332
6346 template <size_t T, size_t P, typename Scalar>
6347 using DynamicNTPMatWithoutSemiring = DynamicMatrix<NTPPlus<T, P, Scalar>,
6351 Scalar>;
6352
6372 template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
6377 R,
6378 C,
6379 Scalar>;
6380
6403 template <size_t T = 0,
6404 size_t P = 0,
6405 size_t R = 0,
6406 size_t C = R,
6407 typename Scalar = size_t>
6408 using NTPMat = std::conditional_t<
6409 R == 0 || C == 0,
6410 std::conditional_t<T == 0 && P == 0,
6414
6415 namespace detail {
6416 template <typename T>
6417 struct IsNTPMatHelper : std::false_type {};
6418
6419 template <typename Scalar>
6420 struct IsNTPMatHelper<DynamicNTPMatWithSemiring<Scalar>> : std::true_type {
6421 static constexpr Scalar threshold = UNDEFINED;
6422 static constexpr Scalar period = UNDEFINED;
6423 };
6424
6425 template <size_t T, size_t P, typename Scalar>
6426 struct IsNTPMatHelper<DynamicNTPMatWithoutSemiring<T, P, Scalar>>
6427 : std::true_type {
6428 static constexpr Scalar threshold = T;
6429 static constexpr Scalar period = P;
6430 };
6431
6432 template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
6433 struct IsNTPMatHelper<StaticNTPMat<T, P, R, C, Scalar>> : std::true_type {
6434 static constexpr Scalar threshold = T;
6435 static constexpr Scalar period = P;
6436 };
6437 } // namespace detail
6438
6450 template <typename U>
6451 static constexpr bool IsNTPMat = detail::IsNTPMatHelper<U>::value;
6452
6453 namespace detail {
6454 template <typename T>
6455 struct IsTruncMatHelper<T, std::enable_if_t<IsNTPMat<T>>> : std::true_type {
6456 static constexpr typename T::scalar_type threshold
6457 = IsNTPMatHelper<T>::threshold;
6458 static constexpr typename T::scalar_type period
6459 = IsNTPMatHelper<T>::period;
6460 };
6461
6462 } // namespace detail
6463
6464 namespace matrix {
6485 //! \noexcept
6486 template <size_t T, size_t P, size_t R, size_t C, typename Scalar>
6487 constexpr Scalar period(StaticNTPMat<T, P, R, C, Scalar> const&) noexcept {
6488 return P;
6489 }
6490
6508 template <size_t T, size_t P, typename Scalar>
6509 constexpr Scalar
6511 return P;
6512 }
6513
6528 //! \noexcept
6529 template <typename Scalar>
6530 Scalar period(DynamicNTPMatWithSemiring<Scalar> const& x) noexcept {
6531 return x.semiring()->period();
6532 }
6533 } // namespace matrix
6534
6535 namespace matrix {
6555 //! defined (only applies to matrices with run time arithmetic).
6556 template <typename Mat>
6557 std::enable_if_t<IsNTPMat<Mat>> throw_if_bad_entry(Mat const& m) {
6558 detail::throw_if_semiring_nullptr(m);
6559
6560 using scalar_type = typename Mat::scalar_type;
6561 scalar_type const t = matrix::threshold(m);
6562 scalar_type const p = matrix::period(m);
6563 auto it = std::find_if_not(m.cbegin(), m.cend(), [t, p](scalar_type x) {
6564 return (0 <= x && x < p + t);
6565 });
6566 if (it != m.cend()) {
6567 uint64_t r, c;
6568 std::tie(r, c) = m.coords(it);
6569
6571 "invalid entry, expected values in {{0, 1, ..., {}}}, but "
6572 "found {} in entry ({}, {})",
6573 p + t,
6574 detail::entry_repr(*it),
6575 r,
6576 c);
6577 }
6578 }
6579
6601 template <typename Mat>
6602 std::enable_if_t<IsNTPMat<Mat>>
6603 throw_if_bad_entry(Mat const& m, typename Mat::scalar_type val) {
6604 detail::throw_if_semiring_nullptr(m);
6605 using scalar_type = typename Mat::scalar_type;
6606 scalar_type const t = matrix::threshold(m);
6607 scalar_type const p = matrix::period(m);
6608 if (val < 0 || val >= p + t) {
6610 "invalid entry, expected values in {{0, 1, ..., {}}}, but "
6611 "found {}",
6612 p + t,
6613 detail::entry_repr(val));
6614 }
6615 }
6616 } // namespace matrix
6617
6619 // Projective max-plus matrices
6621
6622 namespace detail {
6623 template <typename T>
6624 class ProjMaxPlusMat : MatrixPolymorphicBase {
6625 public:
6626 using scalar_type = typename T::scalar_type;
6627 using scalar_reference = typename T::scalar_reference;
6628 using scalar_const_reference = typename T::scalar_const_reference;
6629 using semiring_type = void;
6630
6631 using container_type = typename T::container_type;
6632 using iterator = typename T::iterator;
6633 using const_iterator = typename T::const_iterator;
6634
6635 using underlying_matrix_type = T;
6636
6637 using RowView = typename T::RowView;
6638
6639 // Note that Rows are never normalised, and that's why we use the
6640 // underlying matrix Row type and not 1 x n ProjMaxPlusMat's instead
6641 // (since these will be normalised according to their entries, and
6642 // this might not correspond to the normalised entries of the matrix).
6643 using Row = typename T::Row;
6644
6645 scalar_type scalar_one() const noexcept {
6646 return _underlying_mat.scalar_one();
6647 }
6648
6649 scalar_type scalar_zero() const noexcept {
6650 return _underlying_mat.scalar_zero();
6651 }
6652
6654 // ProjMaxPlusMat - Constructors + destructor - public
6656
6657 ProjMaxPlusMat() : _is_normalized(false), _underlying_mat() {}
6658 ProjMaxPlusMat(ProjMaxPlusMat const&) = default;
6659 ProjMaxPlusMat(ProjMaxPlusMat&&) = default;
6660 ProjMaxPlusMat& operator=(ProjMaxPlusMat const&) = default;
6661 ProjMaxPlusMat& operator=(ProjMaxPlusMat&&) = default;
6662
6663 ProjMaxPlusMat(size_t r, size_t c)
6664 : _is_normalized(false), _underlying_mat(r, c) {}
6665
6666 // TODO(1) other missing constructors
6667 ProjMaxPlusMat(
6668 typename underlying_matrix_type::semiring_type const* semiring,
6669 size_t r,
6670 size_t c)
6671 : _is_normalized(false), _underlying_mat(semiring, r, c) {}
6672
6673 explicit ProjMaxPlusMat(std::vector<std::vector<scalar_type>> const& m)
6674 : _is_normalized(false), _underlying_mat(m) {
6675 normalize();
6676 }
6677
6678 ProjMaxPlusMat(
6679 std::initializer_list<std::initializer_list<scalar_type>> const& m)
6680 : ProjMaxPlusMat(
6681 std::vector<std::vector<scalar_type>>(m.begin(), m.end())) {}
6682
6683 ~ProjMaxPlusMat() = default;
6684
6685 ProjMaxPlusMat one() const {
6686 auto result = ProjMaxPlusMat(_underlying_mat.one());
6687 return result;
6688 }
6689
6690 static ProjMaxPlusMat one(size_t n) {
6691 return ProjMaxPlusMat(T::one(n));
6692 }
6693
6695 // Comparison operators
6697
6698 bool operator==(ProjMaxPlusMat const& that) const {
6699 normalize();
6700 that.normalize();
6701 return _underlying_mat == that._underlying_mat;
6702 }
6703
6704 bool operator!=(ProjMaxPlusMat const& that) const {
6705 return !(_underlying_mat == that._underlying_mat);
6706 }
6707
6708 bool operator<(ProjMaxPlusMat const& that) const {
6709 normalize();
6710 that.normalize();
6711 return _underlying_mat < that._underlying_mat;
6712 }
6713
6714 bool operator>(ProjMaxPlusMat const& that) const {
6715 return that < *this;
6716 }
6717
6718 template <typename Thing>
6719 bool operator>=(Thing const& that) const {
6720 static_assert(IsMatrix<Thing> || std::is_same_v<Thing, RowView>);
6721 return that < *this || that == *this;
6722 }
6723
6724 // not noexcept because operator< isn't
6725 template <typename Thing>
6726 bool operator<=(Thing const& that) const {
6727 static_assert(IsMatrix<Thing> || std::is_same_v<Thing, RowView>);
6728 return *this < that || that == *this;
6729 }
6730
6732 // Attributes
6734
6735 scalar_reference operator()(size_t r, size_t c) {
6736 // to ensure the returned value is normalised
6737 normalize();
6738 // to ensure that the matrix is renormalised if the returned scalar is
6739 // assigned.
6740 _is_normalized = false;
6741 return _underlying_mat(r, c);
6742 }
6743
6744 scalar_reference at(size_t r, size_t c) {
6745 matrix::throw_if_bad_coords(*this, r, c);
6746 return this->operator()(r, c);
6747 }
6748
6749 scalar_const_reference operator()(size_t r, size_t c) const {
6750 normalize();
6751 return _underlying_mat(r, c);
6752 }
6753
6754 scalar_const_reference at(size_t r, size_t c) const {
6755 matrix::throw_if_bad_coords(*this, r, c);
6756 return this->operator()(r, c);
6757 }
6758
6759 size_t number_of_rows() const noexcept {
6760 return _underlying_mat.number_of_rows();
6761 }
6762
6763 size_t number_of_cols() const noexcept {
6764 return _underlying_mat.number_of_cols();
6765 }
6766
6767 size_t hash_value() const {
6768 normalize();
6769 return Hash<T>()(_underlying_mat);
6770 }
6771
6773 // Arithmetic operators - in-place
6775
6776 void product_inplace_no_checks(ProjMaxPlusMat const& A,
6777 ProjMaxPlusMat const& B) {
6778 _underlying_mat.product_inplace_no_checks(A._underlying_mat,
6779 B._underlying_mat);
6780 normalize(true); // force normalize
6781 }
6782
6783 void operator+=(ProjMaxPlusMat const& that) {
6784 _underlying_mat += that._underlying_mat;
6785 normalize(true); // force normalize
6786 }
6787
6788 void operator*=(scalar_type a) {
6789 _underlying_mat *= a;
6790 normalize(true); // force normalize
6791 }
6792
6793 void operator+=(scalar_type a) {
6794 _underlying_mat += a;
6795 normalize(true); // force normalize
6796 }
6797
6798 ProjMaxPlusMat operator*(scalar_type a) const {
6799 ProjMaxPlusMat result(*this);
6800 result *= a;
6801 return result;
6802 }
6803
6804 ProjMaxPlusMat operator+(scalar_type a) const {
6805 ProjMaxPlusMat result(*this);
6806 result += a;
6807 return result;
6808 }
6809
6811 // Arithmetic operators - not in-place
6813
6814 ProjMaxPlusMat operator+(ProjMaxPlusMat const& that) const {
6815 return ProjMaxPlusMat(_underlying_mat + that._underlying_mat);
6816 }
6817
6818 ProjMaxPlusMat operator*(ProjMaxPlusMat const& that) const {
6819 return ProjMaxPlusMat(_underlying_mat * that._underlying_mat);
6820 }
6821
6823 // Iterators
6825
6826 // The following should probably be commented out because I can't
6827 // currently think how to ensure that the matrix is normalised if it's
6828 // changed this way.
6829
6830 iterator begin() noexcept {
6831 // to ensure the returned value is normalised
6832 normalize();
6833 // to ensure that the matrix is renormalised if the returned scalar is
6834 // assigned.
6835 _is_normalized = false;
6836 return _underlying_mat.begin();
6837 }
6838
6839 iterator end() noexcept {
6840 // to ensure the returned value is normalised
6841 normalize();
6842 // to ensure that the matrix is renormalised if the returned scalar is
6843 // assigned.
6844 _is_normalized = false;
6845 return _underlying_mat.end();
6846 }
6847
6848 const_iterator begin() const noexcept {
6849 normalize();
6850 return _underlying_mat.begin();
6851 }
6852
6853 const_iterator end() const noexcept {
6854 normalize();
6855 return _underlying_mat.end();
6856 }
6857
6858 const_iterator cbegin() const noexcept {
6859 normalize();
6860 return _underlying_mat.cbegin();
6861 }
6862
6863 const_iterator cend() const noexcept {
6864 normalize();
6865 return _underlying_mat.cend();
6866 }
6867
6869 // Modifiers
6871
6872 void swap(ProjMaxPlusMat& that) noexcept {
6873 std::swap(_underlying_mat, that._underlying_mat);
6874 }
6875
6876 void transpose() noexcept {
6877 _underlying_mat.transpose();
6878 }
6879
6880 void transpose_no_checks() noexcept {
6881 _underlying_mat.transpose_no_checks();
6882 }
6883
6885 // Rows
6887
6888 RowView row(size_t i) const {
6889 normalize();
6890 return _underlying_mat.row(i);
6891 }
6892
6893 template <typename C>
6894 void rows(C& x) const {
6895 normalize();
6896 return _underlying_mat.rows(x);
6897 }
6898
6900 // Friend functions
6902
6903 friend std::ostream& operator<<(std::ostream& os,
6904 ProjMaxPlusMat const& x) {
6905 x.normalize();
6906 os << detail::to_string(x._underlying_mat);
6907 return os;
6908 }
6909
6910 T const& underlying_matrix() const noexcept {
6911 normalize();
6912 return _underlying_mat;
6913 }
6914
6915 private:
6916 explicit ProjMaxPlusMat(T&& mat)
6917 : _is_normalized(false), _underlying_mat(std::move(mat)) {
6918 normalize();
6919 }
6920
6921 void normalize(bool force = false) const {
6922 if ((_is_normalized && !force)
6923 || (_underlying_mat.number_of_rows() == 0)
6924 || (_underlying_mat.number_of_cols() == 0)) {
6925 _is_normalized = true;
6926 return;
6927 }
6928 scalar_type const n = *std::max_element(_underlying_mat.cbegin(),
6929 _underlying_mat.cend());
6930 std::for_each(_underlying_mat.begin(),
6931 _underlying_mat.end(),
6932 [&n](scalar_type& s) {
6933 if (s != NEGATIVE_INFINITY) {
6934 s -= n;
6935 }
6936 });
6937 _is_normalized = true;
6938 }
6939
6940 mutable bool _is_normalized;
6941 mutable T _underlying_mat;
6942 };
6943 } // namespace detail
6944
6989
7003 template <size_t R, size_t C, typename Scalar>
7005 = detail::ProjMaxPlusMat<StaticMaxPlusMat<R, C, Scalar>>;
7006
7018 template <typename Scalar>
7020 = detail::ProjMaxPlusMat<DynamicMaxPlusMat<Scalar>>;
7021
7036 template <size_t R = 0, size_t C = R, typename Scalar = int>
7037 using ProjMaxPlusMat = std::conditional_t<R == 0 || C == 0,
7040
7041 namespace detail {
7042 template <typename T>
7043 struct IsProjMaxPlusMatHelper : std::false_type {};
7044
7045 template <size_t R, size_t C, typename Scalar>
7046 struct IsProjMaxPlusMatHelper<StaticProjMaxPlusMat<R, C, Scalar>>
7047 : std::true_type {};
7048
7049 template <typename Scalar>
7050 struct IsProjMaxPlusMatHelper<DynamicProjMaxPlusMat<Scalar>>
7051 : std::true_type {};
7052 } // namespace detail
7053
7065 template <typename T>
7066 static constexpr bool IsProjMaxPlusMat
7067 = detail::IsProjMaxPlusMatHelper<T>::value;
7068
7069 namespace matrix {
7070 // \ingroup projmaxplus_group
7071 //
7085 //! \throws LibsemigroupsException if
7086 //! `throw_if_bad_entry(x.underlying_matrix())` throws.
7087 template <typename Mat>
7088 constexpr std::enable_if_t<IsProjMaxPlusMat<Mat>>
7089 throw_if_bad_entry(Mat const& x) {
7090 throw_if_bad_entry(x.underlying_matrix());
7091 }
7092
7093 // \ingroup projmaxplus_group
7094 //
7108 //! \throws LibsemigroupsException if
7109 //! `throw_if_bad_entry(x.underlying_matrix(), val)` throws.
7110 template <typename Mat>
7111 constexpr std::enable_if_t<IsProjMaxPlusMat<Mat>>
7112 throw_if_bad_entry(Mat const& x, typename Mat::scalar_type val) {
7113 throw_if_bad_entry(x.underlying_matrix(), val);
7114 }
7115
7117 // Matrix helpers - pow
7119
7153 //! \endcode
7154 // TODO(1) pow_no_checks
7155 // TODO(2) version that changes x in-place
7156 template <typename Mat>
7157 Mat pow(Mat const& x, typename Mat::scalar_type e) {
7158 using scalar_type = typename Mat::scalar_type;
7159
7160 if constexpr (std::is_signed<scalar_type>::value) {
7161 if (e < 0) {
7163 "negative exponent, expected value >= 0, found {}", e);
7164 }
7165 }
7166
7168
7169 typename Mat::semiring_type const* sr = nullptr;
7170
7171 if constexpr (IsMatWithSemiring<Mat>) {
7172 sr = x.semiring();
7173 }
7174
7175 if (e == 0) {
7176 return x.one();
7177 }
7178
7179 auto y = Mat(x);
7180 if (e == 1) {
7181 return y;
7182 }
7183 auto z = (e % 2 == 0 ? x.one() : y);
7184
7185 Mat tmp(sr, x.number_of_rows(), x.number_of_cols());
7186 while (e > 1) {
7187 tmp.product_inplace_no_checks(y, y);
7188 std::swap(y, tmp);
7189 e /= 2;
7190 if (e % 2 == 1) {
7191 tmp.product_inplace_no_checks(z, y);
7192 std::swap(z, tmp);
7193 }
7194 }
7195 return z;
7196 }
7197
7199 // Matrix helpers - rows
7201
7218 //!
7219 //! \complexity
7220 //! \f$O(m)\f$ where \f$m\f$ is the number of rows in the matrix \p x.
7221 template <typename Mat, typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
7224 x.rows(container);
7225 return container;
7226 }
7227
7246 //! \complexity
7247 //! \f$O(m)\f$ where \f$m\f$ is the number of rows in the matrix \p x.
7248 template <typename Mat, typename = std::enable_if_t<IsStaticMatrix<Mat>>>
7249 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
7250 rows(Mat const& x) {
7251 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
7252 x.rows(container);
7253 return container;
7254 }
7255
7257 // Matrix helpers - bitset_rows
7259
7260 // The main function
7289 //! \complexity
7290 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in `views` and
7291 //! and \f$n\f$ is the number of columns in any vector in `views`.
7292 template <typename Mat, size_t R, size_t C, typename Container>
7293 void bitset_rows(Container&& views,
7294 detail::StaticVector1<BitSet<C>, R>& result) {
7295 using RowView = typename Mat::RowView;
7296 using value_type = typename std::decay_t<Container>::value_type;
7297 // std::vector<bool> is used as value_type in the benchmarks
7298 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7301 "Container::value_type must equal Mat::RowView or "
7302 "std::vector<bool>!!");
7303 static_assert(R <= BitSet<1>::max_size(),
7304 "R must be at most BitSet<1>::max_size()!");
7305 static_assert(C <= BitSet<1>::max_size(),
7306 "C must be at most BitSet<1>::max_size()!");
7307 LIBSEMIGROUPS_ASSERT(views.size() <= R);
7308 LIBSEMIGROUPS_ASSERT(views.empty() || views[0].size() <= C);
7309 for (auto const& v : views) {
7310 result.emplace_back(v.cbegin(), v.cend());
7311 }
7312 }
7313
7343 //! \complexity
7344 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in \p views and
7345 //! and \f$n\f$ is the number of columns in any vector in \p views.
7346 template <typename Mat, size_t R, size_t C, typename Container>
7347 auto bitset_rows(Container&& views) {
7348 using RowView = typename Mat::RowView;
7349 using value_type = typename std::decay_t<Container>::value_type;
7350 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7353 "Container::value_type must equal Mat::RowView or "
7354 "std::vector<bool>!!");
7355 static_assert(R <= BitSet<1>::max_size(),
7356 "R must be at most BitSet<1>::max_size()!");
7357 static_assert(C <= BitSet<1>::max_size(),
7358 "C must be at most BitSet<1>::max_size()!");
7359 LIBSEMIGROUPS_ASSERT(views.size() <= R);
7360 LIBSEMIGROUPS_ASSERT(views.empty() || views[0].size() <= C);
7361 detail::StaticVector1<BitSet<C>, R> result;
7363 return result;
7364 }
7365
7366 // Helper
7392 //! \complexity
7393 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in \p x and and
7394 //! \f$n\f$ is the number of columns in \p x.
7395 template <typename Mat, size_t R, size_t C>
7396 void bitset_rows(Mat const& x,
7397 detail::StaticVector1<BitSet<C>, R>& result) {
7398 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7399 static_assert(R <= BitSet<1>::max_size(),
7400 "R must be at most BitSet<1>::max_size()!");
7401 static_assert(C <= BitSet<1>::max_size(),
7402 "C must be at most BitSet<1>::max_size()!");
7403 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= C);
7404 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= R);
7405 bitset_rows<Mat>(std::move(rows(x)), result);
7406 }
7407
7408 // Helper
7424 //! \complexity
7425 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows in \p x and
7426 //! and \f$n\f$ is the number of columns in \p x.
7427 template <typename Mat>
7428 auto bitset_rows(Mat const& x) {
7429 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7430 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7431 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7432 size_t const M = detail::BitSetCapacity<Mat>::value;
7434 }
7435
7437 // Matrix helpers - bitset_row_basis
7439
7461 //! \f$c\f$ is the size of each bitset in `rows`.
7462 // This works with std::vector and StaticVector1, with value_type equal
7463 // to std::bitset and BitSet.
7464 template <typename Mat, typename Container>
7465 void bitset_row_basis(Container&& rows, std::decay_t<Container>& result) {
7466 using value_type = typename std::decay_t<Container>::value_type;
7467 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7468 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7469 "Container::value_type must be BitSet or std::bitset");
7470 LIBSEMIGROUPS_ASSERT(rows.size() <= BitSet<1>::max_size());
7471 LIBSEMIGROUPS_ASSERT(rows.empty()
7472 || rows[0].size() <= BitSet<1>::max_size());
7473
7474 std::sort(rows.begin(), rows.end(), detail::LessBitSet());
7475 // Remove duplicates
7476 rows.erase(std::unique(rows.begin(), rows.end()), rows.end());
7477 for (size_t i = 0; i < rows.size(); ++i) {
7478 value_type cup;
7479 cup.reset();
7480 for (size_t j = 0; j < i; ++j) {
7481 if ((rows[i] & rows[j]) == rows[j]) {
7482 cup |= rows[j];
7483 }
7484 }
7485 for (size_t j = i + 1; j < rows.size(); ++j) {
7486 if ((rows[i] & rows[j]) == rows[j]) {
7487 cup |= rows[j];
7488 }
7489 }
7490 if (cup != rows[i]) {
7491 result.push_back(std::move(rows[i]));
7492 }
7493 }
7494 }
7495
7516 //! \complexity
7517 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the size of \p rows and
7518 //! \f$c\f$ is the size of each bitset in \p rows.
7519 template <typename Mat, typename Container>
7520 std::decay_t<Container> bitset_row_basis(Container&& rows) {
7521 using value_type = typename std::decay_t<Container>::value_type;
7522 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7523 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7524 "Container::value_type must be BitSet or std::bitset");
7525 LIBSEMIGROUPS_ASSERT(rows.size() <= BitSet<1>::max_size());
7526 LIBSEMIGROUPS_ASSERT(rows.empty()
7527 || rows[0].size() <= BitSet<1>::max_size());
7528 std::decay_t<Container> result;
7530 return result;
7531 }
7532
7557 //! \complexity
7558 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x and
7559 //! \f$c\f$ is the number of columns in \p x.
7560 template <typename Mat, size_t M = detail::BitSetCapacity<Mat>::value>
7561 detail::StaticVector1<BitSet<M>, M> bitset_row_basis(Mat const& x) {
7562 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7563 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7564 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7565 detail::StaticVector1<BitSet<M>, M> result;
7567 return result;
7568 }
7569
7590 //! \complexity
7591 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x
7592 //! and \f$c\f$ is the number of columns in \p x.
7593 template <typename Mat, typename Container>
7594 void bitset_row_basis(Mat const& x, Container& result) {
7595 using value_type = typename Container::value_type;
7596 static_assert(IsBMat<Mat>, "IsBMat<Mat> must be true!");
7597 static_assert(IsBitSet<value_type> || detail::IsStdBitSet<value_type>,
7598 "Container::value_type must be BitSet or std::bitset");
7599 LIBSEMIGROUPS_ASSERT(x.number_of_rows() <= BitSet<1>::max_size());
7600 LIBSEMIGROUPS_ASSERT(x.number_of_cols() <= BitSet<1>::max_size());
7602 }
7603
7605 // Matrix helpers - row_basis - MaxPlusTruncMat
7607
7633 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the size of \p views and
7634 //! \f$c\f$ is the size of each row view or bit set in \p views.
7635 template <typename Mat, typename Container>
7636 std::enable_if_t<IsMaxPlusTruncMat<Mat>>
7637 row_basis(Container&& views, std::decay_t<Container>& result) {
7638 using value_type = typename std::decay_t<Container>::value_type;
7640 "Container::value_type must be Mat::RowView");
7641 using scalar_type = typename Mat::scalar_type;
7642 using Row = typename Mat::Row;
7643
7644 if (views.empty()) {
7645 return;
7646 }
7647
7648 LIBSEMIGROUPS_ASSERT(result.empty());
7649
7650 std::sort(views.begin(), views.end());
7651 Row tmp1(views[0]);
7652
7653 for (size_t r1 = 0; r1 < views.size(); ++r1) {
7654 if (r1 == 0 || views[r1] != views[r1 - 1]) {
7655 std::fill(tmp1.begin(), tmp1.end(), tmp1.scalar_zero());
7656 for (size_t r2 = 0; r2 < r1; ++r2) {
7657 scalar_type max_scalar = matrix::threshold(tmp1);
7658 for (size_t c = 0; c < tmp1.number_of_cols(); ++c) {
7659 if (views[r2][c] == tmp1.scalar_zero()) {
7660 continue;
7661 }
7662 if (views[r1][c] >= views[r2][c]) {
7663 if (views[r1][c] != matrix::threshold(tmp1)) {
7664 max_scalar
7665 = std::min(max_scalar, views[r1][c] - views[r2][c]);
7666 }
7667 } else {
7668 max_scalar = tmp1.scalar_zero();
7669 break;
7670 }
7671 }
7672 if (max_scalar != tmp1.scalar_zero()) {
7673 tmp1 += views[r2] * max_scalar;
7674 }
7675 }
7676 if (tmp1 != views[r1]) {
7677 result.push_back(views[r1]);
7678 }
7679 }
7680 }
7681 }
7682
7684 // Matrix helpers - row_basis - BMat
7686
7687 // This version of row_basis for BMat's is for used for compatibility
7688 // with the MatrixCommon framework, i.e. so that BMat's exhibit the same
7689 // interface/behaviour as other matrices.
7690 //
7691 // This version takes a container of row views of BMat, converts it to a
7692 // container of BitSets, computes the row basis using the BitSets, then
7693 // selects those row views in views that belong to the computed basis.
7694
7710 //! \exceptions
7711 //! \no_libsemigroups_except
7712 // TODO(2) complexity
7713 template <typename Mat, typename Container>
7714 std::enable_if_t<IsBMat<Mat>> row_basis(Container&& views,
7715 std::decay_t<Container>& result) {
7716 using RowView = typename Mat::RowView;
7717 using value_type = typename std::decay_t<Container>::value_type;
7718 // std::vector<bool> is used as value_type in the benchmarks
7721 "Container::value_type must equal Mat::RowView or "
7722 "std::vector<bool>!!");
7723
7724 if (views.empty()) {
7725 return;
7726 }
7727
7728 // Convert RowViews to BitSets
7729 size_t const M = detail::BitSetCapacity<Mat>::value;
7731 using bitset_type = typename decltype(br)::value_type;
7732
7733 // Map for converting bitsets back to row views
7735 LIBSEMIGROUPS_ASSERT(br.size() == views.size());
7736 for (size_t i = 0; i < br.size(); ++i) {
7737 lookup.insert({br[i], i});
7738 }
7739
7740 // Compute rowbasis using bitsets + convert back to rowviews
7741 for (auto const& bs : bitset_row_basis<Mat>(br)) {
7742 auto it = lookup.find(bs);
7743 LIBSEMIGROUPS_ASSERT(it != lookup.end());
7744 result.push_back(views[it->second]);
7745 }
7746 }
7747
7749 // Matrix helpers - row_basis - generic helpers
7751
7773 // Row basis of rowspace of matrix <x> appended to <result>
7774 template <typename Mat,
7775 typename Container,
7776 typename = std::enable_if_t<IsMatrix<Mat>>>
7777 void row_basis(Mat const& x, Container& result) {
7778 row_basis<Mat>(std::move(rows(x)), result);
7779 }
7780
7798 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x
7799 //! and \f$c\f$ is the number of columns in \p x.
7800 // Row basis of rowspace of matrix <x>
7801 template <typename Mat, typename = std::enable_if_t<IsDynamicMatrix<Mat>>>
7804 row_basis(x, container);
7805 return container;
7806 }
7807
7825 //! \f$O(r ^ 2 c)\f$ where \f$r\f$ is the number of rows in \p x
7826 //! and \f$c\f$ is the number of columns in \p x.
7827 template <typename Mat, typename = std::enable_if_t<IsStaticMatrix<Mat>>>
7828 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows>
7829 row_basis(Mat const& x) {
7830 detail::StaticVector1<typename Mat::RowView, Mat::nr_rows> container;
7831 row_basis(x, container);
7832 return container;
7833 }
7834
7851 //! \exceptions
7852 //! \no_libsemigroups_except
7853 // TODO(2) complexity
7854 template <typename Mat, typename Container>
7855 std::decay_t<Container> row_basis(Container&& rows) {
7856 using value_type = typename std::decay_t<Container>::value_type;
7857 static_assert(IsMatrix<Mat>, "IsMatrix<Mat> must be true!");
7859 "Container::value_type must be Mat::RowView");
7860
7861 std::decay_t<Container> result;
7863 return result;
7864 }
7865
7867 // Matrix helpers - row_space_size
7869
7897 //! auto x = make<BMat<>>({{1, 0, 0}, {0, 0, 1}, {0, 1, 0}});
7898 //! matrix::row_space_size(x); // returns 7
7899 //! \endcode
7900 template <typename Mat, typename = std::enable_if_t<IsBMat<Mat>>>
7901 size_t row_space_size(Mat const& x) {
7902 size_t const M = detail::BitSetCapacity<Mat>::value;
7903 auto bitset_row_basis_ = bitset_row_basis<Mat>(
7905
7907 st.insert(bitset_row_basis_.cbegin(), bitset_row_basis_.cend());
7908 std::vector<BitSet<M>> orb(bitset_row_basis_.cbegin(),
7909 bitset_row_basis_.cend());
7910 for (size_t i = 0; i < orb.size(); ++i) {
7911 for (auto& row : bitset_row_basis_) {
7912 auto cup = orb[i];
7913 for (size_t j = 0; j < x.number_of_rows(); ++j) {
7914 cup.set(j, cup[j] || row[j]);
7915 }
7916 if (st.insert(cup).second) {
7917 orb.push_back(std::move(cup));
7918 }
7919 }
7920 }
7921 return orb.size();
7922 }
7923
7924 } // namespace matrix
7925
7942 //! \no_libsemigroups_except
7943 //!
7944 //! \warning This function does not detect overflows of `Mat::scalar_type`.
7945 template <typename Mat>
7946 auto operator+(typename Mat::scalar_type a, Mat const& x)
7947 -> std::enable_if_t<IsMatrix<Mat>, Mat> {
7948 return x + a;
7949 }
7950
7967 //! \no_libsemigroups_except
7968 //!
7969 //! \warning This function does not detect overflows of `Mat::scalar_type`.
7970 template <typename Mat>
7971 auto operator*(typename Mat::scalar_type a, Mat const& x)
7972 -> std::enable_if_t<IsMatrix<Mat>, Mat> {
7973 return x * a;
7974 }
7975
7986
8011 //! \f$n\f$ is the number of columns of the matrix.
8012 template <typename Mat,
8013 typename
8014 = std::enable_if_t<IsMatrix<Mat> && !IsMatWithSemiring<Mat>>>
8016 detail::throw_if_any_row_wrong_size(rows);
8017 detail::throw_if_bad_dim<Mat>(rows);
8018 Mat m(rows);
8020 return m;
8021 }
8022
8047 //! \f$n\f$ is the number of columns of the matrix.
8048 template <typename Mat,
8049 typename
8050 = std::enable_if_t<IsMatrix<Mat> && !IsMatWithSemiring<Mat>>>
8052 rows) {
8054 }
8055
8081 //! parameter \c R is \c 1.
8082 template <typename Mat,
8083 typename
8084 = std::enable_if_t<IsMatrix<Mat> && !IsMatWithSemiring<Mat>>>
8086 // TODO(0) Add row dimension checking for compile-time size matrices
8087 Mat m(row);
8089 return m;
8090 }
8091 // TODO(1) vector version of above
8092
8124 template <typename Mat,
8125 typename Semiring,
8126 typename = std::enable_if_t<IsMatrix<Mat>>>
8127 // TODO(1) pass Semiring by reference, this is hard mostly due to the way
8128 // the tests are written, which is not optimal.
8129 Mat make(Semiring const* semiring,
8132 detail::throw_if_any_row_wrong_size(rows);
8133 detail::throw_if_bad_dim<Mat>(rows);
8134 Mat m(semiring, rows);
8136 return m;
8137 }
8138
8169 //! \f$n\f$ is the number of columns of the matrix.
8170 template <typename Mat,
8171 typename Semiring,
8172 typename = std::enable_if_t<IsMatrix<Mat>>>
8173 Mat make(Semiring const* semiring,
8175 detail::throw_if_any_row_wrong_size(rows);
8176 detail::throw_if_bad_dim<Mat>(rows);
8177 Mat m(semiring, rows);
8179 return m;
8180 }
8181
8203 //! \f$O(n)\f$ where \f$n\f$ is the number of columns of the matrix.
8204 template <typename Mat,
8205 typename Semiring,
8206 typename = std::enable_if_t<IsMatrix<Mat>>>
8207 Mat make(Semiring const* semiring,
8209 // TODO(0) Add row dimension checking for compile-time size matrices
8210 Mat m(semiring, row);
8212 return m;
8213 }
8214
8240 //! \f$O(mn)\f$ where \f$m\f$ is the number of rows and \f$n\f$ is the
8241 //! number of columns of the matrix.
8242 template <size_t R, size_t C, typename Scalar>
8247 }
8248
8250 // Printing etc...
8252
8262 //!
8263 //! \exceptions
8264 //! \no_libsemigroups_except
8265 template <typename S, typename T>
8267 detail::RowViewCommon<S, T> const& x) {
8268 os << "{";
8269 for (auto it = x.cbegin(); it != x.cend(); ++it) {
8270 os << *it;
8271 if (it != x.cend() - 1) {
8272 os << ", ";
8273 }
8274 }
8275 os << "}";
8276 return os;
8277 }
8278
8292 //!
8293 //! \exceptions
8294 //! \no_libsemigroups_except
8295 template <typename Mat>
8296 auto operator<<(std::ostringstream& os, Mat const& x)
8297 -> std::enable_if_t<IsMatrix<Mat>, std::ostringstream&> {
8298 size_t n = 0;
8299 if (x.number_of_rows() != 1) {
8300 os << "{";
8301 }
8302 for (auto&& r : matrix::rows(x)) {
8303 os << r;
8304 if (n != x.number_of_rows() - 1) {
8305 os << ", ";
8306 }
8307 n++;
8308 }
8309 if (x.number_of_rows() != 1) {
8310 os << "}";
8311 }
8312 return os;
8313 }
8314
8328 //! (default: \c 72).
8329 //!
8330 //! \throws LibsemigroupsException if \p braces does not have size \c 2.
8331 template <typename Mat>
8332 auto to_human_readable_repr(Mat const& x,
8333 std::string const& prefix,
8334 std::string const& short_name = "",
8335 std::string const& braces = "{}",
8336 size_t max_width = 72)
8337 -> std::enable_if_t<IsMatrix<Mat>, std::string> {
8338 if (braces.size() != 2) {
8340 "the 4th argument (braces) must have size 2, found {}",
8341 braces.size());
8342 }
8343
8344 size_t const R = x.number_of_rows();
8345 size_t const C = x.number_of_cols();
8346
8347 std::vector<size_t> max_col_widths(C, 0);
8348 std::vector<size_t> row_widths(C, prefix.size() + 1);
8349 for (size_t r = 0; r < R; ++r) {
8350 for (size_t c = 0; c < C; ++c) {
8351 size_t width
8352 = detail::unicode_string_length(detail::entry_repr(x(r, c)));
8353 row_widths[r] += width;
8354 if (width > max_col_widths[c]) {
8355 max_col_widths[c] = width;
8356 }
8357 }
8358 }
8359 auto col_width
8360 = *std::max_element(max_col_widths.begin(), max_col_widths.end());
8361 // The total width if we pad the entries according to the widest column.
8362 auto const total_width = col_width * C + prefix.size() + 1;
8363 if (total_width > max_width) {
8364 // Padding according to the widest column is too wide!
8365 if (*std::max_element(row_widths.begin(), row_widths.end()) > max_width) {
8366 // If the widest row is too wide, then use the short name
8367 return fmt::format(
8368 "<{}x{} {}>", x.number_of_rows(), x.number_of_cols(), short_name);
8369 }
8370 // If the widest row is not too wide, then just don't pad the entries
8371 col_width = 0;
8372 }
8373
8374 std::string result = fmt::format("{}", prefix);
8375 std::string rindent;
8376 auto const lbrace = braces[0], rbrace = braces[1];
8377 if (R != 0 && C != 0) {
8378 result += lbrace;
8379 for (size_t r = 0; r < R; ++r) {
8380 result += fmt::format("{}{}", rindent, lbrace);
8381 rindent = std::string(prefix.size() + 1, ' ');
8382 std::string csep = "";
8383 for (size_t c = 0; c < C; ++c) {
8384 result += fmt::format(
8385 "{}{:>{}}", csep, detail::entry_repr(x(r, c)), col_width);
8386 csep = ", ";
8387 }
8388 result += fmt::format("{}", rbrace);
8389 if (r != R - 1) {
8390 result += ",\n";
8391 }
8392 }
8393 result += rbrace;
8394 }
8395 result += ")";
8396 return result;
8397 }
8398
8400 // Adapters
8402
8417
8425 //! satisfying \ref IsMatrix<Mat>.
8426 //!
8427 //! \tparam Mat the type of matrices.
8428 template <typename Mat>
8429 struct Complexity<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8439 //! \noexcept
8440 //!
8441 //! \complexity
8442 //! Constant.
8443 constexpr size_t operator()(Mat const& x) const noexcept {
8444 return x.number_of_rows() * x.number_of_rows() * x.number_of_rows();
8445 }
8446 };
8447
8455 //! \ref IsMatrix<Mat>.
8456 //!
8457 //! \tparam Mat the type of matrices.
8458 template <typename Mat>
8459 struct Degree<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8468 //! \noexcept
8469 //!
8470 //! \complexity
8471 //! Constant.
8472 constexpr size_t operator()(Mat const& x) const noexcept {
8473 return x.number_of_rows();
8474 }
8475 };
8476
8484 //! \ref IsMatrix<Mat>.
8485 //!
8486 //! \tparam Mat the type of matrices.
8487 template <typename Mat>
8488 struct Hash<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8497 //! \no_libsemigroups_except
8498 //!
8499 //! \complexity
8500 //! Constant.
8501 constexpr size_t operator()(Mat const& x) const {
8502 return x.hash_value();
8503 }
8504 };
8505
8518 //! It is not possible to increase the degree of any of the types
8519 //! satisfying \ref IsMatrix, and as such the call operator of this type
8520 //! does nothing.
8521 template <typename Mat>
8522 struct IncreaseDegree<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8526 constexpr void operator()(Mat&, size_t) const noexcept {
8527 // static_assert(false, "Cannot increase degree for Matrix");
8528 LIBSEMIGROUPS_ASSERT(false);
8529 }
8530 };
8531
8539 //! \ref IsMatrix.
8540 //!
8541 //! \tparam Mat the type of matrices.
8542 template <typename Mat>
8543 struct One<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8553 //!
8554 //! \complexity
8555 //! \f$O(m ^ 2)\f$ where \f$m\f$ is the number of rows of the
8556 //! matrix \p x.
8557 inline Mat operator()(Mat const& x) const {
8558 return x.one();
8559 }
8560 };
8561
8569 //! \ref IsMatrix<Mat>.
8570 //!
8571 //! \tparam Mat the type of matrices.
8572 template <typename Mat>
8573 struct Product<Mat, std::enable_if_t<IsMatrix<Mat>>> {
8589 //!
8590 //! \warning
8591 //! This function only works for square matrices.
8592 inline void
8593 operator()(Mat& xy, Mat const& x, Mat const& y, size_t = 0) const {
8594 xy.product_inplace_no_checks(x, y);
8595 }
8596 };
8597} // namespace libsemigroups
8598
8599namespace std {
8600 template <size_t N,
8601 typename Mat,
8602 std::enable_if_t<libsemigroups::IsMatrix<Mat>>>
8603 inline void swap(Mat& x, Mat& y) noexcept {
8604 x.swap(y);
8605 }
8606} // namespace std
8607
8608#endif // LIBSEMIGROUPS_MATRIX_HPP_
DynamicMatrix(std::initializer_list< scalar_type > const &c)
Construct a vector from a std::initializer_list.
Definition matrix.hpp:2890
DynamicMatrix(std::initializer_list< std::initializer_list< scalar_type > > const &m)
Construct a matrix from std::initializer_list of std::initializer_list of scalars.
Definition matrix.hpp:2912
DynamicMatrix & operator=(DynamicMatrix &&)=default
Default move assignment operator.
scalar_reference at(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
ProdOp Prod
Alias for the template parameter ProdOp.
Definition matrix.hpp:2811
void product_inplace_no_checks(DynamicMatrix const &x, DynamicMatrix const &y)
Multiplies x and y and stores the result in this.
DynamicMatrix & operator=(DynamicMatrix const &)=default
Default copy assignment operator.
DynamicMatrix Row
The type of a row of a DynamicMatrix.
Definition matrix.hpp:2802
PlusOp Plus
Alias for the template parameter PlusOp.
Definition matrix.hpp:2808
void rows(T &x) const
Add row views for every row in the matrix to a container.
scalar_type scalar_one() const noexcept
Returns the multiplicative identity of the underlying semiring.
typename MatrixCommon::scalar_const_reference scalar_const_reference
The type of const references to the entries in the matrix.
Definition matrix.hpp:2798
void swap(DynamicMatrix &that) noexcept
Swaps the contents of *this with the contents of that.
Definition matrix.hpp:3171
const_iterator cend() noexcept
Returns a const iterator pointing one beyond the last entry in the matrix.
static DynamicMatrix one(size_t n)
Construct the identity matrix.
Definition matrix.hpp:2993
DynamicMatrix(size_t r, size_t c)
Construct a matrix with given dimensions.
Definition matrix.hpp:2868
ZeroOp Zero
Alias for the template parameter ZeroOp.
Definition matrix.hpp:2814
scalar_type scalar_zero() const noexcept
Returns the additive identity of the underlying semiring.
semiring_type const * semiring() const noexcept
Returns the underlying semiring.
OneOp One
Alias for the template parameter OneOp.
Definition matrix.hpp:2817
void semiring_type
Alias for the semiring type (void).
Definition matrix.hpp:2824
RowView row(size_t i) const
Returns a view into a row.
DynamicMatrix(RowView const &rv)
Construct a row from a row view.
Definition matrix.hpp:2946
iterator begin() noexcept
Returns an iterator pointing at the first entry.
size_t number_of_rows() const noexcept
Returns the number of rows of the matrix.
DynamicRowView< PlusOp, ProdOp, ZeroOp, OneOp, Scalar > RowView
The type of a row view into a DynamicMatrix.
Definition matrix.hpp:2805
RowView row_no_checks(size_t i) const
Returns a view into a row.
DynamicMatrix(std::vector< std::vector< scalar_type > > const &m)
Construct a matrix from std::vector of std::vector of scalars.
Definition matrix.hpp:2931
typename MatrixCommon::scalar_reference scalar_reference
The type of references to the entries in the matrix.
Definition matrix.hpp:2793
scalar_reference at(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
DynamicMatrix(DynamicMatrix const &)=default
Default copy constructor.
size_t hash_value() const
Return a hash value of a matrix.
const_iterator cbegin() noexcept
Returns a const iterator pointing at the first entry.
DynamicMatrix(DynamicMatrix &&)=default
Default move constructor.
typename MatrixCommon::scalar_type scalar_type
The type of the entries in the matrix.
Definition matrix.hpp:2790
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
std::pair< scalar_type, scalar_type > coords(const_iterator it) const
Get the coordinates of an iterator.
iterator end() noexcept
Returns an iterator pointing one beyond the last entry in the matrix.
DynamicMatrix(Semiring const *sr, std::initializer_list< std::initializer_list< scalar_type > > const &rws)
Construct a matrix over a given semiring (std::initializer_list of std::initializer_list).
Definition matrix.hpp:3310
DynamicMatrix & operator=(DynamicMatrix &&)=default
Default move assignment operator.
static DynamicMatrix one(Semiring const *semiring, size_t n)
Construct the identity matrix.
Definition matrix.hpp:3387
scalar_reference at(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
DynamicMatrix(Semiring const *sr, std::vector< std::vector< scalar_type > > const &rws)
Construct a matrix over a given semiring (std::vector of std::vector).
Definition matrix.hpp:3333
DynamicMatrix(Semiring const *sr, size_t r, size_t c)
Construct a matrix over a given semiring with given dimensions.
Definition matrix.hpp:3290
void product_inplace_no_checks(DynamicMatrix const &x, DynamicMatrix const &y)
Multiplies x and y and stores the result in this.
DynamicMatrix & operator=(DynamicMatrix const &)=default
Default copy assignment operator.
DynamicMatrix Row
Alias for the type of the rows of a DynamicMatrix.
Definition matrix.hpp:3247
void rows(T &x) const
Add row views for every row in the matrix to a container.
scalar_type scalar_one() const noexcept
Returns the multiplicative identity of the underlying semiring.
typename MatrixCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:3243
void swap(DynamicMatrix &that) noexcept
Swaps the contents of *this with the contents of that.
Definition matrix.hpp:3567
const_iterator cend() noexcept
Returns a const iterator pointing one beyond the last entry in the matrix.
scalar_type scalar_zero() const noexcept
Returns the additive identity of the underlying semiring.
void transpose_no_checks()
Transpose a matrix in-place.
semiring_type const * semiring() const noexcept
Returns the underlying semiring.
RowView row(size_t i) const
Returns a view into a row.
DynamicMatrix(RowView const &rv)
Construct a row over a given semiring (RowView).
Definition matrix.hpp:3367
iterator begin() noexcept
Returns an iterator pointing at the first entry.
size_t number_of_rows() const noexcept
Returns the number of rows of the matrix.
DynamicMatrix(Semiring const *sr, std::initializer_list< scalar_type > const &rw)
Construct a row over a given semiring (std::initializer_list).
Definition matrix.hpp:3352
RowView row_no_checks(size_t i) const
Returns a view into a row.
typename MatrixCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:3238
scalar_reference at(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
DynamicMatrix(DynamicMatrix const &)=default
Default copy constructor.
size_t hash_value() const
Return a hash value of a matrix.
const_iterator cbegin() noexcept
Returns a const iterator pointing at the first entry.
DynamicMatrix(DynamicMatrix &&)=default
Default move constructor.
typename MatrixCommon::scalar_type scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:3235
DynamicRowView< Semiring, Scalar > RowView
Alias for the type of row views of a DynamicMatrix.
Definition matrix.hpp:3250
Semiring semiring_type
Alias for the template parameter Semiring.
Definition matrix.hpp:3255
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
void transpose()
Transpose a matrix in-place.
std::pair< scalar_type, scalar_type > coords(const_iterator it) const
Get the coordinates of an iterator.
iterator end() noexcept
Returns an iterator pointing one beyond the last entry in the matrix.
DynamicRowView & operator=(DynamicRowView &&)=default
Default move assignment operator.
size_t size() const noexcept
Returns the size of the row.
DynamicRowView & operator=(DynamicRowView const &)=default
Default copy assignment operator.
DynamicRowView(DynamicRowView const &)=default
Default copy constructor.
DynamicRowView(DynamicRowView &&)=default
Default move constructor.
DynamicRowView(Row const &r)
Construct a row view from a Row.
Definition matrix.hpp:1572
typename RowViewCommon::iterator iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1536
typename RowViewCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1547
typename RowViewCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1542
iterator begin() noexcept
Returns a iterator pointing at the first entry.
iterator cend()
Returns a const iterator pointing one beyond the last entry of the row.
typename matrix_type::Row Row
Alias for the type of a row in the underlying matrix.
Definition matrix.hpp:1554
typename RowViewCommon::const_iterator const_iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1533
const_iterator cbegin() const noexcept
Returns a const iterator pointing at the first entry.
iterator end()
Returns a iterator pointing one beyond the last entry of the row.
Scalar scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1539
typename RowViewCommon::matrix_type matrix_type
Alias for the type of the underlying matrix.
Definition matrix.hpp:1551
size_t size() const noexcept
Returns the size of the row.
DynamicRowView & operator=(DynamicRowView const &)=default
Default copy assignment operator.
typename RowViewCommon::iterator iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1690
typename RowViewCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1701
typename RowViewCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1696
iterator begin() noexcept
Returns a iterator pointing at the first entry.
iterator cend()
Returns a const iterator pointing one beyond the last entry of the row.
typename matrix_type::Row Row
Alias for the type of a row in the underlying matrix.
Definition matrix.hpp:1708
typename RowViewCommon::const_iterator const_iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1687
const_iterator cbegin() const noexcept
Returns a const iterator pointing at the first entry.
iterator end()
Returns a iterator pointing one beyond the last entry of the row.
Scalar scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1693
typename RowViewCommon::matrix_type matrix_type
Alias for the type of the underlying matrix.
Definition matrix.hpp:1705
DynamicRowView()=default
Default constructor.
Class representing a truncated max-plus semiring.
Definition matrix.hpp:5116
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:5190
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in a truncated max-plus semiring.
Definition matrix.hpp:5253
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in a truncated max-plus semiring.
Definition matrix.hpp:5218
MaxPlusTruncSemiring()=delete
Deleted default constructor.
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:5278
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:5176
Class representing a truncated min-plus semiring.
Definition matrix.hpp:5593
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:5666
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in a truncated min-plus semiring.
Definition matrix.hpp:5729
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in a truncated min-plus semiring.
Definition matrix.hpp:5694
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:5754
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:5651
MinPlusTruncSemiring()=delete
Deleted default constructor.
NTPSemiring & operator=(NTPSemiring const &)=default
Default copy assignment operator.
static constexpr Scalar scalar_zero() noexcept
Get the additive identity.
Definition matrix.hpp:6217
Scalar plus_no_checks(Scalar x, Scalar y) const noexcept
Addition in an ntp semiring.
Definition matrix.hpp:6275
NTPSemiring()=delete
Deleted default constructor.
Scalar product_no_checks(Scalar x, Scalar y) const noexcept
Multiplication in an ntp semiring.
Definition matrix.hpp:6245
Scalar period() const noexcept
Get the period.
Definition matrix.hpp:6309
Scalar threshold() const noexcept
Get the threshold.
Definition matrix.hpp:6293
static constexpr Scalar scalar_one() noexcept
Get the multiplicative identity.
Definition matrix.hpp:6201
Static matrix class.
Definition matrix.hpp:1865
typename MatrixCommon::iterator iterator
Definition matrix.hpp:1912
StaticMatrix(std::initializer_list< scalar_type > const &c)
Construct a row (from std::initializer_list).
Definition matrix.hpp:1940
typename MatrixCommon::const_iterator const_iterator
Definition matrix.hpp:1915
scalar_const_reference at(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
scalar_reference at(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
StaticMatrix(StaticMatrix &&)=default
Default move constructor.
typename MatrixCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1890
scalar_reference operator()(size_t r, size_t c)
Returns a reference to the specified entry of the matrix.
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:1966
StaticRowView< PlusOp, ProdOp, ZeroOp, OneOp, C, Scalar > RowView
Definition matrix.hpp:1897
static StaticMatrix one() const
Returns an identity matrix.
StaticMatrix(StaticMatrix const &)=default
Default copy constructor.
iterator begin() noexcept
Returns an iterator pointing at the first entry.
StaticMatrix(RowView const &rv)
Construct a row from a row view.
Definition matrix.hpp:2002
size_t number_of_rows() const noexcept
Returns the number of rows of the matrix.
StaticMatrix(std::vector< std::vector< scalar_type > > const &m)
Construct a matrix.
Definition matrix.hpp:1982
StaticMatrix< PlusOp, ProdOp, ZeroOp, OneOp, 1, C, Scalar > Row
Alias for the type of the rows of a StaticMatrix.
Definition matrix.hpp:1894
StaticMatrix()=default
Default constructor.
typename MatrixCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1885
typename MatrixCommon::scalar_type scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1882
scalar_const_reference operator()(size_t r, size_t c) const
Returns a const reference to the specified entry of the matrix.
StaticMatrix & operator=(StaticMatrix &&)=default
Default move assignment operator.
size_t number_of_cols() const noexcept
Returns the number of columns of the matrix.
StaticMatrix & operator=(StaticMatrix const &)=default
Default copy assignment operator.
std::pair< scalar_type, scalar_type > coords(const_iterator it) const
Class for views into a row of a matrix over a semiring.
Definition matrix.hpp:1080
typename RowViewCommon::iterator iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1096
typename RowViewCommon::scalar_const_reference scalar_const_reference
Alias for const references to the template parameter Scalar.
Definition matrix.hpp:1107
StaticRowView & operator=(StaticRowView &&)=default
Default move assignment operator.
typename RowViewCommon::scalar_reference scalar_reference
Alias for references to the template parameter Scalar.
Definition matrix.hpp:1102
iterator begin() noexcept
Returns a iterator pointing at the first entry.
iterator cend()
Returns a const iterator pointing one beyond the last entry of the row.
StaticRowView()=default
Default constructor.
typename matrix_type::Row Row
Alias for the type of a row in the underlying matrix.
Definition matrix.hpp:1114
typename RowViewCommon::const_iterator const_iterator
Alias for const iterators pointing at entries of a matrix.
Definition matrix.hpp:1093
const_iterator cbegin() const noexcept
Returns a const iterator pointing at the first entry.
iterator end()
Returns a iterator pointing one beyond the last entry of the row.
Scalar scalar_type
Alias for the template parameter Scalar.
Definition matrix.hpp:1099
StaticRowView(StaticRowView &&)=default
Default move constructor.
typename RowViewCommon::matrix_type matrix_type
Alias for the type of the underlying matrix.
Definition matrix.hpp:1111
StaticRowView(StaticRowView const &)=default
Default copy constructor.
static constexpr size_t size() const noexcept
Returns the size of the row.
StaticRowView & operator=(StaticRowView const &)=default
Default copy assignment operator.
StaticRowView(Row const &r)
Construct a row view from a Row.
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(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
Bipartition operator*(Bipartition const &x, Bipartition const &y)
Multiply two bipartitions.
std::ostringstream & operator<<(std::ostringstream &os, BMat8 const &x)
Insertion operator.
StaticMatrix< BooleanPlus, BooleanProd, BooleanZero, BooleanOne, R, C, int > StaticBMat
Alias for static boolean matrices.
Definition matrix.hpp:3949
static constexpr bool IsBMat
Helper to check if a type is BMat.
Definition matrix.hpp:4007
DynamicMatrix< BooleanPlus, BooleanProd, BooleanZero, BooleanOne, int > DynamicBMat
Alias for dynamic boolean matrices.
Definition matrix.hpp:3935
std::enable_if_t< IsBMat< Mat > > throw_if_bad_entry(Mat const &m)
Check the entries in a boolean matrix are valid.
Definition matrix.hpp:4052
std::conditional_t< R==0||C==0, DynamicBMat, StaticBMat< R, C > > BMat
Alias template for boolean matrices.
Definition matrix.hpp:3972
NegativeInfinity const NEGATIVE_INFINITY
Value for negative infinity.
Undefined const UNDEFINED
Value for something undefined.
PositiveInfinity const POSITIVE_INFINITY
Value for positive infinity.
#define LIBSEMIGROUPS_EXCEPTION(...)
Throw a LibsemigroupsException.
Definition exception.hpp:99
std::conditional_t< R==0||C==0, DynamicIntMat< Scalar >, StaticIntMat< R, C, Scalar > > IntMat
Alias template for integer matrices.
Definition matrix.hpp:4296
DynamicMatrix< IntegerPlus< Scalar >, IntegerProd< Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, Scalar > DynamicIntMat
Alias for dynamic integer matrices.
Definition matrix.hpp:4248
StaticMatrix< IntegerPlus< Scalar >, IntegerProd< Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, R, C, Scalar > StaticIntMat
Alias for static integer matrices.
Definition matrix.hpp:4271
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:855
static constexpr bool IsMaxPlusMat
Helper variable template.
Definition matrix.hpp:4622
constexpr bool IsStaticMatrix
Helper variable template.
Definition matrix.hpp:3645
constexpr bool IsDynamicMatrix
Helper variable template.
Definition matrix.hpp:3658
static constexpr bool IsIntMat
Helper variable template.
Definition matrix.hpp:4321
auto operator+(typename Mat::scalar_type a, Mat const &x) -> std::enable_if_t< IsMatrix< Mat >, Mat >
Add a scalar to a matrix.
Definition matrix.hpp:7942
static constexpr bool IsMatWithSemiring
Helper variable template.
Definition matrix.hpp:3672
static constexpr bool IsMinPlusMat
Helper variable template.
Definition matrix.hpp:4930
constexpr bool IsMatrix
Helper variable template.
Definition matrix.hpp:168
StaticMatrix< MaxPlusPlus< Scalar >, MaxPlusProd< Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMaxPlusMat
Alias for static max-plus matrices.
Definition matrix.hpp:4571
DynamicMatrix< MaxPlusPlus< Scalar >, MaxPlusProd< Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMaxPlusMat
Alias for dynamic max-plus matrices.
Definition matrix.hpp:4552
std::conditional_t< R==0||C==0, DynamicMaxPlusMat< Scalar >, StaticMaxPlusMat< R, C, Scalar > > MaxPlusMat
Alias template for max-plus matrices.
Definition matrix.hpp:4595
DynamicMatrix< MaxPlusPlus< Scalar >, MaxPlusTruncProd< T, Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMaxPlusTruncMat
Alias for dynamic truncated max-plus matrices.
Definition matrix.hpp:5299
std::conditional_t< R==0||C==0, std::conditional_t< T==0, DynamicMatrix< MaxPlusTruncSemiring< Scalar >, Scalar >, DynamicMaxPlusTruncMat< T, Scalar > >, StaticMaxPlusTruncMat< T, R, C, Scalar > > MaxPlusTruncMat
Alias template for truncated max-plus matrices.
Definition matrix.hpp:5345
StaticMatrix< MaxPlusPlus< Scalar >, MaxPlusTruncProd< T, Scalar >, MaxPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMaxPlusTruncMat
Alias for static truncated max-plus matrices.
Definition matrix.hpp:5319
static constexpr bool IsMaxPlusTruncMat
Helper to check if a type is MaxPlusTruncMat.
Definition matrix.hpp:5388
DynamicMatrix< MinPlusPlus< Scalar >, MinPlusProd< Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMinPlusMat
Alias for dynamic min-plus matrices.
Definition matrix.hpp:4860
StaticMatrix< MinPlusPlus< Scalar >, MinPlusProd< Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMinPlusMat
Alias for static min-plus matrices.
Definition matrix.hpp:4879
std::conditional_t< R==0||C==0, DynamicMinPlusMat< Scalar >, StaticMinPlusMat< R, C, Scalar > > MinPlusMat
Alias template for min-plus matrices.
Definition matrix.hpp:4903
DynamicMatrix< MinPlusPlus< Scalar >, MinPlusTruncProd< T, Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, Scalar > DynamicMinPlusTruncMat
Alias for dynamic truncated min-plus matrices.
Definition matrix.hpp:5775
StaticMatrix< MinPlusPlus< Scalar >, MinPlusTruncProd< T, Scalar >, MinPlusZero< Scalar >, IntegerZero< Scalar >, R, C, Scalar > StaticMinPlusTruncMat
Alias for static truncated min-plus matrices.
Definition matrix.hpp:5795
static constexpr bool IsMinPlusTruncMat
Helper to check if a type is MinPlusTruncMat.
Definition matrix.hpp:5865
std::conditional_t< R==0||C==0, std::conditional_t< T==0, DynamicMatrix< MinPlusTruncSemiring< Scalar >, Scalar >, DynamicMinPlusTruncMat< T, Scalar > >, StaticMinPlusTruncMat< T, R, C, Scalar > > MinPlusTruncMat
Alias template for truncated min-plus matrices.
Definition matrix.hpp:5822
DynamicMatrix< NTPSemiring< Scalar >, Scalar > DynamicNTPMatWithSemiring
Alias for ntp matrices with dynamic threshold and period.
Definition matrix.hpp:6329
DynamicMatrix< NTPPlus< T, P, Scalar >, NTPProd< T, P, Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, Scalar > DynamicNTPMatWithoutSemiring
Alias for ntp matrices with static threshold and period.
Definition matrix.hpp:6345
static constexpr bool IsNTPMat
Helper to check if a type is NTPMat.
Definition matrix.hpp:6449
std::conditional_t< R==0||C==0, std::conditional_t< T==0 &&P==0, DynamicNTPMatWithSemiring< Scalar >, DynamicNTPMatWithoutSemiring< T, P, Scalar > >, StaticNTPMat< T, P, R, C, Scalar > > NTPMat
Alias template for ntp matrices.
Definition matrix.hpp:6406
StaticMatrix< NTPPlus< T, P, Scalar >, NTPProd< T, P, Scalar >, IntegerZero< Scalar >, IntegerOne< Scalar >, R, C, Scalar > StaticNTPMat
Alias for ntp matrices with static threshold and period, and dimensions.
Definition matrix.hpp:6371
std::conditional_t< R==0||C==0, DynamicProjMaxPlusMat< Scalar >, StaticProjMaxPlusMat< R, C, Scalar > > ProjMaxPlusMat
Alias template for projective max-plus matrices.
Definition matrix.hpp:7033
detail::ProjMaxPlusMat< DynamicMaxPlusMat< Scalar > > DynamicProjMaxPlusMat
Alias for dynamic projective max-plus matrices with run-time dimensions.
Definition matrix.hpp:7016
static constexpr bool IsProjMaxPlusMat
Helper to check if a type is ProjMaxPlusMat.
Definition matrix.hpp:7063
detail::ProjMaxPlusMat< StaticMaxPlusMat< R, C, Scalar > > StaticProjMaxPlusMat
Alias for static projective max-plus matrices with compile-time arithmetic and dimensions.
Definition matrix.hpp:7002
T inner_product(T... args)
T 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:7461
void bitset_rows(Container &&views, detail::StaticVector1< BitSet< C >, R > &result)
Converts a container of row views of a boolean matrix to bit sets, and append them to another contain...
Definition matrix.hpp:7289
constexpr Scalar period(StaticNTPMat< T, P, R, C, Scalar > const &) noexcept
Returns the period of a static ntp matrix.
Definition matrix.hpp:6485
auto throw_if_bad_coords(Mat const &x, size_t r, size_t c) -> std::enable_if_t< IsMatrix< Mat > >
Throws the arguments do not index an entry of a matrix.
Definition matrix.hpp:235
constexpr auto threshold(Mat const &) noexcept -> std::enable_if_t<!detail::IsTruncMat< Mat >, typename Mat::scalar_type >
Returns the threshold of a matrix.
Definition matrix.hpp:3733
size_t row_space_size(Mat const &x)
Returns the size of the row space of a boolean matrix.
Definition matrix.hpp:7897
std::vector< typename Mat::RowView > rows(Mat const &x)
Returns a std::vector of row views into the rows of a dynamic matrix.
Definition matrix.hpp:7218
auto throw_if_bad_dim(Mat const &x, Mat const &y) -> std::enable_if_t< IsMatrix< Mat > >
Throws if two matrices do not have the same dimensions.
Definition matrix.hpp:206
Mat pow(Mat const &x, typename Mat::scalar_type e)
Returns a power of a matrix.
Definition matrix.hpp:7153
auto throw_if_not_square(Mat const &x) -> std::enable_if_t< IsMatrix< Mat > >
Throws if a matrix is not square.
Definition matrix.hpp:184
std::enable_if_t< IsMaxPlusTruncMat< Mat > > row_basis(Container &&views, std::decay_t< Container > &result)
Appends a basis for a space spanned by row views or bit sets to a container.
Definition matrix.hpp:7633
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T push_back(T... args)
T sort(T... args)
Function object for returning the multiplicative identity.
Definition matrix.hpp:3883
constexpr bool operator()() const noexcept
Call operator returning the multiplication identity true of the boolean semiring.
Definition matrix.hpp:3894
Function object for addition in the boolean semiring.
Definition matrix.hpp:3829
constexpr bool operator()(bool x, bool y) const noexcept
Call operator for addition.
Definition matrix.hpp:3842
Function object for multiplication in the boolean semiring.
Definition matrix.hpp:3856
constexpr bool operator()(bool x, bool y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:3869
Function object for returning the additive identity.
Definition matrix.hpp:3908
constexpr bool operator()() const noexcept
Call operator returning the additive identity false of the boolean semiring.
Definition matrix.hpp:3919
constexpr size_t operator()(Mat const &x) const noexcept
Call operator.
Definition matrix.hpp:8439
Adapter for the complexity of multiplication.
Definition adapters.hpp:128
constexpr size_t operator()(Mat const &x) const noexcept
Call operator.
Definition matrix.hpp:8468
Adapter for the degree of an element.
Definition adapters.hpp:166
constexpr size_t operator()(Mat const &x) const
Call operator.
Definition matrix.hpp:8497
Adapter for hashing.
Definition adapters.hpp:453
constexpr void operator()(Mat &, size_t) const noexcept
Call operator.
Definition matrix.hpp:8522
Adapter for increasing the degree of an element.
Definition adapters.hpp:206
Function object for returning the multiplicative identity.
Definition matrix.hpp:4222
constexpr Scalar operator()() const noexcept
Call operator returning the integer 1.
Definition matrix.hpp:4232
Function object for addition in the ring of integers.
Definition matrix.hpp:4138
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4151
Function object for multiplication in the ring of integers.
Definition matrix.hpp:4169
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4182
Function object for returning the additive identity.
Definition matrix.hpp:4197
constexpr Scalar operator()() const noexcept
Call operator returning the integer 0.
Definition matrix.hpp:4207
Function object for addition in the max-plus semiring.
Definition matrix.hpp:4440
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4455
Function object for multiplication in the max-plus semiring.
Definition matrix.hpp:4487
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4502
Function object for multiplication in truncated max-plus semirings.
Definition matrix.hpp:5074
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:5089
Function object for returning the additive identity of the max-plus semiring.
Definition matrix.hpp:4524
constexpr Scalar operator()() const noexcept
Call operator for additive identity.
Definition matrix.hpp:4536
Function object for addition in the min-plus semiring.
Definition matrix.hpp:4748
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:4763
Function object for multiplication in the min-plus semiring.
Definition matrix.hpp:4795
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:4810
Function object for multiplication in min-plus truncated semirings.
Definition matrix.hpp:5554
Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:5567
Function object for returning the additive identity of the min-plus semiring.
Definition matrix.hpp:4832
constexpr Scalar operator()() const noexcept
Call operator for additive identity.
Definition matrix.hpp:4844
Function object for addition in ntp semirings.
Definition matrix.hpp:6061
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for addition.
Definition matrix.hpp:6073
Function object for multiplication in an ntp semirings.
Definition matrix.hpp:6102
constexpr Scalar operator()(Scalar x, Scalar y) const noexcept
Call operator for multiplication.
Definition matrix.hpp:6116
Mat operator()(Mat const &x) const
Call operator.
Definition matrix.hpp:8553
Adapter for the identity element of the given type.
Definition adapters.hpp:253
void operator()(Mat &xy, Mat const &x, Mat const &y, size_t=0) const
Call operator.
Definition matrix.hpp:8589
Adapter for the product of two elements.
Definition adapters.hpp:291
T swap(T... args)
T tie(T... args)
T unique(T... args)