libsemigroups
Public Member Functions | List of all members
libsemigroups::PartialPerm< T > Class Template Reference

Template class for partial permutations. More...

#include <elements.h>

Inheritance diagram for libsemigroups::PartialPerm< T >:
Inheritance graph
Collaboration diagram for libsemigroups::PartialPerm< T >:
Collaboration graph

Public Member Functions

 PartialPerm (std::vector< T > const &dom, std::vector< T > const &ran, size_t deg)
 A constructor. More...
 
size_t crank () const
 Returns the rank of a partial permutation. More...
 
bool operator< (const Element &that) const override
 Returns true if this is less than that. More...
 
Elementreally_copy (size_t increase_deg_by=0) const override
 Returns a pointer to a copy of this. More...
 
void redefine (Element const *x, Element const *y) override
 Multiply x and y and stores the result in this. More...
 
- Public Member Functions inherited from libsemigroups::PartialTransformation< T, PartialPerm< T > >
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< T, PartialPerm< T > >
 ElementWithVectorData ()
 A constructor. More...
 
 ElementWithVectorData (std::vector< T > *vector)
 A constructor. More...
 
 ElementWithVectorData (std::vector< T > const &vector)
 A constructor. More...
 
at (size_t pos) const
 Returns the pos entry in the vector containing the defining data. More...
 
std::vector< T >::iterator begin () const
 Returns an iterator. More...
 
std::vector< T >::iterator cbegin () const
 Returns a const iterator. More...
 
std::vector< T >::iterator cend () const
 Returns a const iterator. More...
 
void copy (Element const *x) override
 Copy another Element into this. More...
 
std::vector< T >::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...
 
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, size_t const &thread_id)
 Multiplies x and y and stores the result in this. 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...
 
- Static Public Attributes inherited from libsemigroups::PartialTransformation< T, PartialPerm< T > >
static T const UNDEFINED
 Undefined image value. More...
 
- Protected Member Functions inherited from libsemigroups::ElementWithVectorDataDefaultHash< T, PartialPerm< T > >
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< T, PartialPerm< 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< T, PartialPerm< T > >
std::vector< T > * _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 T>
class libsemigroups::PartialPerm< T >

Template class for partial permutations.

The value of the template parameter T can be used to reduce the ! amount ! of memory required by instances of this class; see PartialTransformation ! and ElementWithVectorData for more details.

A partial permutation \(f\) is just an injective partial transformation, which is stored as a vector of the images of \(\{0, 1, \ldots, n - 1\}\), i.e. i.e. \(\{(0)f, (1)f, \ldots, (n - 1)f\}\) where the value PartialTransformation::UNDEFINED is used to indicate that \((i)f\) is undefined (i.e. not among the points where \(f\) is defined).

Constructor & Destructor Documentation

§ PartialPerm()

template<typename T>
libsemigroups::PartialPerm< T >::PartialPerm ( std::vector< T > const &  dom,
std::vector< T > const &  ran,
size_t  deg 
)
inlineexplicit

A constructor.

Constructs a partial perm of degree deg such that

(dom[i])f =
ran[i]

for all i and which is undefined on every other value in the range 0 to (strictly less than deg). This method asserts that dom and ran have equal size and that deg is greater than or equal to the maximum value in dom or ran.

Member Function Documentation

§ crank()

template<typename T>
size_t libsemigroups::PartialPerm< T >::crank ( ) const
inline

Returns the rank of a partial permutation.

The rank of a partial permutation is the number of its distinct image values, not including PartialTransformation::UNDEFINED. This method involves slightly less work than PartialTransformation::crank since a partial permutation is injective, and so every image value occurs precisely once. This method recomputes the return value every time it is called.

§ operator<()

template<typename T>
bool libsemigroups::PartialPerm< T >::operator< ( const Element that) const
inlineoverridevirtual

Returns true if this is less than that.

This defines a total order on partial permutations that is equivalent to that used by GAP. It is not short-lex on the list of images.

Returns true if something complicated is true and false if it is not.

Implements libsemigroups::Element.

§ really_copy()

template<typename T>
Element* libsemigroups::PartialPerm< T >::really_copy ( size_t  increase_deg_by = 0) const
inlineoverridevirtual

Returns a pointer to a copy of this.

See Element::really_copy for more details about this method.

The copy returned by this method is undefined on all the values between the PartialPerm::degree of this and increase_deg_by.

Implements libsemigroups::Element.

§ redefine()

template<typename T>
void libsemigroups::PartialPerm< T >::redefine ( Element const *  x,
Element const *  y 
)
inlineoverridevirtual

Multiply x and y and stores the result in this.

See Element::redefine for more details about this method.

This method asserts that the degrees of x, y, and this, are all equal, and that neither x nor y equals this.

Reimplemented from libsemigroups::Element.


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