prefix-tree.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef PREFIX_TREE_H
#define PREFIX_TREE_H
 
#include <cassert>
#include <cstddef>
#include <iostream>
#include <optional>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
 
#include <tpl_tree_node.H>
#include <tpl_dynArray.H>
#include <tpl_dynList.H>
#include <ah-errors.H>
 
namespace Aleph {
class Cnode : public Tree_Node<char>
{
  bool ends_word_ = false;
 
  template <typename Node>
  [[nodiscard]] static std::tuple<Node *, const char *> search_prefix_impl(Node *root,
                                                                           const char *prefix) noexcept
  {
    assert(root != nullptr);
    assert(prefix != nullptr);
 
    auto node = root;
    for (const char *ptr = prefix; *ptr != '\0'; ++ptr)
      {
        auto *child = node->search_child(*ptr);
        if (child == nullptr)
          return std::make_tuple(node, ptr);
        node = child;
      }
 
    return std::make_tuple(node, "");
  }
 
  template <typename Node>
  [[nodiscard]] static Node *search_child_impl(Node *root, const char c) noexcept
  {
    assert(root != nullptr);
 
    for (auto *child = root->get_left_child(); child != nullptr; child = child->get_right_sibling())
      {
        const char key = child->get_key();
        if (key == c)
          return static_cast<Node *>(child);
        if (key > c)
          return nullptr;
      }
 
    return nullptr;
  }
 
  template <typename Node>
  [[nodiscard]] static Node *greater_child_impl(Node *root, const char c) noexcept
  {
    assert(root != nullptr);
 
    for (auto *child = root->get_left_child(); child != nullptr; child = child->get_right_sibling())
      if (child->get_key() > c)
        return static_cast<Node *>(child);
    return nullptr;
  }
 
  class Detached_Subtree_Guard
  {
    Cnode *root_ = nullptr;
 
  public:
    explicit Detached_Subtree_Guard(Cnode *root) noexcept : root_(root)
    {
      // empty
    }
 
    ~Detached_Subtree_Guard()
    {
      if (root_ != nullptr)
        {
          root_->destroy();
          delete root_;
        }
    }
 
    [[nodiscard]] Cnode *get() const noexcept
    {
      return root_;
    }
 
    [[nodiscard]] Cnode *release() noexcept
    {
      Cnode *ret = root_;
      root_ = nullptr;
      return ret;
    }
  };
 
  class Pending_Path_Guard
  {
    Cnode **nodes_ = nullptr;
    size_t count_ = 0;
    bool owns_nodes_ = true;
 
  public:
    explicit Pending_Path_Guard(const size_t count) : nodes_(new Cnode *[count]), count_(count)
    {
      for (size_t i = 0; i < count_; ++i)
        nodes_[i] = nullptr;
    }
 
    ~Pending_Path_Guard()
    {
      if (owns_nodes_)
        for (size_t i = 0; i < count_; ++i)
          delete nodes_[i];
      delete[] nodes_;
    }
 
    [[nodiscard]] Cnode *operator [] (const size_t i) const noexcept
    {
      return nodes_[i];
    }
 
    void set(const size_t i, Cnode *node) const noexcept
    {
      nodes_[i] = node;
    }
 
    void release_nodes() noexcept
    {
      owns_nodes_ = false;
    }
  };
 
  class Clone_Target_Rollback
  {
    Cnode *target_ = nullptr;
    Tree_Node<char> *previous_rightmost_ = nullptr;
    bool previous_ends_word_ = false;
    bool active_ = true;
 
  public:
    explicit Clone_Target_Rollback(Cnode *target) noexcept : target_(target)
    {
      assert(target_ != nullptr);
      previous_rightmost_ = target_->get_right_child();
      previous_ends_word_ = target_->ends_word_;
    }
 
    void release() noexcept
    {
      active_ = false;
    }
 
    ~Clone_Target_Rollback()
    {
      if (not active_)
        return;
 
      while (target_->get_right_child() != previous_rightmost_)
        {
          auto *child = static_cast<Cnode *>(target_->get_right_child());
          const bool child_was_leftmost = child->is_leftmost();
          destroy_tree(child);
          if (child_was_leftmost)
            {
              if (previous_rightmost_ == nullptr)
                target_->set_is_leaf(true);
              break;
            }
        }
 
      target_->ends_word_ = previous_ends_word_;
    }
  };
 
public:
  explicit Cnode(const char c) noexcept
  {
    this->get_key() = c;
  }
 
