tpl_radix_tree.H

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  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 TPL_RADIX_TREE_H
#define TPL_RADIX_TREE_H
 
#include <algorithm>
#include <memory>
#include <optional>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
 
#include <ah-errors.H>
#include <tpl_array.H>
 
namespace Aleph {
 
template <typename T, typename Char = char>
class RadixTree
{
public:
  using Key = std::basic_string<Char>;
 
private:
  struct Node
  {
    Key edge_label;          // label of the edge from the parent to this
                             // node; empty only for the root.
    std::optional<T> value;  // set iff some key ends exactly at this node.
    Array<std::pair<Char, std::unique_ptr<Node>>> children;
    // unordered; a node's children always have
    // pairwise-distinct first characters in
    // their own edge_label.
 
    Node() = default;
    explicit Node(Key label) : edge_label(std::move(label)) {}
  };
 
  static constexpr size_t npos = static_cast<size_t>(-1);
 
  std::unique_ptr<Node> root_;
  size_t size_ = 0;
 
  // Only ever called with a `const Node *` (from find_node(),
  // longest_prefix(), keys_with_prefix(), all read-only traversals);
  // insert_impl()/erase() need the child's *slot index* to mutate the
  // parent afterward, so they use find_child_slot() instead. No non-const
  // overload is needed.
  [[nodiscard]] static const Node *find_child(const Node *node, const Char c) noexcept
  {
    for (const auto &kv : node->children)
      if (kv.first == c)
        return kv.second.get();
    return nullptr;
  }
 
  [[nodiscard]] static size_t find_child_slot(Node *node, const Char c) noexcept
  {
    for (size_t i = 0; i < node->children.size(); ++i)
      if (node->children[i].first == c)
        return i;
    return npos;
  }
 
  static void add_child(Node *node, const Char c, std::unique_ptr<Node> child)
  {
    node->children.append(std::make_pair(c, std::move(child)));
  }
 
  static void remove_child_at(Node *node, const size_t idx)
  {
    const size_t last = node->children.size() - 1;
    if (idx != last)
      std::swap(node->children[idx], node->children[last]);
    std::ignore = node->children.remove_last();
  }
 
  [[nodiscard]] static size_t common_prefix_length(const Key &label, const Key &key,
                                                   const size_t key_off) noexcept
  {
    const size_t max_n = std::min(label.size(), key.size() - key_off);
    size_t n = 0;
    while (n < max_n and label[n] == key[key_off + n])
      ++n;
    return n;
  }
 
  template <typename U>
  bool insert_impl(const Key &key, U &&value, const bool assign_if_present = false)
  {
    Node *cur = root_.get();
    size_t i = 0;
 
    for (;;)
      {
        if (i == key.size())
          {
            if (cur->value.has_value())
              {
                if (assign_if_present)
                  *cur->value = std::forward<U>(value);
                return false;
              }
            cur->value.emplace(std::forward<U>(value));
            ++size_;
            return true;
          }
 
        const Char c = key[i];
        const size_t slot = find_child_slot(cur, c);
 
        if (slot == npos)
          {
            auto leaf = std::make_unique<Node>(key.substr(i));
            leaf->value.emplace(std::forward<U>(value));
            add_child(cur, c, std::move(leaf));
            ++size_;
            return true;
          }
 
        Node *child = cur->children[slot].second.get();
        const Key &label = child->edge_label;
        const size_t remaining = key.size() - i;
        const size_t lcp = common_prefix_length(label, key, i);
 
        if (lcp == label.size())
          {
            // The whole edge matches; keep descending.
            i += lcp;
            cur = child;
            continue;
          }
 
        // `label` only partially matches: split it at `lcp` (lcp >= 1,
        // since `child` was found via its first character matching `c`).
        Key split_label = label.substr(0, lcp);
        Key child_suffix = label.substr(lcp);
        auto split = std::make_unique<Node>(std::move(split_label));
        split->children.reserve(lcp == remaining ? 1 : 2);
 
        if (lcp == remaining)
          {
            // The new key ends exactly at the split point.
            split->value.emplace(std::forward<U>(value));
          }
        else
          {
            auto leaf = std::make_unique<Node>(key.substr(i + lcp));
            leaf->value.emplace(std::forward<U>(value));
            const Char leaf_first = leaf->edge_label[0];
            add_child(split.get(), leaf_first, std::move(leaf));
          }
 
        child->edge_label = std::move(child_suffix);
        const Char child_first = child->edge_label[0];
 
        split->children.append(std::make_pair(child_first, std::unique_ptr<Node>{}));
        std::unique_ptr<Node> detached = std::move(cur->children[slot].second);
        split->children[split->children.size() - 1].second = std::move(detached);
        cur->children[slot].second = std::move(split);
        ++size_;
        return true;
      }
  }
 
