action.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-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 a generic implementation of a class Action which
// represents the action of a semigroup on a set.
 
#ifndef LIBSEMIGROUPS_ACTION_HPP_
#define LIBSEMIGROUPS_ACTION_HPP_
 
#include <cstddef>        // for size_t
#include <stack>          // for stack
#include <type_traits>    // for is_trivially_default_construc...
#include <unordered_map>  // for unordered_map
#include <utility>        // for pair
#include <vector>         // for vector
 
#include "adapters.hpp"    // for One
#include "constants.hpp"   // for UNDEFINED
#include "debug.hpp"       // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"   // for LIBSEMIGROUPS_EXCEPTION
#include "forest.hpp"      // for Forest
#include "gabow.hpp"       // for Gabow
#include "runner.hpp"      // for Runner
#include "word-graph.hpp"  // for WordGraph
 
#include "detail/bruidhinn-traits.hpp"  // for detail::BruidhinnTraits
#include "detail/report.hpp"            // for report_default
 
namespace libsemigroups {

  enum class side {
    left,
    right
  };

  template <typename Element,
            typename Point,
            typename Func,
            typename Traits,
            side LeftOrRight>
  class Action : public Runner, private detail::BruidhinnTraits<Point> {
    // Action - typedefs - private
 
    using internal_point_type =
        typename detail::BruidhinnTraits<Point>::internal_value_type;
    using internal_const_point_type =
        typename detail::BruidhinnTraits<Point>::internal_const_value_type;
    using internal_const_reference =
        typename detail::BruidhinnTraits<Point>::internal_const_reference;
 
    struct InternalEqualTo : private detail::BruidhinnTraits<Point> {
      using EqualTo = typename Traits::EqualTo;
      bool operator()(internal_const_point_type x,
                      internal_const_point_type y) const {
        return EqualTo()(this->to_external_const(x),
                         this->to_external_const(y));
      }
    };
 
    struct InternalHash : private detail::BruidhinnTraits<Point> {
      using Hash = typename Traits::Hash;
      size_t operator()(internal_const_point_type x) const {
        return Hash()(this->to_external_const(x));
      }
    };
 
    using Degree = typename Traits::Degree;
 
    // Forward decls
    class MultiplierCache;
    struct Options;
 
    static_assert(
        std::is_const<internal_const_point_type>::value
            || std::is_const<typename std::remove_pointer<
                internal_const_point_type>::type>::value,
        "internal_const_element_type must be const or pointer to const");
 
   public:
    // Action - typedefs - public

    using element_type = Element;

    using point_type = Point;

    using index_type = size_t;

    using action_type = Func;

    template <typename Elment,
              typename Pint,
              typename Fnc,
              typename Trits,
              side LftOrRight>
    // TODO make this a free function, and non-friend
    friend std::ostringstream&
    operator<<(std::ostringstream&                                 os,
               Action<Elment, Pint, Fnc, Trits, LftOrRight> const& action);

    // TODO make this a free function, and non-friend
    friend std::ostream& operator<<(std::ostream& os, Action const& action) {
      os << detail::to_string(action);
      return os;
    }

    // Action - iterators - public

    using const_iterator
        = detail::BruidhinnConstIterator<point_type,
                                         std::vector<internal_point_type>>;

    using const_reference_point_type =
        typename detail::BruidhinnTraits<Point>::const_reference;

    using const_pointer_point_type =
        typename detail::BruidhinnTraits<Point>::const_pointer;
 
   private:
    // Action - internal types with call operators - private
 
    using ActionOp = Func;
    using One      = typename Traits::One;
    using Product  = typename Traits::Product;
    using Swap     = typename Traits::Swap;
 
    static_assert(std::is_trivially_default_constructible<ActionOp>::value,
                  "the 3rd template parameter Func is not trivially "
                  "default constructible");
    // TODO(2) more static assertions

    // Action - product functions for left/right multiplication  - private
 
    auto internal_product(element_type&       xy,
                          element_type const& x,
                          element_type const& y) {
      if constexpr (LeftOrRight == side::right) {
        Product()(xy, x, y);
      } else {
        Product()(xy, y, x);
      }
    }

    // Action - data members - private
 
    // TODO(1) change size_t -> uint32_t
    std::vector<element_type> _gens;
    WordGraph<uint32_t>       _graph;
    std::unordered_map<internal_const_point_type,
                       size_t,
                       InternalHash,
                       InternalEqualTo>
                                     _map;
    Options                          _options;
    std::vector<internal_point_type> _orb;
    MultiplierCache                  _multipliers_from_scc_root;
    MultiplierCache                  _multipliers_to_scc_root;
    size_t                           _pos;
    Gabow<uint32_t>                  _scc;
    internal_point_type              _tmp_point;
    bool                             _tmp_point_init;
 
   public:
    // Action - constructor + destructor - public

    Action();

    Action& init();

    //! Default copy constructor.
    Action(Action const& that) : Action() {
      *this = that;
    }

    //! Default move constructor.
    Action(Action&& that) : Action() {
      *this = std::move(that);
    }

    Action& operator=(Action const&);

    Action& operator=(Action&&);
 
    ~Action();

    // Action - modifiers - public

    Action& reserve(size_t val);

    Action& add_seed(const_reference_point_type seed);

    //! Constant.
    Action& add_generator(element_type const& gen) {
      throw_if_bad_degree(gen);
      return add_generator_no_checks(gen);
    }

    //! Constant.
    Action& add_generator_no_checks(element_type const& gen) {
      _gens.push_back(gen);
      return *this;
    }

    // Action - member functions: position, empty, size, etc - public

