19 #ifndef LIBSEMIGROUPS_SRC_SEMIGROUPS_H_ 20 #define LIBSEMIGROUPS_SRC_SEMIGROUPS_H_ 26 #include <unordered_map> 31 #include "libsemigroups-debug.h" 35 #if (defined(__GNUC__) && __GNUC__ < 5 \ 36 && !(defined(__clang__) || defined(__INTEL_COMPILER))) 38 "GCC version >=5.0 is recommended, some features may not work correctly") 49 extern Reporter glob_reporter;
55 typedef std::vector<letter_t>
word_t;
69 typedef RecVec<bool> flags_t;
75 typedef size_t index_t;
89 typedef index_t enumerate_index_t;
137 reinterpret_cast<std::vector<
Element const*> const*>(
gens)) {}
165 reinterpret_cast<std::vector<
Element const*> const&>(
gens)) {}
237 return _lenindex.size() - 2;
238 }
else if (_nr > _lenindex.back()) {
239 return _lenindex.size();
241 return _lenindex.size() - 1;
257 LIBSEMIGROUPS_ASSERT(pos < _gens.size());
267 return (_pos >= _nr);
273 LIBSEMIGROUPS_ASSERT(_lenindex.size() > 1);
274 return (_pos >= _lenindex[1]);
289 if (x->
degree() != _degree) {
293 auto it = _map.find(x);
294 return (it == _map.end() ?
UNDEFINED : it->second);
303 return _elements.size();
321 LIBSEMIGROUPS_ASSERT(pos < _nr);
331 LIBSEMIGROUPS_ASSERT(pos < _nr);
348 LIBSEMIGROUPS_ASSERT(pos < _nr);
365 LIBSEMIGROUPS_ASSERT(pos < _nr);
381 LIBSEMIGROUPS_ASSERT(pos < _nr);
439 LIBSEMIGROUPS_ASSERT(i < _nrgens);
440 return _letter_to_pos[i];
495 return _elements.size();
543 return _elements[pos];
558 return _right.get(i, j);
575 return _left.get(i, j);
714 std::atomic<bool> killed(
false);
754 reinterpret_cast<std::vector<Element const*> const*
>(coll));
767 reinterpret_cast<std::vector<Element const*> const&
>(coll));
795 reinterpret_cast<std::vector<Element const*> const*
>(coll));
818 void closure(std::vector<Element const*>
const* coll);
824 void closure(std::vector<Element const*>
const& coll);
830 void closure(std::vector<Element*>
const& coll) {
831 closure(
reinterpret_cast<std::vector<Element const*> const&
>(coll));
838 void closure(std::initializer_list<Element*> coll) {
839 closure(
static_cast<std::vector<Element*>
>(coll));
860 reinterpret_cast<std::vector<Element const*> const*
>(
gens));
877 glob_reporter.set_report(val);
889 = static_cast<unsigned int>(nr_threads == 0 ? 1 : nr_threads);
890 _max_threads = std::min(n, std::thread::hardware_concurrency());
894 template <
typename T,
class C>
class iterator_base {
896 typedef typename std::vector<Element const*>::size_type size_type;
897 typedef typename std::vector<T>::difference_type difference_type;
898 typedef typename std::vector<Element const*>::value_type value_type;
899 typedef typename std::vector<Element const*>::const_reference reference;
900 typedef typename std::vector<Element const*>::const_pointer pointer;
901 typedef std::random_access_iterator_tag iterator_category;
903 explicit iterator_base(
typename std::vector<T>::const_iterator it_vec)
906 iterator_base(iterator_base
const& that) : iterator_base(that._it_vec) {}
908 iterator_base&
operator=(iterator_base
const& that) {
909 _it_vec = that._it_vec;
913 virtual ~iterator_base() {}
915 bool operator==(iterator_base
const& that)
const {
916 return _it_vec == that._it_vec;
919 bool operator!=(iterator_base
const& that)
const {
920 return _it_vec != that._it_vec;
923 bool operator<(iterator_base
const& that)
const {
924 return _it_vec < that._it_vec;
927 bool operator>(iterator_base
const& that)
const {
928 return _it_vec > that._it_vec;
931 bool operator<=(iterator_base
const& that)
const {
932 return operator<(that) || operator==(that);
935 bool operator>=(iterator_base
const& that)
const {
936 return operator>(that) || operator==(that);
940 iterator_base operator++(
int) {
941 iterator_base tmp(*
this);
942 iterator_base::operator++();
946 iterator_base operator--(
int) {
947 iterator_base tmp(*
this);
948 iterator_base::operator--();
952 iterator_base operator+(size_type val)
const {
953 iterator_base out(*
this);
957 friend iterator_base operator+(size_type val, iterator_base
const& it) {
961 iterator_base operator-(size_type val)
const {
962 iterator_base out(*
this);
967 return *(*
this + pos);
970 iterator_base& operator++() {
975 iterator_base& operator--() {
980 iterator_base& operator+=(size_type val) {
985 iterator_base& operator-=(size_type val) {
990 difference_type operator-(iterator_base that)
const {
991 return _it_vec - that._it_vec;
994 reference operator*()
const {
995 return _methods.indirection(_it_vec);
998 pointer operator->()
const {
999 return _methods.addressof(_it_vec);
1003 typename std::vector<T>::const_iterator _it_vec;
1004 static C
const _methods;
1007 struct IteratorMethods {
1008 IteratorMethods() {}
1009 typename std::vector<Element const*>::const_reference indirection(
1010 typename std::vector<Element const*>::const_iterator it)
const {
1013 typename std::vector<Element const*>::const_pointer
1014 addressof(
typename std::vector<Element const*>::const_iterator it)
const {
1019 struct IteratorMethodsPairFirst {
1020 IteratorMethodsPairFirst() {}
1021 typename std::vector<Element const*>::const_reference indirection(
1022 typename std::vector<std::pair<Element const*, element_index_t>>::
1023 const_iterator it)
const {
1027 typename std::vector<Element const*>::const_pointer
1028 addressof(
typename std::vector<
1029 std::pair<Element const*, element_index_t>>::const_iterator it)
1031 return &((*it).first);
1035 typedef iterator_base<Element const*, IteratorMethods> const_iterator;
1036 typedef iterator_base<std::pair<Element const*, element_index_t>,
1037 IteratorMethodsPairFirst>
1038 const_iterator_pair_first;
1039 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1040 typedef std::reverse_iterator<const_iterator_pair_first>
1041 const_reverse_iterator_pair_first;
1043 typedef const_iterator_pair_first const_iterator_sorted;
1044 typedef const_iterator_pair_first const_iterator_idempotents;
1045 typedef const_reverse_iterator_pair_first const_reverse_iterator_sorted;
1046 typedef const_reverse_iterator_pair_first
1047 const_reverse_iterator_idempotents;
1058 return const_iterator(_elements.cbegin());
1080 return const_iterator(_elements.cend());
1102 return const_reverse_iterator(
cend());
1113 return const_reverse_iterator(
cbegin());
1124 return const_iterator_pair_first(_sorted.cbegin());
1135 return const_iterator_pair_first(_sorted.cend());
1146 return const_reverse_iterator_pair_first(
cend_sorted());
1171 return const_iterator_pair_first(_idempotents.cbegin());
1181 return const_iterator_pair_first(_idempotents.cend());
1186 void inline expand(index_t nr) {
1188 _reduced.add_rows(nr);
1189 _right.add_rows(nr);
1195 if (!_found_one && *x == *_id) {
1208 size_t const& thread_id);
1217 typedef std::pair<Element const*, element_index_t> idempotent_value_t;
1221 void init_idempotents();
1228 void idempotents(enumerate_index_t
const first,
1229 enumerate_index_t
const last,
1230 enumerate_index_t
const threshold,
1231 std::vector<idempotent_value_t>& idempotents);
1235 std::vector<std::pair<letter_t, letter_t>> _duplicate_gens;
1236 std::vector<Element const*> _elements;
1237 std::vector<element_index_t> _enumerate_order;
1238 std::vector<letter_t> _final;
1239 std::vector<letter_t> _first;
1241 std::vector<Element const*> _gens;
1243 std::vector<idempotent_value_t> _idempotents;
1244 bool _idempotents_found;
1245 std::vector<uint8_t> _is_idempotent;
1247 std::vector<index_t> _length;
1248 std::vector<enumerate_index_t> _lenindex;
1249 std::vector<element_index_t> _letter_to_pos;
1250 std::unordered_map<Element
const*,
1255 size_t _max_threads;
1260 enumerate_index_t _pos;
1262 std::vector<element_index_t> _prefix;
1265 enumerate_index_t _relation_pos;
1267 std::vector<std::pair<Element const*, element_index_t>> _sorted;
1268 std::vector<element_index_t> _suffix;
1269 Element* _tmp_product;
1272 static std::vector<element_index_t> _tmp_inverter;
1273 static std::vector<bool> _old_new;
1274 #ifdef LIBSEMIGROUPS_STATS 1275 size_t _nr_products;
1283 template <
typename T,
typename C>
1284 C
const Semigroup::iterator_base<T, C>::_methods;
1287 #endif // LIBSEMIGROUPS_SRC_SEMIGROUPS_H_ Semigroup::cayley_graph_t cayley_graph_t
This is just for backwards compatibility and should disappear at some point.
Definition: semigroups.h:1281
element_index_t position_to_sorted_position(element_index_t pos)
Returns the position of this->at(pos) in the sorted array of elements of the semigroup,...
Definition: semigroups.cc:397
void minimal_factorisation(word_t &word, element_index_t pos)
Changes word in-place to contain a minimal word with respect to the short-lex ordering in the generat...
Definition: semigroups.cc:461
static index_t const LIMIT_MAX
This variable is used to indicate the maximum possible limit that can be used with Semigroup::enumera...
Definition: semigroups.h:870
bool is_begun() const
Returns true if no elements other than the generators have been enumerated so far and false otherwise...
Definition: semigroups.h:272
Semigroup(std::initializer_list< Element * > gens)
Construct from generators.
Definition: semigroups.h:171
cayley_graph_t * right_cayley_graph_copy()
Returns a copy of the right Cayley graph of the semigroup.
Definition: semigroups.h:564
size_t current_nrrules() const
Returns the number of relations in the presentation for the semigroup that have been found so far.
Definition: semigroups.h:311
void closure(std::initializer_list< Element * > coll)
Add copies of the non-redundant generators in coll to the generators of this.
Definition: semigroups.h:838
void reset_next_relation()
This method resets Semigroup::next_relation so that when it is next called the resulting relation is ...
Definition: semigroups.h:648
void add_generators(std::vector< Element * > const &coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:765
Semigroup * copy_add_generators(std::vector< Element * > const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.h:793
virtual size_t degree() const =0
Returns the degree of an Element.
const_reverse_iterator_sorted crend_sorted()
Returns a const iterator pointing to one before the first element of the semigroup when the elements ...
Definition: semigroups.h:1155
Semigroup(std::vector< Element * > const *gens)
Construct from generators.
Definition: semigroups.h:135
element_index_t right(element_index_t i, letter_t j)
Returns the index of the product of the element in position i with the generator with index j.
Definition: semigroups.h:556
element_index_t product_by_reduction(element_index_t i, element_index_t j) const
Returns the position in this of the product of this->at(i) and this->at(j) by following a path in the...
Definition: semigroups.cc:332
void set_batch_size(size_t batch_size)
Set a new value for the batch size.
Definition: semigroups.h:478
void enumerate(size_t limit=LIMIT_MAX)
Enumerate the semigroup until limit elements are found.
Definition: semigroups.h:713
Element const * sorted_at(element_index_t pos)
Returns the element of the semigroup in position pos of the sorted array of elements,...
Definition: semigroups.cc:419
std::vector< letter_t > word_t
Type for a word over the generators of a semigroup.
Definition: semigroups.h:55
void closure(std::vector< Element const * > const *coll)
Add copies of the non-redundant generators in coll to the generators of this.
Definition: semigroups.cc:687
const_reverse_iterator_sorted crbegin_sorted()
Returns a const iterator pointing to the last element of the semigroup when the elements are sorted b...
Definition: semigroups.h:1144
const_iterator begin() const
Returns a const iterator pointing to the first element of the semigroup.
Definition: semigroups.h:1068
Abstract base class for semigroup elements.
Definition: elements.h:44
size_t length_non_const(element_index_t pos)
Returns the length of the element in position pos of the semigroup.
Definition: semigroups.h:389
const_iterator cend() const
Returns a const iterator pointing to one past the last currently known element of the semigroup.
Definition: semigroups.h:1079
size_t current_size() const
Returns the number of elements in the semigroup that have been enumerated so far.
Definition: semigroups.h:302
element_index_t letter_to_pos(letter_t i) const
Returns the position in this of the generator with index i.
Definition: semigroups.h:438
element_index_t sorted_position(Element const *x)
Returns the position of x in the sorted array of elements of the semigroup, or Semigroup::UNDEFINED i...
Definition: semigroups.cc:406
const_reverse_iterator crbegin() const
Returns a const reverse iterator pointing to the last currently known element of the semigroup.
Definition: semigroups.h:1101
Semigroup * copy_closure(std::vector< Element * > const *gens)
Returns a new semigroup generated by this and copies of the non-redundant elements of coll.
Definition: semigroups.h:858
const_iterator_idempotents cbegin_idempotents()
Returns a const iterator pointing at the first idempotent in the semigroup.
Definition: semigroups.h:1169
Element const * operator[](element_index_t pos) const
Returns the element of the semigroup in position pos.
Definition: semigroups.h:542
void enumerate(std::atomic< bool > &killed, size_t limit=LIMIT_MAX)
Enumerate the semigroup until limit elements are found or killed is true.
Definition: semigroups.cc:523
const_iterator_sorted cend_sorted()
Returns a const iterator pointing to one past the last element of the semigroup when the elements are...
Definition: semigroups.h:1133
element_index_t fast_product(element_index_t i, element_index_t j) const
Returns the position in this of the product of this->at(i) and this->at(j).
Definition: semigroups.cc:352
Element const * at(element_index_t pos)
Returns the element of the semigroup in position pos, or a nullptr if there is no such element.
Definition: semigroups.cc:410
letter_t first_letter(element_index_t pos) const
Returns the first letter of the element in position pos.
Definition: semigroups.h:347
void set_report(bool val) const
Turn reporting on or off.
Definition: semigroups.h:876
element_index_t position(Element const *x)
Returns the position of x in this, or Semigroup::UNDEFINED if x is not an element of this.
Definition: semigroups.cc:378
Semigroup * copy_closure(std::vector< Element const * > const *coll)
Returns a new semigroup generated by this and copies of the non-redundant elements of coll.
Definition: semigroups.cc:667
word_t * factorisation(element_index_t pos)
Returns a pointer to a libsemigroups::word_t which evaluates to the Element in position pos of this.
Definition: semigroups.h:631
element_index_t left(element_index_t i, letter_t j)
Returns the index of the product of the generator with index j and the element in position i.
Definition: semigroups.h:573
size_t length_const(element_index_t pos) const
Returns the length of the element in position pos of the semigroup.
Definition: semigroups.h:380
const_iterator_idempotents cend_idempotents()
Returns a const iterator referring to past the end of the last idempotent in the semigroup.
Definition: semigroups.h:1179
size_t nrrules()
Returns the total number of relations in the presentation defining the semigroup.
Definition: semigroups.h:461
const_reverse_iterator crend() const
Returns a const reverse iterator pointing to one before the first element of the semigroup.
Definition: semigroups.h:1112
size_t degree() const
Returns the degree of any (and all) Element's in the semigroup.
Definition: semigroups.h:246
void set_max_threads(size_t nr_threads)
Set the maximum number of threads that any method of an instance of Semigroup can use.
Definition: semigroups.h:887
Semigroup & operator=(Semigroup const &semigroup)=delete
Deleted.
void add_generators(std::vector< Element * > const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:752
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
const_iterator end() const
Returns a const iterator pointing to one past the last currently known element of the semigroup.
Definition: semigroups.h:1090
bool is_done() const
Returns true if the semigroup is fully enumerated and false if not.
Definition: semigroups.h:266
bool is_idempotent(element_index_t pos)
Returns true if the element in position pos is an idempotent and false if it is not.
Definition: semigroups.cc:370
void reserve(size_t n)
Requests that the capacity (i.e. number of elements) of the semigroup be at least enough to contain n...
Definition: semigroups.cc:279
RecVec< element_index_t > cayley_graph_t
Type for a left or right Cayley graph of a semigroup.
Definition: semigroups.h:98
element_index_t word_to_pos(word_t const &w) const
Returns the position in the semigroup corresponding to the element represented by the word w.
Definition: semigroups.cc:302
Semigroup(std::vector< Element const * > const *gens)
Construct from generators.
Definition: semigroups.cc:38
Semigroup(std::vector< Element * > const &gens)
Construct from generators.
Definition: semigroups.h:163
Semigroup * copy_add_generators(std::vector< Element const * > const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.cc:702
Semigroup(std::vector< Element const * > *gens)
Construct from generators.
Definition: semigroups.h:151
void closure(std::vector< Element * > const &coll)
Add copies of the non-redundant generators in coll to the generators of this.
Definition: semigroups.h:830
void add_generators(std::initializer_list< Element * > coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:773
letter_t final_letter(element_index_t pos) const
Returns the last letter of the element in position pos.
Definition: semigroups.h:364
element_index_t current_position(Element const *x) const
Returns the position of the element x in the semigroup if it is already known to belong to the semigr...
Definition: semigroups.h:288
void add_generators(std::vector< Element const * > const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.cc:718
size_t size()
Returns the size of the semigroup.
Definition: semigroups.h:493
static index_t const UNDEFINED
This variable is used to indicate that a value is undefined, such as, for example,...
Definition: semigroups.h:866
size_t current_max_word_length() const
Returns the maximum length of a word in the generators so far computed.
Definition: semigroups.h:235
Class for semigroups generated by instances of Element.
Definition: semigroups.h:68
size_t letter_t
Type for the index of a generator of a semigroup.
Definition: semigroups.h:52
size_t nridempotents()
Returns the total number of idempotents in the semigroup.
Definition: semigroups.cc:365
std::pair< word_t, word_t > relation_t
Type for a pair of word_t (a relation) of a semigroup.
Definition: semigroups.h:58
void factorisation(word_t &word, element_index_t pos)
Changes word in-place to contain a word in the generators equal to the pos element of the semigroup.
Definition: semigroups.h:620
Element * word_to_element(word_t const &w) const
Returns a pointer to the element of this represented by the word w.
Definition: semigroups.cc:315
~Semigroup()
A default destructor.
Definition: semigroups.cc:264
size_t batch_size() const
Returns the current value of the batch size. This is the minimum number of elements enumerated in any...
Definition: semigroups.h:371
bool test_membership(Element const *x)
Returns true if x is an element of this and false if it is not.
Definition: semigroups.h:505
const_iterator_sorted cbegin_sorted()
Returns a const iterator pointing to the first element of the semigroup when the elements are sorted ...
Definition: semigroups.h:1122
cayley_graph_t * left_cayley_graph_copy()
Returns a copy of the left Cayley graph of the semigroup.
Definition: semigroups.h:581
const_iterator cbegin() const
Returns a const iterator pointing to the first element of the semigroup.
Definition: semigroups.h:1057
Element const * gens(letter_t pos) const
Return a pointer to the generator with index pos.
Definition: semigroups.h:256
Semigroup(std::vector< Element * > *gens)
Construct from generators.
Definition: semigroups.h:143
index_t element_index_t
Type for the position of an element in an instance of Semigroup. The size of the semigroup being enum...
Definition: semigroups.h:95
element_index_t suffix(element_index_t pos) const
Returns the position of the suffix of the element x in position pos (of the semigroup) of length one ...
Definition: semigroups.h:330
size_t nrgens() const
Returns the number of generators of the semigroup.
Definition: semigroups.h:251
void next_relation(word_t &relation)
This method changes relation in-place to contain the next relation of the presentation defining this.
Definition: semigroups.cc:475
element_index_t prefix(element_index_t pos) const
Returns the position of the prefix of the element x in position pos (of the semigroup) of length one ...
Definition: semigroups.h:320