22#ifndef LIBSEMIGROUPS_ACTION_HPP_
23#define LIBSEMIGROUPS_ACTION_HPP_
28#include <unordered_map>
32#include "adapters.hpp"
33#include "constants.hpp"
35#include "exception.hpp"
39#include "word-graph.hpp"
41#include "detail/bruidhinn-traits.hpp"
42#include "detail/report.hpp"
171 template <
typename Element,
181 using internal_point_type =
182 typename detail::BruidhinnTraits<Point>::internal_value_type;
183 using internal_const_point_type =
184 typename detail::BruidhinnTraits<Point>::internal_const_value_type;
185 using internal_const_reference =
186 typename detail::BruidhinnTraits<Point>::internal_const_reference;
188 struct InternalEqualTo :
private detail::BruidhinnTraits<Point> {
189 using EqualTo =
typename Traits::EqualTo;
190 bool operator()(internal_const_point_type x,
191 internal_const_point_type y)
const {
192 return EqualTo()(this->to_external_const(x),
193 this->to_external_const(y));
197 struct InternalHash :
private detail::BruidhinnTraits<Point> {
198 using Hash =
typename Traits::Hash;
199 size_t operator()(internal_const_point_type x)
const {
200 return Hash()(this->to_external_const(x));
204 using Degree =
typename Traits::Degree;
207 class MultiplierCache;
213 internal_const_point_type>::type>::value,
214 "internal_const_element_type must be const or pointer to const");
256 template <
typename Elment,
270 os << detail::to_string(action);
291 typename detail::BruidhinnTraits<Point>::const_reference;
298 typename detail::BruidhinnTraits<Point>::const_pointer;
305 using ActionOp = Func;
306 using One =
typename Traits::One;
307 using Product =
typename Traits::Product;
308 using Swap =
typename Traits::Swap;
311 "the 3rd template parameter Func is not trivially "
312 "default constructible");
343 MultiplierCache _multipliers_from_scc_root;
344 MultiplierCache _multipliers_to_scc_root;
347 internal_point_type _tmp_point;
348 bool _tmp_point_init;
447 throw_if_bad_degree(gen);
466 _gens.push_back(gen);
527 [[nodiscard]]
bool empty() const noexcept {
546 LIBSEMIGROUPS_ASSERT(pos < _orb.size());
547 return this->to_external_const(_orb[pos]);
564 return this->to_external_const(_orb.at(pos));
579 [[nodiscard]]
size_t size() {
637 [[nodiscard]]
auto range() const noexcept {
638 return rx::iterator_range(_orb.cbegin(), _orb.cend())
639 | rx::transform([
this](
auto const& pt) {
640 return this->to_external_const(pt);
687 return _options._cache_scc_multipliers;
707 _options._cache_scc_multipliers = val;
730 return multiplier_private<true>(
731 _multipliers_from_scc_root, _scc.spanning_forest(), pos);
753 return multiplier_private<false>(
754 _multipliers_to_scc_root, _scc.reverse_spanning_forest(), pos);
798 return this->to_external_const(_orb[_scc.root_of(pos)]);
855 ActionOp()(result, pt, x);
872 apply(result, pt, x);
881 [[nodiscard]]
bool finished_impl()
const override {
885 void run_impl()
override;
891 template <
bool Forward>
896 void throw_if_index_out_of_range(
index_type i)
const;
897 void throw_if_no_generators()
const;
909 template <
typename Element,
typename Po
int>
929 template <
typename Element,
939 template <
typename Element,
Class for generating the action of a semigroup.
Definition action.hpp:176
index_type position(const_reference_point_type pt) const
Returns the position of a point in the so far discovered points.
size_t size()
Returns the size of the fully enumerated action.
Definition action.hpp:578
auto range() const noexcept
Returns a range object containing the current points in the action.
Definition action.hpp:636
Action & init()
Initialize an existing Action object.
Action & operator=(Action const &)
Default copy assignment operator.
typename detail::BruidhinnTraits< Point >::const_reference const_reference_point_type
The type of a const reference to a point_type.
Definition action.hpp:289
const_iterator begin() const noexcept
Returns a const_iterator (random access iterator) pointing at the first point.
Definition action.hpp:618
friend std::ostringstream & operator<<(std::ostringstream &os, Action< Elment, Pint, Fnc, Trits, LftOrRight > const &action)
Insertion operator.
Action & add_generator_no_checks(element_type const &gen)
Add a generator to the action.
Definition action.hpp:464
bool empty() const noexcept
Checks if the Action contains any points.
Definition action.hpp:526
Func action_type
Type of the action of element_type on point_type.
Definition action.hpp:250
Element element_type
The template parameter Element.
Definition action.hpp:225
typename detail::BruidhinnTraits< Point >::const_pointer const_pointer_point_type
The type of a const pointer to a point_type.
Definition action.hpp:296
element_type multiplier_from_scc_root(index_type pos)
Returns a multiplier from a scc root to a given index.
Definition action.hpp:728
const_iterator end() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last point.
Definition action.hpp:663
Action & add_generator(element_type const &gen)
Add a generator to the action.
Definition action.hpp:445
element_type multiplier_to_scc_root(index_type pos)
Returns a multiplier from a given index to a scc root.
Definition action.hpp:751
size_t number_of_generators() const noexcept
Returns the number of generators.
Definition action.hpp:482
Action & reserve(size_t val)
Increase the capacity to a value that is greater or equal to val.
size_t index_type
The type of the index of a point.
Definition action.hpp:238
Point point_type
The template parameter Point.
Definition action.hpp:231
static void apply(point_type &result, point_type const &pt, element_type const &x)
Apply the template parameter Func in-place.
Definition action.hpp:851
detail::BruidhinnConstIterator< point_type, std::vector< internal_point_type > > const_iterator
The type of a const iterator pointing to a point_type.
Definition action.hpp:282
const_iterator cend() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last point.
Definition action.hpp:658
Action()
Default constructor.
Gabow< uint32_t > const & scc()
Returns a reference to a Gabow object for strongly connected components.
Definition action.hpp:831
size_t current_size() const noexcept
Returns the number of points found so far.
Definition action.hpp:595
std::vector< Element > const & generators() const noexcept
Returns a const reference to the vector of generators.
Definition action.hpp:495
const_reference_point_type root_of_scc(const_reference_point_type x)
Returns a const reference to the root point of a strongly connected component.
Definition action.hpp:774
const_iterator cbegin() const noexcept
Returns a const_iterator (random access iterator) pointing at the first point.
Definition action.hpp:613
Action & add_seed(const_reference_point_type seed)
Add a seed to the action.
WordGraph< uint32_t > const & word_graph()
Definition action.hpp:811
friend std::ostream & operator<<(std::ostream &os, Action const &action)
Definition action.hpp:269
bool cache_scc_multipliers() const noexcept
Returns whether or not we are caching scc multipliers.
Definition action.hpp:685
const_reference_point_type at(index_type pos) const
Returns a const reference to the point in a given position.
Definition action.hpp:562
const_reference_point_type operator[](index_type pos) const noexcept
Returns a const reference to the point in a given position.
Definition action.hpp:544
Class implementing Gabow's algorithm for computing strongly connected components of a WordGraph.
Definition gabow.hpp:61
void run()
Run until finished.
Runner()
Default constructor.
Class for representing word graphs.
Definition word-graph.hpp:82
size_type out_degree() const noexcept
Returns the out-degree.
Definition word-graph.hpp:823
Action< Element, Point, Func, Traits, side::right > RightAction
Definition action.hpp:933
Action< Element, Point, Func, Traits, side::left > LeftAction
Definition action.hpp:943
side
Enum class indicating the handedness or side of an action.
Definition action.hpp:91
@ right
Definition action.hpp:97
@ left
Definition action.hpp:94
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
Definition action.hpp:910
::libsemigroups::Hash< Point > Hash
Adapter for hashing.
Definition action.hpp:914
::libsemigroups::Swap< Element > Swap
Adapter for swapping.
Definition action.hpp:918
::libsemigroups::Degree< Element > Degree
Adapter for the degree of an element.
Definition action.hpp:912
::libsemigroups::EqualTo< Point > EqualTo
Adapter for testing equality.
Definition action.hpp:916
::libsemigroups::Product< Element > Product
Adapter for the product of two elements.
Definition action.hpp:922
::libsemigroups::One< Element > One
Adapter for the identity element of the given type.
Definition action.hpp:920
Adapter for the degree of an element.
Definition adapters.hpp:159
Adapter for testing equality.
Definition adapters.hpp:413
Adapter for hashing.
Definition adapters.hpp:446
Adapter for the value of a left action.
Definition adapters.hpp:350
Adapter for the value of a right action.
Definition adapters.hpp:392
Adapter for the identity element of the given type.
Definition adapters.hpp:246
Adapter for the product of two elements.
Definition adapters.hpp:284
Adapter for swapping.
Definition adapters.hpp:666