presentation.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2022-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 the declaration of a class template for semigroup or
// monoid presentations. The idea is to provide a shallow wrapper around a
// vector of words, with some checks that the vector really defines a
// presentation, (i.e. it's consistent with its alphabet etc), and some related
// functionality.
 
#ifndef LIBSEMIGROUPS_PRESENTATION_HPP_
#define LIBSEMIGROUPS_PRESENTATION_HPP_
 
#include <algorithm>         // for reverse, sort
#include <cctype>            // for isprint
#include <cmath>             // for pow
#include <cstring>           // for size_t, strlen
#include <initializer_list>  // for initializer_list
#include <iterator>          // for distance
#include <limits>            // for numeric_limits
#include <map>               // for map
#include <numeric>           // for accumulate
#include <string>            // for basic_string, operator==
#include <tuple>             // for tie, tuple
#include <type_traits>       // for enable_if_t
#include <unordered_map>     // for operator==, operator!=
#include <unordered_set>     // for unordered_set
#include <utility>           // for move, pair
#include <vector>            // for vector, operator!=
 
#include "adapters.hpp"    // for Hash, EqualTo
#include "constants.hpp"   // for Max, UNDEFINED, operator==
#include "debug.hpp"       // for LIBSEMIGROUPS_ASSERT
#include "order.hpp"       // for ShortLexCompare
#include "ranges.hpp"      // for seq, operator|, rx, take, chain, is_sorted
#include "types.hpp"       // for word_type
#include "ukkonen.hpp"     // for GreedyReduceHelper, Ukkonen
#include "word-range.hpp"  // for operator+
 
#include "detail/fmt.hpp"     // for format
#include "detail/string.hpp"  // for maximum_common_prefix
#include "detail/uf.hpp"      // for Duf
 
namespace libsemigroups {


  struct PresentationBase {};

  template <typename Word>
  class Presentation : public PresentationBase {
   public:
    using word_type = Word;

    using letter_type = typename word_type::value_type;

    using const_iterator = typename std::vector<word_type>::const_iterator;

    using iterator = typename std::vector<word_type>::iterator;

    using size_type = typename std::vector<word_type>::size_type;
 
   private:
    word_type                                  _alphabet;
    std::unordered_map<letter_type, size_type> _alphabet_map;
    bool                                       _contains_empty_word;
 
   public:
    std::vector<word_type> rules;

    Presentation();

    Presentation& init();

    Presentation(Presentation const&);

    Presentation(Presentation&&);

    Presentation& operator=(Presentation const&);

    Presentation& operator=(Presentation&&);
 
    ~Presentation();

    [[nodiscard]] word_type const& alphabet() const noexcept {
      return _alphabet;
    }
 
    // TODO(later) alphabet_no_checks

    // TODO(1) Rename alphabet_size
    Presentation& alphabet(size_type n);

    Presentation& alphabet(word_type const& lphbt);

    Presentation& alphabet(word_type&& lphbt);

    Presentation& alphabet_from_rules();

    [[nodiscard]] letter_type letter_no_checks(size_type i) const {
      LIBSEMIGROUPS_ASSERT(i < _alphabet.size());
      return _alphabet[i];
    }

    [[nodiscard]] letter_type letter(size_type i) const;

    [[nodiscard]] size_type index_no_checks(letter_type val) const {
      return _alphabet_map.find(val)->second;
    }

    [[nodiscard]] size_type index(letter_type val) const;

    [[nodiscard]] bool in_alphabet(letter_type val) const {
      return _alphabet_map.find(val) != _alphabet_map.cend();
    }

    template <typename Iterator1, typename Iterator2>
    Presentation& add_rule_no_checks(Iterator1 lhs_begin,
                                     Iterator1 lhs_end,
                                     Iterator2 rhs_begin,
                                     Iterator2 rhs_end) {
      rules.emplace_back(lhs_begin, lhs_end);
      rules.emplace_back(rhs_begin, rhs_end);
      return *this;
    }