  [[nodiscard]] const Node *find_node(const Key &key) const noexcept
  {
    const Node *cur = root_.get();
    size_t i = 0;
    while (i < key.size())
      {
        const Char c = key[i];
        const Node *child = find_child(cur, c);
        if (child == nullptr)
          return nullptr;
 
        const Key &label = child->edge_label;
        const size_t remaining = key.size() - i;
        if (label.size() > remaining or key.compare(i, label.size(), label) != 0)
          return nullptr;
 
        i += label.size();
        cur = child;
      }
    return cur;
  }
 
  static void collect_keys(const Node *node, Key &prefix_acc, Array<Key> &out)
  {
    if (node->value.has_value())
      out.append(prefix_acc);
    for (const auto &kv : node->children)
      {
        const size_t old_size = prefix_acc.size();
        prefix_acc += kv.second->edge_label;
        collect_keys(kv.second.get(), prefix_acc, out);
        prefix_acc.resize(old_size);
      }
  }
 
  [[nodiscard]] static std::unique_ptr<Node> clone_node(const Node *src)
    requires std::is_copy_constructible_v<T>
  {
    auto dst = std::make_unique<Node>(src->edge_label);
    if (src->value.has_value())
      dst->value.emplace(*src->value);
    dst->children.reserve(src->children.size());
    for (const auto &kv : src->children)
      dst->children.append(std::make_pair(kv.first, clone_node(kv.second.get())));
    return dst;
  }
 
public:
  RadixTree() : root_(std::make_unique<Node>()) {}
 
  ~RadixTree() = default;
 
  RadixTree(RadixTree &&other) : root_(std::make_unique<Node>()), size_(0)
  {
    root_.swap(other.root_);
    std::swap(size_, other.size_);
  }
 
  RadixTree &operator = (RadixTree &&other)
  {
    if (this != &other)
      {
        auto empty_root = std::make_unique<Node>();
        root_ = std::move(other.root_);
        size_ = other.size_;
        other.root_ = std::move(empty_root);
        other.size_ = 0;
      }
    return *this;
  }
 
  RadixTree(const RadixTree &other)
    requires std::is_copy_constructible_v<T>
    : root_(clone_node(other.root_.get())), size_(other.size_)
  {}
 
  RadixTree &operator = (const RadixTree &other)
    requires std::is_copy_constructible_v<T>
  {
    if (this != &other)
      {
        root_ = clone_node(other.root_.get());
        size_ = other.size_;
      }
    return *this;
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return size_;
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return size_ == 0;
  }
 
  bool insert(const Key &key, const T &value)
  {
    return insert_impl(key, value);
  }
 
  bool insert(const Key &key, T &&value)
  {
    return insert_impl(key, std::move(value));
  }
 
  void insert_or_assign(const Key &key, T value)
  {
    insert_impl(key, std::move(value), /* assign_if_present = */ true);
  }
 
