1 // 2 // libsemigroups - C++ library for semigroups and monoids 3 // Copyright (C) 2020 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 some functionality for generating elements in the free 20 // monoid over an alphabet with a given number of letters up to a given length 21 // in a lexicographic or short-lex order. 22 // 23 // SILO = Strings In Lexicographic Order 24 // SISLO = Strings In Short-Lex Order 25 // SISO = Strings In Some Order 26 27 // TODO(later): 28 // 1. cbegin_silo and cend_silo for rvalue references to strings 29 // 2. cbegin_sislo and cend_sislo for rvalue references to strings 30 31 #ifndef LIBSEMIGROUPS_SISO_HPP_ 32 #define LIBSEMIGROUPS_SISO_HPP_ 33 34 #include <cstddef> // for size_t, ptrdiff_t, ... 35 #include <iterator> // for forward_iterator_tag 36 #include <string> // for string 37 #include <utility> // for pair 38 39 #include "iterator.hpp" // for detail::ConstIteratorStateful 40 #include "wilo.hpp" // for const_wilo_iterator 41 #include "wislo.hpp" // for const_wislo_iterator 42 #include "word.hpp" // for word_to_string 43 44 namespace libsemigroups { 45 namespace detail { 46 // This is a traits class for ConstIteratorStateful in iterator.hpp 47 template <typename T> 48 struct SisoIteratorTraits { 49 // state_type::first = alphabet, state_type::second = current value 50 using state_type = std::pair<std::string, std::string>; 51 using internal_iterator_type = T; 52 using value_type = std::string; 53 using reference = std::string&; 54 using const_reference = std::string const&; 55 using difference_type = std::ptrdiff_t; 56 using size_type = std::size_t; 57 using const_pointer = std::string const*; 58 using pointer = std::string*; 59 using iterator_category = std::forward_iterator_tag; 60 61 struct Deref { 62 const_reference operator ()libsemigroups::detail::SisoIteratorTraits::Deref63 operator()(state_type& state, 64 internal_iterator_type const& it) const noexcept { 65 if (state.second.empty()) { 66 detail::word_to_string(state.first, *it, state.second); 67 } 68 return state.second; 69 } 70 }; 71 72 struct AddressOf { 73 const_pointer operator ()libsemigroups::detail::SisoIteratorTraits::AddressOf74 operator()(state_type& state, 75 internal_iterator_type const& it) const noexcept { 76 Deref()(state, it); // to ensure that state.second is initialised 77 return &state.second; 78 } 79 }; 80 81 struct PrefixIncrement { operator ()libsemigroups::detail::SisoIteratorTraits::PrefixIncrement82 void operator()(state_type& state, 83 internal_iterator_type& it) const noexcept { 84 ++it; 85 state.second.clear(); 86 } 87 }; 88 89 struct Swap { operator ()libsemigroups::detail::SisoIteratorTraits::Swap90 void operator()(internal_iterator_type& it_this, 91 internal_iterator_type& it_that, 92 state_type& state_this, 93 state_type& state_that) const noexcept { 94 using std::swap; 95 swap(it_this, it_that); 96 swap(state_this, state_that); 97 } 98 }; 99 100 using EqualTo = void; 101 using NotEqualTo = void; 102 using PostfixIncrement = void; 103 }; 104 } // namespace detail 105 106 //! No doc 107 using const_silo_iterator = detail::ConstIteratorStateful< 108 detail::SisoIteratorTraits<const_wilo_iterator>>; 109 110 static_assert(std::is_default_constructible<const_silo_iterator>::value, 111 "forward iterator requires default-constructible"); 112 static_assert(std::is_copy_constructible<const_silo_iterator>::value, 113 "forward iterator requires copy-constructible"); 114 static_assert(std::is_copy_assignable<const_silo_iterator>::value, 115 "forward iterator requires copy-assignable"); 116 static_assert(std::is_destructible<const_silo_iterator>::value, 117 "forward iterator requires destructible"); 118 119 //! No doc 120 using const_sislo_iterator = detail::ConstIteratorStateful< 121 detail::SisoIteratorTraits<const_wislo_iterator>>; 122 123 static_assert(std::is_default_constructible<const_sislo_iterator>::value, 124 "forward iterator requires default-constructible"); 125 static_assert(std::is_copy_constructible<const_sislo_iterator>::value, 126 "forward iterator requires copy-constructible"); 127 static_assert(std::is_copy_assignable<const_sislo_iterator>::value, 128 "forward iterator requires copy-assignable"); 129 static_assert(std::is_destructible<const_sislo_iterator>::value, 130 "forward iterator requires destructible"); 131 132 //! Returns a forward iterator pointing to the 3rd parameter \p first. 133 //! 134 //! If incremented, the iterator will point to the next least lexicographic 135 //! string after \p w over \p alphabet with length less than \p upper_bound. 136 //! Iterators of the type returned by this function are equal whenever they 137 //! are obtained by advancing the return value of any call to \c cbegin_silo 138 //! by the same amount, or they are both obtained by any call to 139 //! \c cend_silo. 140 //! 141 //! \param alphabet the alphabet 142 //! \param upper_bound only strings of length less than this value are 143 //! considered; 144 //! \param first the starting point for the iteration; 145 //! \param last the ending point for the iteration. 146 //! 147 //! \returns An iterator of type \c const_silo_iterator. 148 //! 149 //! \exceptions 150 //! \no_libsemigroups_except 151 //! 152 //! \note 153 //! The parameter \p upper_bound is required because lexicographical 154 //! ordering is not a well-ordering, and there might be infinitely many 155 //! strings between a given pair of stringss. 156 //! 157 //! \warning 158 //! Copying iterators of this type is expensive. As a consequence, prefix 159 //! incrementing \c ++it the iterator \c it returned by \c cbegin_silo is 160 //! significantly cheaper than postfix incrementing \c it++. 161 //! 162 //! \warning 163 //! Iterators constructed using different parameters may not be equal, so 164 //! best not to loop over them. 165 //! 166 //! \sa cend_silo 167 //! 168 //! \par Example 169 //! \code 170 //! std::vector<std::string>(cbegin_silo("ba", 3, "b", "aaa"), 171 //! cend_silo("ba", 3, "b", "aaa")); 172 //! // {"b", "bb", "ba", "a", "ab", "aa"}; 173 //! \endcode 174 const_silo_iterator cbegin_silo(std::string const& alphabet, 175 size_t const upper_bound, 176 std::string const& first, 177 std::string const& last); 178 179 //! Returns a forward iterator pointing to one after the end of the range 180 //! from \p first to \p last. 181 //! 182 //! The iterator returned by this is still dereferencable and incrementable, 183 //! but does not point to a string in the correct range. 184 //! 185 //! \sa cbegin_silo 186 const_silo_iterator cend_silo(std::string const& alphabet, 187 size_t const upper_bound, 188 std::string const& first, 189 std::string const& last); 190 191 //! Returns a forward iterator pointing to the 2nd parameter \p first. 192 //! 193 //! If incremented, the iterator will point to the next least short-lex 194 //! string after \p w over \p alphabet. 195 //! Iterators of the type returned by this function are equal whenever they 196 //! are obtained by advancing the return value of any call to \c cbegin_sislo 197 //! by the same amount, or they are both obtained by any call to 198 //! \c cend_sislo. 199 //! 200 //! \param alphabet the alphabet 201 //! \param first the starting point for the iteration; 202 //! \param last the ending point for the iteration. 203 //! 204 //! \returns An iterator of type \c const_sislo_iterator. 205 //! 206 //! \exceptions 207 //! \no_libsemigroups_except 208 //! 209 //! \warning 210 //! Copying iterators of this type is expensive. As a consequence, prefix 211 //! incrementing \c ++it the iterator \c it returned by \c cbegin_sislo is 212 //! significantly cheaper than postfix incrementing \c it++. 213 //! 214 //! \warning 215 //! Iterators constructed using different parameters may not be equal, so 216 //! best not to loop over them. 217 //! 218 //! \sa cend_sislo 219 //! 220 //! \par Example 221 //! \code 222 //! std::vector<std::string>(cbegin_sislo("ba", "b", "bbb"), 223 //! cend_sislo("ba", "b", "bbb")); 224 //! // {"b", "b", "bb", "ba","ab", "aa"}; 225 //! \endcode 226 const_sislo_iterator cbegin_sislo(std::string const& alphabet, 227 std::string const& first, 228 std::string const& last); 229 230 //! Returns a forward iterator pointing to one after the end of the range 231 //! from \p first to \p last. 232 //! 233 //! The iterator returned by this is still dereferencable and incrementable, 234 //! but does not point to a string in the correct range. 235 //! 236 //! \sa cbegin_sislo 237 const_sislo_iterator cend_sislo(std::string const& alphabet, 238 std::string const& first, 239 std::string const& last); 240 241 } // namespace libsemigroups 242 243 #endif // LIBSEMIGROUPS_SISO_HPP_ 244