27#ifndef LIBSEMIGROUPS_WORD_RANGE_HPP_
28#define LIBSEMIGROUPS_WORD_RANGE_HPP_
32#include <initializer_list>
37#include <unordered_map>
43#include "exception.hpp"
47#include "detail/print.hpp"
48#include "detail/word-iterators.hpp"
52 enum class Order : uint8_t;
55 std::string
const& chars_in_human_readable_order();
69 template <
typename Word>
208 [[nodiscard]] detail::const_wilo_iterator
215 [[nodiscard]] detail::const_wilo_iterator
cend_wilo(
size_t n,
264 [[nodiscard]] detail::const_wislo_iterator
275 [[nodiscard]] detail::const_wislo_iterator
cend_wislo(
size_t n,
283 [[nodiscard]] detail::const_wislo_iterator
cend_wislo(
size_t n,
328 using const_iterator = std::variant<detail::const_wilo_iterator,
329 detail::const_wislo_iterator>;
332 mutable const_iterator _current;
333 mutable const_iterator _end;
334 mutable bool _current_valid;
341 void set_iterator()
const;
358 [](
auto& it) ->
auto const& {
return *it; }, _current);
374 std::visit([](
auto& it) { ++it; }, _current);
384 [[nodiscard]]
bool at_end() const noexcept {
386 return _current == _end;
416 [[nodiscard]]
size_t count() const noexcept;
490 _current_valid &= (n == _alphabet_size);
504 return _alphabet_size;
521 _current_valid &= (frst == _first);
553 _current_valid &= (lst == _last);
608 _current_valid &= (n == _upper_bound);
679 return rx::begin(*
this);
698 auto end() const noexcept {
699 return rx::end(*
this);
724 return _current_valid;
741 size_t max_width = 72);
772 template <
typename From>
826 _alphabet_map.clear();
866 [[nodiscard]]
bool empty() const noexcept {
867 return _alphabet_map.empty();
900 return _alphabet_map.count(c) == 1;
1037 return _alphabet_map.find(input)->second;
1040 template <
typename InputRange>
1061 template <
typename InputRange,
1062 typename = std::enable_if_t<rx::is_input_or_sink_v<InputRange>>>
1063 [[nodiscard]]
constexpr auto operator()(InputRange&& input)
const {
1064 using Inner = rx::get_range_type_t<InputRange>;
1072 template <
typename From>
1073 template <
typename InputRange>
1074 struct ToWord<From>::Range {
1077 static constexpr bool is_finite = rx::is_finite_v<InputRange>;
1078 static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
1083 explicit Range(InputRange
const& input,
ToWord<From> const& t_wrd)
1084 : _input(input), _to_word(t_wrd) {}
1086 explicit Range(InputRange&& input,
ToWord<From> const& t_wrd)
1087 : _input(
std::move(input)), _to_word(t_wrd) {}
1089 explicit Range(InputRange
const& input,
ToWord<From>&& t_wrd)
1090 : _input(input), _to_word(std::
move(t_wrd)) {}
1092 explicit Range(InputRange&& input,
ToWord<From>&& t_wrd)
1093 : _input(std::
move(input)), _to_word(std::
move(t_wrd)) {}
1096 [[nodiscard]] output_type get()
const {
1097 return _to_word.operator()(_input.get());
1100 constexpr void next() noexcept {
1104 [[nodiscard]]
constexpr bool at_end() const noexcept {
1105 return _input.at_end();
1108 [[nodiscard]]
constexpr size_t size_hint() const noexcept {
1109 return _input.size_hint();
1123 template <
typename From>
1125 return fmt::format(
"<ToWord object with alphabet \"{}\">",
1131 using ToWord [[deprecated]] = v4::ToWord<std::string>;
1205 _alphabet_map.clear();
1245 [[nodiscard]]
bool empty() const noexcept {
1246 return _alphabet_map.empty();
1278 return _alphabet_map.count(l) == 1;
1383 template <
typename Int>
1386 static_assert(std::is_integral_v<Int>);
1391 template <
typename InputRange>
1410 template <
typename InputRange,
1411 typename = std::enable_if_t<rx::is_input_or_sink_v<InputRange>>>
1412 [[nodiscard]]
constexpr auto operator()(InputRange&& input)
const {
1413 using Inner = rx::get_range_type_t<InputRange>;
1424 template <
typename InputRange>
1425 struct ToString::Range {
1428 static constexpr bool is_finite = rx::is_finite_v<InputRange>;
1429 static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
1434 Range(InputRange
const& input,
ToString const& t_str)
1435 : _input(input), _to_string(t_str) {}
1437 Range(InputRange&& input,
ToString const& t_str)
1438 : _input(std::
move(input)), _to_string(t_str) {}
1440 Range(InputRange
const& input,
ToString&& t_str)
1441 : _input(input), _to_string(std::
move(t_str)) {}
1443 Range(InputRange&& input,
ToString&& t_str)
1444 : _input(std::
move(input)), _to_string(std::
move(t_str)) {}
1449 [[nodiscard]] output_type get()
const {
1450 return _to_string(_input.get());
1453 constexpr void next() noexcept {
1457 [[nodiscard]]
constexpr bool at_end() const noexcept {
1458 return _input.at_end();
1461 [[nodiscard]]
constexpr size_t size_hint() const noexcept {
1462 return _input.size_hint();
1468#if defined(__clang__)
1469 template <
typename InputRange>
1470 ToString::Range<InputRange>::~Range<InputRange>() =
default;
1471#elif defined(__GNUC__)
1472 template <
typename InputRange>
1473 ToString::Range<InputRange>::~Range() =
default;
1486 [[nodiscard]]
inline std::string
1488 return fmt::format(
"<ToString object with alphabet \"{}\">",
1497 void throw_if_random_string_should_throw(
std::string const& alphabet,
1561 detail::throw_if_random_string_should_throw(alphabet, min, max);
1565 return rx::generate([alphabet, min, max] {
1616 mutable bool _current_valid;
1622 void init_current()
const {
1623 if (!_current_valid) {
1624 _current = _to_string(_word_range.get());
1625 _current_valid =
true;
1656 _current_valid =
false;
1669 return _word_range.at_end();
1683 return _word_range.size_hint();
1698 return _word_range.count();
1785 _word_range.
first(_to_word(frst));
1786 _current_valid &= _word_range.valid();
1801 return _to_string(_word_range.first());
1821 _word_range.
last(_to_word(lst));
1822 _current_valid &= _word_range.valid();
1837 return _to_string(_word_range.last());
1851 _word_range.
order(val);
1852 _current_valid &= _word_range.valid();
1865 return _word_range.order();
1881 _current_valid &= _word_range.valid();
1895 return _word_range.upper_bound();
1910 _word_range.
min(val);
1911 _current_valid &= _word_range.valid();
1933 _word_range.
max(val);
1934 _current_valid &= _word_range.valid();
1955 return rx::begin(*
this);
1975 return rx::end(*
this);
1992 size_t max_width = 72);
2130 template <
typename Word = std::
string>
2136 if constexpr (
sizeof(
typename Word::value_type) <
sizeof(size_t)) {
2140 "expected the argument to be in the range [0, {}), found {}",
2146 if constexpr (!std::is_same_v<Word, std::string>) {
2147 return static_cast<typename Word::value_type
>(i);
2153 return detail::chars_in_human_readable_order()[i];
2234 template <
typename Word>
2252 template <
typename Word>
2253 Word
pow(Word
const& x,
size_t n) {
2311 template <
typename Container,
typename Word = Container>
2312 Word
prod(Container
const& elts,
int first,
int last,
int step = 1);
2328 prod(std::string_view sv,
int first,
int last,
int step = 1) {
2352 sv, first, last, step);
2360 template <
typename Container,
typename Word = Container>
2361 Word
prod(Container
const& elts,
size_t last) {
2362 return prod(elts, 0,
static_cast<int>(last), 1);
2372 return prod(elts, 0,
static_cast<int>(last), 1);
2382 elts, 0,
static_cast<int>(last), 1);
2392 return prod(elts, 0,
static_cast<int>(last), 1);
2410 template <
typename Word>
2413 x.reserve(x.size() * n);
2433 template <
typename Container,
typename Word>
2434 Word
prod(Container
const& elts,
int first,
int last,
int step) {
2437 }
else if (((first < last && step > 0) || (first > last && step < 0))
2438 && elts.size() == 0) {
2440 "given range is not empty");
2445 "the 1st argument must have size less than or equal to {}",
2449 int const s = elts.size();
2455 result.reserve((last - first) / step);
2457 for (
int i = first; i < last; i += step) {
2458 size_t const a = (i % s + s) % s;
2459 LIBSEMIGROUPS_ASSERT(
static_cast<int>(a) < s);
2466 size_t steppos =
static_cast<size_t>(-step);
2467 result.reserve((first - last) / steppos);
2468 for (
int i = first; i > last; i += step) {
2469 size_t const a = (i % s + s) % s;
2470 LIBSEMIGROUPS_ASSERT(
static_cast<int>(a) < s);
2483 template <
typename From>
2486 template <
typename From>
2489 template <
typename From>
2492 template <
typename From>
2495 template <
typename From>
2498 template <
typename From>
2503 "at most 256, found {}",
2506 auto _old_alphabet_map = _alphabet_map;
2508 LIBSEMIGROUPS_ASSERT(_alphabet_map.empty());
2510 auto it = _alphabet_map.emplace(
alphabet[l], l);
2513 std::swap(_old_alphabet_map, _alphabet_map);
2516 detail::to_printable(
alphabet[l]));
2522 template <
typename From>
2527 From output(_alphabet_map.size(),
typename From::value_type());
2528 for (
auto it : _alphabet_map) {
2529 output[it.second] = it.first;
2534 template <
typename From>
2536 From
const& input)
const {
2540 output.
resize(input.size(), 0);
2544 [](
char c) { return words::human_readable_index(c); });
2549 for (
auto const& c : input) {
2555 template <
typename From>
2558 for (
auto const& c : input) {
2559 if (_alphabet_map.find(c) == _alphabet_map.cend()) {
2562 "invalid letter {} in the 2nd argument (input word), "
2563 "expected letters in the alphabet {}!",
2564 detail::to_printable(c),
Class for generating strings in a given range and in a particular order.
Definition word-range.hpp:1606
static constexpr bool is_finite
Value indicating that the range is finite.
Definition word-range.hpp:1702
StringRange & operator=(StringRange const &)
Default copy assignment operator.
StringRange & min(size_type val)
Set the first string in the range by length.
Definition word-range.hpp:1909
auto end() const noexcept
Returns an input iterator pointing one beyond the last string in the range.
Definition word-range.hpp:1974
StringRange & upper_bound(size_type n)
Set an upper bound for the length of a string in the range.
Definition word-range.hpp:1879
std::string first() const noexcept
The current first string in the range.
Definition word-range.hpp:1800
StringRange & init()
Initialize an existing StringRange object.
StringRange & max(size_type val)
Set one past the last string in the range by length.
Definition word-range.hpp:1932
std::string last() const noexcept
The current one past the last string in the range.
Definition word-range.hpp:1836
StringRange & alphabet(std::string const &x)
Set the alphabet.
std::string const & alphabet() const noexcept
The current alphabet.
Definition word-range.hpp:1768
StringRange & order(Order val)
Set the order of the strings in the range.
Definition word-range.hpp:1850
StringRange()
Default constructor.
Definition word-range.hpp:1719
output_type get() const
Get the current value.
Definition word-range.hpp:1641
StringRange & first(std::string const &frst)
Set the first string in the range.
Definition word-range.hpp:1784
auto begin() const noexcept
Returns an input iterator pointing to the first string in the range.
Definition word-range.hpp:1954
size_type upper_bound() const noexcept
The current upper bound on the length of a string in the range.
Definition word-range.hpp:1894
StringRange(StringRange &&)
Default move constructor.
Order order() const noexcept
The current order of the strings in the range.
Definition word-range.hpp:1864
void next() noexcept
Advance to the next value.
Definition word-range.hpp:1654
static constexpr bool is_idempotent
Definition word-range.hpp:1707
size_t size_hint() const noexcept
The possible size of the range.
Definition word-range.hpp:1682
typename std::vector< std::string >::size_type size_type
Alias for the size type.
Definition word-range.hpp:1609
StringRange & operator=(StringRange &&)
Default move assignment operator.
std::string const & output_type
The type of the output of the range object.
Definition word-range.hpp:1612
size_t count() const noexcept
The actual size of the range.
Definition word-range.hpp:1697
bool at_end() const noexcept
Check if the range object is exhausted.
Definition word-range.hpp:1668
StringRange & last(std::string const &lst)
Set one past the last string in the range.
Definition word-range.hpp:1820
StringRange(StringRange const &)
Default copy constructor.
Class for converting word_type into std::string with specified alphabet.
Definition word-range.hpp:1158
ToString & init() noexcept
Initialize an existing ToString object.
Definition word-range.hpp:1204
bool can_convert_letter(letter_type const &l) const
Definition word-range.hpp:1277
ToString()
Default constructor.
Definition word-range.hpp:1163
constexpr auto operator()(InputRange &&input) const
Call operator for combining with other range objects.
Definition word-range.hpp:1412
bool empty() const noexcept
Check if the alphabet is defined.
Definition word-range.hpp:1245
ToString(ToString &&)
Default move constructor.
std::string operator()(std::initializer_list< Int > input) const
Convert a std::initializer_list to a std::string.
Definition word-range.hpp:1385
std::string call_no_checks(word_type const &input) const
Convert a word_type to a std::string.
Definition word-range.hpp:1319
ToString(ToString const &)
Default copy constructor.
std::string operator()(word_type const &input) const
Convert a word_type to a std::string.
Definition word-range.hpp:1361
ToString & init(std::string const &alphabet)
Initialize an existing Tostring object.
ToString & operator=(ToString &&)
Default move assignment.
void call_no_checks(std::string &output, word_type const &input) const
Convert a word_type to a std::string.
ToString(std::string const &alphabet)
Construct with given alphabet.
Definition word-range.hpp:1217
void operator()(std::string &output, word_type const &input) const
Convert a word_type to a std::string.
std::string alphabet() const
Return the alphabet used for conversion.
ToString & operator=(ToString const &)
Default copy assignment.
Class for converting strings to word_type with specified alphabet.
Definition word-range.hpp:773
void operator()(word_type &output, From const &input) const
Convert a string to a word_type.
Definition word-range.hpp:2556
ToWord & init(From const &alphabet)
Initialize an existing ToWord object.
Definition word-range.hpp:2499
std::string from_type
Definition word-range.hpp:780
from_type alphabet() const
Definition word-range.hpp:2523
ToWord()
Default constructor.
Definition word-range.hpp:785
void call_no_checks(word_type &output, From const &input) const
Convert a string to a word_type.
Definition word-range.hpp:2535
Class for generating words in a given range and in a particular order.
Definition word-range.hpp:319
static constexpr bool is_finite
Definition word-range.hpp:422
output_type get() const noexcept
Get the current value.
Definition word-range.hpp:355
word_type const & output_type
The type of the output of a WordRange object.
Definition word-range.hpp:325
auto end() const noexcept
Returns an input iterator pointing one beyond the last word in the range.
Definition word-range.hpp:698
word_type const & last() const noexcept
The current one past the last word in the range.
Definition word-range.hpp:568
WordRange & last(word_type const &lst)
Set one past the last word in the range.
Definition word-range.hpp:552
WordRange(WordRange &&)
Default move constructor.
WordRange & min(size_type val)
Set the first word in the range by length.
Definition word-range.hpp:637
WordRange & max(size_type val)
Set one past the last word in the range by length.
Definition word-range.hpp:657
typename std::vector< word_type >::size_type size_type
Alias for the size type.
Definition word-range.hpp:322
WordRange(WordRange const &)
Default copy constructor.
WordRange & upper_bound(size_type n)
Set an upper bound for the length of a word in the range.
Definition word-range.hpp:607
word_type const & first() const noexcept
The current first word in the range.
Definition word-range.hpp:536
WordRange & order(Order val)
Set the order of the words in the range.
WordRange()
Default constructor.
Definition word-range.hpp:439
WordRange & operator=(WordRange const &)
Default copy assignment operator.
auto begin() const noexcept
Returns an input iterator pointing to the first word in the range.
Definition word-range.hpp:678
size_type upper_bound() const noexcept
The current upper bound on the length of a word in the range.
Definition word-range.hpp:622
bool valid() const noexcept
Returns whether or not the settings have been changed since the last time either next or get has been...
Definition word-range.hpp:723
Order order() const noexcept
The current order of the words in the range.
Definition word-range.hpp:592
void next() noexcept
Advance to the next value.
Definition word-range.hpp:369
static constexpr bool is_idempotent
Definition word-range.hpp:427
WordRange & alphabet_size(size_type n) noexcept
Set the number of letters in the alphabet.
Definition word-range.hpp:489
size_t size_hint() const noexcept
The possible size of the range.
Definition word-range.hpp:399
size_type alphabet_size() const noexcept
The current number of letters in the alphabet.
Definition word-range.hpp:503
size_t count() const noexcept
The actual size of the range.
bool at_end() const noexcept
Check if the range object is exhausted.
Definition word-range.hpp:384
WordRange & first(word_type const &frst)
Set the first word in the range.
Definition word-range.hpp:520
WordRange & init()
Initialize an existing WordRange object.
WordRange & operator=(WordRange &&)
Default move assignment operator.
Class for converting strings to word_type with specified alphabet.
Definition word-range.hpp:773
void operator()(word_type &output, From const &input) const
Convert a string to a word_type.
Definition word-range.hpp:2556
ToWord & init()
Initialize an existing ToWord object.
Definition word-range.hpp:825
bool can_convert_letter(typename from_type::value_type const &c) const
Definition word-range.hpp:899
From from_type
The type of values an instance of ToWord will convert into word_type.
Definition word-range.hpp:780
constexpr auto operator()(InputRange &&input) const
Call operator for combining with other range objects.
Definition word-range.hpp:1063
bool empty() const noexcept
Check if the alphabet is defined.
Definition word-range.hpp:866
word_type operator()(From const &input) const
Convert a string to a word_type.
Definition word-range.hpp:986
ToWord & operator=(ToWord const &)
Default copy assignment.
letter_type call_no_checks(typename From::value_type input) const
Convert a char to a letter_type.
Definition word-range.hpp:1036
ToWord & operator=(ToWord &&)
Default move assignment.
from_type alphabet() const
Return the alphabet used for conversion.
Definition word-range.hpp:2523
ToWord(ToWord &&)
Default move constructor.
ToWord(From const &alphabet)
Construct with given alphabet.
Definition word-range.hpp:838
ToWord()
Default constructor.
Definition word-range.hpp:785
letter_type operator()(typename From::value_type input) const
Convert a char to a letter_type.
Definition word-range.hpp:1009
word_type call_no_checks(From const &input) const
Convert a string to a word_type.
Definition word-range.hpp:943
void call_no_checks(word_type &output, From const &input) const
Convert a string to a word_type.
Definition word-range.hpp:2535
ToWord(ToWord const &)
Default copy constructor.
std::string to_human_readable_repr(AhoCorasick const &ac)
Return a string representation.
#define LIBSEMIGROUPS_EXCEPTION(...)
Throw a LibsemigroupsException.
Definition exception.hpp:99
std::vector< letter_type > word_type
Type for a word over the generators of a semigroup.
Definition types.hpp:99
size_t letter_type
Type for the index of a generator of a semigroup.
Definition types.hpp:96
Order
The possible orderings of words and strings.
Definition order.hpp:45
detail::const_wislo_iterator cend_wislo(size_t n, word_type &&first, word_type &&last)
Returns a forward iterator pointing to one after the end of the range from first to last.
std::string random_string(std::string const &alphabet, size_t length)
Returns a random string.
std::string to_human_readable_repr(ToWord< From > const &twrd)
Return a human readable representation of a ToWord object.
Definition word-range.hpp:1124
detail::const_wilo_iterator cbegin_wilo(size_t n, size_t upper_bound, word_type &&first, word_type &&last)
Returns a forward iterator pointing to the 3rd parameter first.
Word & reverse(Word &&w)
Reverse an object.
Definition word-range.hpp:70
detail::const_wislo_iterator cbegin_wislo(size_t n, word_type &&first, word_type &&last)
Returns a forward iterator pointing to the 2nd parameter first.
auto random_strings(std::string const &alphabet, size_t number, size_t min, size_t max)
Returns a range object of random strings.
Definition word-range.hpp:1557
detail::const_wilo_iterator cend_wilo(size_t n, size_t upper_bound, word_type &&first, word_type &&last)
Returns a forward iterator pointing to one after the end of the range from first to last.
uint64_t number_of_words(size_t n, size_t min, size_t max)
Returns the number of words over an alphabet with a given number of letters with length in a specifie...
word_type random_word(size_t length, size_t nr_letters)
Returns a random word.
Namespace containing some custom literals for creating words.
Definition word-range.hpp:2012
Namespace containing some operators for creating words.
Definition word-range.hpp:2095
static void operator+=(word_type &u, word_type const &v)
Concatenate a word with another word in-place.
Definition word-range.hpp:2201
Word pow(Word const &x, size_t n)
Returns the power of a word.
Definition word-range.hpp:2253
void pow_inplace(Word &w, size_t n)
Power a word in-place.
Definition word-range.hpp:2411
Word prod(Container const &elts, int first, int last, int step=1)
Returns a product of letters or words.
Definition word-range.hpp:2434
Word::value_type human_readable_letter(size_t i)
Returns a character by index in human readable order.
Definition word-range.hpp:2131
word_type operator+(word_type const &u, word_type const &w)
Concatenate two words.
letter_type human_readable_index(char c)
Returns the index of a character in human readable order.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44