    template <typename Iterator1, typename Iterator2>
    Presentation& add_rule(Iterator1 lhs_begin,
                           Iterator1 lhs_end,
                           Iterator2 rhs_begin,
                           Iterator2 rhs_end) {
      throw_if_letter_not_in_alphabet(lhs_begin, lhs_end);
      throw_if_letter_not_in_alphabet(rhs_begin, rhs_end);
      return add_rule_no_checks(lhs_begin, lhs_end, rhs_begin, rhs_end);
    }

    letter_type add_generator();

    void add_generator_no_checks(letter_type x);

    void add_generator(letter_type x);

    void remove_generator_no_checks(letter_type x);

    void remove_generator(letter_type x);

    [[nodiscard]] bool contains_empty_word() const noexcept {
      return _contains_empty_word;
    }

    Presentation& contains_empty_word(bool val) noexcept {
      _contains_empty_word = val;
      return *this;
    }

    void throw_if_alphabet_has_duplicates() const {
      decltype(_alphabet_map) alphabet_map;
      throw_if_alphabet_has_duplicates(alphabet_map);
    }

    void throw_if_letter_not_in_alphabet(letter_type c) const;

    template <typename Iterator1, typename Iterator2>
    void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const;

    void throw_if_bad_rules() const;

    void throw_if_bad_alphabet_or_rules() const {
      throw_if_alphabet_has_duplicates();
      throw_if_bad_rules();
    }
 
   private:
    void try_set_alphabet(decltype(_alphabet_map)& alphabet_map,
                          word_type&               old_alphabet);
    void throw_if_alphabet_has_duplicates(
        decltype(_alphabet_map)& alphabet_map) const;
  };  // class Presentation

  template <typename Word>
  Presentation(Presentation<Word> const&) -> Presentation<Word>;

  template <typename Word>
  Presentation(Presentation<Word>&&) -> Presentation<Word>;

  namespace presentation {

    template <typename Iterator>
    void throw_if_odd_number_of_rules(Iterator first, Iterator last) {
      if ((std::distance(first, last) % 2) == 1) {
        LIBSEMIGROUPS_EXCEPTION(
            "expected even number of words in \"rules\", found {}",
            std::distance(first, last));
      }
    }

    template <typename Word>
    void throw_if_odd_number_of_rules(Presentation<Word> const& p) {
      throw_if_odd_number_of_rules(p.rules.cbegin(), p.rules.cend());
    }

    template <typename Word>
    void throw_if_not_normalized(Presentation<Word> const& p,
                                 std::string_view          arg = "1st") {
      auto first = std::begin(p.alphabet()), last = std::end(p.alphabet());
      if (!std::is_sorted(first, last)) {
        LIBSEMIGROUPS_EXCEPTION("the {} argument (presentation) must have "
                                "sorted alphabet, found {}",
                                arg,
                                p.alphabet());
      }
 
      auto it = std::max_element(first, last);
      if (it != last && *it != p.alphabet().size() - 1) {
        LIBSEMIGROUPS_EXCEPTION("the {} argument (presentation) has invalid "
                                "alphabet, expected [0, ..., {}] found {}",
                                arg,
                                p.alphabet().size() - 1,
                                p.alphabet());
      }
    }

    template <typename Word, typename Iterator>
    void throw_if_bad_rules(Presentation<Word> const& p,
                            Iterator                  first,
                            Iterator                  last) {
      // TODO(0) check if there are an odd number of rules
      for (auto it = first; it != last; ++it) {
        p.throw_if_letter_not_in_alphabet(it->cbegin(), it->cend());
      }
    }

    template <typename Word>
    void throw_if_bad_inverses(Presentation<Word> const& p, Word const& vals);