  [[nodiscard]] char symbol() const noexcept
  {
    return get_key();
  }
 
  [[nodiscard]] DynList<Cnode *> children() const
  {
    DynList<Cnode *> r;
    for_each_child([&r](Tree_Node<char> *p)
      {
        r.append(static_cast<Cnode *>(p));
      });
    return r;
  }
 
  [[nodiscard]] std::string to_str() const
  {
    std::string ret(1, symbol());
    for_each_child([&ret](const Tree_Node<char> *p)
      {
        const auto *node = static_cast<const Cnode *>(p);
        ret += "(" + node->to_str() + ")";
      });
    return ret;
  }
 
  [[nodiscard]] bool is_end_word() const noexcept
  {
    return ends_word_;
  }
 
  void mark_end_word()
  {
    assert(not is_end_word());
    ends_word_ = true;
  }
 
  [[nodiscard]] Cnode *search_child(const char c) noexcept
  {
    return search_child_impl(this, c);
  }
 
  [[nodiscard]] const Cnode *search_child(const char c) const noexcept
  {
    return search_child_impl(this, c);
  }
 
  [[nodiscard]] Cnode *greater_child(const char c) noexcept
  {
    return greater_child_impl(this, c);
  }
 
  [[nodiscard]] const Cnode *greater_child(const char c) const noexcept
  {
    return greater_child_impl(this, c);
  }
 
  [[nodiscard]] std::tuple<Cnode *, const char *> search_prefix(const char *prefix) noexcept
  {
    return search_prefix_impl(this, prefix);
  }
 
  [[nodiscard]] std::tuple<const Cnode *, const char *> search_prefix(const char *prefix) const noexcept
  {
    return search_prefix_impl(this, prefix);
  }
 
  [[nodiscard]] const Cnode *search_word(const char *word) const noexcept
  {
    assert(word != nullptr);
 
    auto node = this;
    for (const char *ptr = word; *ptr != '\0'; ++ptr)
      {
        node = node->search_child(*ptr);
        if (node == nullptr)
          return nullptr;
      }
 
    return node->is_end_word() ? node : nullptr;
  }
 
  [[nodiscard]] bool contains(const std::string &word) const noexcept
  {
    return search_word(word.c_str()) != nullptr;
  }
 
  [[nodiscard]] size_t count() const noexcept
  {
    size_t n = is_end_word() ? 1 : 0;
    for_each_child([&n](const Tree_Node<char> *p)
      {
        n += static_cast<const Cnode *>(p)->count();
      });
    return n;
  }
 
  [[nodiscard]] DynArray<std::string> words_with_prefix(const std::string &prefix,
                                                        const size_t max_word_length = 2048) const
  {
    auto [node, remaining] = search_prefix(prefix.c_str());
 
    // Prefix not fully matched
    if (*remaining != '\0')
      return {};
 
    assert(prefix.size() <= max_word_length);
    DynArray<std::string> ret_val;
    std::string word(prefix);
    word.reserve(max_word_length);
 
    node->words_impl(word, ret_val, max_word_length);
    return ret_val;
  }
 
  Cnode *insert_child(Cnode *child)
  {
    assert(search_child(child->symbol()) == nullptr);
 
    if (Cnode *sibling = greater_child(child->symbol()); sibling == nullptr)
      this->insert_rightmost_child(child);
    else
      sibling->insert_left_sibling(child);
 
    return child;
  }
 
  bool insert_word(const std::string &word)
  {
    auto [pp, rem] = search_prefix(word.c_str());
 
    if (*rem == '\0')
      {
        if (pp->is_end_word())
          return false;
        pp->mark_end_word();
        return true;
      }
 
    size_t n = 0;
    for (const char *ptr = rem; *ptr; ++ptr)
      ++n;
 
    Pending_Path_Guard path(n);
    for (size_t i = 0; i < n; ++i)
      path.set(i, new Cnode(rem[i]));
 
    path[n - 1]->mark_end_word();
    path.release_nodes();
 
    auto *parent = pp->insert_child(path[0]);
    for (size_t i = 1; i < n; ++i)
      {
        parent->insert_rightmost_child(path[i]);
        parent = path[i];
      }
 
    return true;
  }
 
