ukkonen.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021-2025 James D. Mitchell + Maria Tsalakou
//
// 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 a generalised suffix tree, adapted
// from:
//
// https://cp-algorithms.com/string/suffix-tree-ukkonen.html
 
// TODO(1)
// * there's an issue if you add a word containing a very large letter, then
// add more words so that the unique letter used is now in the word with the
// very large letter
// * possibly move more of the inline functions in the ukkoken namespace into
// the cpp file. Seemingly g++-14 complains about some of these (maybe the
// others just aren't currently tested).
 
#ifndef LIBSEMIGROUPS_UKKONEN_HPP_
#define LIBSEMIGROUPS_UKKONEN_HPP_
 
#include <algorithm>  // for find_if, copy, max
#include <cstring>    // for size_t, strlen
#include <iterator>   // for distance
#include <map>        // for operator!=, map, _Rb_tree_iterator
#include <numeric>    // for accumulate
#include <stack>      // for stack
#include <string>     // for allocator, string, basic_string
#include <utility>    // for pair, make_pair
#include <vector>     // for vector
 
#include "constants.hpp"  // for operator==, operator!=, Max, UNDEFINED
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "dot.hpp"        // for Dot
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "types.hpp"      // for word_type, letter_type
 
#include "detail/fmt.hpp"     // for format, format_string
#include "detail/string.hpp"  // for maximum_common_prefix
 
namespace libsemigroups {


  class Ukkonen {
    // Alias for index in _nodes
    using node_index_type = size_t;
 
    // Alias for index in side an edge
    using edge_index_type = size_t;
 
   public:
    using unique_letter_type = size_t;

    using word_index_type = size_t;

    using const_iterator = typename word_type::const_iterator;

    using index_type = size_t;

    // Ukkonen - inner classes - public

    struct State {
      node_index_type v;

      edge_index_type pos;

      State() = default;

      State(State const&) = default;

      State(State&&) = default;

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

      State& operator=(State&&) = default;

      State(node_index_type vv, edge_index_type ppos) : v(vv), pos(ppos) {}

      bool operator==(State const& that) const noexcept {
        return v == that.v && pos == that.pos;
      }
    };

    struct Node {
      index_type l;

      index_type r;

      node_index_type parent;
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      // No doc
      node_index_type link;
      // The next member is a weak indicator of whether or not the node
      // corresponds to a real suffix. If the value is true, then the node
      // corresponds to a real suffix. If the value is false, then the children
      // should be checked via is_real_suffix(Node const&) in Ukkonen.
      mutable bool is_real_suffix;
#endif

      mutable std::map<letter_type, node_index_type> children;

      Node(Node const&) = default;

      Node(Node&&) = default;

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

      Node& operator=(Node&&) = default;

      explicit Node(index_type      l      = 0,
                    index_type      r      = 0,
                    node_index_type parent = UNDEFINED);

      size_t length() const noexcept {
        return r - l;
      }

      node_index_type& child(letter_type c);

      node_index_type child(letter_type c) const;

      bool is_leaf() const noexcept {
        return children.empty();
      }

      bool is_root() const noexcept {
        return parent == UNDEFINED;
      }
    };
 
   private:
    // Ukkonen - private data
 
    size_t                  _max_word_length;
    std::vector<size_t>     _multiplicity;
    unique_letter_type      _next_unique_letter;
    std::vector<Node>       _nodes;
    State                   _ptr;
    std::vector<index_type> _word_begin;
    std::vector<index_type> _word_index_lookup;
    word_type               _word;
 
   public:
    // Ukkonen - constructors - public

    Ukkonen();

    Ukkonen& init();

    Ukkonen(Ukkonen const&);

    Ukkonen(Ukkonen&&);

    Ukkonen& operator=(Ukkonen const&);

    Ukkonen& operator=(Ukkonen&&);
 
    ~Ukkonen();

    // Ukkonen - initialisation - public

    void add_word_no_checks(const_iterator first, const_iterator last);

    void add_word(const_iterator first, const_iterator last) {
      throw_if_contains_unique_letter(first, last);
      add_word_no_checks(first, last);
    }

    // Ukkonen - attributes - public

    std::vector<Node> const& nodes() const noexcept {
      return _nodes;
    }

    size_t number_of_distinct_words() const noexcept {
      return -1 - _next_unique_letter;
    }

