Defined in bipart.hpp.

A bipartition is a partition of the set \(\{0, ..., 2n - 1\}\) for some non-negative integer \(n\); see the Semigroups package for GAP documentation for more details. The Bipartition class is more complex (i.e. has more member functions) than are used in libsemigroups because they are used in the Semigroups package for GAP (see [45]).

See also: bipartition::throw_if_invalid(Bipartition const&).

Public Types
using	const_iterator = std::vector<uint32_t>::const_iterator
	Type of const iterators pointing to block lookup.

using	iterator = std::vector<uint32_t>::iterator
	Type of iterators pointing to block lookup.

using	lookup_const_iterator = typename std::vector<bool>::const_iterator
	Type of const iterators pointing to transverse blocks lookup.

Public Member Functions
	Bipartition ()
	Construct an uninitialised bipartition of degree `0`.

	Bipartition (Bipartition &&)
	Default move constructor.

	Bipartition (Bipartition const &)
	Default copy constructor.

	Bipartition (size_t N)
	Construct an uninitialised bipartition of given degree.

	Bipartition (std::initializer_list< std::vector< int32_t > > const &blocks)
	Construct a bipartition from a partition.

	Bipartition (std::initializer_list< uint32_t > const &blocks)
	Construct a bipartition from an initializer list blocks lookup.

	Bipartition (std::vector< std::vector< int32_t > > const &blocks)
	Construct a bipartition from a partition.

	Bipartition (std::vector< uint32_t > &&blocks)
	Construct a bipartition from an rvalue reference to blocks lookup.

	Bipartition (std::vector< uint32_t > const &blocks)
	Construct a bipartition from a const reference to blocks lookup.

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

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

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

const_iterator	cbegin_left_blocks () const noexcept
	Const iterator pointing to the index of the first left block.

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

const_iterator	cbegin_right_blocks () const noexcept
	Const iterator pointing to the index of the first right block.

const_iterator	cend () const noexcept
	Return a const iterator pointing one beyond the last index of the last block.

const_iterator	cend_left_blocks () const noexcept
	Const iterator pointing one beyond the last index of the last left block.

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

const_iterator	cend_right_blocks () const noexcept
	Const iterator pointing one beyond the last index of the last right block.

size_t	degree () const noexcept
	Return the degree of the bipartition.

size_t	hash_value () const
	Return a hash value.

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

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

Blocks *	left_blocks () const
	Return a pointer to the left blocks of a bipartition.

Blocks *	left_blocks_no_checks () const
	Return a pointer to the left blocks of a bipartition.

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

uint32_t	number_of_blocks () const
	Return the number of blocks in a Bipartition.

uint32_t	number_of_left_blocks () const
	Return the number of blocks containing a positive integer.

uint32_t	number_of_right_blocks () const
	Return the number of blocks containing a negative integer.

bool	operator< (Bipartition const &that) const
	Compare bipartitions for less.

Bipartition &	operator= (Bipartition &&)
	Default move assignment operator.

Bipartition &	operator= (Bipartition const &)
	Default copy assignment operator.

bool	operator== (Bipartition const &that) const
	Compare bipartitions for equality.

uint32_t &	operator[] (size_t i)
	Return the index of the block containing a value.

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

void	product_inplace_no_checks (Bipartition const &x, Bipartition const &y, size_t thread_id=0)
	Modify the current bipartition in-place to contain the product of two bipartitions.

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

Blocks *	right_blocks () const
	Return a pointer to the right blocks of a bipartition.

Blocks *	right_blocks_no_checks () const
	Return a pointer to the right blocks of a bipartition.

void	set_number_of_blocks (size_t n) noexcept
	Set the number of blocks.

void	set_number_of_left_blocks (size_t n) noexcept
	Set the number of left blocks.

void	set_rank (size_t n) noexcept
	Set the rank.

Static Public Member Functions
static Bipartition	one (size_t n)
	Return an identity bipartition of given degree.

Member Typedef Documentation

◆ const_iterator

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

Type for const iterators pointing to the lookup for the blocks of a bipartition.

◆ iterator

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

Type for iterators pointing to the lookup for the blocks of a bipartition.

◆ lookup_const_iterator

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

Type for iterators pointing to the lookup for transverse blocks of a bipartition.

Constructor & Destructor Documentation

◆ Bipartition() [1/9]

Bipartition ( )

Constructs an uninitialised bipartition of degree 0.

◆ Bipartition() [2/9]

Bipartition ( size_t N )

explicit

Constructs a bipartition of degree N that is uninitialised.

Parameters

N	the degree of the bipartition.

◆ Bipartition() [3/9]

Bipartition ( std::vector< uint32_t > const & blocks )

explicit

The parameter blocks:

is copied;
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. The value of blocks[i] should represent the index of the block containing i.

None of these conditions are verified.

For example, if blocks is {0, 1, 1, 2, 1, 1, 3, 1, 1, 4, 5, 6}, then the above conditions are satisfied, but if blocks is {1, 0, 1, 10} then they are not.

Parameters

blocks a lookup for the blocks of the bipartition being constructed.

