Defined in bipart.hpp.

It is possible to associate to every Bipartition a pair of blocks, Bipartition::left_blocks() and Bipartition::right_blocks(), which determine the Green's \(\mathscr{L}\)- and \(\mathscr{R}\)-classes of the Bipartition in the monoid of all bipartitions. This is the purpose of this class.

The Blocks class is not currently used widely in libsemigroups but is used extensively in the Semigroups package for GAP (see [45]).

Public Types
using	const_iterator = typename std::vector<uint32_t>::const_iterator
	Type for const iterators pointing to the index of the block.

using	iterator = typename std::vector<uint32_t>::iterator
	Type for iterators pointing to the index of the block.

using	lookup_const_iterator = std::vector<bool>::const_iterator
	Type for const iterators pointing to the transverse block lookup.

Public Member Functions
	Blocks () noexcept=default
	Constructs a blocks object of size 0.

	Blocks (Blocks &&copy)=default
	Default move constructor.

	Blocks (Blocks const &copy)=default
	Default copy constructor.

	Blocks (const_iterator first, const_iterator last)
	Construct a blocks object from iterators.

	Blocks (size_t degree)
	Constructs a blocks object of given degree.

	Blocks (std::vector< std::vector< int32_t > > const &blocks)
	Constructs a Blocks object from a vector of vectors of integers.

uint32_t const &	at (size_t i) const
	Return a const reference to the index of the block containing a point.

Blocks &	block (size_t i, uint32_t val)
	Set the block that a point belongs to.

Blocks &	block_no_checks (size_t i, uint32_t val)
	Set the block that a point belongs to.

const_iterator	cbegin () const noexcept
	Return a const iterator pointing to the index of the first block.

lookup_const_iterator	cbegin_lookup () const noexcept
	Return a const iterator pointing to the first transverse block lookup.

const_iterator	cend () const noexcept
	Return a const iterator pointing one past-the-end of the last block.

lookup_const_iterator	cend_lookup () const noexcept
	Return a const iterator pointing to the first transverse block lookup.

uint32_t	degree () const noexcept
	Return the degree of a blocks object.

size_t	hash_value () const noexcept
	Return a hash value for a Blocks instance.

Blocks &	is_transverse_block (size_t i, bool val)
	Set whether or not the block containing a point is transverse.

bool	is_transverse_block (size_t index) const
	Check if a block is a transverse block.

Blocks &	is_transverse_block_no_checks (size_t i, bool val)
	Set whether or not the block containing a point is transverse.

bool	is_transverse_block_no_checks (size_t index) const
	Check if a block is a transverse block.

std::vector< bool > const &	lookup () const noexcept
	Return a const reference to the transverse blocks lookup.

uint32_t	number_of_blocks () const noexcept
	Return the number of blocks in a Blocks object.

bool	operator!= (Blocks const &that) const
	Compare two blocks objects for inequality.

bool	operator< (Blocks const &that) const
	Compare two blocks objects for less.

Blocks &	operator= (Blocks &&)=default
	Default move assignment operator.

Blocks &	operator= (Blocks const &)=default
	Default copy assignment operator.

bool	operator== (Blocks const &that) const
	Compare two blocks objects for equality.

uint32_t const &	operator[] (size_t i) const
	Return a const reference to the index of the block containing a point.

uint32_t	rank () const
	Return the number of transverse blocks.

Member Typedef Documentation

◆ const_iterator

using const_iterator = typename std::vector<uint32_t>::const_iterator

Type for const iterators pointing to the index of the block.

◆ iterator

using iterator = typename std::vector<uint32_t>::iterator

Type for iterators pointing to the index of the block.

◆ lookup_const_iterator

using lookup_const_iterator = std::vector<bool>::const_iterator

Type for const iterators pointing to the transverse block lookup.

Constructor & Destructor Documentation

◆ Blocks() [1/6]

Blocks ( )

defaultnoexcept

Default construct an empty Blocks object.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ Blocks() [2/6]

