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"
243 template <
typename Thing>
245 = std::is_same_v<std::decay_t<Thing>,
Bipartition>;
250 template <
typename Thing,
typename Scalar>
253 static_assert(std::is_same_v<Thing, Bipartition>
254 || std::is_same_v<Thing, Blocks>);
256 "the 2nd template parameter Scalar must be signed");
258 if (!std::is_same_v<Thing, Bipartition>) {
264 for (
size_t i = 0; i <
blocks.size(); ++i) {
265 auto const& block =
blocks[i];
268 "expected all blocks to be non-empty, but "
269 "found empty block in position {}",
272 bool positive = block[0] >= 0;
274 for (
size_t j = 0; j < block.size(); ++j) {
279 "expected non-zero values but found 0 in "
280 "position {} of the block with index {}",
283 }
else if (!std::is_same_v<Thing, Bipartition> && positive && x < 0) {
285 "the argument (blocks) is invalid, expected every value in the "
286 "block with index {} to be {}tive, but found {} in position {}",
288 positive ?
"posi" :
"nega",
299 if (m >=
static_cast<int32_t
>(0x40000000)) {
301 "too many points, expected at most {}, found {}", 0x40000000, m);
302 }
else if (deg != offset * m || vals.
size() !=
size_t(deg)) {
304 if (std::is_same_v<Thing, Bipartition>) {
305 prefix =
"the union of";
306 range = fmt::format(
"{{{}, ..., -1, 1, ..., {}}}", -m, m);
309 =
"the set consisting of the absolute values of the entries in ";
310 range = fmt::format(
"[1, {}]", m);
313 " only {} values were given",
321 template <
typename Thing,
typename Scalar>
322 static void throw_if_bad_args(
325 throw_if_bad_args<Thing>(arg);
329 template <
typename Thing,
typename Scalar>
335 template <
typename Thing,
typename Scalar>
483 LIBSEMIGROUPS_ASSERT(i < _lookup.size());
502 throw_if_class_index_out_of_range(i);
525 LIBSEMIGROUPS_ASSERT(index < _lookup.size());
526 return _lookup[index];
545 throw_if_class_index_out_of_range(index);
598 return _blocks == that._blocks && _lookup == that._lookup;
617 return !(*
this == that);
648 [[nodiscard]] uint32_t
degree() const noexcept {
649 return _blocks.size();
665 return _lookup.size();
680 [[nodiscard]] uint32_t
rank()
const;
709 return _lookup.cbegin();
717 return _lookup.cend();
748 return _blocks.cbegin();
762 return _blocks.cend();
778 LIBSEMIGROUPS_ASSERT(i < _blocks.size());
793 [[nodiscard]] uint32_t
const&
at(
size_t i)
const {
795 return _blocks.at(i);
799 void throw_if_class_index_out_of_range(
size_t index)
const;
854 template <
typename Return,
typename Container>
856 detail::throw_if_bad_args<Blocks>(cont);
877 template <
typename Return>
901 std::string_view braces
903 size_t max_width = 72);
924 mutable size_t _nr_blocks;
925 mutable size_t _nr_left_blocks;
927 mutable size_t _rank;
1055 return _vector == that._vector;
1073 return _vector < that._vector;
1147 [[nodiscard]] uint32_t&
at(
size_t i) {
1148 return _vector.at(i);
1168 [[nodiscard]] uint32_t
const&
at(
size_t i)
const {
1169 return _vector.at(i);
1185 return _vector.cbegin();
1200 return _vector.begin();
1217 return _vector.cend();
1234 return _vector.end();
1316 [[nodiscard]]
size_t degree() const noexcept;
1358 size_t thread_id = 0);
1573 init_trans_blocks_lookup();
1574 return _trans_blocks_lookup.cbegin();
1582 init_trans_blocks_lookup();
1583 return _trans_blocks_lookup.cend();
1600 return _trans_blocks_lookup;
1604 void init_trans_blocks_lookup()
const;
1634 template <
typename Return,
typename Container>
1637 detail::throw_if_bad_args<Bipartition>(cont);
1648 template <
typename Return>
1657 template <
typename Return>
1683 std::string_view braces
1685 size_t max_width = 72);
1738 return x < y || x == y;
1787 return x.degree() * x.degree();
1792 struct Degree<Bipartition> {
1793 [[nodiscard]]
size_t operator()(Bipartition
const& x)
const noexcept {
1800 [[nodiscard]]
size_t operator()(Bipartition
const& x)
const {
1807 [[nodiscard]] Bipartition operator()(Bipartition
const& x)
const {
1808 return (*
this)(x.degree());
1811 [[nodiscard]] Bipartition operator()(
size_t N = 0)
const {
1818 void operator()(Bipartition& xy,
1819 Bipartition
const& x,
1820 Bipartition
const& y,
1821 size_t thread_id = 0) {
1828 void operator()(Bipartition&,
size_t) {}
Class for representing bipartitions.
Definition bipart.hpp:922
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:1072
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:1109
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:947
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:941
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:1128
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:1301
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:1581
std::vector< uint32_t >::iterator iterator
Type of iterators pointing to block lookup.
Definition bipart.hpp:935
bool operator==(Bipartition const &that) const
Compare bipartitions for equality.
Definition bipart.hpp:1054
std::vector< bool > const & lookup() const noexcept
Return a const reference to the transverse blocks lookup.
Definition bipart.hpp:1599
const_iterator cbegin_left_blocks() const noexcept
Const iterator pointing to the index of the first left block.
Definition bipart.hpp:1250
iterator begin() noexcept
Return an iterator pointing to the index of the first block.
Definition bipart.hpp:1199
const_iterator cend() const noexcept
Return a const iterator pointing one beyond the last index of the last block.
Definition bipart.hpp:1216
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:1267
uint32_t const & at(size_t i) const
Return a const reference to the index of the block containing a value.
Definition bipart.hpp:1168
lookup_const_iterator cbegin_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:1572
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:1184
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:1091
const_iterator cbegin_right_blocks() const noexcept
Const iterator pointing to the index of the first right block.
Definition bipart.hpp:1284
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:1147
iterator end() noexcept
Return an iterator pointing one beyond the last index of the last block.
Definition bipart.hpp:1233
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:358
Blocks & operator=(Blocks const &)
Default copy assignment operator.
bool operator==(Blocks const &that) const
Compare two blocks objects for equality.
Definition bipart.hpp:597
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:777
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:544
typename std::vector< uint32_t >::iterator iterator
Type for iterators pointing to the index of the block.
Definition bipart.hpp:372
lookup_const_iterator cend_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:716
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:501
std::vector< bool > const & lookup() const noexcept
Return a const reference to the transverse blocks lookup.
Definition bipart.hpp:733
const_iterator cend() const noexcept
Return a const iterator pointing one past-the-end of the last block.
Definition bipart.hpp:761
std::vector< bool >::const_iterator lookup_const_iterator
Type for const iterators pointing to the transverse block lookup.
Definition bipart.hpp:367
bool is_transverse_block_no_checks(size_t index) const
Check if a block is a transverse block.
Definition bipart.hpp:524
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:482
uint32_t const & at(size_t i) const
Return a const reference to the index of the block containing a point.
Definition bipart.hpp:793
lookup_const_iterator cbegin_lookup() const noexcept
Return a const iterator pointing to the first transverse block lookup.
Definition bipart.hpp:708
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:747
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:664
bool operator!=(Blocks const &that) const
Compare two blocks objects for inequality.
Definition bipart.hpp:616
uint32_t degree() const noexcept
Return the degree of a blocks object.
Definition bipart.hpp:648
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:377
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:1736
bool operator>=(Bipartition const &x, Bipartition const &y)
Compare bipartitions.
Definition bipart.hpp:1758
bool operator>(Bipartition const &x, Bipartition const &y)
Compare bipartitions.
Definition bipart.hpp:1747
Bipartition operator*(Bipartition const &x, Bipartition const &y)
Multiply two bipartitions.
static constexpr bool IsBipartition
Helper variable template.
Definition bipart.hpp:245
bool operator!=(Bipartition const &x, Bipartition const &y)
Check bipartitions for inequality.
Definition bipart.hpp:1726
#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:855
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.
void uniform_random(Bipartition &x)
Replace the contents of a bipartition with a random bipartition.
void random(Bipartition &x)
Replace the contents of a bipartition with a random bipartition.
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:1786
Adapter for the complexity of multiplication.
Definition adapters.hpp:128
Adapter for hashing.
Definition adapters.hpp:453
size_t operator()(Value const &x) const
Hash x using std::hash.
Definition adapters.hpp:462
Adapter for increasing the degree of an element.
Definition adapters.hpp:206
Adapter for the identity element of the given type.
Definition adapters.hpp:253
Adapter for the product of two elements.
Definition adapters.hpp:291