libsemigroups
Public Member Functions | List of all members
libsemigroups::Bipartition Class Reference

Class for bipartitions. More...

#include <elements.h>

Inheritance diagram for libsemigroups::Bipartition:
Inheritance graph
Collaboration diagram for libsemigroups::Bipartition:
Collaboration graph

Public Member Functions

 Bipartition (size_t degree)
 A constructor. More...
 
 Bipartition (std::vector< u_int32_t > *blocks)
 A constructor. More...
 
 Bipartition (std::vector< u_int32_t > const &blocks)
 A constructor. More...
 
size_t complexity () const override
 Returns the approximate time complexity of multiplication. More...
 
u_int32_t const_nr_blocks () const
 Returns the number of blocks in a bipartition. More...
 
size_t degree () const override
 Returns the degree of the bipartition. More...
 
Elementidentity () const override
 Returns an identity bipartition. More...
 
bool is_transverse_block (size_t index)
 Returns true if the block with index index is transverse. More...
 
Blocksleft_blocks ()
 Return the left blocks of a bipartition. More...
 
u_int32_t nr_blocks ()
 Returns the number of blocks in a bipartition. More...
 
u_int32_t nr_left_blocks ()
 Returns the number of blocks containing a positive integer. More...
 
u_int32_t nr_right_blocks ()
 Returns the number of blocks containing a negative integer. More...
 
size_t rank ()
 Returns the number of transverse blocks. More...
 
void redefine (Element const *x, Element const *y, size_t const &thread_id) override
 Multiply x and y and stores the result in this. More...
 
Blocksright_blocks ()
 Return the left blocks of a bipartition. More...
 
void set_nr_blocks (size_t nr_blocks)
 Set the cached number of blocks. More...
 
void set_nr_left_blocks (size_t nr_left_blocks)
 Set the cached number of left blocks. More...
 
void set_rank (size_t rank)
 Set the cached rank. More...
 
- Public Member Functions inherited from libsemigroups::ElementWithVectorData< u_int32_t, Bipartition >
 ElementWithVectorData ()
 A constructor. More...
 
 ElementWithVectorData (std::vector< u_int32_t > *vector)
 A constructor. More...
 
 ElementWithVectorData (std::vector< u_int32_t > const &vector)
 A constructor. More...
 
u_int32_t at (size_t pos) const
 Returns the pos entry in the vector containing the defining data. More...
 
std::vector< u_int32_t >::iterator begin () const
 Returns an iterator. More...
 
std::vector< u_int32_t >::iterator cbegin () const
 Returns a const iterator. More...
 
std::vector< u_int32_t >::iterator cend () const
 Returns a const iterator. More...
 
void copy (Element const *x) override
 Copy another Element into this. More...
 
std::vector< u_int32_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...
 
u_int32_t 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...
 

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< u_int32_t, Bipartition >
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< u_int32_t, Bipartition >
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< u_int32_t, Bipartition >
std::vector< u_int32_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

Class for bipartitions.

A bipartition is a partition of the set \(\{0, ..., 2n - 1\}\) for some integer \(n\); see the Semigroups package for GAP documentation for more details. The Bipartition class is more complex (i.e. has more methods) than strictly required by the algorithms for a Semigroup object because the extra methods are used in the GAP package Semigroups package for GAP.

Constructor & Destructor Documentation

§ Bipartition() [1/3]

libsemigroups::Bipartition::Bipartition ( size_t  degree)
inlineexplicit

A constructor.

Constructs a uninitialised bipartition of degree degree.

§ Bipartition() [2/3]

libsemigroups::Bipartition::Bipartition ( std::vector< u_int32_t > *  blocks)
inlineexplicit

A constructor.

The parameter blocks must have length 2n for some positive integer n, consist of non-negative integers, and have the property that if i, i > 0, occurs in blocks, then i - 1 occurs earlier in blocks. None of this is checked.

The parameter blocks is not copied, and should be deleted using ElementWithVectorData::really_delete.

§ Bipartition() [3/3]

libsemigroups::Bipartition::Bipartition ( std::vector< u_int32_t > const &  blocks)
inlineexplicit

A constructor.

The parameter blocks must have length 2n for some positive integer n, consist of non-negative integers, and have the property that if i, i > 0, occurs in blocks, then i - 1 occurs earlier in blocks. None of this is checked.

The parameter blocks is not copied, and should be deleted using ElementWithVectorData::really_delete.

Member Function Documentation

