libsemigroups
Public Member Functions | Static Public Attributes | List of all members
libsemigroups::PartialTransformation< TValueType, TSubclass > Class Template Reference

Abstract class for partial transformations. More...

#include <elements.h>

Inheritance diagram for libsemigroups::PartialTransformation< TValueType, TSubclass >:
Inheritance graph
Collaboration diagram for libsemigroups::PartialTransformation< TValueType, TSubclass >:
Collaboration graph

Public Member Functions

size_t complexity () const override
 Returns the approximate time complexity of multiplying two partial transformations. More...
 
size_t crank () const
 Returns the rank of a partial transformation. More...
 
size_t degree () const override
 Returns the degree of a partial transformation. More...
 
Elementidentity () const override
 Returns the identity transformation with degrees of this. More...
 
- Public Member Functions inherited from libsemigroups::ElementWithVectorData< TValueType, TSubclass >
 ElementWithVectorData ()
 A constructor. More...
 
 ElementWithVectorData (std::vector< TValueType > *vector)
 A constructor. More...
 
 ElementWithVectorData (std::vector< TValueType > const &vector)
 A constructor. More...
 
TValueType at (size_t pos) const
 Returns the pos entry in the vector containing the defining data. More...
 
std::vector< TValueType >::iterator begin () const
 Returns an iterator. More...
 
std::vector< TValueType >::iterator cbegin () const
 Returns a const iterator. More...
 
std::vector< TValueType >::iterator cend () const
 Returns a const iterator. More...
 
void copy (Element const *x) override
 Copy another Element into this. More...
 
std::vector< TValueType >::iterator end () const
 Returns an iterator. More...
 
bool operator< (Element const &that) const override
 Returns true if this is less than that. More...
 
bool operator== (Element const &that) const override
 Returns true if this equals that. More...
 
TValueType operator[] (size_t pos) const
 Returns the pos entry in the vector containing the defining data. More...
 
Elementreally_copy (size_t increase_deg_by=0) const override
 Returns a pointer to a copy of this. More...
 
void really_delete () override
 Deletes the defining data of an ElementWithVectorData. More...
 
void swap (Element *x) override
 Swap another Element with this. More...
 
- Public Member Functions inherited from libsemigroups::Element
 Element (elm_t type=Element::elm_t::NOT_RWSE)
 A constructor. More...
 
virtual ~Element ()
 A default destructor. 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 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...
 

Static Public Attributes

static TValueType const UNDEFINED = std::numeric_limits<TValueType>::max()
 Undefined image value. More...
 

Additional Inherited Members

- Public Types inherited from libsemigroups::Element
enum  elm_t { RWSE = 0, NOT_RWSE = 1 }
 This enum contains some different types of Element. More...
 
- Protected Member Functions inherited from libsemigroups::ElementWithVectorDataDefaultHash< TValueType, TSubclass >
void cache_hash_value () const override
 This method implements the default hash function for an ElementWithVectorData, which uses ElementWithVectorData::vector_hash. Derive from this class if you are defining a class derived from ElementWithVectorData and there is a specialization of std::hash for the template parameter TValueType, and you do not want to define a hash function explicitly in your derived class. More...
 
- Protected Member Functions inherited from libsemigroups::Element
void reset_hash_value () const
 Reset the cached value used by Element::hash_value. More...
 
- Static Protected Member Functions inherited from libsemigroups::ElementWithVectorData< TValueType, TSubclass >
template<typename T >
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 type T. More...
 
- Protected Attributes inherited from libsemigroups::ElementWithVectorData< TValueType, TSubclass >
std::vector< TValueType > * _vector
 The vector containing the defining data of this. More...
 
- Static Protected Attributes inherited from libsemigroups::Element
static size_t const UNDEFINED = std::numeric_limits<size_t>::max()
 UNDEFINED value. More...
 

Detailed Description

template<typename TValueType, typename TSubclass>
class libsemigroups::PartialTransformation< TValueType, TSubclass >

Abstract class for partial transformations.

This is a template class for partial transformations, which is a subclass of ElementWithVectorDataDefaultHash. For example, Transformation<u_int128_t> is a subclass of PartialTransformation<u_int128_t, Transformation<u_int128_t>>.

The template parameter TValueType is the type of image values, i.e. u_int16_t, and so on. The value of the template parameter S can be used to reduce (or increase) the amount of memory required by instances of this class.

The template parameter TSubclass is the subclass of PartialTransformation used by the PartialTransformation::identity method to construct an identity, so that the return value of the method PartialTransformation::identity is of type TSubclass instead of type PartialTransformation.

This class is abstract since it does not implement all methods required by the Element class, it exists to provide common methods for its subclasses.

A partial transformation \(f\) is just a function defined on a subset of \(\{0, 1, \ldots, n - 1\}\) for some integer \(n\) called the degree of f. A partial transformation is stored as a vector of the images of \(\{0, 1, \ldots, n -1\}\), i.e. \(\{(0)f, (1)f, \ldots, (n - 1)f\}\) where the value PartialTransformation::UNDEFINED is used to indicate that \((i)f\) is, you guessed it, undefined (i.e. not among the points where \(f\) is defined).

Member Function Documentation

◆ complexity()

template<typename TValueType, typename TSubclass>
size_t libsemigroups::PartialTransformation< TValueType, TSubclass >::complexity ( ) const
inlineoverridevirtual

Returns the approximate time complexity of multiplying two partial transformations.

The approximate time complexity of multiplying partial transformations is just their degree.

Implements libsemigroups::Element.

◆ crank()

template<typename TValueType, typename TSubclass>
size_t libsemigroups::PartialTransformation< TValueType, TSubclass >::crank ( ) const
inline

Returns the rank of a partial transformation.

The rank of a partial transformation is the number of its distinct image values, not including PartialTransformation::UNDEFINED. This method recomputes the return value every time it is called.

◆ degree()

template<typename TValueType, typename TSubclass>
size_t libsemigroups::PartialTransformation< TValueType, TSubclass >::degree ( ) const
inlineoverridevirtual

Returns the degree of a partial transformation.

The degree of a partial transformation is the number of points used in its definition, which is equal to the size of ElementWithVectorData::_vector.

Implements libsemigroups::Element.

◆ identity()

template<typename TValueType, typename TSubclass>
Element* libsemigroups::PartialTransformation< TValueType, TSubclass >::identity ( ) const
inlineoverridevirtual

Returns the identity transformation with degrees of this.

This method returns a new partial transformation with degree equal to the degree of this that fixes every value from 0 to the degree of this.

Implements libsemigroups::Element.

Member Data Documentation

◆ UNDEFINED

template<typename TValueType, typename TSubclass>
TValueType const libsemigroups::PartialTransformation< TValueType, TSubclass >::UNDEFINED = std::numeric_limits<TValueType>::max()
static

Undefined image value.

This value is used to indicate that a partial transformation is not defined on a value.


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