Quelle siso.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 a lexicographic or short-lex order.
//
// SILO  = Strings In Lexicographic Order
// SISLO = Strings In Short-Lex Order
// SISO  = Strings In Some Order

// TODO(later):
// 1. cbegin_silo and cend_silo for rvalue references to strings
// 2. cbegin_sislo and cend_sislo for rvalue references to strings

#ifndef LIBSEMIGROUPS_SISO_HPP_
#define LIBSEMIGROUPS_SISO_HPP_

#include <cstddef>   // for size_t, ptrdiff_t, ...
#include <iterator>  // for forward_iterator_tag
#include <string>    // for string
#include <utility>   // for pair

#include "iterator.hpp"  // for detail::ConstIteratorStateful
#include "wilo.hpp"      // for const_wilo_iterator
#include "wislo.hpp"     // for const_wislo_iterator
#include "word.hpp"      // for word_to_string

namespace libsemigroups {
  namespace detail {
    // This is a traits class for ConstIteratorStateful in iterator.hpp
    template <typename T>
    struct SisoIteratorTraits {
      // state_type::first = alphabet, state_type::second = current value
      using state_type             = std::pair<std::string, std::string>;
      using internal_iterator_type = T;
      using value_type             = std::string;
      using reference              = std::string&;
      using const_reference        = std::string const&;
      using difference_type        = std::ptrdiff_t;
      using size_type              = std::size_t;
      using const_pointer          = std::string const*;
      using pointer                = std::string*;
      using iterator_category      = std::forward_iterator_tag;

      struct Deref {
        const_reference
        operator()(state_type&                   state,
                   internal_iterator_type const& it) const noexcept {
          if (state.second.empty()) {
            detail::word_to_string(state.first, *it, state.second);
          }
          return state.second;
        }
      };

      struct AddressOf {
        const_pointer
        operator()(state_type&                   state,
                   internal_iterator_type const& it) const noexcept {
          Deref()(state, it);  // to ensure that state.second is initialised
          return &state.second;
        }
      };

      struct PrefixIncrement {
        void operator()(state_type&             state,
                        internal_iterator_type& it) const noexcept {
          ++it;
          state.second.clear();
        }
      };

      struct AddAssign {
        void operator()(state_type&             state,
                        internal_iterator_type& it,
                        size_t                  val) const noexcept {
          std::advance(it, val);
          state.second.clear();
        }
      };

      struct Swap {
        void operator()(internal_iterator_type& it_this,
                        internal_iterator_type& it_that,
                        state_type&             state_this,
                        state_type&             state_that) const noexcept {
          using std::swap;
          swap(it_this, it_that);
          swap(state_this, state_that);
        }
      };

      using EqualTo          = void;
      using NotEqualTo       = void;
      using PostfixIncrement = void;
    };
  }  // namespace detail

  //! No doc
  using const_silo_iterator = detail::ConstIteratorStateful<
      detail::SisoIteratorTraits<const_wilo_iterator>>;

  static_assert(std::is_default_constructible<const_silo_iterator>::value,
                "forward iterator requires default-constructible");
  static_assert(std::is_copy_constructible<const_silo_iterator>::value,
                "forward iterator requires copy-constructible");
  static_assert(std::is_copy_assignable<const_silo_iterator>::value,
                "forward iterator requires copy-assignable");
  static_assert(std::is_destructible<const_silo_iterator>::value,
                "forward iterator requires destructible");

  //! No doc
  using const_sislo_iterator = detail::ConstIteratorStateful<
      detail::SisoIteratorTraits<const_wislo_iterator>>;

  static_assert(std::is_default_constructible<const_sislo_iterator>::value,
                "forward iterator requires default-constructible");
  static_assert(std::is_copy_constructible<const_sislo_iterator>::value,
                "forward iterator requires copy-constructible");
  static_assert(std::is_copy_assignable<const_sislo_iterator>::value,
                "forward iterator requires copy-assignable");
  static_assert(std::is_destructible<const_sislo_iterator>::value,
                "forward iterator requires destructible");