    size_t length_of_distinct_words() const noexcept {
      return _word.size() - number_of_distinct_words();
    }

    size_t length_of_words() const noexcept;

    size_t number_of_words() const noexcept {
      return std::accumulate(_multiplicity.cbegin(), _multiplicity.cend(), 0);
    }

    size_t max_word_length() const noexcept {
      return _max_word_length;
    }

    const_iterator begin() const noexcept {
      return _word.begin();
    }

    const_iterator cbegin() const noexcept {
      return _word.cbegin();
    }

    const_iterator end() const noexcept {
      return _word.end();
    }

    const_iterator cend() const noexcept {
      return _word.cend();
    }

    word_index_type word_index_no_checks(Node const& n) const {
      LIBSEMIGROUPS_ASSERT(n.parent != UNDEFINED);
      return word_index_no_checks(n.r - 1);
    }

    word_index_type word_index(Node const& n) const {
      if (n.parent == UNDEFINED) {
        LIBSEMIGROUPS_EXCEPTION(
            "expected the parent of the parameter to not be UNDEFINED");
      }
      return word_index_no_checks(n);
    }

    word_index_type word_index_no_checks(index_type i) const {
      LIBSEMIGROUPS_ASSERT(i < _word.size());
      return _word_index_lookup[i];
    }

    word_index_type word_index(index_type i) const {
      if (i >= _word.size()) {
        LIBSEMIGROUPS_EXCEPTION(
            "expected the parameter to be in the range [0, {}), found {}",
            _word.size(),
            i);
      }
      return word_index_no_checks(i);
    }

    size_t distance_from_root(Node const& n) const;

    word_index_type is_suffix(State const& st) const;

    size_t multiplicity_no_checks(word_index_type i) const {
      return _multiplicity[i];
    }

    size_t multiplicity(word_index_type i) const {
      if (i >= _multiplicity.size()) {
        LIBSEMIGROUPS_EXCEPTION(
            "expected the parameter to be in the range [0, {}), found {}",
            _multiplicity.size(),
            i);
      }
      return multiplicity_no_checks(i);
    }

    unique_letter_type unique_letter(word_index_type i) const noexcept {
      LIBSEMIGROUPS_ASSERT(i < number_of_distinct_words());
      return -1 - i;
    }

    bool is_unique_letter(letter_type l) const noexcept {
      return l >= _next_unique_letter;
    }

    template <typename Iterator>
    word_index_type index_no_checks(Iterator first, Iterator last) const;
 
    // Returns the index of the word [first, last) in the suffix tree if it is
    // contained (i.e. [first, last) is one of the words added using add_word),
    // and UNDEFINED if not.
    template <typename Iterator>
    word_index_type index(Iterator first, Iterator last) const {
      throw_if_contains_unique_letter(first, last);
      return index_no_checks(first, last);
    }

    template <typename Iterator>
    Iterator traverse_no_checks(State& st, Iterator first, Iterator last) const;

    template <typename Iterator>
    Iterator traverse(State& st, Iterator first, Iterator last) const {
      throw_if_contains_unique_letter(first, last);
      return traverse_no_checks(st, first, last);
    }

    template <typename Iterator>
    std::pair<State, Iterator> traverse_no_checks(Iterator first,
                                                  Iterator last) const {
      State st(0, 0);
      return std::make_pair(st, traverse(st, first, last));
    }

    template <typename Iterator>
    std::pair<State, Iterator> traverse(Iterator first, Iterator last) const {
      throw_if_contains_unique_letter(first, last);
      return traverse_no_checks(first, last);
    }

    // Ukkonen - validation - public

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

    void throw_if_contains_unique_letter(word_type const& w) const {
      throw_if_contains_unique_letter(w.cbegin(), w.cend());
    }
 
   private:
    // Ukkonen - helpers - private
 
    bool is_real_suffix(Node const& n) const;
 
    size_t word_length(word_index_type index) const {
      LIBSEMIGROUPS_ASSERT(index < _word_begin.size() - 1);
      return (_word_begin[index + 1] - _word_begin[index]) - 1;
    }

    // The following functions go, split, get_link, and tree_extend are
    // minimally adapted from:
    //
    // https://cp-algorithms.com/string/suffix-tree-ukkonen.html
 
