forest.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-2025 Finn Smith + James 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/>.
//
 
#ifndef LIBSEMIGROUPS_FOREST_HPP_
#define LIBSEMIGROUPS_FOREST_HPP_
 
#include <cstddef>           // for size_t, ptrdiff_t
#include <cstdint>           // for uint32_t
#include <initializer_list>  // for initializer_list
#include <iterator>          // for forward_iterator_tag
#include <string>            // for string, basic_string
#include <vector>            // for vector, operator==
 
#include "constants.hpp"  // for UNDEFINED, operator!=, operator==
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "dot.hpp"        // for Dot
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "types.hpp"      // for word_type, enable_if_is_same
 
#include "detail/fmt.hpp"  // for formatter, string_view
 
namespace libsemigroups {
  class Forest {
    std::vector<uint32_t> _edge_label;
    std::vector<uint32_t> _parent;
 
   public:
    using node_type = uint32_t;

    using label_type = uint32_t;
 
   private:
    void throw_if_not_acyclic(node_type node, node_type parent) const;
 
   public:
    explicit Forest(size_t n = 0)
        : _edge_label(n, static_cast<uint32_t>(UNDEFINED)),
          _parent(n, static_cast<uint32_t>(UNDEFINED)) {}

    Forest& init(size_t n = 0);

    Forest(Forest const&) = default;

    Forest(Forest&&) = default;

    Forest& operator=(Forest const&) = default;

    Forest& operator=(Forest&&) = default;
 
    ~Forest();

    void throw_if_not_acyclic() const {
      throw_if_not_acyclic(UNDEFINED, UNDEFINED);
    }

    [[nodiscard]] bool operator==(Forest const& that) const {
      return _parent == that._parent && _edge_label == that._edge_label;
    }

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

    Forest& add_nodes(size_t n);

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

    Forest& set_parent_and_label_no_checks(node_type  node,
                                           node_type  parent,
                                           label_type gen) {
      LIBSEMIGROUPS_ASSERT(node < number_of_nodes() || node == UNDEFINED);
      LIBSEMIGROUPS_ASSERT(parent < number_of_nodes() || parent == UNDEFINED);
 
      _parent[node]     = parent;
      _edge_label[node] = gen;
      return *this;
    }

    Forest& set_parent_and_label(node_type  node,
                                 node_type  parent,
                                 label_type gen);

    [[nodiscard]] size_t number_of_nodes() const noexcept {
      return _parent.size();
    }

    [[nodiscard]] node_type parent(node_type i) const {
      throw_if_node_out_of_bounds(i);
      return _parent[i];
    }

    // not noexcept because std::vector::operator[] isn't.
    [[nodiscard]] node_type parent_no_checks(node_type i) const {
      return _parent[i];
    }

    // not noexcept because std::vector::operator[] isn't.
    [[nodiscard]] label_type label(node_type i) const {
      throw_if_node_out_of_bounds(i);
      return _edge_label[i];
    }

    [[nodiscard]] label_type label_no_checks(node_type i) const {
      return _edge_label[i];
    }

    [[nodiscard]] std::vector<node_type> const& parents() const noexcept {
      return _parent;
    }

    [[nodiscard]] std::vector<label_type> const& labels() const noexcept {
      return _edge_label;
    }

    //
    template <typename Iterator>
    Iterator path_to_root_no_checks(Iterator d_first, node_type i) const;

    template <typename Iterator>
    Iterator path_from_root_no_checks(Iterator d_first, node_type i) const;

    void throw_if_node_out_of_bounds(node_type v) const;
 
   private:
    class const_iterator_path {
     private:
      node_type     _current_node;
      Forest const* _forest;
 
     public:
      using iterator_category = std::forward_iterator_tag;
      using value_type        = label_type;
      using difference_type   = std::ptrdiff_t;
      using pointer           = label_type*;
      using reference         = label_type&;
 
      const_iterator_path(Forest const* f, node_type n)
          : _current_node(n), _forest(f) {}
 
      const_iterator_path() = delete;
 
      const_iterator_path(const_iterator_path const& that)            = default;
      const_iterator_path& operator=(const_iterator_path const& that) = default;
      const_iterator_path(const_iterator_path&& that) noexcept        = default;
      const_iterator_path& operator=(const_iterator_path&& that) noexcept
          = default;
 
      ~const_iterator_path() = default;
 
      [[nodiscard]] value_type operator*() const;
 
