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);
939 iterator_base operator++(
int) {
940 iterator_base tmp(*
this);
945 iterator_base operator--(
int) {
946 iterator_base tmp(*
this);
951 iterator_base operator+(size_type val)
const {
952 iterator_base out(*
this);
956 friend iterator_base operator+(size_type val, iterator_base
const& it) {
960 iterator_base operator-(size_type val)
const {
961 iterator_base out(*
this);
966 return *(*
this + pos);
969 iterator_base& operator++() {
974 iterator_base& operator--() {
979 iterator_base& operator+=(size_type val) {
984 iterator_base& operator-=(size_type val) {
989 difference_type operator-(iterator_base that)
const {
990 return _it_vec - that._it_vec;
993 reference operator*()
const {
994 return _methods.indirection(_it_vec);
997 pointer operator->()
const {
998 return _methods.addressof(_it_vec);
1002 typename std::vector<T>::const_iterator _it_vec;
1003 static C
const _methods;
1006 struct IteratorMethods {
1007 IteratorMethods() {}
1008 typename std::vector<Element const*>::const_reference indirection(
1009 typename std::vector<Element const*>::const_iterator it)
const {
1012 typename std::vector<Element const*>::const_pointer
1013 addressof(
typename std::vector<Element const*>::const_iterator it)
const {
1018 struct IteratorMethodsPairFirst {
1019 IteratorMethodsPairFirst() {}
1020 typename std::vector<Element const*>::const_reference indirection(
1021 typename std::vector<std::pair<Element const*, element_index_t>>::
1022 const_iterator it)
const {
1026 typename std::vector<Element const*>::const_pointer addressof(
1027 typename std::vector<std::pair<Element const*, element_index_t>>::
1028 const_iterator it)
const {
1029 return &((*it).first);
1033 typedef iterator_base<Element const*, IteratorMethods> const_iterator;
1034 typedef iterator_base<std::pair<Element const*, element_index_t>,
1035 IteratorMethodsPairFirst>
1036 const_iterator_pair_first;
1037 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1038 typedef std::reverse_iterator<const_iterator_pair_first>
1039 const_reverse_iterator_pair_first;
1041 typedef const_iterator_pair_first const_iterator_sorted;
1042 typedef const_iterator_pair_first const_iterator_idempotents;
1043 typedef const_reverse_iterator_pair_first const_reverse_iterator_sorted;
1044 typedef const_reverse_iterator_pair_first
1045 const_reverse_iterator_idempotents;
1056 return const_iterator(_elements.cbegin());
1078 return const_iterator(_elements.cend());
1100 return const_reverse_iterator(
cend());
1111 return const_reverse_iterator(
cbegin());
1122 return const_iterator_pair_first(_sorted.cbegin());
1133 return const_iterator_pair_first(_sorted.cend());
1144 return const_reverse_iterator_pair_first(
cend_sorted());
1169 return const_iterator_pair_first(_idempotents.cbegin());
1179 return const_iterator_pair_first(_idempotents.cend());
1184 void inline expand(index_t nr) {
1186 _reduced.add_rows(nr);
1187 _right.add_rows(nr);
1193 if (!_found_one && *x == *_id) {
1206 size_t const& thread_id);
1215 typedef std::pair<Element const*, element_index_t> idempotent_value_t;
1219 void init_idempotents();
1226 void idempotents(enumerate_index_t
const first,
1227 enumerate_index_t
const last,
1228 enumerate_index_t
const threshold,
1229 std::vector<idempotent_value_t>& idempotents);
1233 std::vector<std::pair<letter_t, letter_t>> _duplicate_gens;
1234 std::vector<Element const*> _elements;
1235 std::vector<element_index_t> _enumerate_order;
1236 std::vector<letter_t> _final;
1237 std::vector<letter_t> _first;
1239 std::vector<Element const*> _gens;
1241 std::vector<idempotent_value_t> _idempotents;
1242 bool _idempotents_found;
1243 std::vector<uint8_t> _is_idempotent;
1245 std::vector<index_t> _length;
1246 std::vector<enumerate_index_t> _lenindex;
1247 std::vector<element_index_t> _letter_to_pos;
1248 std::unordered_map<Element
const*,
1253 size_t _max_threads;
1258 enumerate_index_t _pos;
1260 std::vector<element_index_t> _prefix;
1263 enumerate_index_t _relation_pos;
1265 std::vector<std::pair<Element const*, element_index_t>> _sorted;
1266 std::vector<element_index_t> _suffix;
1267 Element* _tmp_product;
1270 static std::vector<element_index_t> _tmp_inverter;
1271 static std::vector<bool> _old_new;
1272 #ifdef LIBSEMIGROUPS_STATS 1273 size_t _nr_products;
1281 template <
typename T,
typename C>
1282 C
const Semigroup::iterator_base<T, C>::_methods;
1285 #endif // LIBSEMIGROUPS_SRC_SEMIGROUPS_H_ Semigroup(std::initializer_list< Element *> gens)
Construct from generators.
Definition: semigroups.h:171
Semigroup::cayley_graph_t cayley_graph_t
This is just for backwards compatibility and should disappear at some point.
Definition: semigroups.h:1279
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, or Semigroup::UNDEFINED if pos is greater than the size 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
void add_generators(std::vector< Element const *> const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.cc:720
Semigroup(std::vector< Element *> const *gens)
Construct from generators.
Definition: semigroups.h:135
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
Semigroup * copy_add_generators(std::vector< Element *> const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.h:793
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
Semigroup(std::vector< Element const *> *gens)
Construct from generators.
Definition: semigroups.h:151
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:1153
Semigroup(std::vector< Element const *> const *gens)
Construct from generators.
Definition: semigroups.cc:38
void add_generators(std::initializer_list< Element *> coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:773
Semigroup * copy_add_generators(std::vector< Element const *> const *coll) const
Returns a new semigroup generated by this and coll.
Definition: semigroups.cc:704
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, or nullptr in pos is not valid (i.e. too big).
Definition: semigroups.cc:419
std::vector< letter_t > word_t
Type for a word over the generators of a semigroup.
Definition: semigroups.h:55
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:1142
const_iterator begin() const
Returns a const iterator pointing to the first element of the semigroup.
Definition: semigroups.h:1066
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:1077
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:1099
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
const_iterator_idempotents cbegin_idempotents()
Returns a const iterator pointing at the first idempotent in the semigroup.
Definition: semigroups.h:1167
Element const * operator[](element_index_t pos) const
Returns the element of the semigroup in position pos.
Definition: semigroups.h:542
Semigroup(std::vector< Element *> const &gens)
Construct from generators.
Definition: semigroups.h:163
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:1131
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
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:1177
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:1110
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(std::vector< Element *> *gens)
Construct from generators.
Definition: semigroups.h:143
Semigroup & operator=(Semigroup const &semigroup)=delete
Deleted.
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:1088
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
void add_generators(std::vector< Element *> const &coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:765
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
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, the position of an element that does not belong to a semigroup.
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
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:669
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
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:689
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
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:1120
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:1055
Element const * gens(letter_t pos) const
Return a pointer to the generator with index pos.
Definition: semigroups.h:256
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
void add_generators(std::vector< Element *> const *coll)
Add copies of the generators coll to the generators of this.
Definition: semigroups.h:752
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