    template <typename Word>
    void add_rule_no_checks(Presentation<Word>& p,
                            Word const&         lhop,
                            Word const&         rhop) {
      p.add_rule_no_checks(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
    }

    template <typename Word>
    void add_rule(Presentation<Word>& p, Word const& lhop, Word const& rhop) {
      p.add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
    }

    void add_rule_no_checks(Presentation<std::string>& p,
                            char const*                lhop,
                            char const*                rhop);

    void add_rule(Presentation<std::string>& p,
                  char const*                lhop,
                  char const*                rhop);

    void add_rule(Presentation<std::string>& p,
                  std::string const&         lhop,
                  char const*                rhop);

    void add_rule(Presentation<std::string>& p,
                  char const*                lhop,
                  std::string const&         rhop);

    void add_rule_no_checks(Presentation<std::string>& p,
                            std::string const&         lhop,
                            char const*                rhop);

    void add_rule_no_checks(Presentation<std::string>& p,
                            char const*                lhop,
                            std::string const&         rhop);

    template <typename Word, typename Letter>
    void add_rule_no_checks(Presentation<Word>&           p,
                            std::initializer_list<Letter> lhop,
                            std::initializer_list<Letter> rhop) {
      p.add_rule_no_checks(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
    }

    template <typename Word, typename Letter>
    void add_rule(Presentation<Word>&           p,
                  std::initializer_list<Letter> lhop,
                  std::initializer_list<Letter> rhop) {
      p.add_rule(lhop.begin(), lhop.end(), rhop.begin(), rhop.end());
    }

    template <typename Word, typename Iterator>
    void add_rules(Presentation<Word>& p, Iterator first, Iterator last) {
      for (auto it = first; it != last; it += 2) {
        add_rule(p, *it, *(it + 1));
      }
    }

    template <typename Word, typename Iterator>
    void add_rules_no_checks(Presentation<Word>& p,
                             Iterator            first,
                             Iterator            last) {
      for (auto it = first; it != last; it += 2) {
        add_rule_no_checks(p, *it, *(it + 1));
      }
    }

    template <typename Word>
    void add_rules_no_checks(Presentation<Word>&       p,
                             Presentation<Word> const& q) {
      add_rules_no_checks(p, q.rules.cbegin(), q.rules.cend());
    }

    template <typename Word>
    void add_rules(Presentation<Word>& p, Presentation<Word> const& q) {
      add_rules(p, q.rules.cbegin(), q.rules.cend());
    }

    template <typename Word>
    [[nodiscard]] bool contains_rule(Presentation<Word>& p,
                                     Word const&         lhs,
                                     Word const&         rhs);

    template <typename Word>
    void add_identity_rules(Presentation<Word>&                      p,
                            typename Presentation<Word>::letter_type e);

    template <typename Word>
    void add_zero_rules(Presentation<Word>&                      p,
                        typename Presentation<Word>::letter_type z);

    template <typename Word>
    void add_inverse_rules(Presentation<Word>&                      p,
                           Word const&                              vals,
                           typename Presentation<Word>::letter_type e
                           = UNDEFINED);

    void add_inverse_rules(Presentation<std::string>& p,
                           char const*                vals,
                           char                       e = UNDEFINED);

    template <typename Word>
    void remove_duplicate_rules(Presentation<Word>& p);

    template <typename Word>
    void remove_trivial_rules(Presentation<Word>& p);

    template <typename Word>
    void reduce_complements(Presentation<Word>& p);

    template <typename Word>
    bool sort_each_rule(Presentation<Word>& p);

    template <typename Word, typename Compare>
    bool sort_each_rule(Presentation<Word>& p, Compare cmp);
 
    // TODO(later) is_each_rule_sorted?

    template <typename Word, typename Compare>
    void sort_rules(Presentation<Word>& p, Compare cmp);

    template <typename Word>
    void sort_rules(Presentation<Word>& p) {
      sort_rules(p, ShortLexCompare());
    }

    template <typename Word, typename Compare>
    bool are_rules_sorted(Presentation<Word> const& p, Compare cmp);

    template <typename Word>
    bool are_rules_sorted(Presentation<Word> const& p) {
      return are_rules_sorted(p, ShortLexCompare());
    }

    // TODO(later) complexity
    template <typename Word>
    Word longest_subword_reducing_length(Presentation<Word>& p);

    // TODO(later) complexity
    template <typename Word, typename Iterator>
    typename Presentation<Word>::letter_type
    replace_word_with_new_generator(Presentation<Word>& p,
                                    Iterator            first,
                                    Iterator            last);

    // TODO(later) complexity
    template <typename Word>
    typename Presentation<Word>::letter_type
    replace_word_with_new_generator(Presentation<Word>& p, Word const& w) {
      return replace_word_with_new_generator(p, w.cbegin(), w.cend());
    }

    typename Presentation<std::string>::letter_type
    replace_word_with_new_generator(Presentation<std::string>& p,
                                    char const*                w);

    // TODO(later) complexity
    template <typename Word>
    void replace_subword(Presentation<Word>& p,
                         Word const&         existing,
                         Word const&         replacement);

    template <typename Word, typename Iterator1, typename Iterator2>
    void replace_subword(Presentation<Word>& p,
                         Iterator1           first_existing,
                         Iterator1           last_existing,
                         Iterator2           first_replacement,
                         Iterator2           last_replacement);

    inline void replace_subword(Presentation<std::string>& p,
                                char const*                existing,
                                char const*                replacement) {
      replace_subword(p,
                      existing,
                      existing + std::strlen(existing),
                      replacement,
                      replacement + std::strlen(replacement));
    }

    template <typename Word>
    void replace_word(Presentation<Word>& p,
                      Word const&         existing,
                      Word const&         replacement);

    template <typename Iterator>
    size_t length(Iterator first, Iterator last);

    template <typename Word>
    size_t length(Presentation<Word> const& p) {
      return length(p.rules.cbegin(), p.rules.cend());
    }

    template <typename Word>
    void reverse(Presentation<Word>& p) {
      for (auto& rule : p.rules) {
        std::reverse(rule.begin(), rule.end());
      }
    }

    // This is the only place that JDE can find where a helper that modifies its
    // first argument is not void. This is deliberate, since if we weren't to
    // return anything, the first parameter would go out of scope immediately
    // after this call and this function would be pointless .
    template <typename Word>
    Presentation<Word>&& reverse(Presentation<Word>&& p) {
      for (auto& rule : p.rules) {
        std::reverse(rule.begin(), rule.end());
      }
      return std::move(p);
    }

    template <typename Word>
    void normalize_alphabet(Presentation<Word>& p);

    template <typename Word>
    void change_alphabet(Presentation<Word>& p, Word const& new_alphabet);

    inline void change_alphabet(Presentation<std::string>& p,
                                char const*                new_alphabet) {
      change_alphabet(p, std::string(new_alphabet));
    }

    template <typename Iterator>
    Iterator longest_rule(Iterator first, Iterator last);

    template <typename Word>
    typename std::vector<Word>::const_iterator
    longest_rule(Presentation<Word> const& p) {
      return longest_rule(p.rules.cbegin(), p.rules.cend());
    }

    template <typename Iterator>
    Iterator shortest_rule(Iterator first, Iterator last);

    template <typename Word>
    typename std::vector<Word>::const_iterator
    shortest_rule(Presentation<Word> const& p) {
      return shortest_rule(p.rules.cbegin(), p.rules.cend());
    }

    template <typename Iterator>
    typename Iterator::value_type::size_type longest_rule_length(Iterator first,
                                                                 Iterator last);

    template <typename Word>
    typename Word::size_type longest_rule_length(Presentation<Word> const& p) {
      return longest_rule_length(p.rules.cbegin(), p.rules.cend());
    }

    template <typename Iterator>
    typename Iterator::value_type::size_type
    shortest_rule_length(Iterator first, Iterator last);

    template <typename Word>
    typename Word::size_type shortest_rule_length(Presentation<Word> const& p) {
      return shortest_rule_length(p.rules.cbegin(), p.rules.cend());
    }

    template <typename Word>
    void remove_redundant_generators(Presentation<Word>& p);

    template <typename Word>
    typename Presentation<Word>::letter_type
    first_unused_letter(Presentation<Word> const& p);

    template <typename Word>
    typename Presentation<Word>::letter_type
    make_semigroup(Presentation<Word>& p);

    template <typename Word>
    void greedy_reduce_length(Presentation<Word>& p);

    template <typename Word>
    void greedy_reduce_length_and_number_of_gens(Presentation<Word>& p);

    // not noexcept because std::vector::operator[] isn't
    template <typename Word>
    bool is_strongly_compressible(Presentation<Word> const& p);

    // not noexcept because is_strongly_compressible isn't
    template <typename Word>
    bool strongly_compress(Presentation<Word>& p);

    template <typename Word>
    bool reduce_to_2_generators(Presentation<Word>& p, size_t index = 0);

    template <typename Word>
    void add_idempotent_rules_no_checks(Presentation<Word>& p,
                                        Word const&         letters) {
      for (auto x : letters) {
        add_rule_no_checks(p, {x, x}, {x});
      }
    }

    template <typename Word>
    void add_involution_rules_no_checks(Presentation<Word>& p,
                                        word_type const&    letters) {
      for (auto x : letters) {
        add_rule_no_checks(p, {x, x}, {});
      }
    }

    template <typename Word>
    void add_commutes_rules_no_checks(Presentation<Word>& p,
                                      Word const&         letters1,
                                      Word const&         letters2);

    template <typename Word>
    void add_commutes_rules_no_checks(Presentation<Word>& p,
                                      Word const&         letters) {
      add_commutes_rules_no_checks(p, letters, letters);
    }

    template <typename Word>
    void add_commutes_rules_no_checks(Presentation<Word>&         p,
                                      Word const&                 letters,
                                      std::initializer_list<Word> words);

    template <typename Word1, typename Word2>
    void balance_no_checks(Presentation<Word1>& p,
                           Word2 const&         letters,
                           Word2 const&         inverses);

    template <typename Word>
    void balance_no_checks(Presentation<Word>& p,
                           Word const&         letters,
                           Word const&         inverses) {
      balance_no_checks<Word, Word>(p, letters, inverses);
    }

    inline void balance_no_checks(Presentation<std::string>& p,
                                  char const*                letters,
                                  char const*                inverses) {
      balance_no_checks(
          p, std::string_view(letters), std::string_view(inverses));
    }

    inline void balance_no_checks(Presentation<std::string>& p,
                                  std::string_view           letters,
                                  std::string_view           inverses) {
      balance_no_checks<std::string, std::string_view>(p, letters, inverses);
    }
 
    // TODO(later) add balance that checks p contains empty word, no duplicate
    // letters in alphabet, and inverses are valid.
 
    // // TODO(later) do a proper version of this, where the inverses are
    // // specified, rather than being assumed to be upper/lower cases
    // template <typename Word>
    // void add_cyclic_conjugates(Presentation<Word>& p,
    //                            Word const&         lhs,
    //                            Word const&         rhs);

    std::string to_gap_string(Presentation<word_type> const& p,
                              std::string const&             var_name);

    std::string to_gap_string(Presentation<std::string> const& p,
                              std::string const&               var_name);
 
  }  // namespace presentation

  template <typename Word>
  class InversePresentation : public Presentation<Word> {
   public:
    using word_type = typename Presentation<Word>::word_type;

    using letter_type = typename Presentation<Word>::letter_type;

    using const_iterator = typename Presentation<Word>::const_iterator;

    using iterator = typename Presentation<Word>::iterator;

    using size_type = typename Presentation<Word>::size_type;
 
   private:
    word_type _inverses;
 
   public:
    using Presentation<Word>::Presentation;
 
    // TODO(later) init functions

    explicit InversePresentation(Presentation<Word> const& p)
        : Presentation<Word>(p), _inverses() {}

    explicit InversePresentation(Presentation<Word>&& p)
        : Presentation<Word>(p), _inverses() {}

    InversePresentation& inverses_no_checks(word_type const& w);

    InversePresentation& inverses(word_type const& w) {
      Presentation<Word>::throw_if_alphabet_has_duplicates();
      presentation::throw_if_bad_inverses(*this, w);
      return inverses_no_checks(w);
    }

    word_type const& inverses() const noexcept {
      return _inverses;
    }

    letter_type inverse(letter_type x) const;

    void throw_if_bad_alphabet_rules_or_inverses() const {
      // TODO(0) check if this is used appropriately after rename
      Presentation<Word>::throw_if_bad_alphabet_or_rules();
      presentation::throw_if_bad_inverses(*this, inverses());
    }
  };

  // TODO(later) also we could do a more sophisticated version of this
  template <typename Word>
  bool operator==(Presentation<Word> const& lhop,
                  Presentation<Word> const& rhop) {
    return lhop.alphabet() == rhop.alphabet() && lhop.rules == rhop.rules;
  }

  // TODO(later) also we could do a more sophisticated version of this
  template <typename Word>
  bool operator==(InversePresentation<Word> const& lhop,
                  InversePresentation<Word> const& rhop) {
    return lhop.alphabet() == rhop.alphabet() && lhop.rules == rhop.rules
           && lhop.inverses() == rhop.inverses();
  }

  template <typename Word>
  bool operator!=(Presentation<Word> const& lhop,
                  Presentation<Word> const& rhop) {
    return !(lhop == rhop);
  }

  template <typename Word>
  bool operator!=(InversePresentation<Word> const& lhop,
                  InversePresentation<Word> const& rhop) {
    return !(lhop == rhop);
  }

  template <typename Word>
  std::string to_human_readable_repr(Presentation<Word> const& p);

  template <typename Word>
  std::string to_human_readable_repr(InversePresentation<Word> const& p);
 
  namespace detail {
    template <typename T>
    struct IsPresentationHelper : std::false_type {};
 
    template <typename T>
    struct IsPresentationHelper<Presentation<T>> : std::true_type {};
 
    template <typename T>
    struct IsPresentationHelper<InversePresentation<T>> : std::true_type {};
 
    template <typename T>
    struct IsInversePresentationHelper : std::false_type {};
 
    template <typename T>
    struct IsInversePresentationHelper<InversePresentation<T>>
        : std::true_type {};
 
    class GreedyReduceHelper {
     private:
      size_t              _best;
      int                 _best_goodness;
      std::vector<size_t> _distance_from_root;
      std::vector<size_t> _num_leafs;
      std::vector<size_t> _scratch;
      std::vector<size_t> _suffix_index;
 
     public:
      using const_iterator = typename Ukkonen::const_iterator;
 
      explicit GreedyReduceHelper(Ukkonen const& u);
 
      GreedyReduceHelper()                                     = delete;
      GreedyReduceHelper(GreedyReduceHelper const&)            = delete;
      GreedyReduceHelper(GreedyReduceHelper&&)                 = delete;
      GreedyReduceHelper& operator=(GreedyReduceHelper const&) = delete;
      GreedyReduceHelper& operator=(GreedyReduceHelper&&)      = delete;
      ~GreedyReduceHelper();
 
      void pre_order(Ukkonen const& u, size_t v);
      void post_order(Ukkonen const& u, size_t v);
      std::pair<const_iterator, const_iterator> yield(Ukkonen const& u);
    };
  }  // namespace detail

  template <typename T>
  static constexpr bool IsInversePresentation
      = detail::IsInversePresentationHelper<T>::value;

  template <typename T>
  static constexpr bool IsPresentation = detail::IsPresentationHelper<T>::value;
 
}  // namespace libsemigroups
 
#include "presentation.tpp"
 
#endif  // LIBSEMIGROUPS_PRESENTATION_HPP_