| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/semigroups/libsemigroups/include/libsemigroups/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 18.5.2025 mit Größe 8 kB |
|
Quelle wilo.hpp Sprache: C |
|||||||||
|
//
// libsemigroups - C++ library for semigroups and monoids // Copyright (C) 2020 James D. Mitchell // // This program is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program. If not, see <http://www.gnu.org/licenses/>. // // This file contains the implementation of functionality for generating words // in the free monoid over an alphabet with a given number of letters between a // given pair of words. // // WILO = Words In Lexicographic Order #ifndef LIBSEMIGROUPS_WILO_HPP_ #define LIBSEMIGROUPS_WILO_HPP_ #include <cstddef> // for size_t #include <iterator> // for forward_iterator_tag #include <vector> // for vector #include "constants.hpp" // for UNDEFINED #include "order.hpp" // for lexicographical_compare #include "types.hpp" // for word_type // TODO(later) // 1. const_wilo_iterator using letters other than 0, 1, ... , n - 1. Same // approach as const_silo_iterator. namespace libsemigroups { //! No doc class const_wilo_iterator { public: //! No doc using size_type = typename std::vector<word_type>::size_type; //! No doc using difference_type = typename std::vector<word_type>::difference_type; //! No doc using const_pointer = typename std::vector<word_type>::const_pointer; //! No doc using pointer = typename std::vector<word_type>::pointer; //! No doc using const_reference = typename std::vector<word_type>::const_reference; //! No doc using reference = typename std::vector<word_type>::reference; //! No doc using value_type = word_type; //! No doc using iterator_category = std::forward_iterator_tag; // None of the constructors are noexcept because the corresponding // constructors for std::vector aren't (until C++17). //! No doc const_wilo_iterator() = default; //! No doc const_wilo_iterator(const_wilo_iterator const&); //! No doc const_wilo_iterator(const_wilo_iterator&&) = default; //! No doc const_wilo_iterator& operator=(const_wilo_iterator const&) = default; //! No doc const_wilo_iterator& operator=(const_wilo_iterator&&) = default; //! No doc const_wilo_iterator(size_type n, size_type upper_bound, word_type&& first, word_type&& last) : _current(std::move(first)), _index(), _letter(0), _upper_bound(upper_bound - 1), _last(std::move(last)), _number_letters(n) { _index = (_current == _last ? UNDEFINED : size_type(0)); } //! No doc ~const_wilo_iterator(); //! No doc bool operator==(const_wilo_iterator const& that) const noexcept { return _index == that._index; } //! No doc bool operator!=(const_wilo_iterator const& that) const noexcept { return !(this->operator==(that)); } //! No doc const_reference operator*() const noexcept { return _current; } //! No doc const_pointer operator->() const noexcept { return &_current; } // prefix //! No doc const_wilo_iterator const& operator++() noexcept { if (_index != UNDEFINED) { ++_index; begin: if (_current.size() < _upper_bound && _letter != _number_letters) { _current.push_back(_letter); _letter = 0; if (lexicographical_compare(_current, _last)) { return *this; } } else if (!_current.empty()) { _letter = ++_current.back(); _current.pop_back(); goto begin; } _index = UNDEFINED; } return *this; } //! No doc // postfix const_wilo_iterator operator++(int) noexcept { const_wilo_iterator copy(*this); ++(*this); return copy; } //! No doc void swap(const_wilo_iterator& that) noexcept { std::swap(_letter, that._letter); std::swap(_index, that._index); std::swap(_upper_bound, that._upper_bound); std::swap(_last, that._last); std::swap(_number_letters, that._number_letters); _current.swap(that._current); } private: word_type _current; size_type _index; letter_type _letter; size_type _upper_bound; word_type _last; size_type _number_letters; }; // Assert that the forward iterator requirements are met static_assert(std::is_default_constructible<const_wilo_iterator>::value, "forward iterator requires default-constructible"); static_assert(std::is_copy_constructible<const_wilo_iterator>::value, "forward iterator requires copy-constructible"); static_assert(std::is_copy_assignable<const_wilo_iterator>::value, "forward iterator requires copy-assignable"); static_assert(std::is_destructible<const_wilo_iterator>::value, "forward iterator requires destructible"); //! No doc inline void swap(const_wilo_iterator& x, const_wilo_iterator& y) noexcept { x.swap(y); } //! Returns a forward iterator pointing to the 3rd parameter \p first. //! //! If incremented, the iterator will point to the next least lexicographic //! word after \p w over an \p n letter alphabet with length less than \p //! upper_bound. Iterators of the type returned by this function are equal //! whenever they are obtained by advancing the return value of any call to //! \c cbegin_wilo by the same amount, or they are both obtained by any call //! to \c cend_wilo. //! //! \param n the number of letters in the alphabet; //! \param upper_bound only words of length less than this value are //! considered; //! \param first the starting point for the iteration; //! \param last the value one past the end of the last value in the //! iteration. //! //! \returns An iterator of type \c const_wilo_iterator. //! //! \exceptions //! \no_libsemigroups_except //! //! \note //! The parameter \p upper_bound is required because lexicographical //! ordering is not a well-ordering, and there might be infinitely many words //! between a given pair of words. //! //! \warning //! Copying iterators of this type is expensive. As a consequence, prefix //! incrementing \c ++it the iterator \c it returned by \c cbegin_wilo is //! significantly cheaper than postfix incrementing \c it++. //! //! \warning //! Iterators constructed using different parameters may not be equal, so //! best not to loop over them. //! //! \sa cend_wilo //! //! \par Example //! \code //! std::vector<word_type>(cbegin_wilo(2, 3, {0}, {1, 1, 1}), //! cend_wilo(2, 3, {0}, {1, 1, 1})); //! // {{0}, {0, 0}, {0, 1}, {1}, {1, 0}, {1, 1}}; //! \endcode const_wilo_iterator cbegin_wilo(size_t n, size_t upper_bound, word_type&& first, word_type&& last); //! \copydoc cbegin_wilo(size_t const, size_t const, word_type&&, word_type&&) const_wilo_iterator cbegin_wilo(size_t n, size_t upper_bound, word_type const& first, word_type const& last); //! Returns a forward iterator pointing to one after the end of the range //! from \p first to \p last. //! //! The iterator returned by this function is still dereferenceable and //! incrementable, but does not point to a word in the correct range. //! //! \sa cbegin_wilo const_wilo_iterator cend_wilo(size_t n, size_t upper_bound, word_type&& first, word_type&& last); //! \copydoc cend_wilo(size_t const, size_t const, word_type&&, word_type&&) const_wilo_iterator cend_wilo(size_t n, size_t upper_bound, word_type const& first, word_type const& last); } // namespace libsemigroups namespace std { template <> inline void swap(libsemigroups::const_wilo_iterator& x, libsemigroups::const_wilo_iterator& y) noexcept { x.swap(y); } } // namespace std #endif // LIBSEMIGROUPS_WILO_HPP_ ¤ Dauer der Verarbeitung: 0.24 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28