Blocks	(	const_iterator	first,
		const_iterator	last )

The degree of the blocks object constructed is last - first / 2.

Parameters

first	iterator pointing to the index of the block containing the first point.
last	iterator pointing one past the index of the block containing the last point.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in last - first.

Warning: No checks are made on the validity of the arguments to this function.

See also: throw_if_invalid(Blocks const&)

◆ Blocks() [3/6]

Blocks ( size_t degree )

inlineexplicit

Parameters

degree the degree of the blocks object to construct.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in degree.

◆ Blocks() [4/6]

Blocks ( std::vector< std::vector< int32_t > > const & blocks )

explicit

This function constructs a Blocks object from a vector of vectors of (signed) integers, so that the blocks consisting of negative values are transverse and those consisting of positive values are not.

Parameters

blocks the blocks.

Exceptions

LibsemigroupsException	if the set consisting of the absolute values of the entries in `blocks` is not \({1, \ldots, n\}\) where \(n\) is the maximum such value.
LibsemigroupsException	if `0` is an item in any block.
LibsemigroupsException	if any block is empty.
LibsemigroupsException	if any block contains both negative and positive values.
LibsemigroupsException	if the constructed Blocks object is not valid.

Complexity Linear in the sum of the sizes of the vectors in blocks.

◆ Blocks() [5/6]

Blocks ( Blocks const & copy )

default

Default copy constructor.

◆ Blocks() [6/6]

Blocks ( Blocks && copy )

default

Default move constructor.

Member Function Documentation

◆ at()

uint32_t const & at ( size_t i ) const

inlinenodiscard

Parameters

i	the point.

Returns: A value const reference to a value of type uint32_t.

Exceptions

std::out_of_range if i is out of range.

Complexity: Constant.

◆ block()

Blocks & block	(	size_t	i,
		uint32_t	val )

This function can be used to set the block containing the point i (to equal val).

Parameters

i	the point.
val	the block that `i` should belong to.

Exceptions

LibsemigroupsException if i is not in the range \([0, n)\) where \(n\) is the return value of number_of_blocks.

Complexity: At worst linear in degree().

◆ block_no_checks()

Blocks & block_no_checks	(	size_t	i,
		uint32_t	val )

This function can be used to set the block containing the point i (to equal val).

Parameters

i	the point.
val	the block that `i` should belong to.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst linear in degree().

Warning: No checks are made on the validity of the arguments to this function.

◆ cbegin()

const_iterator cbegin ( ) const

inlinenodiscardnoexcept

Returns: A value of type const_iterator.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ cbegin_lookup()

lookup_const_iterator cbegin_lookup ( ) const

inlinenodiscardnoexcept

The value pointed to is true if the i th block of this is a transverse block; and false otherwise.

Returns: A lookup_const_iterator.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ cend()

const_iterator cend ( ) const

inlinenodiscardnoexcept

Returns: A value of type const_iterator

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ cend_lookup()

lookup_const_iterator cend_lookup ( ) const

inlinenodiscardnoexcept

See also: cbegin_lookup.

◆ degree()

uint32_t degree ( ) const

inlinenodiscardnoexcept

The degree of a Blocks object is the size of the set of which it is a partition, or the size of the blocks parameter to Blocks::Blocks.

Returns: The degree of a Blocks object.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ hash_value()

size_t hash_value ( ) const

nodiscardnoexcept

This value is recomputed every time this function is called.

Returns: A hash value for a this.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Linear in degree().

◆ is_transverse_block() [1/2]

Blocks & is_transverse_block	(	size_t	i,
		bool	val )

inline

This function can be used to set whether or not the block containing i is transverse.

Parameters

i	the point.
val	whether or not the block containing `i` is transverse.

Exceptions

LibsemigroupsException if i is not in the range \([0, n)\) where \(n\) is the return value of number_of_blocks.

Complexity: Constant.

◆ is_transverse_block() [2/2]

bool is_transverse_block ( size_t index ) const