  //! Returns a forward iterator pointing to the 3rd parameter \p first.
  //!
  //! If incremented, the iterator will point to the next least lexicographic
  //! string after \p w over \p 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_silo
  //! by the same amount, or they are both obtained by any call to
  //! \c cend_silo.
  //!
  //! \param alphabet the alphabet
  //! \param upper_bound  only strings of length less than this value are
  //! considered;
  //! \param first the starting point for the iteration;
  //! \param last the ending point for the iteration.
  //!
  //! \returns An iterator of type \c const_silo_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
  //! strings between a given pair of strings.
  //!
  //! \warning
  //! Copying iterators of this type is expensive.  As a consequence, prefix
  //! incrementing \c ++it the iterator \c it returned by \c cbegin_silo 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_silo
  //!
  //! \par Example
  //! \code
  //! std::vector<std::string>(cbegin_silo("ba", 3, "b", "aaa"),
  //!                          cend_silo("ba", 3, "b", "aaa"));
  //! // {"b", "bb", "ba", "a", "ab", "aa"};
  //! \endcode
  const_silo_iterator cbegin_silo(std::string const& alphabet,
                                  size_t const       upper_bound,
                                  std::string const& first,
                                  std::string 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 string in the correct range.
  //!
  //! \sa cbegin_silo
  const_silo_iterator cend_silo(std::string const& alphabet,
                                size_t const       upper_bound,
                                std::string const& first,
                                std::string const& last);

  //! Returns a forward iterator pointing to the 2nd parameter \p first.
  //!
  //! If incremented, the iterator will point to the next least short-lex
  //! string after \p w over \p 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_sislo
  //! by the same amount, or they are both obtained by any call to
  //! \c cend_sislo.
  //!
  //! \param alphabet 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_sislo_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_sislo 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_sislo
  //!
  //! \par Example
  //! \code
  //! std::vector<std::string>(cbegin_sislo("ba", "b", "bbb"),
  //!                          cend_sislo("ba", "b", "bbb"));
  //! // {"b", "b", "bb", "ba","ab", "aa"};
  //! \endcode
  const_sislo_iterator cbegin_sislo(std::string const& alphabet,
                                    std::string const& first,
                                    std::string 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 string in the correct range.
  //!
  //! \sa cbegin_sislo
  const_sislo_iterator cend_sislo(std::string const& alphabet,
                                  std::string const& first,
                                  std::string const& last);

  class Sislo {
   public:
    Sislo()                        = default;
    Sislo(Sislo const&)            = default;
    Sislo(Sislo&&)                 = default;
    Sislo& operator=(Sislo const&) = default;
    Sislo& operator=(Sislo&&)      = default;

    Sislo& alphabet(std::string const& lphbt) {
      _alphabet = lphbt;
      return *this;
    }

    std::string const& alphabet() const {
      return _alphabet;
    }

    char letter(size_t i) const {
      return _alphabet[i];
    }

    Sislo& first(std::string const& first) {
      _first = first;
      return *this;
    }

    Sislo& first(size_t min) {
      _first = std::string(min, letter(0));
      return *this;
    }

    std::string const& first() const noexcept {
      return _first;
    }

    Sislo& last(std::string const& last) {
      _last = last;
      return *this;
    }

    Sislo& last(size_t max) {
      _last = std::string(max, letter(0));
      return *this;
    }

    std::string const& last() const noexcept {
      return _last;
    }

    const_sislo_iterator cbegin() const noexcept {
      return cbegin_sislo(_alphabet, _first, _last);
    }

    const_sislo_iterator cend() const noexcept {
      return cend_sislo(_alphabet, _first, _last);
    }

   private:
    std::string _alphabet;
    std::string _first;
    std::string _last;
  };

}  // namespace libsemigroups

#endif  // LIBSEMIGROUPS_SISO_HPP_

quality95%

¤ 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.