      // pointer operator->() const {
      //   return TODO;
      // }
 
      // Pre-increment
      const_iterator_path& operator++();
 
      // Post-increment
      const_iterator_path operator++(int) {
        const_iterator_path tmp = *this;
        ++(*this);
        return tmp;
      }
 
      [[nodiscard]] bool operator==(const_iterator_path const& that) const;
 
      [[nodiscard]] bool operator!=(const_iterator_path const& that) const {
        return !(*this == that);
      }
    };
 
   public:
    [[nodiscard]] const_iterator_path
    cbegin_path_to_root_no_checks(node_type n) const noexcept {
      return const_iterator_path(this, n);
    }

    [[nodiscard]] const_iterator_path
    cend_path_to_root_no_checks(node_type n) const noexcept {
      (void) n;
      return const_iterator_path(this, UNDEFINED);
    }

    [[nodiscard]] const_iterator_path cbegin_path_to_root(node_type n) const {
      throw_if_node_out_of_bounds(n);
      return cbegin_path_to_root_no_checks(n);
    }

    [[nodiscard]] const_iterator_path cend_path_to_root(node_type n) const {
      throw_if_node_out_of_bounds(n);
      return cend_path_to_root_no_checks(n);
    }
  };  // class Forest


  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Forest>
  make(std::vector<uint32_t> const& parent,
       std::vector<uint32_t> const& edge_labels);

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Forest>
  make(std::initializer_list<uint32_t> parent,
       std::initializer_list<uint32_t> edge_labels) {
    return make<Forest>(std::vector<uint32_t>(parent),
                        std::vector(edge_labels));
  }

  [[nodiscard]] std::string to_human_readable_repr(Forest const& f);

  namespace forest {
    void path_to_root_no_checks(Forest const&     f,
                                word_type&        w,
                                Forest::node_type n);

    void path_from_root_no_checks(Forest const&     f,
                                  word_type&        w,
                                  Forest::node_type n);

    [[nodiscard]] word_type path_to_root_no_checks(Forest const&     f,
                                                   Forest::node_type n);

    [[nodiscard]] word_type path_from_root_no_checks(Forest const&     f,
                                                     Forest::node_type n);

    void path_to_root(Forest const& f, word_type& w, Forest::node_type n);

    void path_from_root(Forest const& f, word_type& w, Forest::node_type n);

    [[nodiscard]] word_type path_to_root(Forest const& f, Forest::node_type n);

    [[nodiscard]] word_type path_from_root(Forest const&     f,
                                           Forest::node_type n);

    [[nodiscard]] size_t depth_no_checks(Forest const& f, Forest::node_type n);

    [[nodiscard]] inline size_t depth(Forest const& f, Forest::node_type n) {
      f.throw_if_node_out_of_bounds(n);
      return depth_no_checks(f, n);
    }

    [[nodiscard]] inline bool is_root_no_checks(Forest const&     f,
                                                Forest::node_type n) {
      return f.parent_no_checks(n) == UNDEFINED;
    }

    [[nodiscard]] inline bool is_root(Forest const& f, Forest::node_type n) {
      f.throw_if_node_out_of_bounds(n);
      return is_root_no_checks(f, n);
    }

    [[nodiscard]] Forest::label_type max_label(Forest const& f);

    [[nodiscard]] bool is_forest(Forest const& f);
 
    namespace detail {
      class PathsFromToRootsCommon {
       public:
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
        // We don't document these because we have to redeclare them in
        // PathsFromRoots and PathsToRoots anyway.
        using size_type   = typename std::vector<word_type>::size_type;
        using output_type = word_type const&;
        using node_type   = Forest::node_type;
        static constexpr bool is_finite     = true;
        static constexpr bool is_idempotent = true;
#endif
 
       protected:
        node_type              _current_node;
        word_type              _current_path;
        std::vector<size_type> _depths;
        Forest const*          _forest;
        word_type              _visited;
 
        // Lazily compute depth of a node in the tree
        size_type depth(node_type n);
 
       public:
        PathsFromToRootsCommon() = delete;

        PathsFromToRootsCommon(PathsFromToRootsCommon const&) = default;

        PathsFromToRootsCommon(PathsFromToRootsCommon&&) = default;

        PathsFromToRootsCommon& operator=(PathsFromToRootsCommon const&)
            = default;

        PathsFromToRootsCommon& operator=(PathsFromToRootsCommon&&) = default;