inlinenodiscard

This function returns true if the block with index index is a transverse (or signed) block and it returns false if it is not transverse (or unsigned).

Parameters

index the index of a block.

Returns: Whether or not the given block is transverse.

Exceptions

LibsemigroupsException if i is not in the range \([0, n)\) where \(n\) is the return value of number_of_blocks.

Complexity: Constant.

◆ is_transverse_block_no_checks() [1/2]

Blocks & is_transverse_block_no_checks	(	size_t	i,
		bool	val )

inline

This function can be used to set whether or not the block containing i is transverse.

Parameters

i	the point.
val	whether or not the block containing `i` is transverse.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Warning: No checks are made on the validity of the arguments to this function.

◆ is_transverse_block_no_checks() [2/2]

bool is_transverse_block_no_checks ( size_t index ) const

inlinenodiscard

This function returns true if the block with index index is a transverse (or signed) block and it returns false if it is not transverse (or unsigned).

Parameters

index the index of a block.

Returns: Whether or not the given block is transverse.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Warning: No checks are made on the validity of the arguments to this function.

◆ lookup()

std::vector< bool > const & lookup ( ) const

inlinenodiscardnoexcept

The value in position i of the returned vector is true if the block with index i is transverse and false if it is not transverse.

Returns: A const reference to a std::vector<bool>.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ number_of_blocks()

uint32_t number_of_blocks ( ) const

inlinenodiscardnoexcept

This function returns the number of parts in the partition that instances of this class represent.

Returns: The number of blocks.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: At worst \(O(n)\) where \(n\) is degree().

◆ operator!=()

bool operator!= ( Blocks const & that ) const

inlinenodiscard

Two Blocks objects are equal if and only if their underlying signed partitions are equal. It is ok to compare blocks of different degree with this operator.

Parameters

that	the Blocks instance for comparison.

Returns: Whether or not *this and that are not equal.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst linear in degree().

◆ operator<()

bool operator< ( Blocks const & that ) const

nodiscard

This operator defines a total order on the set of all Blocks objects (including those of different degree).

Parameters

that	the Blocks instance for comparison.

Returns: Whether or not *this is less than that.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in degree().

◆ operator=() [1/2]

Blocks & operator= ( Blocks && )

default

Default move assignment operator.

◆ operator=() [2/2]

Blocks & operator= ( Blocks const & )

default

Default copy assignment operator.

◆ operator==()

bool operator== ( Blocks const & that ) const

inlinenodiscard

Two Blocks objects are equal if and only if their underlying signed partitions are equal. It is ok to compare blocks of different degree with this operator.

Parameters

that	the Blocks instance for comparison.

Returns: Whether or not *this equals that.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst linear in degree().

◆ operator[]()

uint32_t const & operator[] ( size_t i ) const

inlinenodiscard

Parameters

i	the point.

Returns: A value const reference to a value of type uint32_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

◆ rank()

uint32_t rank ( ) const

nodiscard

This function returns the number of true values in lookup().

Returns: The number of signed (transverse) blocks in this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At most linear in the number of blocks.

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

/Users/jdm/libsemigroups/include/libsemigroups/bipart.hpp

Public Types

Public Member Functions

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ lookup_const_iterator

Constructor & Destructor Documentation

◆ Blocks() [1/6]

◆ Blocks() [2/6]

◆ Blocks() [3/6]

◆ Blocks() [4/6]

◆ Blocks() [5/6]

◆ Blocks() [6/6]

Member Function Documentation

◆ at()

◆ block()

◆ block_no_checks()

◆ cbegin()

◆ cbegin_lookup()

◆ cend()

◆ cend_lookup()

◆ degree()

◆ hash_value()

◆ is_transverse_block() [1/2]

◆ is_transverse_block() [2/2]

◆ is_transverse_block_no_checks() [1/2]

◆ is_transverse_block_no_checks() [2/2]

◆ lookup()

◆ number_of_blocks()

◆ operator!=()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]()

◆ rank()