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 "libsemigroups/froidure-pin-base.hpp" 20 21 #include <vector> 22 23 #include "libsemigroups/libsemigroups-exception.hpp" 24 #include "libsemigroups/report.hpp" 25 26 namespace libsemigroups { 27 using element_index_type = FroidurePinBase::element_index_type; 28 29 //////////////////////////////////////////////////////////////////////// 30 // FroidurePinBase - constructors and destructor - public 31 //////////////////////////////////////////////////////////////////////// 32 FroidurePinBase()33 FroidurePinBase::FroidurePinBase() 34 : Runner(), 35 _degree(UNDEFINED), 36 _duplicate_gens(), 37 _enumerate_order(), 38 _final(), 39 _first(), 40 _found_one(false), 41 _idempotents_found(false), 42 _is_idempotent(), 43 _left(), 44 _length(), 45 _lenindex({0, 0}), 46 _letter_to_pos(), 47 _nr(0), 48 _nr_rules(0), 49 _pos(0), 50 _pos_one(0), 51 _prefix(), 52 _reduced(), 53 _right(), 54 _suffix(), 55 _wordlen(0), // (length of the current word) - 1 56 // Deprecated, remove in v2 57 _relation_gen(0), 58 _relation_pos(UNDEFINED) { 59 #ifdef LIBSEMIGROUPS_VERBOSE 60 _nr_products = 0; 61 #endif 62 _right.set_default_value(UNDEFINED); 63 } 64 FroidurePinBase(FroidurePinBase const & S)65 FroidurePinBase::FroidurePinBase(FroidurePinBase const& S) 66 : Runner(S), 67 _degree(UNDEFINED), // _degree must be UNDEFINED until !_gens.empty() 68 _duplicate_gens(S._duplicate_gens), 69 _enumerate_order(S._enumerate_order), 70 _final(S._final), 71 _first(S._first), 72 _found_one(S._found_one), 73 _idempotents_found(S._idempotents_found), 74 _is_idempotent(S._is_idempotent), 75 _left(S._left), 76 _length(S._length), 77 _lenindex(S._lenindex), 78 _letter_to_pos(S._letter_to_pos), 79 _nr(S._nr), 80 _nr_rules(S._nr_rules), 81 _pos(S._pos), 82 _pos_one(S._pos_one), 83 _prefix(S._prefix), 84 _reduced(S._reduced), 85 _right(S._right), 86 _suffix(S._suffix), 87 _wordlen(S._wordlen), 88 _relation_gen(S._relation_gen), 89 _relation_pos(S._relation_pos) { 90 #ifdef LIBSEMIGROUPS_VERBOSE 91 _nr_products = 0; 92 #endif 93 } 94 95 FroidurePinBase::~FroidurePinBase() = default; 96 97 //////////////////////////////////////////////////////////////////////// 98 // FroidurePinBase - constructors - private 99 //////////////////////////////////////////////////////////////////////// 100 101 // Partial copy. 102 // \p copy a semigroup 103 // \p coll a collection of additional generators 104 // 105 // This is a constructor for a semigroup generated by the generators of the 106 // FroidurePin copy and the (possibly) additional generators coll. 107 // 108 // The relevant parts of the data structure of copy are copied and 109 // \c this will be corrupt unless add_generators or closure is called 110 // subsequently. This is why this member function is private. 111 // 112 // The same effect can be obtained by copying copy using the copy 113 // constructor and then calling add_generators or closure. However, 114 // this constructor avoids copying those parts of the data structure of 115 // copy that add_generators invalidates anyway. If copy has not been 116 // enumerated at all, then these two routes for adding more generators are 117 // equivalent. 118 // 119 // <add_generators> or <closure> should usually be called after this. partial_copy(FroidurePinBase const & S)120 void FroidurePinBase::partial_copy(FroidurePinBase const& S) { 121 _degree = S._degree; // copy for comparison in add_generators 122 _duplicate_gens = S._duplicate_gens; 123 _found_one = S._found_one; // copy in case degree doesn't change in 124 // add_generators 125 _idempotents_found = S._idempotents_found; 126 _is_idempotent = S._is_idempotent; 127 _left = S._left; 128 _lenindex = {0, S._lenindex[1]}; 129 _letter_to_pos = S._letter_to_pos; 130 _nr = S._nr; 131 _nr_rules = 0; 132 _pos = S._pos; 133 _pos_one = S._pos_one; // copy in case degree doesn't change in 134 // add_generators 135 _reduced = S._reduced; 136 _right = S._right; 137 _wordlen = 0; 138 _relation_gen = 0; 139 _relation_pos = UNDEFINED; 140 141 LIBSEMIGROUPS_ASSERT(S._lenindex.size() > 1); 142 143 #ifdef LIBSEMIGROUPS_VERBOSE 144 _nr_products = 0; 145 #endif 146 147 // the following are required for assignment to specific positions in 148 // add_generators 149 _final.resize(S._nr, 0); 150 _first.resize(S._nr, 0); 151 _length.resize(S._nr, 0); 152 _prefix.resize(S._nr, 0); 153 _suffix.resize(S._nr, 0); 154 155 _enumerate_order.reserve(S._nr); 156 157 // add the distinct old generators to new _enumerate_order 158 LIBSEMIGROUPS_ASSERT(S._lenindex.size() > 1); 159 for (enumerate_index_type i = 0; i < S._lenindex[1]; i++) { 160 _enumerate_order.push_back(S._enumerate_order[i]); 161 _final[_enumerate_order[i]] = S._final[S._enumerate_order[i]]; 162 _first[_enumerate_order[i]] = S._first[S._enumerate_order[i]]; 163 _prefix[_enumerate_order[i]] = UNDEFINED; 164 _suffix[_enumerate_order[i]] = UNDEFINED; 165 _length[_enumerate_order[i]] = 1; 166 } 167 } 168 169 //////////////////////////////////////////////////////////////////////// 170 // FroidurePinBase - member functions - public 171 //////////////////////////////////////////////////////////////////////// 172 word_to_pos(word_type const & w) const173 element_index_type FroidurePinBase::word_to_pos(word_type const& w) const { 174 // w is a word in the generators (i.e. a vector of letter_type's) 175 if (w.size() == 0) { 176 LIBSEMIGROUPS_EXCEPTION("the given word has length 0"); 177 } 178 for (auto x : w) { 179 validate_letter_index(x); 180 } 181 element_index_type out = _letter_to_pos[w[0]]; 182 for (auto it = w.cbegin() + 1; it < w.cend() && out != UNDEFINED; ++it) { 183 out = _right.get(out, *it); 184 } 185 return out; 186 } 187 188 element_index_type product_by_reduction(element_index_type i,element_index_type j) const189 FroidurePinBase::product_by_reduction(element_index_type i, 190 element_index_type j) const { 191 validate_element_index(i); 192 validate_element_index(j); 193 194 if (length_const(i) <= length_const(j)) { 195 while (i != UNDEFINED) { 196 j = _left.get(j, _final[i]); 197 i = _prefix[i]; 198 } 199 return j; 200 } else { 201 while (j != UNDEFINED) { 202 i = _right.get(i, _first[j]); 203 j = _suffix[j]; 204 } 205 return i; 206 } 207 } 208 209 // Deprecated, remove in v2 next_relation(word_type & relation)210 void FroidurePinBase::next_relation(word_type& relation) { 211 if (!finished()) { 212 run(); 213 } 214 215 relation.clear(); 216 217 if (_relation_pos == _nr) { // no more relations 218 return; 219 } 220 221 if (_relation_pos != UNDEFINED) { 222 while (_relation_pos < _nr) { 223 while (_relation_gen < nr_generators()) { 224 if (!_reduced.get(_enumerate_order[_relation_pos], _relation_gen) 225 && (_relation_pos < _lenindex[1] 226 || _reduced.get(_suffix[_enumerate_order[_relation_pos]], 227 _relation_gen))) { 228 relation.push_back(_enumerate_order[_relation_pos]); 229 relation.push_back(_relation_gen); 230 relation.push_back( 231 _right.get(_enumerate_order[_relation_pos], _relation_gen)); 232 break; 233 } 234 _relation_gen++; 235 } 236 if (_relation_gen == nr_generators()) { // then relation is empty 237 _relation_gen = 0; 238 _relation_pos++; 239 } else { 240 break; 241 } 242 } 243 _relation_gen++; 244 } else { 245 // duplicate generators 246 if (_relation_gen < _duplicate_gens.size()) { 247 relation.push_back(_duplicate_gens[_relation_gen].first); 248 relation.push_back(_duplicate_gens[_relation_gen].second); 249 _relation_gen++; 250 } else { 251 _relation_gen = 0; 252 _relation_pos++; 253 next_relation(relation); 254 } 255 } 256 } 257 enumerate(size_t limit)258 void FroidurePinBase::enumerate(size_t limit) { 259 if (finished() || limit <= current_size()) { 260 return; 261 } else if (LIMIT_MAX - batch_size() > current_size()) { 262 limit = std::max(limit, current_size() + batch_size()); 263 } else { // batch_size() is very big for some reason 264 limit = batch_size(); 265 } 266 REPORT_DEFAULT( 267 "limit = %llu (%s)\n", static_cast<uint64_t>(limit), __func__); 268 run_until([this, &limit]() -> bool { return current_size() >= limit; }); 269 } 270 271 //////////////////////////////////////////////////////////////////////// 272 // FroidurePinBase - settings - public 273 //////////////////////////////////////////////////////////////////////// 274 batch_size(size_t batch_size)275 FroidurePinBase& FroidurePinBase::batch_size(size_t batch_size) noexcept { 276 _settings._batch_size = batch_size; 277 return *this; 278 } 279 batch_size() const280 size_t FroidurePinBase::batch_size() const noexcept { 281 return _settings._batch_size; 282 } 283 max_threads(size_t nr_threads)284 FroidurePinBase& FroidurePinBase::max_threads(size_t nr_threads) noexcept { 285 unsigned int n 286 = static_cast<unsigned int>(nr_threads == 0 ? 1 : nr_threads); 287 _settings._max_threads = std::min(n, std::thread::hardware_concurrency()); 288 return *this; 289 } 290 max_threads() const291 size_t FroidurePinBase::max_threads() const noexcept { 292 return _settings._max_threads; 293 } 294 295 FroidurePinBase& concurrency_threshold(size_t thrshld)296 FroidurePinBase::concurrency_threshold(size_t thrshld) noexcept { 297 _settings._concurrency_threshold = thrshld; 298 return *this; 299 } 300 concurrency_threshold() const301 size_t FroidurePinBase::concurrency_threshold() const noexcept { 302 return _settings._concurrency_threshold; 303 } 304 immutable(bool val)305 FroidurePinBase& FroidurePinBase::immutable(bool val) noexcept { 306 _settings._immutable = val; 307 return *this; 308 } 309 immutable() const310 bool FroidurePinBase::immutable() const noexcept { 311 return _settings._immutable; 312 } 313 314 //////////////////////////////////////////////////////////////////////// 315 // FroidurePinBase - helper non-member functions 316 //////////////////////////////////////////////////////////////////////// 317 relations(FroidurePinBase & S,std::function<void (word_type,word_type)> && hook)318 void relations(FroidurePinBase& S, 319 std::function<void(word_type, word_type)>&& hook) { 320 S.run(); 321 322 std::vector<size_t> relation; // a triple 323 S.reset_next_relation(); 324 S.next_relation(relation); 325 326 while (relation.size() == 2 && !relation.empty()) { 327 hook(word_type({relation[0]}), word_type({relation[1]})); 328 S.next_relation(relation); 329 } 330 word_type lhs, rhs; // changed in-place by factorisation 331 while (!relation.empty()) { 332 S.factorisation(lhs, relation[0]); 333 S.factorisation(rhs, relation[2]); 334 lhs.push_back(relation[1]); 335 hook(lhs, rhs); 336 S.next_relation(relation); 337 } 338 } 339 relations(FroidurePinBase & S,std::function<void (word_type)> && hook)340 void relations(FroidurePinBase& S, std::function<void(word_type)>&& hook) { 341 S.run(); 342 343 std::vector<size_t> relation; // a triple 344 S.reset_next_relation(); 345 S.next_relation(relation); 346 347 while (relation.size() == 2 && !relation.empty()) { 348 hook(word_type({relation[0]})); 349 hook(word_type({relation[1]})); 350 S.next_relation(relation); 351 } 352 word_type word; // changed in-place by factorisation 353 while (!relation.empty()) { 354 S.factorisation(word, relation[0]); 355 word.push_back(relation[1]); 356 hook(word); 357 S.factorisation(word, relation[2]); 358 hook(word); 359 S.next_relation(relation); 360 } 361 } 362 } // namespace libsemigroups 363