    //! Constant.
    [[nodiscard]] size_t number_of_generators() const noexcept {
      return _gens.size();
    }

    //! Constant.
    [[nodiscard]] std::vector<Element> const& generators() const noexcept {
      return _gens;
    }

    [[nodiscard]] index_type position(const_reference_point_type pt) const;

    //! Constant.
    [[nodiscard]] bool empty() const noexcept {
      return _orb.empty();
    }

    [[nodiscard]] inline const_reference_point_type
    operator[](index_type pos) const noexcept {
      LIBSEMIGROUPS_ASSERT(pos < _orb.size());
      return this->to_external_const(_orb[pos]);
    }

    //! Constant.
    [[nodiscard]] inline const_reference_point_type at(index_type pos) const {
      return this->to_external_const(_orb.at(pos));
    }

    //! points in the orbit and \f$n\f$ is the number of generators.
    [[nodiscard]] size_t size() {
      run();
      return _orb.size();
    }

    //! Constant.
    [[nodiscard]] size_t current_size() const noexcept {
      return _orb.size();
    }

    //! Constant.
    [[nodiscard]] const_iterator cbegin() const noexcept {
      return const_iterator(_orb.cbegin());
    }

    //! \copydoc cbegin
    [[nodiscard]] const_iterator begin() const noexcept {
      return cbegin();
    }

    // TODO(1) add a reference to the ranges page when it exists
    [[nodiscard]] auto range() const noexcept {
      return rx::iterator_range(_orb.cbegin(), _orb.cend())
             | rx::transform([this](auto const& pt) {
                 return this->to_external_const(pt);
               });
    }

    //! Constant.
    [[nodiscard]] const_iterator cend() const noexcept {
      return const_iterator(_orb.cend());
    }

    //! \copydoc cend
    [[nodiscard]] const_iterator end() const noexcept {
      return cend();
    }

    // Action - member functions: strongly connected components - public

    //! Constant.
    [[nodiscard]] bool cache_scc_multipliers() const noexcept {
      return _options._cache_scc_multipliers;
    }

    //! Constant.
    Action& cache_scc_multipliers(bool val) noexcept {
      _options._cache_scc_multipliers = val;
      return *this;
    }

    //! enumerated orbit.
    [[nodiscard]] element_type multiplier_from_scc_root(index_type pos) {
      return multiplier_private<true>(
          _multipliers_from_scc_root, _scc.spanning_forest(), pos);
    }

    //! enumerated orbit.
    [[nodiscard]] element_type multiplier_to_scc_root(index_type pos) {
      return multiplier_private<false>(
          _multipliers_to_scc_root, _scc.reverse_spanning_forest(), pos);
    }

    [[nodiscard]] const_reference_point_type
    root_of_scc(const_reference_point_type x) {
      // TODO(2) this could be a helper
      return root_of_scc(position(x));
    }

    //! enumerated orbit.
    [[nodiscard]] const_reference_point_type root_of_scc(index_type pos) {
      return this->to_external_const(_orb[_scc.root_of(pos)]);
    }

    //! enumerated orbit.
    [[nodiscard]] WordGraph<uint32_t> const& word_graph() {
      run();
      return _graph;
    }

    //! enumerated orbit.
    [[nodiscard]] Gabow<uint32_t> const& scc() {
      run();
      return _scc;
    }

    // These functions allow the action operation (defined by Func) to be called
    // on an instance of Action. This isn't very helpful in C++ code, but is in
    // the python bindings, where figuring out the type of Func is a bit fiddly.
    static void apply(point_type&         result,
                      point_type const&   pt,
                      element_type const& x) {
      ActionOp()(result, pt, x);
    }

    //! \no_libsemigroups_except
    [[nodiscard]] static point_type apply(point_type const&   pt,
                                          element_type const& x) {
      point_type result;
      apply(result, pt, x);
      return result;
    }
 
   private:
    // Runner - pure virtual member functions - private
 
    [[nodiscard]] bool finished_impl() const override {
      return (_pos == _orb.size()) && (_graph.out_degree() == _gens.size());
    }
 
    void run_impl() override;

    // Action - member functions - private
 
    template <bool Forward>
    element_type multiplier_private(MultiplierCache& mults,
                                    Forest const&    f,
                                    index_type       pos);
 
    void throw_if_index_out_of_range(index_type i) const;
    void throw_if_no_generators() const;
    void throw_if_bad_degree(element_type const&) const;
  };  // class Action

  template <typename Element, typename Point>
  struct ActionTraits {
    using Degree = ::libsemigroups::Degree<Element>;
    using Hash = ::libsemigroups::Hash<Point>;
    using EqualTo = ::libsemigroups::EqualTo<Point>;
    using Swap = ::libsemigroups::Swap<Element>;
    using One = ::libsemigroups::One<Element>;
    using Product = ::libsemigroups::Product<Element>;
  };

  template <typename Element,
            typename Point,
            typename Func   = ImageRightAction<Element, Point>,
            typename Traits = ActionTraits<Element, Point>>
  using RightAction = Action<Element, Point, Func, Traits, side::right>;

  template <typename Element,
            typename Point,
            typename Func   = ImageLeftAction<Element, Point>,
            typename Traits = ActionTraits<Element, Point>>
  using LeftAction = Action<Element, Point, Func, Traits, side::left>;

  template <typename Element,
            typename Point,
            typename Func,
            typename Traits,
            side LeftOrRight>
  std::string to_human_readable_repr(
      Action<Element, Point, Func, Traits, LeftOrRight> const& action);
}  // namespace libsemigroups
 
#include "action.tpp"
#endif  // LIBSEMIGROUPS_ACTION_HPP_