        explicit PathsFromToRootsCommon(Forest const& f);

        PathsFromToRootsCommon& init(Forest const& f);

        [[nodiscard]] node_type target() const noexcept {
          return _current_node;
        }

        [[nodiscard]] output_type get() const noexcept {
          return _current_path;
        }

        [[nodiscard]] bool at_end() const noexcept {
          return _forest->empty()
                 || _current_node >= _forest->number_of_nodes();
        }

        [[nodiscard]] size_type size_hint() const noexcept {
          if (at_end()) {
            return 0;
          }
          return _forest->number_of_nodes() - _current_node;
        }

        [[nodiscard]] size_type count() const noexcept {
          return size_hint();
        }

        [[nodiscard]] Forest const& forest() const noexcept {
          return *_forest;
        }
      };  // class PathsFromToRootsCommonRoots
    }     // namespace detail

    class PathsFromRoots : public detail::PathsFromToRootsCommon {
      using detail::PathsFromToRootsCommon::depth;
 
     public:
      using size_type = typename std::vector<word_type>::size_type;

      using output_type = word_type const&;

      using node_type = Forest::node_type;

      static constexpr bool is_finite = true;

      static constexpr bool is_idempotent = true;
 
      using detail::PathsFromToRootsCommon::at_end;
      using detail::PathsFromToRootsCommon::count;
      using detail::PathsFromToRootsCommon::forest;
      using detail::PathsFromToRootsCommon::get;
      using detail::PathsFromToRootsCommon::init;
      using detail::PathsFromToRootsCommon::PathsFromToRootsCommon;
      using detail::PathsFromToRootsCommon::size_hint;
      using detail::PathsFromToRootsCommon::target;

      void next();

      PathsFromRoots& skip_n(size_type n);

      // This can't go in the base class because the base class has no "next"
      // mem fn and so rx::begin/end don't compile.
      [[nodiscard]] auto begin() noexcept {
        return rx::begin(*this);
      }

      // This can't go in the base class because the base class has no "next"
      // mem fn and so rx::begin/end don't compile.
      [[nodiscard]] auto end() noexcept {
        return rx::end(*this);
      }
    };  // class PathsFromRoots

    class PathsToRoots : public detail::PathsFromToRootsCommon {
      using detail::PathsFromToRootsCommon::depth;
 
     public:
      using size_type = typename std::vector<word_type>::size_type;

      using output_type = word_type const&;

      using node_type = Forest::node_type;

      static constexpr bool is_finite = true;

      static constexpr bool is_idempotent = true;
 
      using detail::PathsFromToRootsCommon::at_end;
      using detail::PathsFromToRootsCommon::count;
      using detail::PathsFromToRootsCommon::forest;
      using detail::PathsFromToRootsCommon::get;
      using detail::PathsFromToRootsCommon::init;
      using detail::PathsFromToRootsCommon::PathsFromToRootsCommon;
      using detail::PathsFromToRootsCommon::size_hint;
      using detail::PathsFromToRootsCommon::target;

      void next();

      PathsToRoots& skip_n(size_type n);

      // This can't go in the base class because the base class has no "next"
      // mem fn and so rx::begin/end don't compile.
      [[nodiscard]] auto begin() noexcept {
        return rx::begin(*this);
      }

      // This can't go in the base class because the base class has no "next"
      // mem fn and so rx::begin/end don't compile.
      [[nodiscard]] auto end() noexcept {
        return rx::end(*this);
      }
    };  // class PathsToRoots

    [[nodiscard]] Dot dot(Forest const& f);

    Dot dot(Forest const& f, std::vector<std::string> const& labels);
 
  }  // namespace forest

  [[nodiscard]] std::string
  to_human_readable_repr(forest::PathsToRoots const& ptr,
                         std::string const&          sep = "::");

  [[nodiscard]] std::string
  to_human_readable_repr(forest::PathsFromRoots const& pfr,
                         std::string const&            sep = "::");
 
}  // namespace libsemigroups
 
namespace fmt {
  template <>
  struct formatter<libsemigroups::Forest> : formatter<std::string> {
    template <typename FormatContext>
    auto format(libsemigroups::Forest const& f, FormatContext& ctx) const {
      return formatter<string_view>::format(
          fmt::format("{{{}, {}}}", f.parents(), f.labels()), ctx);
    }
  };
}  // namespace fmt
 
#include "forest.tpp"
 
#endif  // LIBSEMIGROUPS_FOREST_HPP_