21#ifndef LIBSEMIGROUPS_BIPART_HPP_
22#define LIBSEMIGROUPS_BIPART_HPP_
33#include <initializer_list>
36#include <unordered_set>
39#include "adapters.hpp"
41#include "exception.hpp"
44#include "detail/fmt.hpp"
178 template <
typename Thing>
180 = std::is_same_v<std::decay_t<Thing>,
Bipartition>;
185 template <
typename Thing,
typename Scalar>
188 static_assert(std::is_same_v<Thing, Bipartition>
189 || std::is_same_v<Thing, Blocks>);
191 "the 2nd template parameter Scalar must be signed");
193 if (!std::is_same_v<Thing, Bipartition>) {
199 for (
size_t i = 0; i <
blocks.size(); ++i) {
200 auto const& block =
blocks[i];
203 "expected all blocks to be non-empty, but "
204 "found empty block in position {}",
207 bool positive = block[0] >= 0;
209 for (
size_t j = 0; j < block.size(); ++j) {
214 "expected non-zero values but found 0 in "
215 "position {} of the block with index {}",
218 }
else if (!std::is_same_v<Thing, Bipartition> && positive && x < 0) {
220 "the argument (blocks) is invalid, expected every value in the "
221 "block with index {} to be {}tive, but found {} in position {}",
223 positive ?
"posi" :
"nega",
234 if (m >=
static_cast<int32_t
>(0x40000000)) {
236 "too many points, expected at most {}, found {}", 0x40000000, m);
237 }
else if (deg != offset * m || vals.
size() !=
size_t(deg)) {
239 if (std::is_same_v<Thing, Bipartition>) {
240 prefix =
"the union of";
241 range = fmt::format(
"{{{}, ..., -1, 1, ..., {}}}", -m, m);
244 =
"the set consisting of the absolute values of the entries in ";
245 range = fmt::format(
"[1, {}]", m);
248 " only {} values were given",
256 template <
typename Thing,
typename Scalar>
257 static void throw_if_bad_args(
260 throw_if_bad_args<Thing>(arg);
264 template <
typename Thing,
typename Scalar>
270 template <
typename Thing,
typename Scalar>
418 LIBSEMIGROUPS_ASSERT(i < _lookup.size());
437 throw_if_class_index_out_of_range(i);
460 LIBSEMIGROUPS_ASSERT(index < _lookup.size());
461 return _lookup[index];
480 throw_if_class_index_out_of_range(index);
533 return _blocks == that._blocks && _lookup == that._lookup;
552 return !(*
this == that);
583 [[nodiscard]] uint32_t
degree() const noexcept {
584 return _blocks.size();
600 return _lookup.size();
615 [[nodiscard]] uint32_t
rank()
const;
644 return _lookup.cbegin();
652 return _lookup.cend();
683 return _blocks.cbegin();
697 return _blocks.cend();
713 LIBSEMIGROUPS_ASSERT(i < _blocks.size());
728 [[nodiscard]] uint32_t
const&
at(
size_t i)
const {
730 return _blocks.at(i);
734 void throw_if_class_index_out_of_range(
size_t index)
const;
789 template <
typename Return,
typename Container>
791 detail::throw_if_bad_args<Blocks>(cont);
812 template <
typename Return>
836 std::string_view braces
838 size_t max_width = 72);
859 mutable size_t _nr_blocks;
860 mutable size_t _nr_left_blocks;
862 mutable size_t _rank;
990 return _vector == that._vector;
1008 return _vector < that._vector;
1082 [[nodiscard]] uint32_t&
at(
size_t i) {
1083 return _vector.at(i);
1103 [[nodiscard]] uint32_t
const&
at(
size_t i)
const {
1104 return _vector.at(i);
1120 return _vector.cbegin();
1137 return _vector.cend();
1219 [[nodiscard]]
size_t degree() const noexcept;
1261 size_t thread_id = 0);
1476 init_trans_blocks_lookup();
1477 return _trans_blocks_lookup.cbegin();
1485 init_trans_blocks_lookup();
1486 return _trans_blocks_lookup.cend();
1503 return _trans_blocks_lookup;
1507 void init_trans_blocks_lookup()
const;
1537 template <
typename Return,
typename Container>
1540 detail::throw_if_bad_args<Bipartition>(cont);
1551 template <
typename Return>
1560 template <
typename Return>
1586 std::string_view braces
1588 size_t max_width = 72);
1641 return x < y || x == y;
1690 return x.degree() * x.degree();
1695 struct Degree<Bipartition> {
1696 [[nodiscard]]
size_t operator()(Bipartition
const& x)
const noexcept {
1703 [[nodiscard]]
size_t operator()(Bipartition
const& x)
const {
1710 [[nodiscard]] Bipartition operator()(Bipartition
const& x)
const {
1711 return (*
this)(x.degree());
1714 [[nodiscard]] Bipartition operator()(
size_t N = 0)
const {
1721 void operator()(Bipartition& xy,
1722 Bipartition
const& x,
1723 Bipartition
const& y,
1724 size_t thread_id = 0) {
1731 void operator()(Bipartition&,
size_t) {}
Class for representing bipartitions.
Definition bipart.hpp:857
size_t rank() const
Return the number of transverse blocks.
Bipartition(std::vector< std::vector< int32_t > > const &blocks)
Construct a bipartition from a partition.
bool operator<(Bipartition const &that) const
Compare bipartitions for less.
Definition bipart.hpp:1007
void set_number_of_left_blocks(size_t n) noexcept
Set the number of left blocks.
uint32_t & operator[](size_t i)
Return the index of the block containing a value.
Definition bipart.hpp:1044
uint32_t number_of_blocks() const
Return the number of blocks in a Bipartition.
typename std::vector< bool >::const_iterator lookup_const_iterator
Type of const iterators pointing to transverse blocks lookup.
Definition bipart.hpp:882
Bipartition(std::vector< uint32_t > const &blocks)
Construct a bipartition from a const reference to blocks lookup.
std::vector< uint32_t >::const_iterator const_iterator
Type of const iterators pointing to block lookup.
Definition bipart.hpp:876
Blocks * left_blocks_no_checks() const
Return a pointer to the left blocks of a bipartition.
Blocks * right_blocks() const
Return a pointer to the right blocks of a bipartition.
uint32_t const & operator[](size_t i) const
Return the index of the block containing a value.
Definition bipart.hpp:1063
Blocks * left_blocks() const
Return a pointer to the left blocks of a bipartition.
Bipartition & operator=(Bipartition const &)
Default copy assignment operator.
uint32_t number_of_right_blocks() const
Return the number of blocks containing a negative integer.
size_t degree() const noexcept
Return the degree of the bipartition.
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.
Bipartition()
Construct an uninitialised bipartition of degree 0.
void set_number_of_blocks(size_t n) noexcept
Set the number of blocks.
const_iterator cend_right_blocks() const noexcept
Const iterator pointing one beyond the last index of the last right block.
Definition bipart.hpp:1204
void set_rank(size_t n) noexcept
Set the rank.
bool is_transverse_block(size_t index) const
Check if a block is a transverse block.
uint32_t number_of_left_blocks() const
Return the number of blocks containing a positive integer.
lookup_const_iterator cend_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:1484
std::vector< uint32_t >::iterator iterator
Type of iterators pointing to block lookup.
Definition bipart.hpp:870
bool operator==(Bipartition const &that) const
Compare bipartitions for equality.
Definition bipart.hpp:989
std::vector< bool > const & lookup() const noexcept
Return a const reference to the transverse blocks lookup.
Definition bipart.hpp:1502
const_iterator cbegin_left_blocks() const noexcept
Const iterator pointing to the index of the first left block.
Definition bipart.hpp:1153
const_iterator cend() const noexcept
Return a const iterator pointing one beyond the last index of the last block.
Definition bipart.hpp:1136
bool is_transverse_block_no_checks(size_t index) const
Check if a block is a transverse block.
Bipartition(Bipartition &&)
Default move constructor.
const_iterator cend_left_blocks() const noexcept
Const iterator pointing one beyond the last index of the last left block.
Definition bipart.hpp:1170
uint32_t const & at(size_t i) const
Return a const reference to the index of the block containing a value.
Definition bipart.hpp:1103
lookup_const_iterator cbegin_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:1475
Bipartition(size_t N)
Construct an uninitialised bipartition of given degree.
Bipartition(std::initializer_list< uint32_t > const &blocks)
Construct a bipartition from an initializer list blocks lookup.
const_iterator cbegin() const noexcept
Return a const iterator pointing to the index of the first block.
Definition bipart.hpp:1119
static Bipartition one(size_t n)
Return an identity bipartition of given degree.
Bipartition & operator=(Bipartition &&)
Default move assignment operator.
Bipartition(Bipartition const &)
Default copy constructor.
Bipartition(std::vector< uint32_t > &&blocks)
Construct a bipartition from an rvalue reference to blocks lookup.
size_t hash_value() const
Return a hash value.
Definition bipart.hpp:1026
const_iterator cbegin_right_blocks() const noexcept
Const iterator pointing to the index of the first right block.
Definition bipart.hpp:1187
Bipartition(std::initializer_list< std::vector< int32_t > > const &blocks)
Construct a bipartition from a partition.
uint32_t & at(size_t i)
Return a reference to the index of the block containing a value.
Definition bipart.hpp:1082
Blocks * right_blocks_no_checks() const
Return a pointer to the right blocks of a bipartition.
A Blocks object represents a signed partition of the set .
Definition bipart.hpp:293
Blocks & operator=(Blocks const &)
Default copy assignment operator.
bool operator==(Blocks const &that) const
Compare two blocks objects for equality.
Definition bipart.hpp:532
Blocks(std::vector< std::vector< int32_t > > const &blocks)
Constructs a Blocks object from a vector of vectors of integers.
uint32_t const & operator[](size_t i) const
Return a const reference to the index of the block containing a point.
Definition bipart.hpp:712
Blocks & block_no_checks(size_t i, uint32_t val)
Set the block that a point belongs to.
Blocks & operator=(Blocks &&)
Default move assignment operator.
Blocks() noexcept
Constructs a blocks object of size 0.
bool is_transverse_block(size_t index) const
Check if a block is a transverse block.
Definition bipart.hpp:479
typename std::vector< uint32_t >::iterator iterator
Type for iterators pointing to the index of the block.
Definition bipart.hpp:307
lookup_const_iterator cend_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:651
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.
Definition bipart.hpp:436
std::vector< bool > const & lookup() const noexcept
Return a const reference to the transverse blocks lookup.
Definition bipart.hpp:668
const_iterator cend() const noexcept
Return a const iterator pointing one past-the-end of the last block.
Definition bipart.hpp:696
std::vector< bool >::const_iterator lookup_const_iterator
Type for const iterators pointing to the transverse block lookup.
Definition bipart.hpp:302
bool is_transverse_block_no_checks(size_t index) const
Check if a block is a transverse block.
Definition bipart.hpp:459
bool operator<(Blocks const &that) const
Compare two blocks objects for less.
Blocks & is_transverse_block_no_checks(size_t i, bool val)
Set whether or not the block containing a point is transverse.
Definition bipart.hpp:417
uint32_t const & at(size_t i) const
Return a const reference to the index of the block containing a point.
Definition bipart.hpp:728
lookup_const_iterator cbegin_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:643
Blocks(Blocks const ©)
Default copy constructor.
const_iterator cbegin() const noexcept
Return a const iterator pointing to the index of the first block.
Definition bipart.hpp:682
uint32_t rank() const
Return the number of transverse blocks.
uint32_t number_of_blocks() const noexcept
Return the number of blocks in a Blocks object.
Definition bipart.hpp:599
bool operator!=(Blocks const &that) const
Compare two blocks objects for inequality.
Definition bipart.hpp:551
uint32_t degree() const noexcept
Return the degree of a blocks object.
Definition bipart.hpp:583
Blocks(Blocks &©)
Default move constructor.
typename std::vector< uint32_t >::const_iterator const_iterator
Type for const iterators pointing to the index of the block.
Definition bipart.hpp:312
Blocks & block(size_t i, uint32_t val)
Set the block that a point belongs to.
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
bool operator<=(Bipartition const &x, Bipartition const &y)
Compare bipartitions.
Definition bipart.hpp:1639
bool operator>=(Bipartition const &x, Bipartition const &y)
Compare bipartitions.
Definition bipart.hpp:1661
bool operator>(Bipartition const &x, Bipartition const &y)
Compare bipartitions.
Definition bipart.hpp:1650
Bipartition operator*(Bipartition const &x, Bipartition const &y)
Multiply two bipartitions.
static constexpr bool IsBipartition
Helper variable template.
Definition bipart.hpp:180
bool operator!=(Bipartition const &x, Bipartition const &y)
Check bipartitions for inequality.
Definition bipart.hpp:1629
#define LIBSEMIGROUPS_EXCEPTION(...)
Throw a LibsemigroupsException.
Definition exception.hpp:99
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:790
std::enable_if_t< std::is_same_v< Given, Expected >, Expected > enable_if_is_same
Alias equal to the second template parameter if both template parameters are equal.
Definition types.hpp:48
Namespace for Bipartition helper functions.
Definition bipart.hpp:118
std::vector< std::vector< int32_t > > underlying_partition(Bipartition const &x)
Return the underlying partition of a Bipartition object.
Bipartition one(Bipartition const &f)
Return the identity bipartition with the same degree as the given bipartition.
void throw_if_invalid(Bipartition const &x)
Checks a bipartition.
Namespace for Blocks helper functions.
Definition bipart.hpp:67
void throw_if_invalid(Blocks const &x)
Check a Blocks object.
std::vector< std::vector< int32_t > > underlying_partition(Blocks const &x)
Return the underlying partition of a Blocks object.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
size_t operator()(Bipartition const &x) const noexcept
Definition bipart.hpp:1689
Adapter for the complexity of multiplication.
Definition adapters.hpp:121
Adapter for hashing.
Definition adapters.hpp:446
size_t operator()(Value const &x) const
Hash x using std::hash.
Definition adapters.hpp:455
Adapter for increasing the degree of an element.
Definition adapters.hpp:199
Adapter for the identity element of the given type.
Definition adapters.hpp:246
Adapter for the product of two elements.
Definition adapters.hpp:284