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_

quality100%

¤ Dauer der Verarbeitung: 0.5 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.