See also: bipartition::throw_if_invalid(Bipartition const&).

◆ Bipartition() [4/9]

Bipartition ( std::vector< uint32_t > && blocks )

explicit

Parameters

blocks a lookup for the blocks of the bipartition being constructed.

See also: Bipartition(std::vector<uint32_t> const&) and bipartition::throw_if_invalid(Bipartition const&).

◆ Bipartition() [5/9]

Bipartition ( std::initializer_list< uint32_t > const & blocks )

Parameters

blocks a lookup for the blocks of the bipartition being constructed.

See also: Bipartition(std::vector<uint32_t> const&) and bipartition::throw_if_invalid(Bipartition const&).

◆ Bipartition() [6/9]

Bipartition ( std::initializer_list< std::vector< int32_t > > const & blocks )

The items in blocks should be:

duplicate-free;
pairwise disjoint; and
partition the set \(\{-n, \ldots, -1, 1, \ldots, n\}\) for some positive integer \(n\).

Parameters

blocks the partition.

Warning: None of these conditions is checked by the constructor.

See also: bipartition::throw_if_invalid(Bipartition const&).

◆ Bipartition() [7/9]

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

explicit

The items in blocks should be:

duplicate-free;
pairwise disjoint; and
partition the set \(\{-n, \ldots, -1, 1, \ldots, n\}\) for some positive integer \(n\).

Parameters

blocks the partition.

Warning: None of these conditions is checked by the constructor.

See also: bipartition::throw_if_invalid(Bipartition const&).

◆ Bipartition() [8/9]

Bipartition ( Bipartition const & )

Default copy constructor.

◆ Bipartition() [9/9]

Bipartition ( Bipartition && )

Default move constructor.

Member Function Documentation

◆ at() [1/2]

uint32_t & at ( size_t i )

inlinenodiscard

Returns a reference to the index of the block containing a value.

Parameters

i	an integer.

Returns: A reference to the index of the block containing i.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Exceptions

std::out_of_range if the parameter i is out of range.

Complexity: Constant.

◆ at() [2/2]

uint32_t const & at ( size_t i ) const

inlinenodiscard

Returns a const reference to the index of the block containing a value.

Parameters

i	an integer.

Returns: A const reference to the index of the block containing i.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Exceptions

std::out_of_range if the parameter i is out of range.

Complexity: Constant.

◆ cbegin()

const_iterator cbegin ( ) const

inlinenodiscardnoexcept

Returns a const iterator pointing to the index of the first block.

Returns: A value of type const_iterator.

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

Complexity: Constant.

◆ cbegin_left_blocks()

const_iterator cbegin_left_blocks ( ) const

inlinenodiscardnoexcept

Returns a const iterator pointing to the index of the first left block.

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.

◆ cbegin_right_blocks()

const_iterator cbegin_right_blocks ( ) const

inlinenodiscardnoexcept

Returns a const iterator pointing to the index of the first right block.

Returns: A value of type const_iterator.

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

Complexity: Constant.

◆ cend()

const_iterator cend ( ) const

inlinenodiscardnoexcept

Returns a const iterator pointing one beyond the last index of the last block.

Returns: A value of type const_iterator.

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

Complexity: Constant.

◆ cend_left_blocks()

const_iterator cend_left_blocks ( ) const

inlinenodiscardnoexcept

Returns a const iterator pointing one beyond the last index of the last left block.

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.

◆ cend_right_blocks()

const_iterator cend_right_blocks ( ) const

inlinenodiscardnoexcept

Returns a const iterator pointing one beyond the last index of the last right block.

Returns: A value of type const_iterator.

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

Complexity: Constant.

◆ degree()

size_t degree ( ) const

nodiscardnoexcept

Returns the degree of the bipartition.

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

Returns: A value of type size_t.

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

◆ hash_value()

size_t hash_value ( ) const

inlinenodiscard

Returns a hash value for a Bipartition object.

Returns: A value of size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Linear in degree().

◆ is_transverse_block()

bool is_transverse_block ( size_t index ) const

nodiscard

A block of a biparition is transverse if it contains integers less than and greater than \(n\), which is the degree of the bipartition.

Parameters

index the index of a block.

Returns: Whether or not the given block is transverse.

Exceptions

LibsemigroupsException if index is not in the range from 0 to number_of_left_blocks.

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

◆ is_transverse_block_no_checks()

bool is_transverse_block_no_checks ( size_t index ) const

nodiscard

A block of a biparition is transverse if it contains integers less than and greater than \(n\), which is the degree of the bipartition.

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: At worst \(O(n)\) where \(n\) is the degree().

Warning: This function does no checks on its arguments.

◆ left_blocks()

Blocks * left_blocks ( ) const

nodiscard

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

Returns: A pointer to a newly constructed Blocks object.

Exceptions

LibsemigroupsException if this is not valid.

Complexity: \(O(n)\) where \(n\) is the degree().

◆ left_blocks_no_checks()

Blocks * left_blocks_no_checks ( ) const

nodiscard

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

