word-graph-view.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2025 Nadim Searight
//
// 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 an implementation of word graph views, a thin layer over
// word graphs exposing a chosen range of nodes
 
#ifndef LIBSEMIGROUPS_WORD_GRAPH_VIEW_HPP_
#define LIBSEMIGROUPS_WORD_GRAPH_VIEW_HPP_
 
#include <type_traits>  // for is_integral
#include <utility>      // for pair
 
#include "config.hpp"      // for LIBSEMIGROUPS_DEBUG
#include "debug.hpp"       // for LIBSEMIGROUPS_ASSERT
#include "word-graph.hpp"  // for word_graph pointer
 
#include "detail/containers.hpp"
#include "detail/int-range.hpp"  // for IntRange
 
namespace libsemigroups {
  template <typename Node>
  class WordGraphView {
   public:
    static_assert(std::is_integral<Node>(),
                  "the template parameter Node must be an integral type!");
    static_assert(
        std::is_unsigned<Node>(),
        "the template parameter Node must be an unsigned integral type!");

    using node_type = Node;

    using label_type = Node;

    using size_type = std::size_t;

    using const_iterator_nodes =
        typename detail::IntRange<Node>::const_iterator;

    using const_reverse_iterator_nodes =
        typename detail::IntRange<Node>::const_reverse_iterator;

    using const_iterator_targets =
        typename detail::DynamicArray2<Node>::const_iterator;
 
   private:
    WordGraph<Node> const* _graph;
    node_type              _start;
    node_type              _end;
 
    constexpr node_type to_graph(node_type n) const noexcept;
 
    constexpr node_type to_view(node_type n) const noexcept;
 
    constexpr auto
    to_view(rx::iterator_range<const_iterator_targets> it) const {
      return it
             | rx::transform([this](auto elem) { return this->to_view(elem); });
    }
 
    void to_view(std::pair<label_type, node_type>& in) const {
      // this is designed to operate on pairs of <label, node>
      // so does not modify the first element
      in.second = to_view(in.second);
    }
 
   public:
    // Constructors + initialisers
    // TODO: Add make functions that construct with checks

    WordGraphView(WordGraph<Node> const& graph, size_type start, size_type end)
        : _graph(&graph), _start(start), _end(end) {
      LIBSEMIGROUPS_ASSERT(start <= end);
      LIBSEMIGROUPS_ASSERT(end <= graph.number_of_nodes());
    }

    WordGraphView& init(WordGraph<Node> const& graph,
                        size_type              start,
                        size_type              end);

    explicit WordGraphView(WordGraph<Node> const& graph)
        : _graph(&graph), _start(0), _end(graph.number_of_nodes()) {}

    WordGraphView& init(WordGraph<Node> const& graph) {
      return init(graph, 0, graph.number_of_nodes());
    }

    WordGraphView() : _graph(nullptr), _start(0), _end(0) {}

    WordGraphView& init() {
      _graph = nullptr;
      _start = 0;
      _end   = 0;
      return *this;
    }

    WordGraphView(WordGraphView<Node> const&) = default;

    WordGraphView(WordGraphView<Node>&&) = default;

    WordGraphView& operator=(WordGraphView<Node> const&) = default;

    WordGraphView& operator=(WordGraphView<Node>&&) = default;
 
    ~WordGraphView() = default;

    // Modifiers

    WordGraphView& reshape_no_checks(node_type start, node_type end);

    WordGraphView& reshape(node_type start, node_type end) {
      throw_if_graph_is_nullptr();
      throw_if_invalid_range(start, end);
      return reshape_no_checks(start, end);
    }

    WordGraphView& start_node_no_checks(node_type start) noexcept {
      LIBSEMIGROUPS_ASSERT(start <= _end);
      _start = start;
      return *this;
    }

    WordGraphView& start_node(node_type start);

    WordGraphView& end_node_no_checks(node_type end) noexcept;

    WordGraphView& end_node(node_type end);

    // Accessors

    [[nodiscard]] size_type number_of_nodes_no_checks() const noexcept {
      LIBSEMIGROUPS_ASSERT(_start <= _end);
      return _end - _start;
    }

    [[nodiscard]] size_type number_of_nodes() const {
      throw_if_invalid_view();
      return number_of_nodes_no_checks();
    }

    [[nodiscard]] size_type number_of_edges_no_checks() const noexcept;

    [[nodiscard]] size_type number_of_edges() const {
      throw_if_invalid_view();
      return number_of_edges_no_checks();
    }

    [[nodiscard]] node_type start_node() const noexcept {
      return _start;
    }

    [[nodiscard]] node_type end_node() const noexcept {
      return _end;
    }

    [[nodiscard]] size_type out_degree_no_checks() const noexcept {
      return _graph->out_degree();
    }

    [[nodiscard]] size_type out_degree() const {
      throw_if_graph_is_nullptr();
      return out_degree_no_checks();
    }

    [[nodiscard]] WordGraph<Node> const* word_graph() const noexcept {
      return _graph;
    }

    // Nodes, targets and labels

    const_iterator_nodes cbegin_nodes_no_checks() const noexcept {
      return detail::IntRange<node_type>(0, number_of_nodes_no_checks())
          .cbegin();
    }

    const_iterator_nodes cbegin_nodes() const {
      throw_if_invalid_view();
      return cbegin_nodes_no_checks();
    }

    [[nodiscard]] const_iterator_nodes cend_nodes_no_checks() const noexcept {
      return detail::IntRange<node_type>(0, number_of_nodes_no_checks()).cend();
    }

    [[nodiscard]] const_iterator_nodes cend_nodes() const {
      throw_if_invalid_view();
      return cend_nodes_no_checks();
    }

