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
-
inline 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.
- 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 inblocks
. None of this is checked. The parameterblocks
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 valuetrue
in position \(i\) indicates that the \(i\)th block is signed (transverse) andfalse
that it is unsigned.nr_blocks – must be the number of blocks (i.e. one more than the maximum value in
blocks
).
- Returns
A Blocks object.
-
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 inblocks
. None of this is checked. The parameterblocks
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 valuetrue
in position \(i\) indicates that the \(i\)th block is signed (transverse) andfalse
that it is unsigned.
-
Blocks &operator=(Blocks const&) = delete¶
The assignment operator is deleted for Blocks to avoid unintended copying.
-
inline ~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.
- Exceptions
This function only throws if std::vector::operator== does.
- Complexity
Linear in
degree()
.
- Parameters
that – a Blocks instance
- Returns
true
ifthis
equalsthat
.
-
bool operator<(Blocks const &that) const¶
This operator defines a total order on the set of all Blocks objects (including those of different degree).
- Exceptions
This function only throws if std::vector::operator[] does.
- Complexity
Linear in
degree()
.
- Parameters
that – a Blocks instance
- Returns
true
ifthis
is less thanthat
.
-
inline 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.- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Parameters
(None)
- Returns
The degree of a Blocks object.
-
inline uint32_t block(size_t pos) const noexcept¶
- 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.
- Returns
The index of the block containing
pos
.
-
inline bool is_transverse_block(size_t index) const noexcept¶
This function returns
true
if the block with indexindex
is a transverse (or signed) block and it returnsfalse
if it is not transverse (or unsigned).- 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
- Returns
true
if the block with indexindex
is transverse, andfalse
if not.
-
inline std::vector<bool> const *lookup() const noexcept¶
The vector pointed to by the return value of this function has value
true
in positioni
if thei
th block ofthis
is a transverse block; the entry in positioni
isfalse
otherwise.- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
- Parameters
(None)
- Returns
A pointer to the lookup table for block indices.
-
inline uint32_t nr_blocks() const noexcept¶
This function returns the number of parts in the partition that instances of this class represent.
- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
- Parameters
(None)
- Returns
The number of blocks in a Blocks object.
-
uint32_t rank()¶
This function returns the number of
true
values in Blocks::lookup().- Exceptions
Throws if
std::count
throws.- Complexity
At most linear in
lookup()->size()
- Parameters
(None)
- Returns
The number of signed (transverse) blocks in
this
.
-
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.
- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Linear in
degree()
.- Parameters
(None)
- Returns
A hash value for a
this
.
-
inline std::vector<uint32_t>::const_iterator cbegin() const noexcept¶
- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
- Parameters
(None)
- Returns
A
const_iterator
pointing to the index of the first block.
-
inline std::vector<uint32_t>::const_iterator cend() const noexcept¶
- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
- Parameters
(None)
- Returns
A
const_iterator
referring to past-the-end of the last block.
-
inline Blocks() noexcept¶