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 <algorithm>         // for fill
#include <cstddef>           // for size_t
#include <initializer_list>  // for initializer_list
#include <iterator>          // for begin, end
#include <vector>            // for vector, allocator, operator==
 
#include "constants.hpp"  // for Undefined, Max, UNDEFINED, operator!=
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "types.hpp"      // for word_type, enable_if_is_same
 
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;

    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();

    [[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) {
      _parent[node]     = parent;
      _edge_label[node] = gen;
      return *this;
    }

    // not noexcept because std::vector::operator[] isn't.
    Forest& set_parent_and_label(node_type  node,
                                 node_type  parent,
                                 label_type gen) {
      throw_if_node_out_of_bounds(node);
      throw_if_node_out_of_bounds(parent);
      return set_parent_and_label_no_checks(node, parent, gen);
    }

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

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

    [[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);
    }
  };


  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);
    }
  }  // namespace forest
}  // 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_