Quelle  wislo.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 some functionality for generating elements in the free
// monoid over an alphabet with a given number of letters up to a given length
// in short-lex order.
//
// WISLO = Words In Short-Lex Order

#ifndef LIBSEMIGROUPS_WISLO_HPP_
#define LIBSEMIGROUPS_WISLO_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 shortlex_compare
#include "types.hpp"      // for word_type

// TODO(later)
// 1. rvalue reference cend_wislo and cbegin_wislo

namespace libsemigroups {
  //! No doc
  class const_wislo_iterator final {
   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_wislo_iterator() = default;
    //! No doc
    const_wislo_iterator(const_wislo_iterator const&);
    //! No doc
    const_wislo_iterator(const_wislo_iterator&&) = default;
    //! No doc
    const_wislo_iterator& operator=(const_wislo_iterator const&) = default;
    //! No doc
    const_wislo_iterator& operator=(const_wislo_iterator&&) = default;

    //! No doc
    const_wislo_iterator(size_type n, word_type&& first, word_type&& last)
        : _current(std::move(first)),
          _index(),
          _last(std::move(last)),
          _number_letters(n) {
      _current.reserve(last.size());
      _index = (_current == _last ? UNDEFINED : size_t(0));
    }

    //! No doc
    ~const_wislo_iterator();

    //! No doc
    bool operator==(const_wislo_iterator const& that) const noexcept {
      return _index == that._index;
    }

    //! No doc
    bool operator!=(const_wislo_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_wislo_iterator const& operator++() noexcept {
      if (_index != UNDEFINED) {
        ++_index;
        size_t n = _current.size();
        while (!_current.empty() && ++_current.back() == _number_letters) {
          _current.pop_back();
        }
        _current.resize((_current.empty() ? n + 1 : n), 0);
        if (!shortlex_compare(_current, _last)) {
          _index = UNDEFINED;
        }
      }
      return *this;
    }

    // postfix
    //! No doc
    const_wislo_iterator operator++(int) noexcept {
      const_wislo_iterator copy(*this);
      ++(*this);
      return copy;
    }

    //! No doc
    void swap(const_wislo_iterator& that) noexcept {
      std::swap(_current, that._current);
      std::swap(_index, that._index);
      std::swap(_last, that._last);
      std::swap(_number_letters, that._number_letters);
    }

   private:
    word_type _current;
    size_type _index;
    word_type _last;
    size_type _number_letters;
  };

  // Assert that the forward iterator requirements are met
  static_assert(std::is_default_constructible<const_wislo_iterator>::value,
                "forward iterator requires default-constructible");
  static_assert(std::is_copy_constructible<const_wislo_iterator>::value,
                "forward iterator requires copy-constructible");
  static_assert(std::is_copy_assignable<const_wislo_iterator>::value,
                "forward iterator requires copy-assignable");
  static_assert(std::is_destructible<const_wislo_iterator>::value,
                "forward iterator requires destructible");

  //! Returns a forward iterator pointing to the 2nd parameter \p first.
  //!
  //! If incremented, the iterator will point to the next least short-lex
  //! word after \p w over an \p n letter alphabet. 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_wislo by the same
  //! amount, or they are both obtained by any call to \c cend_wislo.
  //!
  //! \param n the number of letters in the alphabet;
  //! \param first the starting point for the iteration;
  //! \param last the ending point for the iteration.
  //!
  //! \returns An iterator of type \c const_wislo_iterator.
  //!
  //! \exceptions
  //! \no_libsemigroups_except
  //!
  //! \warning
  //! Copying iterators of this type is expensive.  As a consequence, prefix
  //! incrementing \c ++it the iterator \c it returned by \c cbegin_wislo 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_wislo
  //!
  //! \par Example
  //! \code
  //! std::vector<word_type>(cbegin_wislo(2, {0}, {0, 0, 0}),
  //!                        cend_wislo(2,  {0}, {0, 0, 0}));
  //! // {{0}, {1}, {0, 0}, {0, 1}, {1, 0}, {1, 1}};
  //! \endcode
  const_wislo_iterator cbegin_wislo(size_t      n,
                                    word_type&& first,
                                    word_type&& last);

  //! \copydoc cbegin_wislo(size_t const, word_type&&, word_type&&)
  const_wislo_iterator cbegin_wislo(size_t           n,
                                    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 is still dereferenceable and incrementable,
  //! but does not point to a word in the correct range.
  //!
  //! \sa cbegin_wislo
  const_wislo_iterator cend_wislo(size_t      n,
                                  word_type&& first,
                                  word_type&& last);

  //! \copydoc cend_wislo(size_t const, word_type&&, word_type&&)
  const_wislo_iterator cend_wislo(size_t           n,
                                  word_type const& first,
                                  word_type const& last);
  //! No doc
  inline void swap(const_wislo_iterator& x, const_wislo_iterator& y) noexcept {
    x.swap(y);
  }

}  // namespace libsemigroups

namespace std {
  template <>
  inline void swap(libsemigroups::const_wislo_iterator& x,
                   libsemigroups::const_wislo_iterator& y) noexcept {
    x.swap(y);
  }
}  // namespace std
#endif  // LIBSEMIGROUPS_WISLO_HPP_