libsemigroups
Classes | Public Types | Public Member Functions | Protected Member Functions | Static Protected Attributes | List of all members
libsemigroups::Element Class Referenceabstract

Abstract base class for semigroup elements. More...

#include <elements.h>

Inheritance diagram for libsemigroups::Element:
Inheritance graph

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 Elementidentity () 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 Elementreally_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...
 

Detailed Description

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.

Member Enumeration Documentation

§ elm_t

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.

Constructor & Destructor Documentation

§ Element()

libsemigroups::Element::Element ( elm_t  type = Element::elm_t::NOT_RWSE)
inlineexplicit

A constructor.

The parameter type should be the type elm_t of the element being created (defaults to libsemigroups::Element::NOT_RWSE).

§ ~Element()

virtual libsemigroups::Element::~Element ( )
inlinevirtual

A default destructor.

This does not properly delete the underlying data of the object, this should be done using Element::really_delete.

Member Function Documentation

§ cache_hash_value()

virtual void libsemigroups::Element::cache_hash_value ( ) const
protectedpure virtual

§ complexity()

virtual size_t libsemigroups::Element::complexity ( ) const
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.

§ copy()

virtual void libsemigroups::Element::copy ( Element const *  x)
pure virtual

§ degree()

virtual size_t libsemigroups::Element::degree ( ) const
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.

§ get_type()

elm_t libsemigroups::Element::get_type ( ) const
inline

Returns the type libsemigroups::Element::elm_t of an Element object.

§ hash_value()

size_t libsemigroups::Element::hash_value ( ) const
inline

Return the hash value of an Element.

This method returns a hash value for an object in a subclass of Element. This value is only computed the first time this method is called.

§ identity()

virtual Element* libsemigroups::Element::identity ( ) const
pure virtual

§ operator<()

virtual bool libsemigroups::Element::operator< ( const Element that) const
pure virtual

§ operator==()

virtual bool libsemigroups::Element::operator== ( const Element that) const
pure virtual

§ really_copy()

virtual Element* libsemigroups::Element::really_copy ( size_t  increase_deg_by = 0) const
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.

See also
Element::really_delete.

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.

§ really_delete()

virtual void libsemigroups::Element::really_delete ( )
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.

See also
Element::really_copy.

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.

§ redefine() [1/2]

virtual void libsemigroups::Element::redefine ( Element const *  x,
Element const *  y 
)
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.

§ redefine() [2/2]

virtual void libsemigroups::Element::redefine ( Element const *  x,
Element const *  y,
size_t const &  thread_id 
)
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.

§ reset_hash_value()

void libsemigroups::Element::reset_hash_value ( ) const
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.

§ swap()

virtual void libsemigroups::Element::swap ( Element x)
pure virtual

Member Data Documentation

§ UNDEFINED

size_t const libsemigroups::Element::UNDEFINED = std::numeric_limits<size_t>::max()
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.


The documentation for this class was generated from the following files: