word-range.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2020-2025 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 declarations for function related to words (counting, and
// converting) in libsemigroups.
 
// TODO:
// * iwyu
// * nodiscard
// * tests for code coverage
 
#ifndef LIBSEMIGROUPS_WORD_RANGE_HPP_
#define LIBSEMIGROUPS_WORD_RANGE_HPP_
 
#include <cstddef>           // for size_t
#include <cstdint>           // for uint64_t, uint8_t
#include <initializer_list>  // for initializer_list
#include <limits>            // for numeric_limits
#include <string>            // for basic_string
#include <string_view>       // for string_view
#include <type_traits>       // for enable_if_t
#include <unordered_map>     // for vector, operator==
#include <utility>           // for forward
#include <variant>           // for visit, operator==
#include <vector>            // for vector, operator==
 
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LibsemigroupsException
#include "ranges.hpp"     // for begin, end
#include "types.hpp"      // for word_type
 
#include "detail/word-iterators.hpp"  // for const_wilo_iterator
 
namespace libsemigroups {
 
  enum class Order : uint8_t;  // forward decl
 
  namespace detail {
    std::string const& chars_in_human_readable_order();
  }

  template <typename Word>
  Word& reverse(Word&& w) {
    std::reverse(w.begin(), w.end());
    return w;
  }

  // Words


  [[nodiscard]] uint64_t number_of_words(size_t n, size_t min, size_t max);

  [[nodiscard]] word_type random_word(size_t length, size_t nr_letters);

  [[nodiscard]] detail::const_wilo_iterator cbegin_wilo(size_t      n,
                                                        size_t      upper_bound,
                                                        word_type&& first,
                                                        word_type&& last);

  [[nodiscard]] detail::const_wilo_iterator cbegin_wilo(size_t n,
                                                        size_t upper_bound,
                                                        word_type const& first,
                                                        word_type const& last);

  [[nodiscard]] detail::const_wilo_iterator
  cend_wilo(size_t n, size_t upper_bound, word_type&& first, word_type&& last);

  [[nodiscard]] detail::const_wilo_iterator cend_wilo(size_t n,
                                                      size_t upper_bound,
                                                      word_type const& first,
                                                      word_type const& last);

  [[nodiscard]] detail::const_wislo_iterator cbegin_wislo(size_t      n,
                                                          word_type&& first,
                                                          word_type&& last);

  [[nodiscard]] detail::const_wislo_iterator
  cbegin_wislo(size_t n, word_type const& first, word_type const& last);

  [[nodiscard]] detail::const_wislo_iterator cend_wislo(size_t      n,
                                                        word_type&& first,
                                                        word_type&& last);

  [[nodiscard]] detail::const_wislo_iterator cend_wislo(size_t           n,
                                                        word_type const& first,
                                                        word_type const& last);

  class WordRange {
   public:
    using size_type = typename std::vector<word_type>::size_type;

    using output_type = word_type const&;
 
   private:
    using const_iterator = std::variant<detail::const_wilo_iterator,
                                        detail::const_wislo_iterator>;
 
    size_type              _alphabet_size;
    mutable const_iterator _current;
    mutable const_iterator _end;
    mutable bool           _current_valid;
    word_type              _first;
    word_type              _last;
    Order                  _order;
    size_type              _upper_bound;
    mutable size_type      _visited;
 
    void set_iterator() const;
 
   public:
    [[nodiscard]] output_type get() const noexcept {
      set_iterator();
      return std::visit(
          [](auto& it) -> auto const& { return *it; }, _current);
    }

    void next() noexcept {
      set_iterator();
      if (!at_end()) {
        ++_visited;
      }
      std::visit([](auto& it) { ++it; }, _current);
    }

    [[nodiscard]] bool at_end() const noexcept {
      set_iterator();
      return _current == _end;
    }

    [[nodiscard]] size_t size_hint() const noexcept {
      return number_of_words(_alphabet_size, _first.size(), _last.size())
             - _visited;
      // This is only the actual size if _order is shortlex
    }

    [[nodiscard]] size_t count() const noexcept;
 
    // For some reason, there needs to be two doxygen comment lines here for
    // this to render.
    static constexpr bool is_finite = true;  // This may not always be true

    static constexpr bool is_idempotent = true;

    WordRange() {
      init();
    }

    WordRange& init();

    WordRange(WordRange const&);

    WordRange(WordRange&&);

    WordRange& operator=(WordRange const&);

    WordRange& operator=(WordRange&&);

    ~WordRange();

    WordRange& alphabet_size(size_type n) noexcept {
      _current_valid &= (n == _alphabet_size);
      _alphabet_size = n;
      return *this;
    }

    [[nodiscard]] size_type alphabet_size() const noexcept {
      return _alphabet_size;
    }

    WordRange& first(word_type const& frst) {
      _current_valid &= (frst == _first);
      _first = frst;
      return *this;
    }

    [[nodiscard]] word_type const& first() const noexcept {
      return _first;
    }

    WordRange& last(word_type const& lst) {
      _current_valid &= (lst == _last);
      _last = lst;
      return *this;
    }

    [[nodiscard]] word_type const& last() const noexcept {
      return _last;
    }

    WordRange& order(Order val);

    [[nodiscard]] Order order() const noexcept {
      return _order;
    }

    WordRange& upper_bound(size_type n) {
      _current_valid &= (n == _upper_bound);
      _upper_bound = n;
      return *this;
    }

    [[nodiscard]] size_type upper_bound() const noexcept {
      return _upper_bound;
    }

    WordRange& min(size_type val) {
      first(word_type(val, 0));
      return *this;
    }
 
    // No corresponding getter for min, because what would it mean? Could be the
    // length of first(), but that doesn't correspond well to what happens with
    // the setter.

    WordRange& max(size_type val) {
      last(word_type(val, 0));
      return *this;
    }

    // REQUIRED so that we can use StringRange in range based loops
    auto begin() const noexcept {
      return rx::begin(*this);
    }

    // REQUIRED so that we can use StringRange in range based loops
    auto end() const noexcept {
      return rx::end(*this);
    }
 
    // TODO(now) this doc doesn't feel nice, but JDE can't think of a good way
    // to write it.
    // Required so StringRange can accurately set _current_valid
    bool valid() const noexcept {
      return _current_valid;
    }
  };

  [[nodiscard]] std::string to_human_readable_repr(WordRange const& wr,
                                                   size_t max_width = 72);

  // Strings -> Words

  // TODO (later) a version that takes a word_type, so that we can permute the
  // letters in a word
  class ToWord {
   public:
    // Not noexcept because std::array::fill isn't
    ToWord() : _alphabet_map() {
      init();
    }
 
    // TODO (later) noexcept?
    ToWord(ToWord const&);

    ToWord(ToWord&&);

    ToWord& operator=(ToWord const&);

    ToWord& operator=(ToWord&&);

    ~ToWord();

    ToWord& init() {
      _alphabet_map.clear();
      return *this;
    }

    explicit ToWord(std::string const& alphabet) : _alphabet_map() {
      init(alphabet);
    }

    ToWord& init(std::string const& alphabet);

    [[nodiscard]] bool empty() const noexcept {
      return _alphabet_map.empty();
    }

    [[nodiscard]] std::string alphabet() const;

    [[nodiscard]] bool can_convert_letter(char const& c) const {
      return _alphabet_map.count(c) == 1;
    }

    void call_no_checks(word_type& output, std::string const& input) const;

    [[nodiscard]] word_type call_no_checks(std::string const& input) const {
      word_type output;
      call_no_checks(output, input);
      return output;
    }

    void operator()(word_type& output, std::string const& input) const;

    [[nodiscard]] word_type operator()(std::string const& input) const {
      word_type output;
                operator()(output, input);
      return output;
    }

    [[nodiscard]] letter_type operator()(char input) const {
      // TODO improve this
      // FIXME(1) it also doesn't work for example to_word('a') returns 63 for
      // some reason
      word_type output;
      // operator()(output, std::string_view(&input, 1));
      operator()(output, std::string(input, 1));
      return output[0];
    }

    [[nodiscard]] letter_type call_no_checks(char input) const {
      return _alphabet_map.find(input)->second;
    }
 
    template <typename InputRange>
    struct Range;

    template <typename InputRange,
              typename = std::enable_if_t<rx::is_input_or_sink_v<InputRange>>>
    [[nodiscard]] constexpr auto operator()(InputRange&& input) const {
      using Inner = rx::get_range_type_t<InputRange>;
      return Range<Inner>(std::forward<InputRange>(input), *this);
    }
 
   private:
    std::unordered_map<char, letter_type> _alphabet_map;
  };
 
  template <typename InputRange>
  struct ToWord::Range {
    using output_type = word_type;
 
    static constexpr bool is_finite     = rx::is_finite_v<InputRange>;
    static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
 
    InputRange _input;
    ToWord     _to_word;
 
    explicit Range(InputRange const& input, ToWord const& t_wrd)
        : _input(input), _to_word(t_wrd) {}
 
    explicit Range(InputRange&& input, ToWord const& t_wrd)
        : _input(std::move(input)), _to_word(t_wrd) {}
 
    explicit Range(InputRange const& input, ToWord&& t_wrd)
        : _input(input), _to_word(std::move(t_wrd)) {}
 
    explicit Range(InputRange&& input, ToWord&& t_wrd)
        : _input(std::move(input)), _to_word(std::move(t_wrd)) {}
 
    // Not noexcept because ToWord()() isn't
    [[nodiscard]] output_type get() const {
      return _to_word.operator()(_input.get());
    }
 
    constexpr void next() noexcept {
      _input.next();
    }
 
    [[nodiscard]] constexpr bool at_end() const noexcept {
      return _input.at_end();
    }
 
    [[nodiscard]] constexpr size_t size_hint() const noexcept {
      return _input.size_hint();
    }
  };

  [[nodiscard]] inline std::string to_human_readable_repr(ToWord const& twrd) {
    return fmt::format("<ToWord object with alphabet \"{}\">", twrd.alphabet());
  }

  // Words -> Strings

  class ToString {
   public:
    ToString() : _alphabet_map() {
      init();
    }
 
    // TODO (later) noexcept?
    ToString(ToString const&);

    ToString(ToString&&);

    ToString& operator=(ToString const&);

    ToString& operator=(ToString&&);

    ~ToString();

    ToString& init() noexcept {
      _alphabet_map.clear();
      return *this;
    }

    explicit ToString(std::string const& alphabet) : _alphabet_map() {
      init(alphabet);
    }

    ToString& init(std::string const& alphabet);

    [[nodiscard]] bool empty() const noexcept {
      return _alphabet_map.empty();
    }

    [[nodiscard]] std::string alphabet() const;

    [[nodiscard]] bool can_convert_letter(letter_type const& l) const {
      return _alphabet_map.count(l) == 1;
    }

    void call_no_checks(std::string& output, word_type const& input) const;

    [[nodiscard]] std::string call_no_checks(word_type const& input) const {
      std::string output;
      call_no_checks(output, input);
      return output;
    }

    void operator()(std::string& output, word_type const& input) const;

    [[nodiscard]] std::string operator()(word_type const& input) const {
      std::string output;
                  operator()(output, input);
      return output;
    }

    template <typename Int>
    [[nodiscard]] std::string
    operator()(std::initializer_list<Int> input) const {
      static_assert(std::is_integral_v<Int>);
      word_type copy(input.begin(), input.end());
      return    operator()(copy);
    }
 
    template <typename InputRange>
    struct Range;

    template <typename InputRange,
              typename = std::enable_if_t<rx::is_input_or_sink_v<InputRange>>>
    [[nodiscard]] constexpr auto operator()(InputRange&& input) const {
      using Inner = rx::get_range_type_t<InputRange>;
      return Range<Inner>(std::forward<InputRange>(input), *this);
    }
 
   private:
    // We could use std::vector<char> (or similar) here, but an
    // unordered_ordered hap has been used instead to allow for potential future
    // conversions between different types.
    std::unordered_map<letter_type, char> _alphabet_map;
  };
 
  template <typename InputRange>
  struct ToString::Range {
    using output_type = std::string;
 
    static constexpr bool is_finite     = rx::is_finite_v<InputRange>;
    static constexpr bool is_idempotent = rx::is_idempotent_v<InputRange>;
 
    InputRange _input;
    ToString   _to_string;
 
    Range(InputRange const& input, ToString const& t_str)
        : _input(input), _to_string(t_str) {}
 
    Range(InputRange&& input, ToString const& t_str)
        : _input(std::move(input)), _to_string(t_str) {}
 
    Range(InputRange const& input, ToString&& t_str)
        : _input(input), _to_string(std::move(t_str)) {}
 
    Range(InputRange&& input, ToString&& t_str)
        : _input(std::move(input)), _to_string(std::move(t_str)) {}
 
    ~Range();
 
    // Not noexcept because ToString()() isn't
    [[nodiscard]] output_type get() const {
      return _to_string(_input.get());
    }
 
    constexpr void next() noexcept {
      _input.next();
    }
 
    [[nodiscard]] constexpr bool at_end() const noexcept {
      return _input.at_end();
    }
 
    [[nodiscard]] constexpr size_t size_hint() const noexcept {
      return _input.size_hint();
    }
  };
 
  // NOTE: This is a terrible hack to avoid compiler warnings. Maybe remove in
  // the future?
#if defined(__clang__)
  template <typename InputRange>
  ToString::Range<InputRange>::~Range<InputRange>() = default;
#elif defined(__GNUC__)
  template <typename InputRange>
  ToString::Range<InputRange>::~Range() = default;
#endif

  [[nodiscard]] inline std::string
  to_human_readable_repr(ToString const& tstr) {
    return fmt::format("<ToString object with alphabet \"{}\">",
                       tstr.alphabet());
  }

  // StringRange
 
  namespace detail {
    void throw_if_random_string_should_throw(std::string const& alphabet,
                                             size_t             min,
                                             size_t             max);
  }  // namespace detail

  std::string random_string(std::string const& alphabet, size_t length);

  std::string random_string(std::string const& alphabet,
                            size_t             min,
                            size_t             max);

  auto inline random_strings(std::string const& alphabet,
                             size_t             number,
                             size_t             min,
                             size_t             max) {
    detail::throw_if_random_string_should_throw(alphabet, min, max);
 
    // Lambda must capture by copy, as the lambda will exist outside the scope
    // of this function once the range is returned.
    return rx::generate([alphabet, min, max] {
             return random_string(alphabet, min, max);
           })
           | rx::take(number);
  }

  // This can in many places be replaced by "WordRange | ToString" but this
  // makes some things more awkward and so we retain this class for its
  // convenience.
  class StringRange {
   public:
    using size_type = typename std::vector<std::string>::size_type;

    using output_type = std::string const&;
 
   private:
    mutable std::string _current;
    mutable bool        _current_valid;
    std::string         _letters;
    ToWord              _to_word;
    ToString            _to_string;
    WordRange           _word_range;
 
    void init_current() const {
      if (!_current_valid) {
        _current       = _to_string(_word_range.get());
        _current_valid = true;
      }
    }
 
   public:
    output_type get() const {
      init_current();
      return _current;
    }

    void next() noexcept {
      _word_range.next();
      _current_valid = false;
    }

    bool at_end() const noexcept {
      return _word_range.at_end();
    }

    size_t size_hint() const noexcept {
      return _word_range.size_hint();
    }

    size_t count() const noexcept {
      return _word_range.count();
    }

    static constexpr bool is_finite = true;  // This may not always be true

    static constexpr bool is_idempotent = true;

    StringRange() {
      init();
    }

    StringRange& init();

    StringRange(StringRange const&);

    StringRange(StringRange&&);

    StringRange& operator=(StringRange const&);

    StringRange& operator=(StringRange&&);

    ~StringRange();

    StringRange& alphabet(std::string const& x);

    [[nodiscard]] std::string const& alphabet() const noexcept {
      return _letters;
    }

    StringRange& first(std::string const& frst) {
      _word_range.first(_to_word(frst));
      _current_valid &= _word_range.valid();
      return *this;
    }

    [[nodiscard]] std::string first() const noexcept {
      return _to_string(_word_range.first());
    }

    StringRange& last(std::string const& lst) {
      _word_range.last(_to_word(lst));
      _current_valid &= _word_range.valid();
      return *this;
    }

    [[nodiscard]] std::string last() const noexcept {
      return _to_string(_word_range.last());
    }

    StringRange& order(Order val) {
      _word_range.order(val);
      _current_valid &= _word_range.valid();
      return *this;
    }

    [[nodiscard]] Order order() const noexcept {
      return _word_range.order();
    }

    StringRange& upper_bound(size_type n) {
      _word_range.upper_bound(n);
      _current_valid &= _word_range.valid();
      return *this;
    }

    [[nodiscard]] size_type upper_bound() const noexcept {
      return _word_range.upper_bound();
    }

    StringRange& min(size_type val) {
      _word_range.min(val);
      _current_valid &= _word_range.valid();
      return *this;
    }
 
    // No corresponding getter for min, because what would it mean? Could be the
    // length of first(), but that doesn't correspond well to what happens with
    // the setter.

    StringRange& max(size_type val) {
      _word_range.max(val);
      _current_valid &= _word_range.valid();
      return *this;
    }

    // REQUIRED so that we can use StringRange in range based loops
    auto begin() const noexcept {
      return rx::begin(*this);
    }

    // REQUIRED so that we can use StringRange in range based loops
    auto end() const noexcept {
      return rx::end(*this);
    }
  };

  [[nodiscard]] std::string to_human_readable_repr(StringRange const& sr,
                                                   size_t max_width = 72);

  // Literals

  namespace literals {
    word_type operator"" _w(const char* w, size_t n);

    word_type operator"" _w(const char* w);

    std::string operator"" _p(const char* w, size_t n);

    std::string operator"" _p(const char* w);
  }  // namespace literals


  namespace words {

    [[nodiscard]] letter_type human_readable_index(char c);

    template <typename Word = std::string>
    typename Word::value_type human_readable_letter(size_t i) {
      // This check ensures that i is not too large to be converted to a
      // Word::value_type. This is check is only needed if the number of
      // distinct Word::value objects is less than the number of distinct size_t
      // objects.
      if constexpr (sizeof(typename Word::value_type) < sizeof(size_t)) {
        if (i > std::numeric_limits<typename Word::value_type>::max()
                    - std::numeric_limits<typename Word::value_type>::min()) {
          LIBSEMIGROUPS_EXCEPTION(
              "expected the argument to be in the range [0, {}), found {}",
              1 + std::numeric_limits<typename Word::value_type>::max()
                  - std::numeric_limits<typename Word::value_type>::min(),
              i);
        }
      }
      if constexpr (!std::is_same_v<Word, std::string>) {
        return static_cast<typename Word::value_type>(i);
      } else {
        // Choose visible characters a-zA-Z0-9 first before anything else
        // The ascii ranges for these characters are: [97, 123), [65, 91),
        // [48, 58) so the remaining range of chars that are appended to the end
        // after these chars are [0,48), [58, 65), [91, 97), [123, 255]
        return detail::chars_in_human_readable_order()[i];
      }
    }

    // operator+

    word_type operator+(word_type const& u, word_type const& w);

    word_type operator+(word_type const& u, letter_type w);

    word_type operator+(letter_type w, word_type const& u);

    // operator+=

    static inline void operator+=(word_type& u, word_type const& v) {
      u.insert(u.end(), v.cbegin(), v.cend());
    }

    inline void operator+=(word_type& u, letter_type a) {
      u.push_back(a);
    }

    inline void operator+=(letter_type a, word_type& u) {
      u.insert(u.begin(), a);
    }

    // pow

    template <typename Word>
    void pow_inplace(Word& w, size_t n);
    // No pow_inplace for string_view or initializer_list because there's no
    // where to store the result.

    template <typename Word>
    Word pow(Word const& x, size_t n) {
      Word y(x);
      pow_inplace(y, n);
      return y;
    }

    word_type pow(std::initializer_list<letter_type> ilist, size_t n);

    std::string pow(std::string_view w, size_t n);

    // prod

    template <typename Container, typename Word = Container>
    Word prod(Container const& elts, int first, int last, int step = 1);

    static inline word_type prod(std::initializer_list<letter_type> ilist,
                                 int                                first,
                                 int                                last,
                                 int                                step = 1) {
      return prod<word_type>(word_type(ilist), first, last, step);
    }

    static inline std::string
    prod(std::string_view sv, int first, int last, int step = 1) {
      return prod<std::string>(std::string(sv), first, last, step);
    }

    static inline word_type prod(std::initializer_list<word_type> const& elts,
                                 int                                     first,
                                 int                                     last,
                                 int step = 1) {
      return prod<std::vector<word_type>, word_type>(
          std::vector<word_type>(elts), first, last, step);
    }

    static inline std::string
    prod(std::initializer_list<std::string_view> const& sv,
         int                                            first,
         int                                            last,
         int                                            step = 1) {
      return prod<std::vector<std::string_view>, std::string>(
          sv, first, last, step);
    }

    template <typename Container, typename Word = Container>
    Word prod(Container const& elts, size_t last) {
      return prod(elts, 0, static_cast<int>(last), 1);
    }

    static inline word_type prod(std::initializer_list<letter_type> const& elts,
                                 size_t last) {
      return prod(elts, 0, static_cast<int>(last), 1);
    }

    static inline std::string prod(std::string_view elts, size_t last) {
      return prod<std::string_view, std::string>(
          elts, 0, static_cast<int>(last), 1);
    }

    static inline word_type prod(std::initializer_list<word_type> const& elts,
                                 size_t                                  last) {
      return prod(elts, 0, static_cast<int>(last), 1);
    }

    static inline std::string
    prod(std::initializer_list<std::string_view> const& elts, size_t last) {
      return prod<std::vector<std::string_view>, std::string>(
          std::vector<std::string_view>(elts), 0, static_cast<int>(last), 1);
    }

    // pow - implementation
 
    template <typename Word>
    void pow_inplace(Word& x, size_t n) {
      Word y(x);
      x.reserve(x.size() * n);
      if (n % 2 == 0) {
        x = Word({});
      }
 
      while (n > 1) {
        y += y;
        n /= 2;
        if (n % 2 == 1) {
          x += y;
        }
      }
    }

    // prod - implementation
 
    // Note: we could do a version of the below using insert on words, where
    // the step is +/- 1.
    template <typename Container, typename Word>
    Word prod(Container const& elts, int first, int last, int step) {
      if (step == 0) {
        LIBSEMIGROUPS_EXCEPTION("the 4th argument must not be 0");
      } else if (((first < last && step > 0) || (first > last && step < 0))
                 && elts.size() == 0) {
        LIBSEMIGROUPS_EXCEPTION("the 1st argument must not be empty if the "
                                "given range is not empty");
        // TODO Is int signed? Should this also contain
        // std::numeric_limits<int>::min?
      } else if (elts.size() > std::numeric_limits<int>::max()) {
        LIBSEMIGROUPS_EXCEPTION(
            "the 1st argument must have size less than or equal to {}",
            std::numeric_limits<int>::max());
      }
      Word      result;
      int const s = elts.size();
 
      if (first < last) {
        if (step < 0) {
          return result;
        }
        result.reserve((last - first) / step);
 
        for (int i = first; i < last; i += step) {
          size_t const a = (i % s + s) % s;
          LIBSEMIGROUPS_ASSERT(static_cast<int>(a) < s);
          result += elts[a];
        }
      } else {
        if (step > 0) {
          return result;
        }
        size_t steppos = static_cast<size_t>(-step);
        result.reserve((first - last) / steppos);
        for (int i = first; i > last; i += step) {
          size_t const a = (i % s + s) % s;
          LIBSEMIGROUPS_ASSERT(static_cast<int>(a) < s);
          result += elts[a];
        }
      }
      return result;
    }
  }  // namespace words
  //
}  // namespace libsemigroups
 
#endif  // LIBSEMIGROUPS_WORD_RANGE_HPP_