  void destroy() noexcept
  {
    for (auto p = static_cast<Cnode *>(get_right_child()); p != nullptr;)
      {
        Cnode *to_delete = p;
        p = static_cast<Cnode *>(p->get_left_sibling());
        destroy_tree(to_delete);
      }
    this->set_is_leaf(true);
  }
 
private:
  void words_impl(std::string &word, DynArray<std::string> &l, const size_t max_word_length) const
  {
    if (is_end_word())
      l.append(word);
 
    for (const Tree_Node<char> *child = get_left_child(); child != nullptr;
         child = child->get_right_sibling())
      {
        assert(word.size() < max_word_length);
        const auto *node = static_cast<const Cnode *>(child);
        word.push_back(node->symbol());
        node->words_impl(word, l, max_word_length);
        word.pop_back();
      }
  }
 
public:
  [[nodiscard]] DynArray<std::string> words(size_t max_word_length = 2048) const
  {
    DynArray<std::string> ret_val;
    std::string word;
    word.reserve(max_word_length);
 
    words_impl(word, ret_val, max_word_length);
 
    return ret_val;
  }
 
  void print_words(const size_t max_word_length = 2048) const
  {
    words(max_word_length)
      .for_each([](const std::string &w)
      {
        std::cout << w << '\n';
      });
  }
 
  static void clone(const Tree_Node<char> *src, Tree_Node<char> *tgt)
  {
    const auto *src_node = static_cast<const Cnode *>(src);
    auto *tgt_node = static_cast<Cnode *>(tgt);
    Clone_Target_Rollback rollback(tgt_node);
    tgt_node->ends_word_ = src_node->ends_word_;
 
    for (const Tree_Node<char> *src_child = src_node->get_left_child(); src_child != nullptr;
         src_child = src_child->get_right_sibling())
      {
        const auto *child = static_cast<const Cnode *>(src_child);
        Detached_Subtree_Guard cloned_child(new Cnode(child->symbol()));
        Cnode *tgt_child = cloned_child.get();
        tgt_node->insert_rightmost_child(tgt_child);
        (void) cloned_child.release();
        clone(child, tgt_child);
      }
 
    rollback.release();
  }
 
  [[nodiscard]] Cnode *clone() const
  {
    Detached_Subtree_Guard ret(new Cnode(symbol()));
    clone(this, ret.get());
    return ret.release();
  }
};
 
class Prefix_Tree
{
  Cnode *root_ = nullptr;
  mutable size_t word_count_ = 0;
  mutable bool count_dirty_ = false;
  mutable bool mutable_root_exposed_ = false;
 
  static void destroy_root(Cnode *root) noexcept
  {
    if (root == nullptr)
      return;
 
    root->destroy();
    delete root;
  }
 
  void swap_state(Prefix_Tree &other) noexcept
  {
    std::swap(root_, other.root_);
    std::swap(word_count_, other.word_count_);
    std::swap(count_dirty_, other.count_dirty_);
    std::swap(mutable_root_exposed_, other.mutable_root_exposed_);
  }
 
public:
  Prefix_Tree() : root_(new Cnode('\0'))
  {
    // empty
  }
 
  Prefix_Tree(const Prefix_Tree &other)
    : root_(other.root_->clone()), word_count_(other.count()),
      count_dirty_(false)
  {
    // empty
  }
 
  Prefix_Tree(Prefix_Tree &&other) : Prefix_Tree()
  {
    swap_state(other);
  }
 
  ~Prefix_Tree() noexcept
  {
    destroy_root(root_);
  }
 
  Prefix_Tree &operator = (const Prefix_Tree &other)
  {
    if (this == &other)
      return *this;
 
    Cnode *new_root = other.root_->clone();
    const size_t new_count = other.count();
    destroy_root(root_);
    root_ = new_root;
    word_count_ = new_count;
    count_dirty_ = false;
    mutable_root_exposed_ = false;
    return *this;
  }
 
  Prefix_Tree &operator = (Prefix_Tree &&other)
  {
    if (this == &other)
      return *this;
 
    Prefix_Tree tmp(std::move(other));
    swap_state(tmp);
    return *this;
  }
 
  bool insert_word(const std::string &word)
  {
    const bool inserted = root_->insert_word(word);
    if (inserted and not count_dirty_ and not mutable_root_exposed_)
      ++word_count_;
    return inserted;
  }
 
  [[nodiscard]] bool contains(const std::string &word) const noexcept
  {
    return root_->contains(word);
  }
 
  [[nodiscard]] DynArray<std::string> words(const size_t max_word_length = 2048) const
  {
    return root_->words(max_word_length);
  }
 
