libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
word-range.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2020-2025 James D. Mitchell
4//
5// This program is free software: you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program. If not, see <http://www.gnu.org/licenses/>.
17//
18
19// This file contains declarations for function related to words (counting, and
20// converting) in libsemigroups.
21
22// TODO:
23// * iwyu
24// * nodiscard
25// * tests for code coverage
26
27#ifndef LIBSEMIGROUPS_WORD_RANGE_HPP_
28#define LIBSEMIGROUPS_WORD_RANGE_HPP_
29
30#include <cstddef> // for size_t
31#include <cstdint> // for uint64_t, uint8_t
32#include <initializer_list> // for initializer_list
33#include <limits> // for numeric_limits
34#include <string> // for basic_string
35#include <string_view> // for string_view
36#include <type_traits> // for enable_if_t
37#include <unordered_map> // for vector, operator==
38#include <utility> // for forward
39#include <variant> // for visit, operator==
40#include <vector> // for vector, operator==
41
42#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
43#include "exception.hpp" // for LibsemigroupsException
44#include "ranges.hpp" // for begin, end
45#include "types.hpp" // for word_type
46
47#include "detail/print.hpp" // for isprint etc
48#include "detail/word-iterators.hpp" // for const_wilo_iterator
49
50namespace libsemigroups {
51
52 enum class Order : uint8_t; // forward decl
53
54 namespace detail {
55 std::string const& chars_in_human_readable_order();
56 }
57
69 template <typename Word>
70 Word& reverse(Word&& w) {
71 std::reverse(w.begin(), w.end());
72 return w;
73 }
74
76 // Words
78
104
124 [[nodiscard]] uint64_t number_of_words(size_t n, size_t min, size_t max);
125
140 [[nodiscard]] word_type random_word(size_t length, size_t nr_letters);
141
187 [[nodiscard]] detail::const_wilo_iterator cbegin_wilo(size_t n,
188 size_t upper_bound,
189 word_type&& first,
190 word_type&& last);
191
195 [[nodiscard]] detail::const_wilo_iterator cbegin_wilo(size_t n,
196 size_t upper_bound,
197 word_type const& first,
198 word_type const& last);
199
208 [[nodiscard]] detail::const_wilo_iterator
209 cend_wilo(size_t n, size_t upper_bound, word_type&& first, word_type&& last);
210
215 [[nodiscard]] detail::const_wilo_iterator cend_wilo(size_t n,
216 size_t upper_bound,
217 word_type const& first,
218 word_type const& last);
219
257 [[nodiscard]] detail::const_wislo_iterator cbegin_wislo(size_t n,
258 word_type&& first,
259 word_type&& last);
260
264 [[nodiscard]] detail::const_wislo_iterator
265 cbegin_wislo(size_t n, word_type const& first, word_type const& last);
266
275 [[nodiscard]] detail::const_wislo_iterator cend_wislo(size_t n,
276 word_type&& first,
277 word_type&& last);
278
283 [[nodiscard]] detail::const_wislo_iterator cend_wislo(size_t n,
284 word_type const& first,
285 word_type const& last);
286
319 class WordRange {
320 public:
323
325 using output_type = word_type const&;
326
327 private:
328 using const_iterator = std::variant<detail::const_wilo_iterator,
329 detail::const_wislo_iterator>;
330
331 size_type _alphabet_size;
332 mutable const_iterator _current;
333 mutable const_iterator _end;
334 mutable bool _current_valid;
335 word_type _first;
336 word_type _last;
337 Order _order;
338 size_type _upper_bound;
339 mutable size_type _visited;
340
341 void set_iterator() const;
342
343 public:
355 [[nodiscard]] output_type get() const noexcept {
356 set_iterator();
357 return std::visit(
358 [](auto& it) -> auto const& { return *it; }, _current);
359 }
360
369 void next() noexcept {
370 set_iterator();
371 if (!at_end()) {
372 ++_visited;
373 }
374 std::visit([](auto& it) { ++it; }, _current);
375 }
376
384 [[nodiscard]] bool at_end() const noexcept {
385 set_iterator();
386 return _current == _end;
387 }
388
399 [[nodiscard]] size_t size_hint() const noexcept {
400 return number_of_words(_alphabet_size, _first.size(), _last.size())
401 - _visited;
402 // This is only the actual size if _order is shortlex
403 }
404
416 [[nodiscard]] size_t count() const noexcept;
417
418 // For some reason, there needs to be two doxygen comment lines here for
419 // this to render.
422 static constexpr bool is_finite = true; // This may not always be true
423
427 static constexpr bool is_idempotent = true;
428
440 init();
441 }
442
453
458
463
468
473
477 ~WordRange();
478
490 _current_valid &= (n == _alphabet_size);
491 _alphabet_size = n;
492 return *this;
493 }
494
503 [[nodiscard]] size_type alphabet_size() const noexcept {
504 return _alphabet_size;
505 }
506
520 WordRange& first(word_type const& frst) {
521 _current_valid &= (frst == _first);
522 _first = frst;
523 return *this;
524 }
525
536 [[nodiscard]] word_type const& first() const noexcept {
537 return _first;
538 }
539
552 WordRange& last(word_type const& lst) {
553 _current_valid &= (lst == _last);
554 _last = lst;
555 return *this;
556 }
557
568 [[nodiscard]] word_type const& last() const noexcept {
569 return _last;
570 }
571
583
592 [[nodiscard]] Order order() const noexcept {
593 return _order;
594 }
595
608 _current_valid &= (n == _upper_bound);
609 _upper_bound = n;
610 return *this;
611 }
612
622 [[nodiscard]] size_type upper_bound() const noexcept {
623 return _upper_bound;
624 }
625
638 first(word_type(val, 0));
639 return *this;
640 }
641
642 // No corresponding getter for min, because what would it mean? Could be the
643 // length of first(), but that doesn't correspond well to what happens with
644 // the setter.
645
658 last(word_type(val, 0));
659 return *this;
660 }
661
677 // REQUIRED so that we can use StringRange in range based loops
678 auto begin() const noexcept {
679 return rx::begin(*this);
680 }
681
697 // REQUIRED so that we can use StringRange in range based loops
698 auto end() const noexcept {
699 return rx::end(*this);
700 }
701
702 // TODO(now) this doc doesn't feel nice, but JDE can't think of a good way
703 // to write it.
722 // Required so StringRange can accurately set _current_valid
723 bool valid() const noexcept {
724 return _current_valid;
725 }
726 };
727
741 size_t max_width = 72);
742
744 // Strings -> Words
746
747 namespace v4 {
769 // TODO (later) a version that takes a word_type, so that we can permute the
770 // letters in a word
771 // TODO(0) remove default template param
772 template <typename From>
773 class ToWord {
774 private:
776
777 public:
780 using from_type = From;
781
785 ToWord() : _alphabet_map() {
786 init();
787 }
788
792 ToWord(ToWord const&);
793
798
803
808
812 ~ToWord();
813
826 _alphabet_map.clear();
827 return *this;
828 }
829
838 explicit ToWord(From const& alphabet) : _alphabet_map() {
839 init(alphabet);
840 }
841
855 ToWord& init(From const& alphabet);
856
866 [[nodiscard]] bool empty() const noexcept {
867 return _alphabet_map.empty();
868 }
869
885 [[nodiscard]] from_type alphabet() const;
886
898 [[nodiscard]] bool
899 can_convert_letter(typename from_type::value_type const& c) const {
900 return _alphabet_map.count(c) == 1;
901 }
902
903 // TODO remove "string" from all the doc here
925 void call_no_checks(word_type& output, From const& input) const;
926
943 [[nodiscard]] word_type call_no_checks(From const& input) const {
944 word_type output;
945 call_no_checks(output, input);
946 return output;
947 }
948
969 void operator()(word_type& output, From const& input) const;
970
986 [[nodiscard]] word_type operator()(From const& input) const {
987 word_type output;
988 operator()(output, input);
989 return output;
990 }
991
992 // TODO remove reference to char in the doc
1008 [[nodiscard]] letter_type
1009 operator()(typename From::value_type input) const {
1010 // TODO improve this
1011 // FIXME(1) it also doesn't work for example to_word('a') returns 63 for
1012 // some reason
1013 word_type output;
1014 // operator()(output, std::string_view(&input, 1));
1015 operator()(output, std::string(input, 1));
1016 return output[0];
1017 }
1018
1035 [[nodiscard]] letter_type
1036 call_no_checks(typename From::value_type input) const {
1037 return _alphabet_map.find(input)->second;
1038 }
1039
1040 template <typename InputRange>
1041 struct Range;
1042
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>;
1065 return Range<Inner>(std::forward<InputRange>(input), *this);
1066 }
1067 }; // class ToWord
1068
1069 template <size_t N>
1070 ToWord(const char (&)[N]) -> ToWord<std::string>;
1071
1072 template <typename From>
1073 template <typename InputRange>
1074 struct ToWord<From>::Range {
1075 using output_type = word_type;
1076
1077 static constexpr bool is_finite = rx::is_finite_v<InputRange>;
1078 static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
1079
1080 InputRange _input;
1081 ToWord<From> _to_word;
1082
1083 explicit Range(InputRange const& input, ToWord<From> const& t_wrd)
1084 : _input(input), _to_word(t_wrd) {}
1085
1086 explicit Range(InputRange&& input, ToWord<From> const& t_wrd)
1087 : _input(std::move(input)), _to_word(t_wrd) {}
1088
1089 explicit Range(InputRange const& input, ToWord<From>&& t_wrd)
1090 : _input(input), _to_word(std::move(t_wrd)) {}
1091
1092 explicit Range(InputRange&& input, ToWord<From>&& t_wrd)
1093 : _input(std::move(input)), _to_word(std::move(t_wrd)) {}
1094
1095 // Not noexcept because ToWord<From>()() isn't
1096 [[nodiscard]] output_type get() const {
1097 return _to_word.operator()(_input.get());
1098 }
1099
1100 constexpr void next() noexcept {
1101 _input.next();
1102 }
1103
1104 [[nodiscard]] constexpr bool at_end() const noexcept {
1105 return _input.at_end();
1106 }
1107
1108 [[nodiscard]] constexpr size_t size_hint() const noexcept {
1109 return _input.size_hint();
1110 }
1111 };
1112
1123 template <typename From>
1125 return fmt::format("<ToWord object with alphabet \"{}\">",
1126 twrd.alphabet());
1127 }
1128
1129 } // namespace v4
1130
1131 using ToWord [[deprecated]] = v4::ToWord<std::string>;
1132
1134 // Words -> Strings
1136
1158 class ToString {
1159 public:
1163 ToString() : _alphabet_map() {
1164 init();
1165 }
1166
1167 // TODO (later) noexcept?
1172
1177
1182
1187
1191 ~ToString();
1192
1204 ToString& init() noexcept {
1205 _alphabet_map.clear();
1206 return *this;
1207 }
1208
1217 explicit ToString(std::string const& alphabet) : _alphabet_map() {
1218 init(alphabet);
1219 }
1220
1235
1245 [[nodiscard]] bool empty() const noexcept {
1246 return _alphabet_map.empty();
1247 }
1248
1264 [[nodiscard]] std::string alphabet() const;
1265
1277 [[nodiscard]] bool can_convert_letter(letter_type const& l) const {
1278 return _alphabet_map.count(l) == 1;
1279 }
1280
1301 void call_no_checks(std::string& output, word_type const& input) const;
1302
1319 [[nodiscard]] std::string call_no_checks(word_type const& input) const {
1320 std::string output;
1321 call_no_checks(output, input);
1322 return output;
1323 }
1324
1344 void operator()(std::string& output, word_type const& input) const;
1345
1361 [[nodiscard]] std::string operator()(word_type const& input) const {
1362 std::string output;
1363 operator()(output, input);
1364 return output;
1365 }
1366
1383 template <typename Int>
1384 [[nodiscard]] std::string
1386 static_assert(std::is_integral_v<Int>);
1387 word_type copy(input.begin(), input.end());
1388 return operator()(copy);
1389 }
1390
1391 template <typename InputRange>
1392 struct Range;
1393
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>;
1414 return Range<Inner>(std::forward<InputRange>(input), *this);
1415 }
1416
1417 private:
1418 // We could use std::vector<char> (or similar) here, but an
1419 // unordered_ordered hap has been used instead to allow for potential future
1420 // conversions between different types.
1422 };
1423
1424 template <typename InputRange>
1425 struct ToString::Range {
1426 using output_type = std::string;
1427
1428 static constexpr bool is_finite = rx::is_finite_v<InputRange>;
1429 static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
1430
1431 InputRange _input;
1432 ToString _to_string;
1433
1434 Range(InputRange const& input, ToString const& t_str)
1435 : _input(input), _to_string(t_str) {}
1436
1437 Range(InputRange&& input, ToString const& t_str)
1438 : _input(std::move(input)), _to_string(t_str) {}
1439
1440 Range(InputRange const& input, ToString&& t_str)
1441 : _input(input), _to_string(std::move(t_str)) {}
1442
1443 Range(InputRange&& input, ToString&& t_str)
1444 : _input(std::move(input)), _to_string(std::move(t_str)) {}
1445
1446 ~Range();
1447
1448 // Not noexcept because ToString()() isn't
1449 [[nodiscard]] output_type get() const {
1450 return _to_string(_input.get());
1451 }
1452
1453 constexpr void next() noexcept {
1454 _input.next();
1455 }
1456
1457 [[nodiscard]] constexpr bool at_end() const noexcept {
1458 return _input.at_end();
1459 }
1460
1461 [[nodiscard]] constexpr size_t size_hint() const noexcept {
1462 return _input.size_hint();
1463 }
1464 };
1465
1466 // NOTE: This is a terrible hack to avoid compiler warnings. Maybe remove in
1467 // the future?
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;
1474#endif
1475
1486 [[nodiscard]] inline std::string
1488 return fmt::format("<ToString object with alphabet \"{}\">",
1489 tstr.alphabet());
1490 }
1491
1493 // StringRange
1495
1496 namespace detail {
1497 void throw_if_random_string_should_throw(std::string const& alphabet,
1498 size_t min,
1499 size_t max);
1500 } // namespace detail
1501
1516 std::string random_string(std::string const& alphabet, size_t length);
1517
1536 size_t min,
1537 size_t max);
1538
1557 auto inline random_strings(std::string const& alphabet,
1558 size_t number,
1559 size_t min,
1560 size_t max) {
1561 detail::throw_if_random_string_should_throw(alphabet, min, max);
1562
1563 // Lambda must capture by copy, as the lambda will exist outside the scope
1564 // of this function once the range is returned.
1565 return rx::generate([alphabet, min, max] {
1566 return random_string(alphabet, min, max);
1567 })
1568 | rx::take(number);
1569 }
1570
1603 // This can in many places be replaced by "WordRange | ToString" but this
1604 // makes some things more awkward and so we retain this class for its
1605 // convenience.
1607 public:
1610
1612 using output_type = std::string const&;
1613
1614 private:
1615 mutable std::string _current;
1616 mutable bool _current_valid;
1617 std::string _letters;
1618 v4::ToWord<std::string> _to_word;
1619 ToString _to_string;
1620 WordRange _word_range;
1621
1622 void init_current() const {
1623 if (!_current_valid) {
1624 _current = _to_string(_word_range.get());
1625 _current_valid = true;
1626 }
1627 }
1628
1629 public:
1642 init_current();
1643 return _current;
1644 }
1645
1654 void next() noexcept {
1655 _word_range.next();
1656 _current_valid = false;
1657 }
1658
1668 bool at_end() const noexcept {
1669 return _word_range.at_end();
1670 }
1671
1682 size_t size_hint() const noexcept {
1683 return _word_range.size_hint();
1684 }
1685
1697 size_t count() const noexcept {
1698 return _word_range.count();
1699 }
1700
1702 static constexpr bool is_finite = true; // This may not always be true
1703
1707 static constexpr bool is_idempotent = true;
1708
1720 init();
1721 }
1722
1733
1736
1739
1742
1745
1747 ~StringRange();
1748
1759
1768 [[nodiscard]] std::string const& alphabet() const noexcept {
1769 return _letters;
1770 }
1771
1785 _word_range.first(_to_word(frst));
1786 _current_valid &= _word_range.valid();
1787 return *this;
1788 }
1789
1800 [[nodiscard]] std::string first() const noexcept {
1801 return _to_string(_word_range.first());
1802 }
1803
1821 _word_range.last(_to_word(lst));
1822 _current_valid &= _word_range.valid();
1823 return *this;
1824 }
1825
1836 [[nodiscard]] std::string last() const noexcept {
1837 return _to_string(_word_range.last());
1838 }
1839
1851 _word_range.order(val);
1852 _current_valid &= _word_range.valid();
1853 return *this;
1854 }
1855
1864 [[nodiscard]] Order order() const noexcept {
1865 return _word_range.order();
1866 }
1867
1880 _word_range.upper_bound(n);
1881 _current_valid &= _word_range.valid();
1882 return *this;
1883 }
1884
1894 [[nodiscard]] size_type upper_bound() const noexcept {
1895 return _word_range.upper_bound();
1896 }
1897
1910 _word_range.min(val);
1911 _current_valid &= _word_range.valid();
1912 return *this;
1913 }
1914
1915 // No corresponding getter for min, because what would it mean? Could be the
1916 // length of first(), but that doesn't correspond well to what happens with
1917 // the setter.
1918
1933 _word_range.max(val);
1934 _current_valid &= _word_range.valid();
1935 return *this;
1936 }
1937
1953 // REQUIRED so that we can use StringRange in range based loops
1954 auto begin() const noexcept {
1955 return rx::begin(*this);
1956 }
1957
1973 // REQUIRED so that we can use StringRange in range based loops
1974 auto end() const noexcept {
1975 return rx::end(*this);
1976 }
1977 };
1978
1992 size_t max_width = 72);
1993
1995 // Literals
1997
2012 namespace literals {
2040 word_type operator"" _w(const char* w, size_t n);
2041
2045 word_type operator"" _w(const char* w);
2046
2068 std::string operator"" _p(const char* w, size_t n);
2069
2074 std::string operator"" _p(const char* w);
2075 } // namespace literals
2076
2078
2095 namespace words {
2096
2112 [[nodiscard]] letter_type human_readable_index(char c);
2113
2130 template <typename Word = std::string>
2131 typename Word::value_type human_readable_letter(size_t i) {
2132 // This check ensures that i is not too large to be converted to a
2133 // Word::value_type. This is check is only needed if the number of
2134 // distinct Word::value objects is less than the number of distinct size_t
2135 // objects.
2136 if constexpr (sizeof(typename Word::value_type) < sizeof(size_t)) {
2140 "expected the argument to be in the range [0, {}), found {}",
2143 i);
2144 }
2145 }
2146 if constexpr (!std::is_same_v<Word, std::string>) {
2147 return static_cast<typename Word::value_type>(i);
2148 } else {
2149 // Choose visible characters a-zA-Z0-9 first before anything else
2150 // The ascii ranges for these characters are: [97, 123), [65, 91),
2151 // [48, 58) so the remaining range of chars that are appended to the end
2152 // after these chars are [0,48), [58, 65), [91, 97), [123, 255]
2153 return detail::chars_in_human_readable_order()[i];
2154 }
2155 }
2156
2158 // operator+
2160
2174
2179
2184
2186 // operator+=
2188
2201 static inline void operator+=(word_type& u, word_type const& v) {
2202 u.insert(u.end(), v.cbegin(), v.cend());
2203 }
2204
2208 inline void operator+=(word_type& u, letter_type a) {
2209 u.push_back(a);
2210 }
2211
2215 inline void operator+=(letter_type a, word_type& u) {
2216 u.insert(u.begin(), a);
2217 }
2218
2220 // pow
2222
2234 template <typename Word>
2235 void pow_inplace(Word& w, size_t n);
2236 // No pow_inplace for string_view or initializer_list because there's no
2237 // where to store the result.
2238
2252 template <typename Word>
2253 Word pow(Word const& x, size_t n) {
2254 Word y(x);
2255 pow_inplace(y, n);
2256 return y;
2257 }
2258
2263
2267 std::string pow(std::string_view w, size_t n);
2268
2270 // prod
2272
2311 template <typename Container, typename Word = Container>
2312 Word prod(Container const& elts, int first, int last, int step = 1);
2313
2318 int first,
2319 int last,
2320 int step = 1) {
2321 return prod<word_type>(word_type(ilist), first, last, step);
2322 }
2323
2327 static inline std::string
2328 prod(std::string_view sv, int first, int last, int step = 1) {
2329 return prod<std::string>(std::string(sv), first, last, step);
2330 }
2331
2336 int first,
2337 int last,
2338 int step = 1) {
2340 std::vector<word_type>(elts), first, last, step);
2341 }
2342
2346 static inline std::string
2348 int first,
2349 int last,
2350 int step = 1) {
2352 sv, first, last, step);
2353 }
2354
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);
2363 }
2364
2371 size_t last) {
2372 return prod(elts, 0, static_cast<int>(last), 1);
2373 }
2374
2380 static inline std::string prod(std::string_view elts, size_t last) {
2382 elts, 0, static_cast<int>(last), 1);
2383 }
2384
2391 size_t last) {
2392 return prod(elts, 0, static_cast<int>(last), 1);
2393 }
2394
2400 static inline std::string
2403 std::vector<std::string_view>(elts), 0, static_cast<int>(last), 1);
2404 }
2405
2407 // pow - implementation
2409
2410 template <typename Word>
2411 void pow_inplace(Word& x, size_t n) {
2412 Word y(x);
2413 x.reserve(x.size() * n);
2414 if (n % 2 == 0) {
2415 x = Word({});
2416 }
2417
2418 while (n > 1) {
2419 y += y;
2420 n /= 2;
2421 if (n % 2 == 1) {
2422 x += y;
2423 }
2424 }
2425 }
2426
2428 // prod - implementation
2430
2431 // Note: we could do a version of the below using insert on words, where
2432 // the step is +/- 1.
2433 template <typename Container, typename Word>
2434 Word prod(Container const& elts, int first, int last, int step) {
2435 if (step == 0) {
2436 LIBSEMIGROUPS_EXCEPTION("the 4th argument must not be 0");
2437 } else if (((first < last && step > 0) || (first > last && step < 0))
2438 && elts.size() == 0) {
2439 LIBSEMIGROUPS_EXCEPTION("the 1st argument must not be empty if the "
2440 "given range is not empty");
2441 // TODO Is int signed? Should this also contain
2442 // std::numeric_limits<int>::min?
2443 } else if (elts.size() > std::numeric_limits<int>::max()) {
2445 "the 1st argument must have size less than or equal to {}",
2447 }
2448 Word result;
2449 int const s = elts.size();
2450
2451 if (first < last) {
2452 if (step < 0) {
2453 return result;
2454 }
2455 result.reserve((last - first) / step);
2456
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);
2460 result += elts[a];
2461 }
2462 } else {
2463 if (step > 0) {
2464 return result;
2465 }
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);
2471 result += elts[a];
2472 }
2473 }
2474 return result;
2475 }
2476 } // namespace words
2477
2478 namespace v4 {
2480 // Out-of-line implementation of ToWord mem fns
2482
2483 template <typename From>
2484 ToWord<From>::ToWord(ToWord const&) = default;
2485
2486 template <typename From>
2487 ToWord<From>::ToWord(ToWord&&) = default;
2488
2489 template <typename From>
2490 ToWord<From>& ToWord<From>::operator=(ToWord const&) = default;
2491
2492 template <typename From>
2494
2495 template <typename From>
2496 ToWord<From>::~ToWord() = default;
2497
2498 template <typename From>
2500 if (alphabet.size() > 256) {
2501 // TODO replace 256 with numeric_limits::max - numeric_limits::min
2502 LIBSEMIGROUPS_EXCEPTION("The argument (alphabet) is too big, expected "
2503 "at most 256, found {}",
2504 alphabet.size());
2505 }
2506 auto _old_alphabet_map = _alphabet_map;
2507 init();
2508 LIBSEMIGROUPS_ASSERT(_alphabet_map.empty());
2509 for (letter_type l = 0; l < alphabet.size(); ++l) {
2510 auto it = _alphabet_map.emplace(alphabet[l], l);
2511 if (!it.second) {
2512 // Strong exception guarantee
2513 std::swap(_old_alphabet_map, _alphabet_map);
2514 LIBSEMIGROUPS_EXCEPTION("invalid alphabet {}, duplicate letter {}!",
2515 detail::to_printable(alphabet),
2516 detail::to_printable(alphabet[l]));
2517 }
2518 }
2519 return *this;
2520 }
2521
2522 template <typename From>
2523 [[nodiscard]] From ToWord<From>::alphabet() const {
2524 if (empty()) {
2525 return From();
2526 }
2527 From output(_alphabet_map.size(), typename From::value_type());
2528 for (auto it : _alphabet_map) {
2529 output[it.second] = it.first;
2530 }
2531 return output;
2532 }
2533
2534 template <typename From>
2536 From const& input) const {
2537 // Empty alphabet implies conversion should use human_readable_index
2538 if (empty()) {
2539 // TODO remove this behaviour
2540 output.resize(input.size(), 0);
2541 std::transform(input.cbegin(),
2542 input.cend(),
2543 output.begin(),
2544 [](char c) { return words::human_readable_index(c); });
2545 } else { // Non-empty alphabet implies conversion should use the
2546 // alphabet.
2547 output.clear();
2548 output.reserve(input.size());
2549 for (auto const& c : input) {
2550 output.push_back(_alphabet_map.at(c));
2551 }
2552 }
2553 }
2554
2555 template <typename From>
2556 void ToWord<From>::operator()(word_type& output, From const& input) const {
2557 if (!empty()) {
2558 for (auto const& c : input) {
2559 if (_alphabet_map.find(c) == _alphabet_map.cend()) {
2560 // TODO improve this like in presentation
2562 "invalid letter {} in the 2nd argument (input word), "
2563 "expected letters in the alphabet {}!",
2564 detail::to_printable(c),
2565 detail::to_printable(alphabet()));
2566 }
2567 }
2568 }
2569 call_no_checks(output, input);
2570 }
2571 } // namespace v4
2572} // namespace libsemigroups
2573
2574#endif // LIBSEMIGROUPS_WORD_RANGE_HPP_
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.
T clear(T... args)
T forward(T... args)
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.
T insert(T... args)
T max(T... args)
T min(T... args)
T move(T... args)
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
T next(T... args)
T push_back(T... args)
T reserve(T... args)
T resize(T... args)
T reverse(T... args)
T swap(T... args)
T transform(T... args)