  bool erase(const Key &key)
  {
    struct Frame
    {
      Node *parent;
      size_t slot;
    };
    Array<Frame> path;
 
    Node *cur = root_.get();
    size_t i = 0;
    while (i < key.size())
      {
        const Char c = key[i];
        const size_t slot = find_child_slot(cur, c);
        if (slot == npos)
          return false;
 
        Node *child = cur->children[slot].second.get();
        const Key &label = child->edge_label;
        const size_t remaining = key.size() - i;
        if (label.size() > remaining or key.compare(i, label.size(), label) != 0)
          return false;
 
        path.append(Frame{cur, slot});
        i += label.size();
        cur = child;
      }
 
    if (not cur->value.has_value())
      return false;
 
    cur->value.reset();
    --size_;
 
    // Bubble upward: prune now-empty leaves, and merge any node left with
    // exactly one child and no value back into a single compressed edge.
    while (not path.is_empty())
      {
        const Frame f = path.get_last();
        std::ignore = path.remove_last();
        Node *node = f.parent->children[f.slot].second.get();
 
        if (node->children.is_empty() and not node->value.has_value())
          {
            remove_child_at(f.parent, f.slot);
            continue;  // f.parent's shape changed; the next frame re-checks it.
          }
 
        if (node->children.size() == 1 and not node->value.has_value())
          {
            auto &only = node->children[0];
            only.second->edge_label = node->edge_label + only.second->edge_label;
            f.parent->children[f.slot].second = std::move(only.second);
          }
 
        break;  // Nothing above `node` changed shape; stop bubbling.
      }
 
    return true;
  }
 
  [[nodiscard]] bool contains(const Key &key) const noexcept
  {
    return find(key) != nullptr;
  }
 
  [[nodiscard]] const T *find(const Key &key) const noexcept
  {
    const Node *n = find_node(key);
    return (n != nullptr and n->value.has_value()) ? &*n->value : nullptr;
  }
 
  [[nodiscard]] T *find(const Key &key) noexcept
  {
    const Node *n = find_node(key);
    return (n != nullptr and n->value.has_value()) ? const_cast<T *>(&*n->value) : nullptr;
  }
 
  [[nodiscard]] std::optional<Key> longest_prefix(const Key &key) const
  {
    std::optional<Key> best;
    const Node *cur = root_.get();
    size_t i = 0;
 
    if (cur->value.has_value())
      best = Key{};
 
    while (i < key.size())
      {
        const Char c = key[i];
        const Node *child = find_child(cur, c);
        if (child == nullptr)
          break;
 
        const Key &label = child->edge_label;
        const size_t remaining = key.size() - i;
        if (label.size() > remaining or key.compare(i, label.size(), label) != 0)
          break;
 
        i += label.size();
        cur = child;
        if (cur->value.has_value())
          best = key.substr(0, i);
      }
 
    return best;
  }
 
  [[nodiscard]] Array<Key> keys_with_prefix(const Key &prefix) const
  {
    Array<Key> result;
    const Node *cur = root_.get();
    size_t i = 0;
 
    while (i < prefix.size())
      {
        const Char c = prefix[i];
        const Node *child = find_child(cur, c);
        if (child == nullptr)
          return result;
 
        const Key &label = child->edge_label;
        const size_t remaining = prefix.size() - i;
        const size_t lcp = common_prefix_length(label, prefix, i);
 
        if (lcp < label.size())
          {
            if (lcp != remaining)
              return result;  // genuine mismatch: nothing shares `prefix`.
            // `prefix` runs out partway through this edge: every key under
            // `child` still starts with `prefix` (the edge is consistent
            // with it as far as it goes).
            Key base = prefix.substr(0, i) + label;
            collect_keys(child, base, result);
            return result;
          }
 
        i += lcp;
        cur = child;
      }
 
    Key base = prefix;
    collect_keys(cur, base, result);
    return result;
  }
 
  [[nodiscard]] bool verify() const
  {
    size_t counted_values = 0;
    const bool structurally_valid = verify_rec(root_.get(), true, counted_values);
    return structurally_valid and counted_values == size_;
  }
 
private:
  static bool verify_rec(const Node *node, const bool is_root, size_t &counted_values)
  {
    if (node->value.has_value())
      ++counted_values;
 
    if (not is_root)
      {
        if (node->edge_label.empty())
          return false;
        if (node->children.size() == 1 and not node->value.has_value())
          return false;
      }
 
    for (size_t i = 0; i < node->children.size(); ++i)
      for (size_t j = i + 1; j < node->children.size(); ++j)
        if (node->children[i].first == node->children[j].first)
          return false;
 
    for (const auto &kv : node->children)
      {
        if (kv.second->edge_label.empty() or kv.second->edge_label[0] != kv.first)
          return false;
        if (not verify_rec(kv.second.get(), false, counted_values))
          return false;
      }
 
    return true;
  }
};
 
}  // namespace Aleph
 
#endif  // TPL_RADIX_TREE_H