Returns: A pointer to a newly constructed Blocks object.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(n)\) where \(n\) is the degree().

◆ 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

nodiscard

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

Returns: The number of blocks.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ number_of_left_blocks()

uint32_t number_of_left_blocks ( ) const

nodiscard

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

Returns: A value of type uint32_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ number_of_right_blocks()

uint32_t number_of_right_blocks ( ) const

nodiscard

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

Returns: A value of type uint32_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ one()

static Bipartition one ( size_t n )

staticnodiscard

Returns an identity bipartition of degree n.

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

Parameters

n	the degree of the identity to be returned.

Returns: A newly constructed Bipartition.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ operator<()

bool operator< ( Bipartition const & that ) const

inlinenodiscard

This operator defines a total order on Bipartition objects. It is ok to compare Bipartition objects of different degrees.

Parameters

that	the Bipartition for comparison.

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

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst linear in degree().

◆ operator=() [1/2]

Bipartition & operator= ( Bipartition && )

Default move assignment operator.

◆ operator=() [2/2]

Bipartition & operator= ( Bipartition const & )

Default copy assignment operator.

◆ operator==()

bool operator== ( Bipartition const & that ) const

inlinenodiscard

Parameters

that	the Bipartition 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[]() [1/2]

uint32_t & operator[] ( size_t i )

inlinenodiscard

Returns the index of the block containing a value. No bound checks are performed on the parameter i.

Parameters

i	an integer.

Returns: A reference to the index of the block containing i.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

◆ operator[]() [2/2]

uint32_t const & operator[] ( size_t i ) const

inlinenodiscard

Returns the index of the block containing a value.

No bound checks are performed on the parameter i.

Parameters

i	an integer.

Returns: A const reference to the index of the block containing i.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

◆ product_inplace_no_checks()

void product_inplace_no_checks	(	Bipartition const &	x,
		Bipartition const &	y,
		size_t	thread_id = 0 )

The parameter thread_id can be used some temporary storage is required to find the product of x and y.

Parameters

x	the first bipartition to multiply.
y	the second bipartition to multiply.
thread_id	the index of the calling thread (defaults to `0`).

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Quadratic in x.degree().

Warning: If different threads call this function concurrently with the same parameter thread_id, then bad things will happen.; This function expects its arguments to have equal degree, but this is not checked.

◆ rank()

size_t rank ( ) const

nodiscard

The rank of a bipartition is the number of blocks containing both positive and negative values, which are referred to as the transverse blocks.

Returns: The number of transverse blocks.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

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

◆ right_blocks()

Blocks * right_blocks ( ) const

nodiscard

The right blocks of a bipartition is the partition of \(\{n, \ldots, 2n - 1\}\) induced by the bipartition.

Returns: A pointer to a newly constructed Blocks object.

Exceptions

LibsemigroupsException if this is not valid.

Complexity: \(O(n)\) where \(n\) is the degree().

◆ right_blocks_no_checks()

Blocks * right_blocks_no_checks ( ) const

nodiscard

The right blocks of a bipartition is the partition of \(\{n, \ldots, 2n - 1\}\) induced by the bipartition.

Returns: A pointer to a newly constructed Blocks object.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(n)\) where \(n\) is the degree().

◆ set_number_of_blocks()

void set_number_of_blocks ( size_t n )

noexcept

This function sets the number of blocks of this to n. No checks are performed.

Parameters

n	the number of blocks.

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

Complexity: Constant.

◆ set_number_of_left_blocks()

void set_number_of_left_blocks ( size_t n )

noexcept

This function sets the number of left blocks of this to n. No checks are performed.

Parameters

n	the number of blocks.

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

Complexity: Constant.

◆ set_rank()

void set_rank ( size_t n )

noexcept

This function sets the rank of this to n. No checks are performed.

Parameters

n the rank.

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

Complexity: Constant.

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

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

Public Types

Public Member Functions

Static Public Member Functions

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ lookup_const_iterator

Constructor & Destructor Documentation

◆ Bipartition() [1/9]

◆ Bipartition() [2/9]

◆ Bipartition() [3/9]

◆ Bipartition() [4/9]

◆ Bipartition() [5/9]

◆ Bipartition() [6/9]

◆ Bipartition() [7/9]

◆ Bipartition() [8/9]

◆ Bipartition() [9/9]

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ cbegin()

◆ cbegin_left_blocks()

◆ cbegin_lookup()

◆ cbegin_right_blocks()

◆ cend()

◆ cend_left_blocks()

◆ cend_lookup()

◆ cend_right_blocks()

◆ degree()

◆ hash_value()

◆ is_transverse_block()

◆ is_transverse_block_no_checks()

◆ left_blocks()

◆ left_blocks_no_checks()

◆ lookup()

◆ number_of_blocks()

◆ number_of_left_blocks()

◆ number_of_right_blocks()

◆ one()

◆ operator<()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ product_inplace_no_checks()

◆ rank()

◆ right_blocks()

◆ right_blocks_no_checks()

◆ set_number_of_blocks()

◆ set_number_of_left_blocks()

◆ set_rank()