21 #ifndef LIBSEMIGROUPS_SRC_ELEMENTS_H_ 22 #define LIBSEMIGROUPS_SRC_ELEMENTS_H_ 29 #include <unordered_set> 33 #include "libsemigroups-debug.h" 116 virtual size_t degree()
const = 0;
127 return this->_hash_value;
268 mutable size_t _hash_value;
288 template <
typename TValueType,
class TSub
class>
329 inline TValueType
at(
size_t pos)
const {
338 return *(static_cast<TSubclass const&>(that)._vector) == *(this->
_vector);
347 TSubclass
const& ewvd = static_cast<TSubclass const&>(that);
348 if (this->
_vector->size() != ewvd._vector->size()) {
349 return this->
_vector->size() < ewvd._vector->size();
351 for (
size_t i = 0; i < this->
_vector->size(); i++) {
352 if ((*
this)[i] != ewvd[i]) {
353 return (*
this)[i] < ewvd[i];
367 LIBSEMIGROUPS_ASSERT(increase_deg_by == 0);
368 (void) increase_deg_by;
369 std::vector<TValueType>* vector(
new std::vector<TValueType>(*
_vector));
370 TSubclass*
copy =
new TSubclass(vector);
371 copy->_hash_value = this->_hash_value;
385 = static_cast<ElementWithVectorData const*>(x);
386 _vector->assign(xx->_vector->cbegin(), xx->_vector->cend());
387 this->_hash_value = xx->_hash_value;
401 std::swap(this->_hash_value, xx->_hash_value);
413 inline typename std::vector<TValueType>::iterator
begin()
const {
421 inline typename std::vector<TValueType>::iterator
end()
const {
429 inline typename std::vector<TValueType>::iterator
cbegin()
const {
437 inline typename std::vector<TValueType>::iterator
cend()
const {
446 template <
typename T>
449 for (
auto const& x : *vec) {
450 seed ^= std::hash<T>{}(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
467 template <
typename TValueType,
class TSub
class>
514 template <
typename TValueType,
typename TSub
class>
519 ElementWithVectorDataDefaultHash;
546 _lookup.resize(
degree(),
false);
548 for (
auto const& x : *(this->
_vector)) {
563 std::vector<TValueType>* vector(
new std::vector<TValueType>());
564 vector->reserve(this->
degree());
565 for (
size_t i = 0; i < this->
degree(); i++) {
566 vector->push_back(i);
568 return new TSubclass(vector);
579 static std::vector<bool> _lookup;
582 template <
typename TValueType,
typename TSub
class>
584 = std::vector<bool>();
586 template <
typename TValueType,
typename TSub
class>
588 = std::numeric_limits<TValueType>::max();
601 template <
typename T>
615 if (increase_deg_by == 0) {
616 copy->_hash_value = this->_hash_value;
618 size_t n =
copy->_vector->size();
619 copy->_vector->reserve(n + increase_deg_by);
620 for (
size_t i = n; i < n + increase_deg_by; i++) {
621 copy->_vector->push_back(i);
636 LIBSEMIGROUPS_ASSERT(x !=
this && y !=
this);
639 size_t const n = this->
_vector->size();
640 for (T i = 0; i < n; i++) {
641 (*this->
_vector)[i] = (*yy)[(*xx)[i]];
651 size_t deg = this->
_vector->size();
652 for (
auto const& val : *(this->
_vector)) {
656 this->_hash_value = seed;
673 template <
typename T>
687 std::vector<T>
const& ran,
690 LIBSEMIGROUPS_ASSERT(dom.size() == ran.size());
691 LIBSEMIGROUPS_ASSERT(dom.empty()
692 || deg >= *std::max_element(dom.begin(), dom.end()));
695 for (
size_t i = 0; i < dom.size(); i++) {
696 (*this->
_vector)[dom[i]] = ran[i];
711 size_t deg_this = pp_this->
degree();
712 for (
auto it = pp_this->_vector->end() - 1;
713 it >= pp_this->_vector->begin();
721 size_t deg_that = pp_that.
degree();
722 for (
auto it = pp_that.
_vector->end() - 1;
723 it >= pp_that.
_vector->begin() && deg_that >= deg_this;
732 if (deg_this != deg_that) {
733 return deg_this < deg_that;
736 for (
size_t i = 0; i < deg_this; i++) {
737 if ((*pp_this)[i] != pp_that[i]) {
739 || (pp_that[i] !=
UNDEFINED && (*pp_this)[i] < pp_that[i]);
754 if (increase_deg_by == 0) {
755 copy->_hash_value = this->_hash_value;
757 size_t n =
copy->_vector->size();
758 copy->_vector->reserve(n + increase_deg_by);
759 for (
size_t i = n; i < n + increase_deg_by; i++) {
775 LIBSEMIGROUPS_ASSERT(x !=
this && y !=
this);
778 size_t const n = this->
degree();
779 for (T i = 0; i < n; i++) {
825 _trans_blocks_lookup(),
827 this->
_vector->resize(2 * degree);
843 _trans_blocks_lookup(),
856 :
Bipartition(new std::vector<u_int32_t>(blocks)) {}
870 size_t degree()
const override;
892 size_t const& thread_id)
override;
955 LIBSEMIGROUPS_ASSERT(_nr_blocks == Bipartition::UNDEFINED
967 LIBSEMIGROUPS_ASSERT(_nr_left_blocks == Bipartition::UNDEFINED
978 LIBSEMIGROUPS_ASSERT(_rank == Bipartition::UNDEFINED || _rank ==
rank);
983 u_int32_t fuseit(std::vector<u_int32_t>& fuse, u_int32_t pos);
984 void init_trans_blocks_lookup();
986 static std::vector<std::vector<u_int32_t>> _fuse;
987 static std::vector<std::vector<u_int32_t>> _lookup;
990 size_t _nr_left_blocks;
991 std::vector<bool> _trans_blocks_lookup;
994 static u_int32_t
const UNDEFINED;
1012 template <
typename TValueType,
class TSub
class>
1034 _degree(sqrt(matrix->size())),
1036 LIBSEMIGROUPS_ASSERT(
semiring !=
nullptr);
1037 LIBSEMIGROUPS_ASSERT(!matrix->empty());
1038 LIBSEMIGROUPS_ASSERT(matrix->size() == _degree * _degree);
1065 _degree(matrix[0].size()),
1067 LIBSEMIGROUPS_ASSERT(
semiring !=
nullptr);
1068 LIBSEMIGROUPS_ASSERT(!matrix.empty());
1069 LIBSEMIGROUPS_ASSERT(all_of(
1070 matrix.begin(), matrix.end(), [matrix](std::vector<TValueType> row) {
1071 return row.size() == matrix.size();
1074 this->
_vector->reserve(matrix.size() * matrix.size());
1075 for (
auto const& row : matrix) {
1076 this->
_vector->insert(this->
_vector->end(), row.begin(), row.end());
1090 return pow(this->
degree(), 3);
1107 std::vector<TValueType>* vec(
new std::vector<TValueType>());
1108 vec->resize(this->
_vector->size(), _semiring->
zero());
1109 size_t n = this->
degree();
1110 for (
auto it = vec->begin(); it < vec->end(); it += n + 1) {
1111 (*it) = _semiring->
one();
1113 return new TSubclass(vec, _semiring);
1121 LIBSEMIGROUPS_ASSERT(increase_deg_by == 0);
1122 (void) increase_deg_by;
1126 LIBSEMIGROUPS_ASSERT(
copy->_semiring ==
nullptr 1127 ||
copy->_semiring == this->_semiring);
1128 copy->_semiring = _semiring;
1139 auto xx = static_cast<MatrixOverSemiringBase const*>(x);
1140 auto yy = static_cast<MatrixOverSemiringBase const*>(y);
1141 LIBSEMIGROUPS_ASSERT(xx->degree() == yy->degree());
1142 LIBSEMIGROUPS_ASSERT(xx->degree() == this->
degree());
1143 LIBSEMIGROUPS_ASSERT(xx !=
this && yy !=
this);
1150 size_t deg = this->
degree();
1152 for (
size_t i = 0; i < deg; i++) {
1153 for (
size_t j = 0; j < deg; j++) {
1154 int64_t v = _semiring->
zero();
1155 for (
size_t k = 0; k < deg; k++) {
1156 v = _semiring->
plus(
1157 v, _semiring->
prod((*xx)[i * deg + k], (*yy)[k * deg + j]));
1159 (*this->
_vector)[i * deg + j] = v;
1173 _degree(sqrt(matrix->size())),
1174 _semiring(nullptr) {}
1178 virtual inline void after() {}
1180 Semiring<TValueType>
const* _semiring;
1189 template <
typename TValueType>
1192 MatrixOverSemiring<TValueType>> {
1243 inline void after() final {
1244 int64_t norm = *std::max_element(
_vector->begin(),
_vector->end());
1246 if (x != LONG_MIN) {
1273 size_t const n = this->
_vector->size();
1275 for (T i = 0; i < n; i++) {
1276 (*
id->_vector)[(*this->
_vector)[i]] = i;
1309 explicit BooleanMat(std::vector<std::vector<bool>>
const& matrix)
1333 explicit BooleanMat(std::vector<bool>* matrix,
1337 static BooleanSemiring
const*
const _semiring;
1369 size_t degree()
const override;
1392 size_t const& thread_id)
override;
1398 void unite_rows(RecVec<bool>& out,
1400 size_t const& vertex1,
1401 size_t const& vertex2);
1403 void x_dfs(std::vector<bool>& x_seen,
1404 std::vector<bool>& y_seen,
1412 void y_dfs(std::vector<bool>& x_seen,
1413 std::vector<bool>& y_seen,
1421 static std::vector<std::vector<bool>> _x_seen;
1422 static std::vector<std::vector<bool>> _y_seen;
1423 static std::vector<RecVec<bool>> _out;
1424 static std::vector<RecVec<bool>> _tmp;
1427 template <
typename T>
static inline void really_delete_cont(T cont) {
1428 for (
Element const* x : cont) {
1429 const_cast<Element*>(x)->really_delete();
1434 template <
typename T>
static inline void really_delete_cont(T* cont) {
1435 for (Element
const* x : *cont) {
1436 const_cast<Element*>(x)->really_delete();
1442 #endif // LIBSEMIGROUPS_SRC_ELEMENTS_H_ Class for bipartitions.
Definition: elements.h:814
virtual T prod(T x, T y) const =0
Returns the product of x and y.
Element(elm_t type=Element::elm_t::NOT_RWSE)
A constructor.
Definition: elements.h:63
size_t operator()(Element const *x) const
Returns the value of Element::hash_value applied to the Element pointed to by x.
Definition: elements.h:235
BooleanMat(std::vector< bool > *matrix)
A constructor.
Definition: elements.h:1301
Class for partitioned binary relations (PBR).
Definition: elements.h:1345
ElementWithVectorData()
A constructor.
Definition: elements.h:294
ProjectiveMaxPlusMatrix(std::vector< int64_t > *matrix, Semiring< int64_t > const *semiring)
A constructor.
Definition: elements.h:1218
virtual void redefine(Element const *x, Element const *y, size_t const &thread_id)
Multiplies x and y and stores the result in this.
Definition: elements.h:209
Matrices over a semiring.
Definition: elements.h:1190
virtual void swap(Element *x)=0
Swap another Element with this.
virtual size_t degree() const =0
Returns the degree of an Element.
MatrixOverSemiringBase(std::vector< TValueType > *matrix, Semiring< TValueType > const *semiring)
A constructor.
Definition: elements.h:1031
size_t degree() const override
Returns the degree of a PBR.
Definition: elements.cc:284
bool is_transverse_block(size_t index)
Returns true if the block with index index is transverse.
Definition: elements.cc:203
u_int32_t nr_left_blocks()
Returns the number of blocks containing a positive integer.
Definition: elements.cc:179
Matrices over the boolean semiring.
Definition: elements.h:1289
Class for signed partitions of the set .
Definition: blocks.h:45
std::vector< TValueType >::iterator cend() const
Returns a const iterator.
Definition: elements.h:437
bool operator<(Element const &that) const override
Returns true if this is less than that.
Definition: elements.h:346
size_t degree() const override
Returns the degree of the bipartition.
Definition: elements.cc:71
MatrixOverSemiringBase(std::vector< TValueType > *matrix)
Constructs a MatrixOverSemiringBase with whose underlying semiring is not defined....
Definition: elements.h:1171
Bipartition(std::vector< u_int32_t > const &blocks)
A constructor.
Definition: elements.h:855
virtual void cache_hash_value() const =0
Calculate and cache a hash value.
MatrixOverSemiringBase(std::vector< std::vector< TValueType >> const &matrix, Semiring< TValueType > const *semiring)
A constructor.
Definition: elements.h:1062
std::vector< TValueType >::iterator cbegin() const
Returns a const iterator.
Definition: elements.h:429
void redefine(Element const *x, Element const *y, size_t const &thread_id) override
Multiply x and y and stores the result in this.
Definition: elements.cc:88
Abstract base class for elements using a vector to store their defining data.
Definition: elements.h:289
Provides a call operator for comparing Elements via pointers.
Definition: elements.h:219
virtual void copy(Element const *x)=0
Copy another Element into this.
PartialPerm(std::vector< T > const &dom, std::vector< T > const &ran, size_t deg)
A constructor.
Definition: elements.h:686
Abstract base class for semigroup elements.
Definition: elements.h:44
Blocks * right_blocks()
Return the left blocks of a bipartition.
Definition: elements.cc:242
void redefine(Element const *x, Element const *y) override
Multiply x and y and stores the result in this.
Definition: elements.h:772
void set_nr_blocks(size_t nr_blocks)
Set the cached number of blocks.
Definition: elements.h:954
Template class for permutations.
Definition: elements.h:1265
size_t complexity() const override
Returns the approximate time complexity of multiplying two matrices.
Definition: elements.h:1089
Element * identity() const override
Returns an identity bipartition.
Definition: elements.cc:76
Template class for partial permutations.
Definition: elements.h:674
Matrices over a semiring.
Definition: elements.h:1013
ElementWithVectorData(std::vector< TValueType > const &vector)
A constructor.
Definition: elements.h:313
ElementWithVectorData(std::vector< TValueType > *vector)
A constructor.
Definition: elements.h:304
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:1120
void reset_hash_value() const
Reset the cached value used by Element::hash_value.
Definition: elements.h:252
Type for Element objects not arising from a rewriting system RWS.
Definition: elements.h:56
u_int32_t const_nr_blocks() const
Returns the number of blocks in a bipartition.
Definition: elements.cc:162
Bipartition(std::vector< u_int32_t > *blocks)
A constructor.
Definition: elements.h:839
virtual T plus(T x, T y) const =0
Returns the sum of x and y.
u_int32_t nr_blocks()
Returns the number of blocks in a bipartition.
Definition: elements.cc:172
TValueType operator[](size_t pos) const
Returns the pos entry in the vector containing the defining data.
Definition: elements.h:321
void swap(Element *x) override
Swap another Element with this.
Definition: elements.h:397
ProjectiveMaxPlusMatrix(std::vector< std::vector< int64_t >> const &matrix, Semiring< int64_t > const *semiring)
A constructor.
Definition: elements.h:1231
void cache_hash_value() const override
Calculate and cache a hash value.
Definition: elements.cc:288
void cache_hash_value() const override
This method implements the default hash function for an ElementWithVectorData, which uses ElementWith...
Definition: elements.h:479
elm_t get_type() const
Returns the type libsemigroups::Element::elm_t of an Element object.
Definition: elements.h:73
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:751
bool operator()(Element const *x, Element const *y) const
Returns true if x and y point to equal Element's.
Definition: elements.h:221
Namespace for everything in the libsemigroups library.
Definition: blocks.cc:32
size_t hash_value() const
Return the hash value of an Element.
Definition: elements.h:123
bool operator<(const Element &that) const override
Returns true if this is less than that.
Definition: elements.h:707
size_t complexity() const override
Returns the approximate time complexity of multiplication.
Definition: elements.cc:67
void set_rank(size_t rank)
Set the cached rank.
Definition: elements.h:977
Permutation * inverse()
Returns the inverse of a permutation.
Definition: elements.h:1272
void copy(Element const *x) override
Copy another Element into this.
Definition: elements.h:382
elm_t
This enum contains some different types of Element.
Definition: elements.h:52
static size_t vector_hash(std::vector< T > const *vec)
Returns a hash value for a vector provided there is a specialization of std::hash for the template ty...
Definition: elements.h:447
Abstract base class for elements using a vector to store their defining data and the default hash fun...
Definition: elements.h:468
Element * identity() const override
Returns the identity PBR with degree equal to that of this.
Definition: elements.cc:295
virtual bool operator==(const Element &that) const =0
Returns true if this equals that.
virtual void really_delete()=0
Deletes the defining data of an Element.
void set_nr_left_blocks(size_t nr_left_blocks)
Set the cached number of left blocks.
Definition: elements.h:966
void redefine(Element const *x, Element const *y) final
Multiplies x and y and stores the result in this.
Definition: elements.cc:36
static size_t const UNDEFINED
UNDEFINED value.
Definition: elements.h:261
void redefine(Element const *x, Element const *y, size_t const &thread_id) override
Multiply x and y and stores the result in this.
Definition: elements.cc:311
std::vector< TValueType >::iterator begin() const
Returns an iterator.
Definition: elements.h:413
size_t complexity() const override
Returns the approximate time complexity of multiplying PBRs.
Definition: elements.cc:280
std::vector< TValueType > * _vector
The vector containing the defining data of this.
Definition: elements.h:458
u_int32_t nr_right_blocks()
Returns the number of blocks containing a negative integer.
Definition: elements.cc:193
virtual ~Element()
A default destructor.
Definition: elements.h:70
virtual void redefine(Element const *x, Element const *y)
Multiplies x and y and stores the result in this.
Definition: elements.h:185
Element * identity() const override
Returns the identity matrix with dimension of this.
Definition: elements.h:1106
virtual Element * really_copy(size_t increase_deg_by=0) const =0
Returns a new element completely independent of this.
virtual bool operator<(const Element &that) const =0
Returns true if this is less than that.
Subclass of Element that wraps an libsemigroups::rws_word_t.
Definition: rwse.h:37
size_t crank() const
Returns the rank of a partial permutation.
Definition: elements.h:794
Blocks * left_blocks()
Return the left blocks of a bipartition.
Definition: elements.cc:231
BooleanMat(std::vector< std::vector< bool >> const &matrix)
A constructor.
Definition: elements.h:1309
virtual T zero() const =0
Returns the additive identity, or zero, of the semiring.
std::vector< TValueType >::iterator end() const
Returns an iterator.
Definition: elements.h:421
Element * really_copy(size_t increase_deg_by=0) const override
Returns a pointer to a copy of this.
Definition: elements.h:366
Semiring< TValueType > const * semiring() const
Returns a pointer to the Semiring over which the matrix is defined.
Definition: elements.h:1081
Provides a call operator returning a hash value for an Element via a pointer.
Definition: elements.h:232
size_t degree() const override
Returns the dimension of the matrix.
Definition: elements.h:1097
virtual Element * identity() const =0
Returns a new copy of the identity element.
Class for projective max-plus matrices.
Definition: elements.h:1208
virtual size_t complexity() const =0
Returns the approximate time complexity of multiplying two Element objects in a given subclass.
virtual T one() const =0
Returns the multiplicative identity, or one, of the semiring.
TValueType at(size_t pos) const
Returns the pos entry in the vector containing the defining data.
Definition: elements.h:329
Bipartition(size_t degree)
A constructor.
Definition: elements.h:821
size_t rank()
Returns the number of transverse blocks.
Definition: elements.cc:222
void really_delete() override
Deletes the defining data of an ElementWithVectorData.
Definition: elements.h:405
bool operator==(Element const &that) const override
Returns true if this equals that.
Definition: elements.h:337
void redefine(Element const *x, Element const *y) override
Multiply x and y and stores the result in this.
Definition: elements.h:1138