  [[nodiscard]] DynArray<std::string> words_with_prefix(const std::string &prefix,
                                                        const size_t max_word_length = 2048) const
  {
    return root_->words_with_prefix(prefix, max_word_length);
  }
 
  [[nodiscard]] size_t count() const noexcept
  {
    if (root_ == nullptr)
      return 0;
 
    if (count_dirty_ or mutable_root_exposed_)
      {
        word_count_ = root_->count();
        count_dirty_ = false;
      }
    return word_count_;
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return count();
  }
 
  [[nodiscard]] Cnode *root() noexcept
  {
    count_dirty_ = true;
    mutable_root_exposed_ = true;
    return root_;
  }
 
  [[nodiscard]] const Cnode *root() const noexcept
  {
    return root_;
  }
};
 
template <typename T>
class Prefix_Tree_Map
{
public:
  using Key = std::string;
 
  using Value = T;
 
private:
  class Node : public Tree_Node<char>
  {
    std::optional<Value> value_;
 
    template <typename Node_Type>
    [[nodiscard]] static Node_Type *search_child_impl(Node_Type *root,
                                                       const char c) noexcept
    {
      assert(root != nullptr);
 
      for (auto *child = root->get_left_child(); child != nullptr;
           child = child->get_right_sibling())
        {
          const char key = child->get_key();
          if (key == c)
            return static_cast<Node_Type *>(child);
          if (key > c)
            return nullptr;
        }
 
      return nullptr;
    }
 
    template <typename Node_Type>
    [[nodiscard]] static Node_Type *greater_child_impl(Node_Type *root,
                                                        const char c) noexcept
    {
      assert(root != nullptr);
 
      for (auto *child = root->get_left_child(); child != nullptr;
           child = child->get_right_sibling())
        if (child->get_key() > c)
          return static_cast<Node_Type *>(child);
      return nullptr;
    }
 
    template <typename Node_Type>
    [[nodiscard]] static std::tuple<Node_Type *, const char *>
    search_prefix_impl(Node_Type *root, const char *prefix) noexcept
    {
      assert(root != nullptr);
      assert(prefix != nullptr);
 
      auto *node = root;
      for (const char *ptr = prefix; *ptr != '\0'; ++ptr)
        {
          auto *child = node->search_child(*ptr);
          if (child == nullptr)
            return std::make_tuple(node, ptr);
          node = child;
        }
 
      return std::make_tuple(node, "");
    }
 
    class Detached_Subtree_Guard
    {
      Node *root_ = nullptr;
 
    public:
      explicit Detached_Subtree_Guard(Node *root) noexcept : root_(root)
      {
        // empty
      }
 
      ~Detached_Subtree_Guard()
      {
        if (root_ != nullptr)
          {
            root_->destroy();
            delete root_;
          }
      }
 
      [[nodiscard]] Node *get() const noexcept
      {
        return root_;
      }
 
      [[nodiscard]] Node *release() noexcept
      {
        Node *ret = root_;
        root_ = nullptr;
        return ret;
      }
    };
 
    class Pending_Path_Guard
    {
      Node **nodes_ = nullptr;
      size_t count_ = 0;
      bool owns_nodes_ = true;
 
    public:
      explicit Pending_Path_Guard(const size_t count)
        : nodes_(new Node *[count]), count_(count)
      {
        for (size_t i = 0; i < count_; ++i)
          nodes_[i] = nullptr;
      }
 
      ~Pending_Path_Guard()
      {
        if (owns_nodes_)
          for (size_t i = 0; i < count_; ++i)
            delete nodes_[i];
        delete[] nodes_;
      }
 
      [[nodiscard]] Node *operator [] (const size_t i) const noexcept
      {
        return nodes_[i];
      }
 
      void set(const size_t i, Node *node) const noexcept
      {
        nodes_[i] = node;
      }
 
      void release_nodes() noexcept
      {
        owns_nodes_ = false;
      }
    };
 
  public:
    explicit Node(const char c) noexcept
    {
      this->get_key() = c;
    }
 
    template <typename U>
    Node(const char c, U &&value) : value_(std::forward<U>(value))
    {
      this->get_key() = c;
    }
 
    [[nodiscard]] char symbol() const noexcept
    {
      return get_key();
    }
 
    [[nodiscard]] bool has_value() const noexcept
    {
      return value_.has_value();
    }
 
    [[nodiscard]] const Value *value() const noexcept
    {
      return value_.has_value() ? &*value_ : nullptr;
    }
 
    [[nodiscard]] Value *value() noexcept
    {
      return value_.has_value() ? &*value_ : nullptr;
    }
 
