libsemigroups
|
Abstract base class for semigroup elements. More...
#include <elements.h>
Classes | |
struct | Equal |
Provides a call operator for comparing Elements via pointers. More... | |
struct | Hash |
Provides a call operator returning a hash value for an Element via a pointer. More... | |
Public Types | |
enum | elm_t { RWSE = 0, NOT_RWSE = 1 } |
This enum contains some different types of Element. More... | |
Public Member Functions | |
Element (elm_t type=Element::elm_t::NOT_RWSE) | |
A constructor. More... | |
virtual | ~Element () |
A default destructor. More... | |
virtual size_t | complexity () const =0 |
Returns the approximate time complexity of multiplying two Element objects in a given subclass. More... | |
virtual void | copy (Element const *x)=0 |
Copy another Element into this . More... | |
virtual size_t | degree () const =0 |
Returns the degree of an Element. More... | |
elm_t | get_type () const |
Returns the type libsemigroups::Element::elm_t of an Element object. More... | |
size_t | hash_value () const |
Return the hash value of an Element. More... | |
virtual Element * | identity () const =0 |
Returns a new copy of the identity element. More... | |
virtual bool | operator< (const Element &that) const =0 |
Returns true if this is less than that . More... | |
virtual bool | operator== (const Element &that) const =0 |
Returns true if this equals that . More... | |
virtual Element * | really_copy (size_t increase_deg_by=0) const =0 |
Returns a new element completely independent of this . More... | |
virtual void | really_delete ()=0 |
Deletes the defining data of an Element. More... | |
virtual void | redefine (Element const *x, Element const *y) |
Multiplies x and y and stores the result in this . More... | |
virtual void | redefine (Element const *x, Element const *y, size_t const &thread_id) |
Multiplies x and y and stores the result in this . More... | |
virtual void | swap (Element *x)=0 |
Swap another Element with this . More... | |
Protected Member Functions | |
virtual void | cache_hash_value () const =0 |
Calculate and cache a hash value. More... | |
void | reset_hash_value () const |
Reset the cached value used by Element::hash_value. More... | |
Static Protected Attributes | |
static size_t const | UNDEFINED = std::numeric_limits<size_t>::max() |
UNDEFINED value. More... | |
Abstract base class for semigroup elements.
The Semigroup class consists of Element objects. Every derived class of Element implements the deleted methods of Element, which are used by the Semigroup class.
This enum contains some different types of Element.
This exists so that the type of a subclass of Element can be determined from a pointer to the base class. Currently, it is only necessary to distiguish RWSE objects from other Element objects and so there are only two values.
Enumerator | |
---|---|
RWSE | Type for Element objects arising from a rewriting system RWS. |
NOT_RWSE | Type for Element objects not arising from a rewriting system RWS. |
|
inlineexplicit |
A constructor.
The parameter type
should be the type elm_t of the element being created (defaults to libsemigroups::Element::NOT_RWSE).
|
inlinevirtual |
A default destructor.
This does not properly delete the underlying data of the object, this should be done using Element::really_delete.
|
protectedpure virtual |
Calculate and cache a hash value.
This method is used to compute and cache the hash value of this
.
Implemented in libsemigroups::PBR, libsemigroups::Transformation< T >, libsemigroups::ElementWithVectorDataDefaultHash< TValueType, TSubclass >, libsemigroups::ElementWithVectorDataDefaultHash< bool, BooleanMat >, libsemigroups::ElementWithVectorDataDefaultHash< T, Transformation< T > >, libsemigroups::ElementWithVectorDataDefaultHash< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorDataDefaultHash< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorDataDefaultHash< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorDataDefaultHash< T, PartialPerm< T > >, and libsemigroups::RWSE.
|
pure virtual |
Returns the approximate time complexity of multiplying two Element objects in a given subclass.
This method returns an integer which represents the approximate time complexity of multiplying two objects in the same subclass of Element which have the same Element::degree. For example, the approximate time complexity of multiplying two \(3\times 3\) matrices over a common semiring is \(O(3 ^ 3)\), and 27 is returned by MatrixOverSemiring::complexity.
The returned value is used in, for example, Semigroup::fast_product and Semigroup::nridempotents to decide if it is better to multiply elements or follow a path in the Cayley graph.
Implemented in libsemigroups::PBR, libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >, libsemigroups::MatrixOverSemiringBase< bool, BooleanMat >, libsemigroups::MatrixOverSemiringBase< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::MatrixOverSemiringBase< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::Bipartition, libsemigroups::PartialTransformation< TValueType, TSubclass >, libsemigroups::PartialTransformation< T, Transformation< T > >, libsemigroups::PartialTransformation< T, PartialPerm< T > >, and libsemigroups::RWSE.
|
pure virtual |
Copy another Element into this
.
This method copies x
into this
by changing this
in-place.
Implemented in libsemigroups::ElementWithVectorData< TValueType, TSubclass >, libsemigroups::ElementWithVectorData< bool, BooleanMat >, libsemigroups::ElementWithVectorData< T, Transformation< T > >, libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorData< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorData< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorData< T, PartialPerm< T > >, libsemigroups::ElementWithVectorData< std::vector< u_int32_t >, PBR >, and libsemigroups::RWSE.
|
pure virtual |
Returns the degree of an Element.
This method returns an integer which represents the size of the element, and is used to determine whether or not two elements are compatible for multiplication. For example, two Transformation objects of different degrees cannot be multiplied, and a Bipartition of degree 10 cannot be an element of a monoid of bipartitions of degree 3.
See the relevant subclass for the particular meaning of the return value of this method for each subclass.
Implemented in libsemigroups::PBR, libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >, libsemigroups::MatrixOverSemiringBase< bool, BooleanMat >, libsemigroups::MatrixOverSemiringBase< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::MatrixOverSemiringBase< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::Bipartition, libsemigroups::PartialTransformation< TValueType, TSubclass >, libsemigroups::PartialTransformation< T, Transformation< T > >, libsemigroups::PartialTransformation< T, PartialPerm< T > >, and libsemigroups::RWSE.
|
inline |
Returns the type libsemigroups::Element::elm_t of an Element object.
|
inline |
|
pure virtual |
Returns a new copy of the identity element.
This method returns the multiplicative identity element for an object in a subclass of Element. The returned identity belongs to the same subclass and has the same degree as this
.
Implemented in libsemigroups::PBR, libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >, libsemigroups::MatrixOverSemiringBase< bool, BooleanMat >, libsemigroups::MatrixOverSemiringBase< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::MatrixOverSemiringBase< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::Bipartition, libsemigroups::PartialTransformation< TValueType, TSubclass >, libsemigroups::PartialTransformation< T, Transformation< T > >, libsemigroups::PartialTransformation< T, PartialPerm< T > >, and libsemigroups::RWSE.
|
pure virtual |
Returns true
if this
is less than that
.
This method defines a total order on the set of objects in a given subclass of Element with a given Element::degree. The definition of this total order depends on the method for the operator < in the subclass.
Implemented in libsemigroups::PartialPerm< T >, libsemigroups::ElementWithVectorData< TValueType, TSubclass >, libsemigroups::ElementWithVectorData< bool, BooleanMat >, libsemigroups::ElementWithVectorData< T, Transformation< T > >, libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorData< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorData< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorData< T, PartialPerm< T > >, libsemigroups::ElementWithVectorData< std::vector< u_int32_t >, PBR >, and libsemigroups::RWSE.
|
pure virtual |
Returns true
if this
equals that
.
This method checks the mathematical equality of two Element objects in the same subclass of Element.
Implemented in libsemigroups::ElementWithVectorData< TValueType, TSubclass >, libsemigroups::ElementWithVectorData< bool, BooleanMat >, libsemigroups::ElementWithVectorData< T, Transformation< T > >, libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorData< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorData< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorData< T, PartialPerm< T > >, libsemigroups::ElementWithVectorData< std::vector< u_int32_t >, PBR >, and libsemigroups::RWSE.
|
pure virtual |
Returns a new element completely independent of this
.
If increase_deg_by
is non-zero, then the degree (the size of the container) of the defining data of this
will be increased by this amount.
This method really copies an Element. To minimise the amount of copying when Element objects are inserted in a std::unordered_map and other containers, an Element behaves somewhat like a pointer, in that the actual data in an Element is only copied when this method is called. Otherwise, if an Element is copied, then its defining data is only stored once.
Implemented in libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >, libsemigroups::MatrixOverSemiringBase< bool, BooleanMat >, libsemigroups::MatrixOverSemiringBase< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::MatrixOverSemiringBase< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::PartialPerm< T >, libsemigroups::Transformation< T >, libsemigroups::ElementWithVectorData< TValueType, TSubclass >, libsemigroups::ElementWithVectorData< bool, BooleanMat >, libsemigroups::ElementWithVectorData< T, Transformation< T > >, libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorData< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorData< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorData< T, PartialPerm< T > >, libsemigroups::ElementWithVectorData< std::vector< u_int32_t >, PBR >, and libsemigroups::RWSE.
|
pure virtual |
Deletes the defining data of an Element.
This method really deletes an Element. To minimise the amount of copying when Elements are inserted in an std::unordered_map or other containers, an Element behaves somewhat like a pointer, in that the actual data in an Element is only deleted when this method is called. Otherwise, if an Element is deleted, then its defining data is not deleted, since it may be contained in several copies of the Element.
Implemented in libsemigroups::ElementWithVectorData< TValueType, TSubclass >, libsemigroups::ElementWithVectorData< bool, BooleanMat >, libsemigroups::ElementWithVectorData< T, Transformation< T > >, libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorData< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorData< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorData< T, PartialPerm< T > >, libsemigroups::ElementWithVectorData< std::vector< u_int32_t >, PBR >, and libsemigroups::RWSE.
|
inlinevirtual |
Multiplies x
and y
and stores the result in this
.
Redefine this
to be the product of x
and y
. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.
The implementation of this method in the Element base class simply calls the 3 parameter version with third parameter 0. Any subclass of Element can implement either a two or three parameter version of this method and the base class method implements the other method.
Reimplemented in libsemigroups::BooleanMat, libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >, libsemigroups::MatrixOverSemiringBase< bool, BooleanMat >, libsemigroups::MatrixOverSemiringBase< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::MatrixOverSemiringBase< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::PartialPerm< T >, libsemigroups::Transformation< T >, and libsemigroups::RWSE.
|
inlinevirtual |
Multiplies x
and y
and stores the result in this
.
Redefine this
to be the product of x
and y
. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.
The implementation of this method in the Element base class simply calls the 2 parameter version and ignores the third parameter thread_id
. Any subclass of Element can implement either a two or three parameter version of this method and the base class method implements the other method.
The parameter thread_id
is required in some derived classes of Element because some temporary storage is required to find the product of x
and y
.
Note that if different threads call this method on a derived class of Element where static temporary storage is used in the redefine method with the same value of thread_id
, then bad things may happen.
Reimplemented in libsemigroups::PBR, and libsemigroups::Bipartition.
|
inlineprotected |
Reset the cached value used by Element::hash_value.
This method is used to reset the cached hash value to libsemigroups::Element::UNDEFINED. This is required after running Element::redefine, Element::copy, or any other method that changes the defining data of this
.
|
pure virtual |
Swap another Element with this
.
This method swaps the defining data of x
and this
.
Implemented in libsemigroups::ElementWithVectorData< TValueType, TSubclass >, libsemigroups::ElementWithVectorData< bool, BooleanMat >, libsemigroups::ElementWithVectorData< T, Transformation< T > >, libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >, libsemigroups::ElementWithVectorData< TValueType, MatrixOverSemiring< TValueType > >, libsemigroups::ElementWithVectorData< int64_t, ProjectiveMaxPlusMatrix >, libsemigroups::ElementWithVectorData< T, PartialPerm< T > >, libsemigroups::ElementWithVectorData< std::vector< u_int32_t >, PBR >, and libsemigroups::RWSE.
|
staticprotected |
UNDEFINED value.
This variable is used to indicate that a value is undefined. For example, the cached hash value of an Element is initially set to this value.