Blocks

Declared in blocks.hpp.

This file contains the documentation for the Blocks class. Blocks is a class representing signed partitions of the set \(\{0, \ldots, n - 1\}\), for use with Bipartition.

Full API

class libsemigroups::Blocks

Blocks is a class representing signed partitions of the set \(\{0, \ldots, n - 1\}\).

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 by any of the functions for the FroidurePin class but the extra functions are used in the GAP package Semigroups package for GAP.

Public Functions

Blocks() noexcept

Constructs a blocks object of size 0.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

Blocks(std::vector<uint32_t> *blocks, std::vector<bool> *lookup, uint32_t nr_blocks) noexcept

This constructor is provided for the situation where the number of blocks in blocks is known a priori and so does not need to be calculated in the constructor.

Return

A Blocks object.

Exceptions

This function noexcept and is guaranteed never to throw, the caller is responsible for the validity of the arguments.

Complexity

Constant.

Parameters
  • blocks: must have length \(n\) for some integer \(n > 0\), 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 is deleted by the destructor Blocks::~Blocks.

  • lookup: must have length equal to the number of different values in blocks (or one more than the maximum value in the list); this is equal to the number of blocks in the partition. A value true in position \(i\) indicates that the \(i\)th block is signed (transverse) and false that it is unsigned.

  • nr_blocks: must be the number of blocks (i.e. one more than the maximum value in blocks).

Blocks(std::vector<uint32_t> *blocks, std::vector<bool> *lookup)

Construct a blocks object.

Exceptions

This function throws if std::max_element throws, the caller is responsible for the validity of the arguments.

Complexity

Linear in blocks->size().

Parameters
  • blocks: must be non-empty, consist of non-negative integers, and have the property that if some positive \(i\) occurs in blocks, then \(i - 1\) occurs earlier in blocks. None of this is checked. The parameter blocks is not copied, and is deleted by the destructor Blocks::~Blocks.

  • lookup: must have length equal to the number of different values in blocks (or one more than the maximum value in the list); this is equal to the number of blocks in the partition. A value true in position \(i\) indicates that the \(i\)th block is signed (transverse) and false that it is unsigned.

Blocks &operator=(Blocks const&) = delete

The assignment operator is deleted for Blocks to avoid unintended copying.

Blocks(Blocks const &copy)

Copy construct a Blocks object.

~Blocks()

Deletes the blocks and lookup provided at construction time.

bool operator==(Blocks const &that) const

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.

Return

true if this equals that.

Exceptions

This function only throws if std::vector::operator== does.

Complexity

Linear in degree().

Parameters

bool operator<(Blocks const &that) const

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

Return

true if this is less than that.

Exceptions

This function only throws if std::vector::operator[] does.

Complexity

Linear in degree().

Parameters

uint32_t degree() const noexcept

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.

Return

The degree of a Blocks object.

Exceptions

This function is noexcept and is guaranteed never to throw.

Parameters

(None)

uint32_t block(size_t pos) const noexcept

Return

The index of the block containing pos.

Exceptions

This function is noexcept and is guaranteed never to throw, the caller is responsible for the validity of the arguments.

Complexity

Constant.

Parameters
  • pos: the integer whose block index is sought.

bool is_transverse_block(size_t index) const noexcept

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).

Return

true if the block with index index is transverse, and false if not.

Exceptions

This function is noexcept and is guaranteed never to throw, the caller is responsible for the validity of the arguments.

Complexity

Constant.

Parameters
  • index: the index of a block

std::vector<bool> const *lookup() const noexcept

The vector pointed to by the return value of this function has value true in position i if the i th block of this is a transverse block; the entry in position i is false otherwise.

Return

A pointer to the lookup table for block indices.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

uint32_t nr_blocks() const noexcept

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

Return

The number of blocks in a Blocks object.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

uint32_t rank()

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

Return

The number of signed (transverse) blocks in this.

Exceptions

Throws if std::count throws.

Complexity

At most linear in lookup()->size()

Parameters

(None)

size_t hash_value() const noexcept

This function returns a hash value for an instance of Blocks.

This value is recomputed every time this function is called.

Return

A hash value for a this.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Linear in degree().

Parameters

(None)

std::vector<uint32_t>::const_iterator cbegin() const noexcept

Return

A const_iterator pointing to the index of the first block.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

std::vector<uint32_t>::const_iterator cend() const noexcept

Return

A const_iterator referring to past-the-end of the last block.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)