    void reset_value() noexcept
    {
      value_.reset();
    }
 
    template <typename U>
    void emplace_value(U &&value)
    {
      value_.emplace(std::forward<U>(value));
    }
 
    [[nodiscard]] Node *search_child(const char c) noexcept
    {
      return search_child_impl(this, c);
    }
 
    [[nodiscard]] const Node *search_child(const char c) const noexcept
    {
      return search_child_impl(this, c);
    }
 
    [[nodiscard]] Node *greater_child(const char c) noexcept
    {
      return greater_child_impl(this, c);
    }
 
    [[nodiscard]] const Node *greater_child(const char c) const noexcept
    {
      return greater_child_impl(this, c);
    }
 
    [[nodiscard]] std::tuple<Node *, const char *>
    search_prefix(const char *prefix) noexcept
    {
      return search_prefix_impl(this, prefix);
    }
 
    [[nodiscard]] std::tuple<const Node *, const char *>
    search_prefix(const char *prefix) const noexcept
    {
      return search_prefix_impl(this, prefix);
    }
 
    Node *insert_child(Node *child)
    {
      assert(search_child(child->symbol()) == nullptr);
 
      if (Node *sibling = greater_child(child->symbol()); sibling == nullptr)
        this->insert_rightmost_child(child);
      else
        sibling->insert_left_sibling(child);
 
      return child;
    }
 
    template <typename U>
    void insert_suffix(const char *suffix, U &&value)
    {
      assert(suffix != nullptr);
      assert(*suffix != '\0');
 
      size_t n = 0;
      for (const char *ptr = suffix; *ptr != '\0'; ++ptr)
        ++n;
 
      Pending_Path_Guard path(n);
      for (size_t i = 0; i + 1 < n; ++i)
        path.set(i, new Node(suffix[i]));
      path.set(n - 1, new Node(suffix[n - 1], std::forward<U>(value)));
      path.release_nodes();
 
      Node *parent = insert_child(path[0]);
      for (size_t i = 1; i < n; ++i)
        {
          parent->insert_rightmost_child(path[i]);
          parent = path[i];
        }
    }
 
    void destroy() noexcept
    {
      for (auto *p = static_cast<Node *>(get_right_child()); p != nullptr;)
        {
          Node *to_delete = p;
          p = static_cast<Node *>(p->get_left_sibling());
          destroy_tree(to_delete);
        }
      this->set_is_leaf(true);
    }
 
    [[nodiscard]] Node *clone() const
      requires std::is_copy_constructible_v<Value>
    {
      Detached_Subtree_Guard ret(new Node(symbol()));
      clone_into(this, ret.get());
      return ret.release();
    }
 
    static void clone_into(const Node *src, Node *tgt)
      requires std::is_copy_constructible_v<Value>
    {
      assert(src != nullptr);
      assert(tgt != nullptr);
 
      if (src->value_.has_value())
        tgt->value_.emplace(*src->value_);
 
      for (const Tree_Node<char> *src_child = src->get_left_child();
           src_child != nullptr; src_child = src_child->get_right_sibling())
        {
          const auto *child = static_cast<const Node *>(src_child);
          Detached_Subtree_Guard cloned_child(new Node(child->symbol()));
          Node *tgt_child = cloned_child.get();
          tgt->insert_rightmost_child(tgt_child);
          (void) cloned_child.release();
          clone_into(child, tgt_child);
        }
    }
 
    void words_impl(std::string &word, DynArray<std::string> &out,
                    const size_t max_word_length) const
    {
      if (has_value())
        out.append(word);
 
      for (const Tree_Node<char> *child = get_left_child(); child != nullptr;
           child = child->get_right_sibling())
        {
          assert(word.size() < max_word_length);
          const auto *node = static_cast<const Node *>(child);
          word.push_back(node->symbol());
          node->words_impl(word, out, max_word_length);
          word.pop_back();
        }
    }
  };
 
  Node *root_ = nullptr;
  size_t size_ = 0;
 
  static void destroy_root(Node *root) noexcept
  {
    if (root == nullptr)
      return;
 
    root->destroy();
    delete root;
  }
 
  void ensure_root()
  {
    if (root_ == nullptr)
      root_ = new Node('\0');
  }
 
  [[nodiscard]] const Node *find_node(const std::string &word) const noexcept
  {
    if (root_ == nullptr)
      return nullptr;
 
    auto [node, remaining] = root_->search_prefix(word.c_str());
    return *remaining == '\0' ? node : nullptr;
  }
 