    [[nodiscard]] auto nodes_no_checks() const noexcept {
      return rx::iterator_range(cbegin_nodes_no_checks(),
                                cend_nodes_no_checks());
    }

    [[nodiscard]] auto nodes() const {
      throw_if_invalid_view();
      return nodes_no_checks();
    }

    [[nodiscard]] auto
    cbegin_targets_no_checks(node_type source) const noexcept {
      return rx::begin(targets_no_checks(source));
    }

    // Not noexcept because throw_if_node_out_of_bounds isn't
    [[nodiscard]] auto cbegin_targets(node_type source) const {
      throw_if_invalid_view();
      throw_if_node_out_of_bounds(source);
      return cbegin_targets_no_checks(source);
    }

    [[nodiscard]] auto cend_targets_no_checks(node_type source) const noexcept {
      return rx::end(targets_no_checks(source));
    }

    // Not noexcept because throw_if_node_out_of_bounds isn't
    [[nodiscard]] auto cend_targets(node_type source) const {
      throw_if_invalid_view();
      throw_if_node_out_of_bounds(source);
      return cend_targets_no_checks(source);
    }

    [[nodiscard]] auto targets_no_checks(node_type source) const noexcept {
      node_type translated = to_graph(source);
      return to_view(_graph->targets_no_checks(translated));
    }

    [[nodiscard]] auto targets(node_type source) const {
      throw_if_invalid_view();
      throw_if_node_out_of_bounds(source);
      return targets_no_checks(source);
    }

    [[nodiscard]] auto labels_no_checks() const noexcept {
      return _graph->labels();
    }

    [[nodiscard]] auto labels() const {
      throw_if_graph_is_nullptr();
      return labels_no_checks();
    }

    [[nodiscard]] std::pair<label_type, node_type>
    next_label_and_target_no_checks(node_type s, label_type a) const;

    // Not noexcept because next_label_and_target_no_checks is not
    [[nodiscard]] std::pair<label_type, node_type>
    next_label_and_target(node_type s, label_type a) const;

    [[nodiscard]] auto
    labels_and_targets_no_checks(node_type source) const noexcept {
      return rx::enumerate(targets_no_checks(source));
    }

    [[nodiscard]] auto labels_and_targets(node_type source) const {
      throw_if_invalid_view();
      throw_if_node_out_of_bounds(source);
      return labels_and_targets_no_checks(source);
    }

    // Not noexcept because throw_if_node_out_of_bounds/label aren't
    [[nodiscard]] node_type target_no_checks(node_type  source,
                                             label_type a) const {
      node_type translated = to_graph(source);
      return to_view(_graph->target_no_checks(translated, a));
    }

    // Not noexcept because throw_if_node_out_of_bounds/label aren't
    [[nodiscard]] node_type target(node_type source, label_type a) const;

    // Operators

    [[nodiscard]] bool equal_to_no_checks(WordGraphView const& that) const;

    [[nodiscard]] bool operator==(WordGraphView const& that) const;

    [[nodiscard]] bool not_equal_to_no_checks(WordGraphView const& that) const {
      return !equal_to_no_checks(that);
    }

    [[nodiscard]] bool operator!=(WordGraphView const& that) const {
      return !operator==(that);
    }

    // Validation

    void throw_if_any_target_out_of_bounds() const {
      throw_if_any_target_out_of_bounds(cbegin_nodes_no_checks(),
                                        cend_nodes_no_checks());
    }

    template <typename Iterator>
    void throw_if_any_target_out_of_bounds(Iterator first, Iterator last) const;

    // not noexcept because it throws an exception!
    void
    throw_if_label_out_of_bounds(typename WordGraph<Node>::label_type a) const;

    void throw_if_label_out_of_bounds(word_type const& word) const {
      throw_if_label_out_of_bounds(word.cbegin(), word.cend());
    }

    template <typename Iterator>
    void throw_if_label_out_of_bounds(Iterator first, Iterator last) const {
      std::for_each(first, last, [this](letter_type a) {
        this->throw_if_label_out_of_bounds(a);
      });
    }

    void
    throw_if_label_out_of_bounds(std::vector<word_type> const& rules) const {
      std::for_each(rules.cbegin(), rules.cend(), [this](word_type const& w) {
        this->throw_if_label_out_of_bounds(w);
      });
    }

    // not noexcept because it throws an exception!
    template <typename Node2>
    void throw_if_node_out_of_bounds(Node2 n) const;

    // not noexcept because it throws an exception!
    template <typename Iterator1, typename Iterator2>
    void throw_if_node_out_of_bounds(Iterator1 first, Iterator2 last) const {
      for (auto it = first; it != last; ++it) {
        throw_if_node_out_of_bounds(*it);
      }
    }

    void throw_if_invalid_range() const {
      throw_if_invalid_range(_start, _end);
    }

    void throw_if_invalid_view() const {
      throw_if_graph_is_nullptr();
      throw_if_invalid_range();
    }
 
   private:
    void throw_if_graph_is_nullptr() const {
      if (_graph == nullptr) {
        LIBSEMIGROUPS_EXCEPTION("the underlying WordGraph is not defined");
      }
    }
 
    void throw_if_endpoint_out_of_bounds(node_type        endpoint,
                                         std::string_view node_name) const;
 
    void throw_if_endpoints_wrong_order(node_type start, node_type end) const;
 
    void throw_if_invalid_range(node_type start, node_type end) const {
      throw_if_endpoint_out_of_bounds(start, "start");
      throw_if_endpoint_out_of_bounds(end, "end");
      throw_if_endpoints_wrong_order(start, end);
    }
  };
}  // namespace libsemigroups
#include "word-graph-view.tpp"
 
#endif  // LIBSEMIGROUPS_WORD_GRAPH_VIEW_HPP_