§ complexity()

size_t libsemigroups::Bipartition::complexity ( ) const
overridevirtual

Returns the approximate time complexity of multiplication.

In the case of a Bipartition of degree n the value 2n ^ 2 is returned.

Implements libsemigroups::Element.

§ const_nr_blocks()

u_int32_t libsemigroups::Bipartition::const_nr_blocks ( ) const

Returns the number of blocks in a bipartition.

This method differs for Bipartition::nr_blocks in that the number of blocks is not cached if it has not been previously computed.

§ degree()

size_t libsemigroups::Bipartition::degree ( ) const
overridevirtual

Returns the degree of the bipartition.

A bipartition is of degree n if it is a partition of \(\{0, \ldots, 2n - 1\}\).

Implements libsemigroups::Element.

§ identity()

Element * libsemigroups::Bipartition::identity ( ) const
overridevirtual

Returns an identity bipartition.

The identity bipartition of degree \(n\) has blocks \(\{i, -i\}\) for all \(i\in \{0, \ldots, n - 1\}\). This method returns a new identity bipartition of degree equal to the degree of this.

Implements libsemigroups::Element.

§ is_transverse_block()

bool libsemigroups::Bipartition::is_transverse_block ( size_t  index)

Returns true if the block with index index is transverse.

A block of a biparition is transverse if it contains integers less than and greater than \(n\), which is the degree of the bipartition. This method asserts that the parameter index is less than the number of blocks in the bipartition.

§ left_blocks()

Blocks * libsemigroups::Bipartition::left_blocks ( )

Return the left blocks of a bipartition.

The left blocks of a bipartition is the partition of \(\{0, \ldots, n - 1\}\) induced by the bipartition. This method returns a Blocks object representing this partition.

§ nr_blocks()

u_int32_t libsemigroups::Bipartition::nr_blocks ( )

Returns the number of blocks in a bipartition.

This value is cached the first time it is computed.

§ nr_left_blocks()

u_int32_t libsemigroups::Bipartition::nr_left_blocks ( )

Returns the number of blocks containing a positive integer.

The left blocks of a bipartition is the partition of \(\{0, \ldots, n - 1\}\) induced by the bipartition. This method returns the number of blocks in this partition.

§ nr_right_blocks()

u_int32_t libsemigroups::Bipartition::nr_right_blocks ( )

Returns the number of blocks containing a negative integer.

The right blocks of a bipartition is the partition of \(\{n, \ldots, 2n - 1\}\) induced by the bipartition. This method returns the number of blocks in this partition.

§ rank()

size_t libsemigroups::Bipartition::rank ( )

Returns the number of transverse blocks.

The rank of a bipartition is the number of blocks containing both positive and negative values. This value is cached after it is first computed.

§ redefine()

void libsemigroups::Bipartition::redefine ( Element const *  x,
Element const *  y,
size_t const &  thread_id 
)
overridevirtual

Multiply x and y and stores the result in this.

This method redefines this to be the product (as defined at the top of this page) of the parameters x and y. This method asserts that the degrees of x, y, and this, are all equal, and that neither x nor y equals this.

The parameter thread_id is required since some temporary storage is required to find the product of x and y. Note that if different threads call this method with the same value of thread_id then bad things will happen.

Reimplemented from libsemigroups::Element.

§ right_blocks()

Blocks * libsemigroups::Bipartition::right_blocks ( )

Return the left blocks of a bipartition.

The right blocks of a bipartition is the partition of \(\{n, \ldots, 2n - 1\}\) induced by the bipartition. This method returns a Blocks object representing this partition.

§ set_nr_blocks()

void libsemigroups::Bipartition::set_nr_blocks ( size_t  nr_blocks)
inline

Set the cached number of blocks.

This method sets the cached value of the number of blocks of this to nr_blocks. It asserts that either there is no existing cached value or nr_blocks equals the existing cached value.

§ set_nr_left_blocks()

void libsemigroups::Bipartition::set_nr_left_blocks ( size_t  nr_left_blocks)
inline

Set the cached number of left blocks.

This method sets the cached value of the number of left blocks of this to nr_left_blocks. It asserts that either there is no existing cached value or nr_left_blocks equals the existing cached value.

§ set_rank()

void libsemigroups::Bipartition::set_rank ( size_t  rank)
inline

Set the cached rank.

This method sets the cached value of the rank of this to rank. It asserts that either there is no existing cached value or rank equals the existing cached value.


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