1 // 2 // libsemigroups - C++ library for semigroups and monoids 3 // Copyright (C) 2019 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 #include <cstddef> // for size_t 20 #include <vector> // for vector 21 22 #include "catch.hpp" // for REQUIRE 23 #include "libsemigroups/element-adapters.hpp" // for Product etc 24 #include "libsemigroups/element.hpp" // for BooleanMat 25 #include "libsemigroups/froidure-pin.hpp" // for FroidurePin<>::element_index_type 26 #include "libsemigroups/semiring.hpp" // for BooleanSemiring 27 #include "test-main.hpp" // for LIBSEMIGROUPS_TEST_CASE 28 29 namespace libsemigroups { 30 // Forward declaration 31 struct LibsemigroupsException; 32 33 bool constexpr REPORT = false; 34 35 LIBSEMIGROUPS_TEST_CASE("FroidurePin", 36 "016", 37 "non-pointer BooleanMat", 38 "[quick][froidure-pin][boolmat][booleanmat]") { 39 FroidurePin<BooleanMat> S; 40 S.add_generator( 41 BooleanMat({0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0})); 42 S.add_generator( 43 BooleanMat({0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1})); 44 S.add_generator( 45 BooleanMat({0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1})); 46 47 S.reserve(26); 48 auto rg = ReportGuard(REPORT); 49 50 REQUIRE(S.size() == 26); 51 REQUIRE(S.nr_idempotents() == 4); 52 size_t pos = 0; 53 54 for (auto it = S.cbegin(); it < S.cend(); ++it) { 55 REQUIRE(S.position(*it) == pos); 56 pos++; 57 } 58 59 S.add_generators( 60 {BooleanMat({1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0})}); 61 REQUIRE(S.size() == 29); 62 S.closure({BooleanMat({1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0})}); 63 REQUIRE(S.size() == 29); 64 REQUIRE(S.minimal_factorisation( 65 BooleanMat({1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0}) 66 * BooleanMat({0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0})) 67 == word_type({3, 0})); 68 REQUIRE(S.minimal_factorisation(28) == word_type({3, 0})); 69 REQUIRE( 70 S.at(28) 71 == BooleanMat({1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0}) 72 * BooleanMat({0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0})); 73 REQUIRE_THROWS_AS(S.minimal_factorisation(1000000000), 74 LibsemigroupsException); 75 pos = 0; 76 for (auto it = S.cbegin_idempotents(); it < S.cend_idempotents(); ++it) { 77 REQUIRE(*it * *it == *it); 78 pos++; 79 } 80 REQUIRE(pos == S.nr_idempotents()); 81 for (auto it = S.cbegin_sorted() + 1; it < S.cend_sorted(); ++it) { 82 REQUIRE(*(it - 1) < *it); 83 } 84 } 85 } // namespace libsemigroups 86