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<size_t> _edge_label;
    std::vector<size_t> _parent;
 
   public:
    using node_type = size_t;

    using label_type = size_t;

    explicit Forest(size_t n = 0)
        : _edge_label(n, static_cast<size_t>(UNDEFINED)),
          _parent(n, static_cast<size_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 {
      LIBSEMIGROUPS_ASSERT(i < _parent.size());
      LIBSEMIGROUPS_ASSERT(i < _edge_label.size());
      auto it = d_first;
      for (; parent_no_checks(i) != UNDEFINED; ++it) {
        *it = label_no_checks(i);
        LIBSEMIGROUPS_ASSERT(i != parent_no_checks(i));
        i = parent_no_checks(i);
      }
      return it;
    }

    void throw_if_node_out_of_bounds(node_type v) const;
  };


  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Forest>
  make(std::vector<size_t> parent, std::vector<size_t> edge_labels) {
    if (parent.size() != edge_labels.size()) {
      LIBSEMIGROUPS_EXCEPTION(
          "expected the 1st and 2nd arguments (parents and edge labels) to "
          "have equal size equal, found {} != {}",
          parent.size(),
          edge_labels.size());
    }
    size_t const num_nodes = parent.size();
    Forest       result(num_nodes);
    for (size_t i = 0; i < num_nodes; ++i) {
      auto p = *(parent.begin() + i);
      auto l = *(edge_labels.begin() + i);
      if (p != UNDEFINED && l != UNDEFINED) {
        result.set_parent_and_label(i, p, l);
      } else if (!(p == UNDEFINED && l == UNDEFINED)) {
        LIBSEMIGROUPS_EXCEPTION(
            "roots not at the same indices in the 1st and 2nd arguments "
            "(parents and edge labels), expected UNDEFINED at index {} found "
            "{} and {}",
            i,
            p,
            l);
      }
    }
    return result;
  }

  template <typename Return>
  [[nodiscard]] enable_if_is_same<Return, Forest>
  make(std::initializer_list<size_t> parent,
       std::initializer_list<size_t> edge_labels) {
    return make<Forest>(std::vector<size_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 i);

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

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

    [[nodiscard]] word_type path_to_root(Forest const& f, Forest::node_type i);
 
  }  // 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
#endif  // LIBSEMIGROUPS_FOREST_HPP_