1 // 2 // libsemigroups - C++ library for semigroups and monoids 3 // Copyright (C) 2019 Finn Smith 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 // This file contains a declaration of fast boolean matrices up to dimension 8. 20 21 #ifndef LIBSEMIGROUPS_BMAT8_HPP_ 22 #define LIBSEMIGROUPS_BMAT8_HPP_ 23 24 #include <algorithm> // for uniform_int_distribution, swap 25 #include <cstddef> // for size_t 26 #include <cstdint> // for uint64_t 27 #include <iosfwd> // for operator<<, ostringstream 28 #include <random> // for mt19937, random_device 29 #include <utility> // for hash 30 #include <vector> // for vector 31 32 #include "adapters.hpp" // for Complexity, Degree, etc . . . 33 #include "libsemigroups-debug.hpp" // for LIBSEMIGROUPS_ASSERT 34 #include "string.hpp" // for detail::to_string 35 36 namespace libsemigroups { 37 namespace bmat8_helpers { 38 //! Returns the identity boolean matrix of a given dimension. 39 //! 40 //! \tparam T the type of the boolean matrix being constructed, should be 41 //! BMat8 or HPCombi::BMat8. 42 //! 43 //! \param dim the dimension of the identity matrix, must be at most 7. 44 //! 45 //! \returns 46 //! A value of type \p T with the first \p dim values on the main diagonal 47 //! equal to 1 and every other entry equal to 0. 48 //! 49 //! \exceptions 50 //! \noexcept 51 //! 52 //! \complexity 53 //! Constant. 54 //! 55 //! \sa BMat8::one. 56 // TODO(later) noexcept should depend on whether or not the constructor of 57 // T is noexcept 58 template <typename T> one(size_t dim)59 T one(size_t dim) noexcept { 60 LIBSEMIGROUPS_ASSERT(dim <= 8); 61 static std::array<uint64_t, 9> const ones = {0x0000000000000000, 62 0x8000000000000000, 63 0x8040000000000000, 64 0x8040200000000000, 65 0x8040201000000000, 66 0x8040201008000000, 67 0x8040201008040000, 68 0x8040201008040200, 69 0x8040201008040201}; 70 return T(ones[dim]); 71 } 72 } // namespace bmat8_helpers 73 74 //! Defined in ``bmat8.hpp``. 75 //! 76 //! Class for fast boolean matrices of dimension up to 8 x 8 77 //! 78 //! The member functions for these small matrices over the boolean semiring 79 //! are more optimised than the generic member functions for boolean matrices. 80 //! Note that all BMat8 are represented internally as an 8 x 8 matrix; 81 //! any entries not defined by the user are taken to be 0. This does 82 //! not affect the results of any calculations. 83 //! 84 //! BMat8 is a trivial class. 85 class BMat8 final { 86 public: 87 //! Default constructor. 88 //! 89 //! There is no guarantee about the contents of the matrix constructed. 90 //! 91 //! \par Parameters 92 //! (None) 93 //! 94 //! \exceptions 95 //! \noexcept 96 //! 97 //! \complexity 98 //! Constant. 99 BMat8() noexcept = default; 100 101 //! Construct from uint64_t. 102 //! 103 //! This constructor initializes a BMat8 to have rows equal to the 104 //! 8 chunks, of 8 bits each, of the binary representation of \p mat. 105 //! 106 //! \param mat the integer representation of the matrix being constructed. 107 //! 108 //! \exceptions 109 //! \noexcept 110 //! 111 //! \complexity 112 //! Constant. BMat8(uint64_t mat)113 explicit BMat8(uint64_t mat) noexcept : _data(mat) {} 114 115 //! A constructor. 116 //! 117 //! This constructor initializes a matrix where the rows of the matrix 118 //! are the vectors in \p mat. 119 //! 120 //! \param mat the vector of vectors representation of the matrix being 121 //! constructed. 122 //! 123 //! \throws LibsemigroupsException if \p mat has 0 rows. 124 //! \throws LibsemigroupsException if \p mat has more than 8 rows. 125 //! \throws LibsemigroupsException if the rows of \p mat are not all of the 126 //! same length. 127 //! 128 //! \complexity 129 //! Constant. 130 explicit BMat8(std::vector<std::vector<bool>> const& mat); 131 132 //! Default copy constructor. 133 //! 134 //! \exceptions 135 //! \noexcept 136 //! 137 //! \complexity 138 //! Constant. 139 BMat8(BMat8 const&) noexcept = default; 140 141 //! Default move constructor. 142 //! 143 //! \exceptions 144 //! \noexcept 145 //! 146 //! \complexity 147 //! Constant. 148 BMat8(BMat8&&) noexcept = default; 149 150 //! Default copy assignment operator. 151 //! 152 //! \exceptions 153 //! \noexcept 154 //! 155 //! \complexity 156 //! Constant. 157 BMat8& operator=(BMat8 const&) noexcept = default; 158 159 //! Default move assignment operator. 160 //! 161 //! \exceptions 162 //! \noexcept 163 //! 164 //! \complexity 165 //! Constant. 166 BMat8& operator=(BMat8&&) noexcept = default; 167 168 ~BMat8() = default; 169 170 //! Returns \c true if \c this equals \p that. 171 //! 172 //! This member function checks the mathematical equality of two BMat8 173 //! objects. 174 //! 175 //! \param that the BMat8 for comparison. 176 //! 177 //! \exceptions 178 //! \noexcept 179 //! 180 //! \complexity 181 //! Constant. operator ==(BMat8 const & that) const182 bool operator==(BMat8 const& that) const noexcept { 183 return _data == that._data; 184 } 185 186 //! Returns \c true if \c this does not equal \p that 187 //! 188 //! This member function checks the mathematical inequality of two BMat8 189 //! objects. 190 //! 191 //! \param that the BMat8 for comparison. 192 //! 193 //! \exceptions 194 //! \noexcept 195 //! 196 //! \complexity 197 //! Constant. operator !=(BMat8 const & that) const198 bool operator!=(BMat8 const& that) const noexcept { 199 return _data != that._data; 200 } 201 202 //! Returns \c true if \c this is less than \p that. 203 //! 204 //! This member function checks whether a BMat8 objects is less than 205 //! another. We order by the results of to_int() for each matrix. 206 //! 207 //! \param that the BMat8 for comparison. 208 //! 209 //! \exceptions 210 //! \noexcept 211 //! 212 //! \complexity 213 //! Constant. operator <(BMat8 const & that) const214 bool operator<(BMat8 const& that) const noexcept { 215 return _data < that._data; 216 } 217 218 //! Returns \c true if \c this is greater than \p that. 219 //! 220 //! This member function checks whether a BMat8 objects is greater than 221 //! another. We order by the results of to_int() for each matrix. 222 //! 223 //! \param that the BMat8 for comparison. 224 //! 225 //! \exceptions 226 //! \noexcept 227 //! 228 //! \complexity 229 //! Constant. operator >(BMat8 const & that) const230 bool operator>(BMat8 const& that) const noexcept { 231 return _data > that._data; 232 } 233 234 //! Returns the entry in the (\p i, \p j)th position. 235 //! 236 //! This member function returns the entry in the (\p i, \p j)th position. 237 //! 238 //! \param i the row of the entry sought. 239 //! \param j the column of the entry sought. 240 //! 241 //! \returns 242 //! A ``bool``. 243 //! 244 //! \exceptions 245 //! \noexcept 246 //! 247 //! \complexity 248 //! Constant. 249 //! 250 //! \note 251 //! Note that since all matrices are internally represented as 8 x 8, it 252 //! is possible to access entries that you might not believe exist. 253 //! 254 //! \warning 255 //! No checks on the parameters \p i and \p j are performed, if \p i or \p 256 //! j is greater than 7, then bad things will happen. get(size_t i,size_t j) const257 bool get(size_t i, size_t j) const noexcept { 258 LIBSEMIGROUPS_ASSERT(i < 8); 259 LIBSEMIGROUPS_ASSERT(j < 8); 260 return (_data << (8 * i + j)) >> 63; 261 } 262 263 // TODO(later) at method 264 265 //! Sets the (\p i, \p j)th position to \p val. 266 //! 267 //! This member function sets the (\p i, \p j)th entry of \c this to \p val. 268 //! Uses the bit twiddle for setting bits found 269 //! <a href=http://graphics.stanford.edu/~seander/bithacks>here</a>. 270 //! 271 //! \param i the row 272 //! \param j the column 273 //! \param val the value to set in position (\p i, \p j)th 274 //! 275 //! \returns 276 //! (None) 277 //! 278 //! \throws LibsemigroupsException if \p i or \p j is out of bounds. 279 //! 280 //! \complexity 281 //! Constant. 282 void set(size_t i, size_t j, bool val); 283 284 //! Returns the integer representation of \c this. 285 //! 286 //! Returns an unsigned integer obtained by interpreting an 8 x 8 287 //! BMat8 as a sequence of 64 bits (reading rows left to right, 288 //! from top to bottom) and then realising this sequence as an unsigned 289 //! int. 290 //! 291 //! \returns 292 //! A ``uint64_t``. 293 //! 294 //! \exceptions 295 //! \noexcept 296 //! 297 //! \complexity 298 //! Constant. 299 //! 300 //! \par Parameters 301 //! (None) to_int() const302 inline uint64_t to_int() const noexcept { 303 return _data; 304 } 305 306 //! Returns the transpose of \c this. 307 //! 308 //! Uses the technique found in [Knu09](../biblio.html#knuth2009aa). 309 //! 310 //! \returns 311 //! A BMat8. 312 //! 313 //! \exceptions 314 //! \noexcept 315 //! 316 //! \complexity 317 //! Constant. 318 //! 319 //! \par Parameters 320 //! (None) transpose() const321 inline BMat8 transpose() const noexcept { 322 uint64_t x = _data; 323 uint64_t y = (x ^ (x >> 7)) & 0xAA00AA00AA00AA; 324 x = x ^ y ^ (y << 7); 325 y = (x ^ (x >> 14)) & 0xCCCC0000CCCC; 326 x = x ^ y ^ (y << 14); 327 y = (x ^ (x >> 28)) & 0xF0F0F0F0; 328 x = x ^ y ^ (y << 28); 329 return BMat8(x); 330 } 331 332 //! Returns the matrix product of \c this and \p that 333 //! 334 //! This member function returns the standard matrix product (over the 335 //! boolean semiring) of two BMat8 objects. 336 //! Uses the technique given [here](https://stackoverflow.com/a/18448513). 337 //! 338 //! \param that the matrix we want to multiply by \c this. 339 //! 340 //! \returns 341 //! A BMat8. 342 //! 343 //! \exceptions 344 //! \noexcept 345 //! 346 //! \complexity 347 //! Constant. 348 BMat8 operator*(BMat8 const& that) const noexcept; 349 350 //! Insertion operator 351 //! 352 //! This member function allows BMat8 objects to be inserted into an 353 //! std::ostringstream. 354 friend std::ostringstream& operator<<(std::ostringstream& os, 355 BMat8 const& bm); 356 357 //! Insertion operator 358 //! 359 //! This member function allows BMat8 objects to be inserted into a 360 //! std::ostream. operator <<(std::ostream & os,BMat8 const & bm)361 friend std::ostream& operator<<(std::ostream& os, BMat8 const& bm) { 362 os << detail::to_string(bm); 363 return os; 364 } 365 366 //! Construct a random BMat8. 367 //! 368 //! This static member function returns a BMat8 chosen at random. 369 //! 370 //! \returns 371 //! A BMat8. 372 //! 373 //! \exceptions 374 //! \no_libsemigroups_except 375 //! 376 //! \par Parameters 377 //! (None) 378 // Not noexcept since std::uniform_int_distribution::operator() is not 379 // noexcept. random()380 static BMat8 random() { 381 return BMat8(_dist(_gen)); 382 } 383 384 //! Construct a random BMat8 of dimension at most \p dim. 385 //! 386 //! This static member function returns a BMat8 chosen at random, where 387 //! only the top-left \p dim x \p dim entries can be non-zero. 388 //! 389 //! \returns 390 //! A BMat8. 391 //! 392 //! \exceptions 393 //! \no_libsemigroups_except 394 //! 395 //! \par Parameters 396 //! (None) 397 // Not noexcept since std::uniform_int_distribution::operator() is not 398 // noexcept. 399 static BMat8 random(size_t dim); 400 401 //! Swaps \c this with \p that. 402 //! 403 //! This member function swaps the values of \c this and \p that. 404 //! 405 //! \param that the BMat8 to swap \c this with. 406 //! 407 //! \returns 408 //! (None) 409 //! 410 //! \exceptions 411 //! \noexcept 412 //! 413 //! \complexity 414 //! Constant. swap(BMat8 & that)415 inline void swap(BMat8& that) noexcept { 416 std::swap(this->_data, that._data); 417 } 418 419 //! Find a basis for the row space of \c this. 420 //! 421 //! This member function returns a BMat8 whose non-zero rows form a basis 422 //! for the row space of \c this. 423 //! 424 //! \returns 425 //! A BMat8. 426 //! 427 //! \exceptions 428 //! \noexcept 429 //! 430 //! \complexity 431 //! Constant. 432 //! 433 //! \par Parameters 434 //! (None) 435 BMat8 row_space_basis() const noexcept; 436 437 //! Find a basis for the column space of \c this. 438 //! 439 //! This member function returns a BMat8 whose non-zero columns form a basis 440 //! for the column space of \c this. 441 //! 442 //! \returns 443 //! A BMat8. 444 //! 445 //! \exceptions 446 //! \noexcept 447 //! 448 //! \complexity 449 //! Constant. 450 //! 451 //! \par Parameters 452 //! (None) col_space_basis() const453 BMat8 col_space_basis() const noexcept { 454 return this->transpose().row_space_basis().transpose(); 455 } 456 457 //! Returns a vector containing the rows of \c this 458 //! 459 //! This member function returns a std::vector of uint8_ts representing the 460 //! rows of \c this. The vector will always be of length 8, even if \c this 461 //! was constructed with fewer rows. 462 //! 463 //! \returns 464 //! A std::vector<uint8_t>. 465 //! 466 //! \exceptions 467 //! \no_libsemigroups_except 468 //! 469 //! \complexity 470 //! Constant. 471 //! 472 //! \par Parameters 473 //! (None) 474 // TODO(later) make this return an array instead of a vector 475 std::vector<uint8_t> rows() const; 476 477 //! Find the size of the row space of \c this. 478 //! 479 //! \returns 480 //! A \c size_t. 481 //! 482 //! \exceptions 483 //! \no_libsemigroups_except 484 //! 485 //! \complexity 486 //! \f$O(n)\f$ where \f$n\f$ is the return value of this function. 487 //! 488 //! \par Parameters 489 //! (None) 490 //! 491 //! \sa bmat8_helpers::col_space_size. 492 size_t row_space_size() const; 493 494 //! Returns the number of non-zero rows in \c this. 495 //! 496 //! BMat8s do not know their "dimension" - in effect they are all of 497 //! dimension 8. However, this member function can be used to obtain the 498 //! number of non-zero rows of \c this. 499 //! 500 //! \returns 501 //! A \c size_t. 502 //! 503 //! \exceptions 504 //! \noexcept 505 //! 506 //! \complexity 507 //! Constant. 508 //! 509 //! \par Parameters 510 //! (None) 511 //! 512 //! \sa bmat8_helpers::nr_cols and bmat8_helpers::minimum_dim. nr_rows() const513 size_t nr_rows() const noexcept { 514 size_t count = 0; 515 for (size_t i = 0; i < 8; ++i) { 516 if (_data << (8 * i) >> 56 > 0) { 517 count++; 518 } 519 } 520 return count; 521 } 522 523 //! Check whether \c this is a regular element of the full boolean matrix 524 //! monoid of appropriate dimension. 525 //! 526 //! \returns 527 //! A \c true if there exists a boolean matrix \c y such that `x * y * x = 528 //! x` where \c x is \c *this. 529 //! 530 //! \exceptions 531 //! \noexcept 532 //! 533 //! \complexity 534 //! Constant. 535 //! 536 //! \par Parameters 537 //! (None) is_regular_element() const538 bool is_regular_element() const noexcept { 539 return *this 540 * BMat8( 541 ~(*this * BMat8(~_data).transpose() * (*this)).to_int()) 542 .transpose() 543 * (*this) 544 == *this; 545 } 546 547 //! Returns the identity BMat8. 548 //! 549 //! This member function returns the BMat8 with the first \c dim entries in 550 //! the main diagonal equal to \c 1 and every other value equal to \c 0. 551 //! 552 //! \param dim the dimension of the identity (default: 8) 553 //! 554 //! \returns 555 //! A BMat8. 556 //! 557 //! \exceptions 558 //! \noexcept 559 //! 560 //! \complexity 561 //! Constant. one(size_t dim=8)562 static BMat8 one(size_t dim = 8) noexcept { 563 return bmat8_helpers::one<BMat8>(dim); 564 } 565 566 private: 567 void sort_rows() noexcept; 568 569 uint64_t _data; 570 static std::random_device _rd; 571 static std::mt19937 _gen; 572 static std::uniform_int_distribution<uint64_t> _dist; 573 }; 574 575 static_assert(std::is_trivial<BMat8>(), "BMat8 is not a trivial class!"); 576 577 //! Defined in ``bmat8.hpp``. 578 //! 579 //! This namespace contains various helper functions for the class BMat8. 580 //! These functions could be member functions of BMat8 but they only use 581 //! public member functions of BMat8, and so they are declared as free 582 //! functions instead. 583 namespace bmat8_helpers { 584 // TODO(later) these should be templated to allow using HPCombi::BMat8's 585 // here too. 586 //! Returns the number of non-zero columns in \p x. 587 //! 588 //! BMat8s do not know their "dimension" - in effect they are all of 589 //! dimension 8. However, this member function can be used to obtain the 590 //! number of non-zero rows of \c this. 591 //! 592 //! \param x the BMat8 whose number of columns we want. 593 //! 594 //! \returns 595 //! A \c size_t. 596 //! 597 //! \exceptions 598 //! \noexcept 599 //! 600 //! \complexity 601 //! Constant. 602 //! 603 //! \sa BMat8::nr_rows and bmat8_helpers::minimum_dim. 604 // noexcept because transpose and nr_rows are. nr_cols(BMat8 const & x)605 static inline size_t nr_cols(BMat8 const& x) noexcept { 606 return x.transpose().nr_rows(); 607 } 608 609 //! Find the size of the column space of \c x. 610 //! 611 //! \param x a BMat8. 612 //! 613 //! \returns 614 //! A \c size_t. 615 //! 616 //! \exceptions 617 //! \no_libsemigroups_except 618 //! 619 //! \complexity 620 //! \f$O(n)\f$ where \f$n\f$ is the return value of this function. 621 //! 622 //! \sa BMat8::row_space_size. 623 // Not noexcept because row_space_size isn't. col_space_size(BMat8 const & x)624 static inline size_t col_space_size(BMat8 const& x) { 625 return x.transpose().row_space_size(); 626 } 627 628 //! Find the minimum dimension of \p x. 629 //! 630 //! This member function returns the maximal \c i such that row \c i or 631 //! column \c i contains a \c 1. 632 //! 633 //! \param x a BMat8. 634 //! 635 //! \exceptions 636 //! \noexcept 637 //! 638 //! \complexity 639 //! Constant. 640 size_t minimum_dim(BMat8 const& x) noexcept; 641 642 } // namespace bmat8_helpers 643 } // namespace libsemigroups 644 645 namespace std { 646 template <> 647 struct hash<libsemigroups::BMat8> { operator ()std::hash648 size_t operator()(libsemigroups::BMat8 const& bm) const { 649 return hash<uint64_t>()(bm.to_int()); 650 } 651 }; 652 } // namespace std 653 654 namespace libsemigroups { 655 //! Specialization of the adapter Complexity for instances of BMat8. 656 //! 657 //! \sa Complexity. 658 template <> 659 struct Complexity<BMat8> { 660 //! Returns 0; BMat8 multiplication is constant complexity. operator ()libsemigroups::Complexity661 constexpr inline size_t operator()(BMat8 const&) const noexcept { 662 return 0; 663 } 664 }; 665 666 //! Specialization of the adapter Degree for instances of BMat8. 667 //! 668 //! \sa Degree. 669 template <> 670 struct Degree<BMat8> { 671 //! Returns 8; all BMat8s have degree 8. operator ()libsemigroups::Degree672 constexpr inline size_t operator()(BMat8 const&) const noexcept { 673 return 8; 674 } 675 }; 676 677 //! Specialization of the adapter IncreaseDegree for instances of BMat8. 678 //! 679 //! \sa IncreaseDegree. 680 template <> 681 struct IncreaseDegree<BMat8> { 682 //! Does nothing. operator ()libsemigroups::IncreaseDegree683 inline void operator()(BMat8 const&) const noexcept {} 684 }; 685 686 //! Specialization of the adapter One for instances of BMat8. 687 //! 688 //! \sa One. 689 template <> 690 struct One<BMat8> { 691 //! Returns \p x.one() operator ()libsemigroups::One692 inline BMat8 operator()(BMat8 const& x) const noexcept { 693 return x.one(); 694 } 695 //! Returns BMat8::one(dim) operator ()libsemigroups::One696 inline BMat8 operator()(size_t dim = 8) const noexcept { 697 return BMat8::one(dim); 698 } 699 }; 700 701 //! Specialization of the adapter Product for instances of BMat8. 702 //! 703 //! \sa Product. 704 template <> 705 struct Product<BMat8> { 706 //! Changes \p xy in place to hold the product of \p x and \p y operator ()libsemigroups::Product707 inline void operator()(BMat8& xy, 708 BMat8 const& x, 709 BMat8 const& y, 710 size_t = 0) const noexcept { 711 xy = x * y; 712 } 713 }; 714 715 //! Specialization of the adapter ImageRightAction for instances of BMat8. 716 //! 717 //! \sa ImageRightAction. 718 template <> 719 struct ImageRightAction<BMat8, BMat8> { 720 //! Changes \p res in place to hold the image of \p pt under the right 721 //! action of \p x. operator ()libsemigroups::ImageRightAction722 void operator()(BMat8& res, 723 BMat8 const& pt, 724 BMat8 const& x) const noexcept { 725 res = (pt * x).row_space_basis(); 726 } 727 }; 728 729 //! Specialization of the adapter ImageLeftAction for instances of BMat8. 730 //! 731 //! \sa ImageLeftAction. 732 template <> 733 struct ImageLeftAction<BMat8, BMat8> { 734 //! Changes \p res in place to hold the image of \p pt under the left 735 //! action of \p x. operator ()libsemigroups::ImageLeftAction736 void operator()(BMat8& res, 737 BMat8 const& pt, 738 BMat8 const& x) const noexcept { 739 res = (x * pt).col_space_basis(); 740 } 741 }; 742 743 //! Specialization of the adapter Inverse for instances of BMat8. 744 //! 745 //! \sa Inverse. 746 template <> 747 struct Inverse<BMat8> { 748 //! Returns the group inverse of \p x. operator ()libsemigroups::Inverse749 inline BMat8 operator()(BMat8 const& x) const noexcept { 750 LIBSEMIGROUPS_ASSERT(x * x.transpose() == x.one()); 751 return x.transpose(); 752 } 753 }; 754 755 //! Specialization of the adapter LambdaValue for instances of BMat8. 756 //! 757 //! \sa LambdaValue 758 template <> 759 struct LambdaValue<BMat8> { 760 //! The type of Lambda values for BMat8 is also BMat8; this provides an 761 //! efficient representation of row space bases. 762 using type = BMat8; 763 }; 764 765 //! Specialization of the adapter RhoValue for instances of BMat8. 766 //! 767 //! \sa RhoValue 768 template <> 769 struct RhoValue<BMat8> { 770 //! The type of Rho values for BMat8 is also BMat8; this provides an 771 //! efficient representation of column space bases. 772 using type = BMat8; 773 }; 774 775 //! Specialization of the adapter Lambda for instances of BMat8. 776 //! 777 //! \sa Lambda. 778 template <> 779 struct Lambda<BMat8, BMat8> { 780 //! Returns the lambda value of \p x as used in the Konieczny algorithm; for 781 //! BMat8 this is the row space basis. 782 // noexcept because BMat8::row_space_basis is noexcept operator ()libsemigroups::Lambda783 inline void operator()(BMat8& res, BMat8 const& x) const noexcept { 784 res = x.row_space_basis(); 785 } 786 }; 787 788 //! Specialization of the adapter Rho for instances of BMat8. 789 //! 790 //! \sa Rho. 791 template <> 792 struct Rho<BMat8, BMat8> { 793 //! Returns the rho value of \p x as used in the Konieczny algorithm; for 794 //! BMat8 this is the column space basis. 795 // noexcept because BMat8::col_space_basis is noexcept operator ()libsemigroups::Rho796 inline void operator()(BMat8& res, BMat8 const& x) const noexcept { 797 res = x.col_space_basis(); 798 } 799 }; 800 801 //! Specialization of the adapter Rank for instances of BMat8. 802 //! 803 //! \sa Rank. 804 template <> 805 struct Rank<BMat8> { 806 //! Returns the rank of \p x as used in the Konieczny algorithm; for BMat8 807 //! this is the size of the row space. operator ()libsemigroups::Rank808 inline size_t operator()(BMat8 const& x) const noexcept { 809 return x.row_space_size(); 810 } 811 }; 812 } // namespace libsemigroups 813 814 #endif // LIBSEMIGROUPS_BMAT8_HPP_ 815