  [[nodiscard]] Node *find_node(const std::string &word) noexcept
  {
    return const_cast<Node *>(
      static_cast<const Prefix_Tree_Map *>(this)->find_node(word));
  }
 
  template <typename U>
  bool insert_impl(const std::string &word, U &&value,
                    const bool assign_if_present = false)
  {
    ensure_root();
 
    auto [node, remaining] = root_->search_prefix(word.c_str());
    if (*remaining == '\0')
      {
        if (node->has_value())
          {
            if (assign_if_present)
              *node->value() = std::forward<U>(value);
            return false;
          }
        node->emplace_value(std::forward<U>(value));
        ++size_;
        return true;
      }
 
    node->insert_suffix(remaining, std::forward<U>(value));
    ++size_;
    return true;
  }
 
public:
  Prefix_Tree_Map() : root_(new Node('\0'))
  {
    // empty
  }
 
  Prefix_Tree_Map(const Prefix_Tree_Map &other)
    requires std::is_copy_constructible_v<Value>
    : root_(other.root_ != nullptr ? other.root_->clone() : nullptr),
      size_(other.size_)
  {
    // empty
  }
 
  Prefix_Tree_Map(Prefix_Tree_Map &&other) noexcept
    : root_(other.root_), size_(other.size_)
  {
    other.root_ = nullptr;
    other.size_ = 0;
  }
 
  ~Prefix_Tree_Map() noexcept
  {
    destroy_root(root_);
  }
 
  Prefix_Tree_Map &operator = (const Prefix_Tree_Map &other)
    requires std::is_copy_constructible_v<Value>
  {
    if (this == &other)
      return *this;
 
    Node *new_root = other.root_ != nullptr ? other.root_->clone() : nullptr;
    destroy_root(root_);
    root_ = new_root;
    size_ = other.size_;
    return *this;
  }
 
  Prefix_Tree_Map &operator = (Prefix_Tree_Map &&other) noexcept
  {
    if (this == &other)
      return *this;
 
    destroy_root(root_);
    root_ = other.root_;
    size_ = other.size_;
    other.root_ = nullptr;
    other.size_ = 0;
    return *this;
  }
 
  bool insert(const Key &key, const Value &value)
  {
    return insert_impl(key, value);
  }
 
  bool insert(const Key &key, Value &&value)
  {
    return insert_impl(key, std::move(value));
  }
 
  void insert_or_assign(const Key &key, Value value)
  {
    insert_impl(key, std::move(value), /* assign_if_present = */ true);
  }
 
  bool erase(const Key &key) noexcept
  {
    Node *node = find_node(key);
    if (node == nullptr or not node->has_value())
      return false;
 
    node->reset_value();
    --size_;
    return true;
  }
 
  [[nodiscard]] bool contains(const Key &key) const noexcept
  {
    return find(key) != nullptr;
  }
 
  [[nodiscard]] const Value *find(const Key &key) const noexcept
  {
    const Node *node = find_node(key);
    return node != nullptr ? node->value() : nullptr;
  }
 
  [[nodiscard]] Value *find(const Key &key) noexcept
  {
    Node *node = find_node(key);
    return node != nullptr ? node->value() : nullptr;
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return size_;
  }
 
  [[nodiscard]] size_t count() const noexcept
  {
    return size();
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return size_ == 0;
  }
 
  void clear()
  {
    Node *new_root = new Node('\0');
    destroy_root(root_);
    root_ = new_root;
    size_ = 0;
  }
 
  [[nodiscard]] DynArray<Key> words(const size_t max_word_length = 2048) const
  {
    DynArray<Key> ret;
    if (root_ == nullptr)
      return ret;
 
    std::string word;
    word.reserve(max_word_length);
    root_->words_impl(word, ret, max_word_length);
    return ret;
  }
 
  [[nodiscard]] DynArray<Key> words_with_prefix(const Key &prefix,
                                                const size_t max_word_length = 2048) const
  {
    DynArray<Key> ret;
    if (root_ == nullptr)
      return ret;
 
    auto [node, remaining] = root_->search_prefix(prefix.c_str());
    if (*remaining != '\0')
      return ret;
 
    assert(prefix.size() <= max_word_length);
    std::string word(prefix);
    word.reserve(max_word_length);
    node->words_impl(word, ret, max_word_length);
    return ret;
  }
};
}  // end namespace Aleph
 
#endif  // PREFIX_TREE_H