    // Follow the path in the tree starting at the position described by
    // State st, and corresponding to the range [l, r) in _word.
    void go(State& st, index_type l, index_type r) const;
 
    // Split the node _nodes[st.v] into two nodes, the new node
    // with edge corresponding to
    //
    // [_nodes[st.v].l, _nodes[st.v].l + st.pos)
    //
    // and the old node with edge corresponding to
    //
    // [_nodes[st.v].l + st.pos, _nodes[st.v].r)
    node_index_type split(State const& st);
 
    // Get the suffix link of a node by index
    node_index_type get_link(node_index_type v);
 
    // Perform the phase starting with the pos letter of the word.
    void tree_extend(index_type pos);
  };

  namespace ukkonen {
    void add_word_no_checks(Ukkonen& u, word_type const& w);

    template <typename Iterator>
    void add_word_no_checks(Ukkonen& u, Iterator first, Iterator last) {
      // TODO(later) it'd be better to just convert the values pointed at by the
      // iterators, than to allocate a word_type here, but this is currently a
      // bit tricky to set up
      add_word_no_checks(u, word_type(first, last));
    }

    template <typename Word>
    void add_word_no_checks(Ukkonen& u, Word const& w) {
      add_word_no_checks(u, w.cbegin(), w.cend());
    }

    void add_word_no_checks(Ukkonen& u, char const* w);

    void add_word(Ukkonen& u, word_type const& w);

    template <typename Iterator>
    void add_word(Ukkonen& u, Iterator first, Iterator last) {
      // TODO(later) it'd be better to just convert the values pointed at by the
      // iterators, than to allocate a word_type here, but this is currently a
      // bit tricky to set up
      add_word(u, word_type(first, last));
    }

    template <typename Word>
    void add_word(Ukkonen& u, Word const& w) {
      add_word(u, w.cbegin(), w.cend());
    }

    void add_word(Ukkonen& u, char const* w);

    void add_words_no_checks(Ukkonen& u, std::vector<word_type> const& words);

    template <typename Iterator1, typename Iterator2>
    void add_words_no_checks(Ukkonen& u, Iterator1 first, Iterator2 last) {
      for (auto it = first; it != last; ++it) {
        add_word_no_checks(u, *it);
      }
    }

    void add_words(Ukkonen& u, std::vector<word_type> const& words);

    template <typename Iterator1, typename Iterator2>
    void add_words(Ukkonen& u, Iterator1 first, Iterator2 last) {
      for (auto it = first; it != last; ++it) {
        add_word(u, *it);
      }
    }

    template <typename Word>
    auto traverse_no_checks(Ukkonen const& u, Word const& w) {
      return u.traverse_no_checks(w.cbegin(), w.cend());
    }

    std::pair<Ukkonen::State, word_type::const_iterator>
    traverse_no_checks(Ukkonen const& u, word_type const& w);

    std::pair<Ukkonen::State, char const*> traverse_no_checks(Ukkonen const& u,
                                                              char const*    w);

    template <typename Word>
    auto traverse(Ukkonen const& u, Word const& w) {
      return u.traverse(w.cbegin(), w.cend());
    }

    std::pair<Ukkonen::State, word_type::const_iterator>
    traverse(Ukkonen const& u, word_type const& w);

    std::pair<Ukkonen::State, char const*> traverse(Ukkonen const& u,
                                                    char const*    w);

    template <typename Word>
    auto traverse_no_checks(Ukkonen::State& st,
                            Ukkonen const&  u,
                            Word const&     w) {
      return u.traverse_no_checks(st, w.cbegin(), w.cend());
    }

    word_type::const_iterator traverse_no_checks(Ukkonen::State&  st,
                                                 Ukkonen const&   u,
                                                 word_type const& w);

    char const* traverse_no_checks(Ukkonen::State& st,
                                   Ukkonen const&  u,
                                   char const*     w);

    template <typename Word>
    auto traverse(Ukkonen::State& st, Ukkonen const& u, Word const& w) {
      return u.traverse(st, w.cbegin(), w.cend());
    }

    word_type::const_iterator traverse(Ukkonen::State&  st,
                                       Ukkonen const&   u,
                                       word_type const& w);

    char const* traverse(Ukkonen::State& st, Ukkonen const& u, char const* w);

    template <typename Iterator>
    bool is_subword_no_checks(Ukkonen const& u, Iterator first, Iterator last);

    template <typename Word>
    bool is_subword_no_checks(Ukkonen const& u, Word const& w) {
      return is_subword_no_checks(u, w.cbegin(), w.cend());
    }

    bool is_subword_no_checks(Ukkonen const& u, char const* w);

    bool is_subword_no_checks(Ukkonen const& u, word_type const& w);

    template <typename Iterator>
    bool is_subword(Ukkonen const& u, Iterator first, Iterator last) {
      u.throw_if_contains_unique_letter(first, last);
      return is_subword_no_checks(u, first, last);
    }

    template <typename Word>
    bool is_subword(Ukkonen const& u, Word const& w) {
      return is_subword(u, w.cbegin(), w.cend());
    }

    bool is_subword(Ukkonen const& u, char const* w);

    bool is_subword(Ukkonen const& u, word_type const& w);

    template <typename Iterator>
    bool is_suffix_no_checks(Ukkonen const& u, Iterator first, Iterator last);

    template <typename Word>
    bool is_suffix_no_checks(Ukkonen const& u, Word const& w) {
      return is_suffix_no_checks(u, w.cbegin(), w.cend());
    }

    // This function is required so that we can use initialiser list, as an
    // argument to is_suffix_no_checks
    bool is_suffix_no_checks(Ukkonen const& u, word_type const& w);

    bool is_suffix_no_checks(Ukkonen const& u, char const* w);

    template <typename Iterator>
    bool is_suffix(Ukkonen const& u, Iterator first, Iterator last) {
      u.throw_if_contains_unique_letter(first, last);
      return is_suffix_no_checks(u, first, last);
    }

    template <typename Word>
    bool is_suffix(Ukkonen const& u, Word const& w) {
      return is_suffix(u, w.cbegin(), w.cend());
    }

    // This function is required so that we can use initialiser list, as an
    // argument to is_suffix
    bool is_suffix(Ukkonen const& u, word_type const& w);

    bool is_suffix(Ukkonen const& u, char const* w);

    template <typename Iterator>
    Iterator maximal_piece_prefix_no_checks(Ukkonen const& u,
                                            Iterator       first,
                                            Iterator       last);

    template <typename Word>
    typename Word::const_iterator
    maximal_piece_prefix_no_checks(Ukkonen const& u, Word const& w) {
      return maximal_piece_prefix_no_checks(u, w.cbegin(), w.cend());
    }

    inline typename word_type::const_iterator
    maximal_piece_prefix_no_checks(Ukkonen const& u, word_type const& w) {
      return maximal_piece_prefix_no_checks(u, w.cbegin(), w.cend());
    }

    inline char const* maximal_piece_prefix_no_checks(Ukkonen const& u,
                                                      char const*    w) {
      return maximal_piece_prefix_no_checks(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    Iterator maximal_piece_prefix(Ukkonen const& u,
                                  Iterator       first,
                                  Iterator       last) {
      u.throw_if_contains_unique_letter(first, last);
      return maximal_piece_prefix_no_checks(u, first, last);
    }

    template <typename Word>
    typename Word::const_iterator maximal_piece_prefix(Ukkonen const& u,
                                                       Word const&    w) {
      return maximal_piece_prefix(u, w.cbegin(), w.cend());
    }

    inline typename word_type::const_iterator
    maximal_piece_prefix(Ukkonen const& u, word_type const& w) {
      return maximal_piece_prefix(u, w.cbegin(), w.cend());
    }

    inline char const* maximal_piece_prefix(Ukkonen const& u, char const* w) {
      return maximal_piece_prefix(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    size_t length_maximal_piece_prefix_no_checks(Ukkonen const& u,
                                                 Iterator       first,
                                                 Iterator       last) {
      return std::distance(first,
                           maximal_piece_prefix_no_checks(u, first, last));
    }

    template <typename Word>
    size_t length_maximal_piece_prefix_no_checks(Ukkonen const& u,
                                                 Word const&    w) {
      return length_maximal_piece_prefix_no_checks(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_prefix_no_checks(Ukkonen const&   u,
                                                        word_type const& w) {
      return length_maximal_piece_prefix_no_checks(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_prefix_no_checks(Ukkonen const& u,
                                                        char const*    w) {
      return length_maximal_piece_prefix_no_checks(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    size_t length_maximal_piece_prefix(Ukkonen const& u,
                                       Iterator       first,
                                       Iterator       last) {
      return std::distance(first, maximal_piece_prefix(u, first, last));
    }

    template <typename Word>
    size_t length_maximal_piece_prefix(Ukkonen const& u, Word const& w) {
      return length_maximal_piece_prefix(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_prefix(Ukkonen const&   u,
                                              word_type const& w) {
      return length_maximal_piece_prefix(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_prefix(Ukkonen const& u, char const* w) {
      return length_maximal_piece_prefix(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    bool is_piece_no_checks(Ukkonen const& u, Iterator first, Iterator last) {
      return maximal_piece_prefix_no_checks(u, first, last) == last;
    }

    template <typename Word>
    bool is_piece_no_checks(Ukkonen const& u, Word const& w) {
      return is_piece_no_checks(u, w.cbegin(), w.cend());
    }

    inline bool is_piece_no_checks(Ukkonen const& u, word_type const& w) {
      return is_piece_no_checks(u, w.cbegin(), w.cend());
    }

    inline bool is_piece_no_checks(Ukkonen const& u, char const* w) {
      return is_piece_no_checks(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    bool is_piece(Ukkonen const& u, Iterator first, Iterator last) {
      return maximal_piece_prefix(u, first, last) == last;
    }

    template <typename Word>
    bool is_piece(Ukkonen const& u, Word const& w) {
      return is_piece(u, w.cbegin(), w.cend());
    }

    inline bool is_piece(Ukkonen const& u, word_type const& w) {
      return is_piece(u, w.cbegin(), w.cend());
    }

    inline bool is_piece(Ukkonen const& u, char const* w) {
      return is_piece(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    Iterator maximal_piece_suffix_no_checks(Ukkonen const& u,
                                            Iterator       first,
                                            Iterator       last);

    template <typename Word>
    typename Word::const_iterator
    maximal_piece_suffix_no_checks(Ukkonen const& u, Word const& w) {
      return maximal_piece_suffix_no_checks(u, w.cbegin(), w.cend());
    }

    inline typename word_type::const_iterator
    maximal_piece_suffix_no_checks(Ukkonen const& u, word_type const& w) {
      return maximal_piece_suffix_no_checks(u, w.cbegin(), w.cend());
    }

    inline char const* maximal_piece_suffix_no_checks(Ukkonen const& u,
                                                      char const*    w) {
      return maximal_piece_suffix_no_checks(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    Iterator maximal_piece_suffix(Ukkonen const& u,
                                  Iterator       first,
                                  Iterator       last) {
      u.throw_if_contains_unique_letter(first, last);
      return maximal_piece_suffix_no_checks(u, first, last);
    }

    template <typename Word>
    typename Word::const_iterator maximal_piece_suffix(Ukkonen const& u,
                                                       Word const&    w) {
      return maximal_piece_suffix(u, w.cbegin(), w.cend());
    }

    inline typename word_type::const_iterator
    maximal_piece_suffix(Ukkonen const& u, word_type const& w) {
      return maximal_piece_suffix(u, w.cbegin(), w.cend());
    }

    inline char const* maximal_piece_suffix(Ukkonen const& u, char const* w) {
      return maximal_piece_suffix(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    size_t length_maximal_piece_suffix_no_checks(Ukkonen const& u,
                                                 Iterator       first,
                                                 Iterator       last) {
      return std::distance(maximal_piece_suffix_no_checks(u, first, last),
                           last);
    }

    template <typename Word>
    size_t length_maximal_piece_suffix_no_checks(Ukkonen const& u,
                                                 Word const&    w) {
      return length_maximal_piece_suffix_no_checks(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_suffix_no_checks(Ukkonen const&   u,
                                                        word_type const& w) {
      return length_maximal_piece_suffix_no_checks(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_suffix_no_checks(Ukkonen const& u,
                                                        char const*    w) {
      return length_maximal_piece_suffix_no_checks(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    size_t length_maximal_piece_suffix(Ukkonen const& u,
                                       Iterator       first,
                                       Iterator       last) {
      return std::distance(maximal_piece_suffix(u, first, last), last);
    }

    template <typename Word>
    size_t length_maximal_piece_suffix(Ukkonen const& u, Word const& w) {
      return length_maximal_piece_suffix(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_suffix(Ukkonen const&   u,
                                              word_type const& w) {
      return length_maximal_piece_suffix(u, w.cbegin(), w.cend());
    }

    inline size_t length_maximal_piece_suffix(Ukkonen const& u, char const* w) {
      return length_maximal_piece_suffix(u, w, w + std::strlen(w));
    }

    template <typename Iterator>
    size_t number_of_pieces_no_checks(Ukkonen const& u,
                                      Iterator       first,
                                      Iterator       last);

    template <typename Word>
    size_t number_of_pieces_no_checks(Ukkonen const& u, Word const& w) {
      return number_of_pieces_no_checks(u, w.cbegin(), w.cend());
    }

    inline size_t number_of_pieces_no_checks(Ukkonen const&   u,
                                             word_type const& w) {
      return number_of_pieces_no_checks(u, w.cbegin(), w.cend());
    }

    inline size_t number_of_pieces_no_checks(Ukkonen const& u, char const* w) {
      return number_of_pieces_no_checks(u, w, w + std::strlen(w));
    }
 
    // clang-format off
    // NOLINTNEXTLINE(whitespace/line_length)
    // clang-format on
    template <typename Iterator>
    size_t number_of_pieces(Ukkonen const& u, Iterator first, Iterator last) {
      u.throw_if_contains_unique_letter(first, last);
      return number_of_pieces_no_checks(u, first, last);
    }

    template <typename Word>
    size_t number_of_pieces(Ukkonen const& u, Word const& w) {
      return number_of_pieces(u, w.cbegin(), w.cend());
    }

    inline size_t number_of_pieces(Ukkonen const& u, word_type const& w) {
      return number_of_pieces(u, w.cbegin(), w.cend());
    }

    inline size_t number_of_pieces(Ukkonen const& u, char const* w) {
      return number_of_pieces(u, w, w + std::strlen(w));
    }

    size_t number_of_distinct_subwords(Ukkonen const& u);

    template <typename Iterator>
    std::vector<Iterator> pieces_no_checks(Ukkonen const& u,
                                           Iterator       first,
                                           Iterator       last);

    template <typename Word>
    std::vector<Word> pieces_no_checks(Ukkonen const& u, Word const& w);

    std::vector<word_type> pieces_no_checks(Ukkonen const&   u,
                                            word_type const& w);

    std::vector<std::string> pieces_no_checks(Ukkonen const& u, char const* w);

    template <typename Iterator>
    std::vector<Iterator> pieces(Ukkonen const& u,
                                 Iterator       first,
                                 Iterator       last) {
      u.throw_if_contains_unique_letter(first, last);
      return pieces_no_checks(u, first, last);
    }

    template <typename Word>
    std::vector<Word> pieces(Ukkonen const& u, Word const& w) {
      u.throw_if_contains_unique_letter(w.cbegin(), w.cend());
      return pieces_no_checks(u, w);
    }

    inline std::vector<word_type> pieces(Ukkonen const& u, word_type const& w) {
      u.throw_if_contains_unique_letter(w);
      return pieces_no_checks(u, w);
    }

    inline std::vector<std::string> pieces(Ukkonen const& u, char const* w) {
      u.throw_if_contains_unique_letter(w, w + std::strlen(w));
      return pieces_no_checks(u, w);
    }

    [[nodiscard]] Dot dot(Ukkonen const& u);

    template <typename T>
    auto dfs(Ukkonen const& u, T& helper);
 
  }  // namespace ukkonen

  [[nodiscard]] inline std::string to_human_readable_repr(Ukkonen const& u) {
    return fmt::format("<Ukkonen with {} distinct words>",
                       u.number_of_distinct_words());
  }

  [[nodiscard]] inline std::string
  to_human_readable_repr(Ukkonen::State const& st,
                         std::string const&    sep = "::") {
    return fmt::format(
        "<Ukkonen{}State with pos = {} and v = {}>", sep, st.pos, st.v);
  }

  [[nodiscard]] inline std::string
  to_human_readable_repr(Ukkonen::Node const& node,
                         std::string const&   sep = "::") {
    return fmt::format(
        "<Ukkonen{}Node with {} children and parent edge label [{}, {})>",
        sep,
        node.children.size(),
        node.l,
        node.r);
  }

 
}  // namespace libsemigroups
 
#include "ukkonen.tpp"
 
#endif  // LIBSEMIGROUPS_UKKONEN_HPP_