tpl_patricia_trie.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_PATRICIA_TRIE_H
#define TPL_PATRICIA_TRIE_H
 
#include <array>
#include <cstddef>
#include <limits>
#include <memory>
#include <optional>
#include <type_traits>
#include <utility>
 
#include <tpl_array.H>
 
namespace Aleph
{
 
namespace patricia_trie_detail
{
 
template <typename UInt>
struct Bitwise_Trie_Utils
{
  static constexpr size_t bit_width = std::numeric_limits<UInt>::digits;
 
  [[nodiscard]] static bool bit_at(const UInt key,
                                   const size_t bit_index) noexcept
  {
    return ((key >> (bit_width - 1 - bit_index)) & UInt{1}) != UInt{0};
  }
 
  [[nodiscard]] static size_t first_differing_bit(const UInt lhs,
                                                   const UInt rhs) noexcept
  {
    const UInt diff = lhs ^ rhs;
    for (size_t i = 0; i < bit_width; ++i)
      if (bit_at(diff, i))
        return i;
    return bit_width;
  }
 
  template <typename Node>
  [[nodiscard]] static const Node * leaf_for(const Node * node,
                                             const UInt key) noexcept
  {
    while (node != nullptr and not node->leaf)
      node = node->child[bit_at(key, node->bit_index) ? 1 : 0].get();
    return node;
  }
 
  template <typename Node>
  [[nodiscard]] static Node * leaf_for(Node * node, const UInt key) noexcept
  {
    return const_cast<Node *>(leaf_for(static_cast<const Node *>(node), key));
  }
 
  template <typename Node>
  static void collect_keys(const Node * node, Array<UInt> & out)
  {
    if (node == nullptr)
      return;
    if (node->leaf)
      {
        out.append(node->key);
        return;
      }
    collect_keys(node->child[0].get(), out);
    collect_keys(node->child[1].get(), out);
  }
 
  template <typename Node>
  [[nodiscard]] static bool erase_key(std::unique_ptr<Node> & root,
                                      size_t & size,
                                      const UInt key) noexcept
  {
    if (root == nullptr)
      return false;
 
    if (root->leaf)
      {
        if (root->key != key)
          return false;
        root.reset();
        size = 0;
        return true;
      }
 
    std::unique_ptr<Node> * parent_link = nullptr;
    std::unique_ptr<Node> * link = &root;
    while ((*link)->leaf == false)
      {
        parent_link = link;
        link = &(*link)->child[bit_at(key, (*link)->bit_index) ? 1 : 0];
      }
 
    if ((*link)->key != key)
      return false;
 
    Node * parent = parent_link->get();
    const size_t side = bit_at(key, parent->bit_index) ? 1 : 0;
    *parent_link = std::move(parent->child[1 - side]);
    --size;
    return true;
  }
 
  template <typename Node>
  [[nodiscard]] static bool subtree_matches(const Node * node,
                                            const size_t bit_index,
                                            const bool expected) noexcept
  {
    if (node == nullptr)
      return false;
    if (node->leaf)
      return bit_at(node->key, bit_index) == expected;
    return subtree_matches(node->child[0].get(), bit_index, expected) and
           subtree_matches(node->child[1].get(), bit_index, expected);
  }
 
  template <typename Node>
  [[nodiscard]] static bool check_invariants_rec(const Node * node,
                                                  const size_t parent_bit,
                                                  const bool has_parent,
                                                  size_t & counted) noexcept
  {
    if (node == nullptr)
      return true;
 
    if (node->leaf)
      {
        if constexpr (requires { node->value.has_value(); })
          if (not node->value.has_value())
            return false;
        ++counted;
        return true;
      }
 
    if constexpr (requires { node->value.has_value(); })
      if (node->value.has_value())
        return false;
    if (node->bit_index >= bit_width)
      return false;
    if (has_parent and node->bit_index <= parent_bit)
      return false;
    if (node->child[0] == nullptr or node->child[1] == nullptr)
      return false;
    if (not subtree_matches(node->child[0].get(), node->bit_index, false))
      return false;
    if (not subtree_matches(node->child[1].get(), node->bit_index, true))
      return false;
 
    return check_invariants_rec(node->child[0].get(), node->bit_index, true,
                                counted) and
           check_invariants_rec(node->child[1].get(), node->bit_index, true,
                                counted);
  }
};
 
} // namespace patricia_trie_detail
 
template <typename UInt>
requires (std::is_integral_v<UInt> and std::is_unsigned_v<UInt> and
          not std::is_same_v<UInt, bool>)
class PatriciaSet
{
public:
  using Key = UInt;
 
  static constexpr size_t bit_width = std::numeric_limits<Key>::digits;
 
private:
  struct Node
  {
    bool leaf = true;
    Key key = 0;
    size_t bit_index = 0;
    std::array<std::unique_ptr<Node>, 2> child{};
 
    explicit Node(const Key k) noexcept : leaf(true), key(k) {}
    explicit Node(const size_t bit) noexcept : leaf(false), bit_index(bit) {}
  };
 
  std::unique_ptr<Node> root_;
  size_t size_ = 0;
  using Detail = patricia_trie_detail::Bitwise_Trie_Utils<Key>;
 
  [[nodiscard]] static std::unique_ptr<Node> clone_node(const Node * src)
  {
    if (src == nullptr)
      return nullptr;
    auto dst = src->leaf ? std::make_unique<Node>(src->key)
                         : std::make_unique<Node>(src->bit_index);
    if (not src->leaf)
      {
        dst->child[0] = clone_node(src->child[0].get());
        dst->child[1] = clone_node(src->child[1].get());
      }
    return dst;
  }
 
public:
  PatriciaSet() = default;
 
  ~PatriciaSet() = default;
 
  PatriciaSet(const PatriciaSet & other)
    : root_(clone_node(other.root_.get())), size_(other.size_)
  {}
 
  PatriciaSet & operator=(const PatriciaSet & other)
  {
    if (this != &other)
      {
        root_ = clone_node(other.root_.get());
        size_ = other.size_;
      }
    return *this;
  }
 
  PatriciaSet(PatriciaSet && other) noexcept
    : root_(std::move(other.root_)), size_(other.size_)
  {
    other.size_ = 0;
  }
 
  PatriciaSet & operator=(PatriciaSet && other) noexcept
  {
    if (this != &other)
      {
        root_ = std::move(other.root_);
        size_ = other.size_;
        other.size_ = 0;
      }
    return *this;
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return size_;
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return size_ == 0;
  }
 
  void clear() noexcept
  {
    root_.reset();
    size_ = 0;
  }
 
  [[nodiscard]] bool contains(const Key key) const noexcept
  {
    const Node * leaf = Detail::leaf_for(root_.get(), key);
    return leaf != nullptr and leaf->key == key;
  }
 
  bool insert(const Key key)
  {
    if (root_ == nullptr)
      {
        root_ = std::make_unique<Node>(key);
        size_ = 1;
        return true;
      }
 
    const Node * existing = Detail::leaf_for(root_.get(), key);
    if (existing->key == key)
      return false;
 
    const size_t diff_bit = Detail::first_differing_bit(key, existing->key);
    auto * link = &root_;
    while ((*link)->leaf == false and (*link)->bit_index < diff_bit)
      link = &(*link)->child[Detail::bit_at(key, (*link)->bit_index) ? 1 : 0];
 
    auto branch = std::make_unique<Node>(diff_bit);
    const size_t side = Detail::bit_at(key, diff_bit) ? 1 : 0;
    branch->child[side] = std::make_unique<Node>(key);
    branch->child[1 - side] = std::move(*link);
    *link = std::move(branch);
    ++size_;
    return true;
  }
 
  bool erase(const Key key) noexcept
  {
    return Detail::erase_key(root_, size_, key);
  }
 
  [[nodiscard]] Array<Key> keys() const
  {
    Array<Key> result;
    result.reserve(size_);
    Detail::collect_keys(root_.get(), result);
    return result;
  }
 
  [[nodiscard]] bool check_invariants() const noexcept
  {
    size_t counted = 0;
    const bool ok = Detail::check_invariants_rec(root_.get(), 0, false, counted);
    return ok and counted == size_;
  }
};
 
template <typename UInt, typename T>
requires (std::is_integral_v<UInt> and std::is_unsigned_v<UInt> and
          not std::is_same_v<UInt, bool>)
class PatriciaMap
{
public:
  using Key = UInt;
 
  using Value = T;
 
  static constexpr size_t bit_width = std::numeric_limits<Key>::digits;
 
private:
  struct Node
  {
    bool leaf = true;
    Key key = 0;
    size_t bit_index = 0;
    std::optional<Value> value;
    std::array<std::unique_ptr<Node>, 2> child{};
 
    template <typename U>
    Node(const Key k, U && v) : leaf(true), key(k), value(std::forward<U>(v)) {}
 
    explicit Node(const size_t bit) noexcept : leaf(false), bit_index(bit) {}
  };
 
  std::unique_ptr<Node> root_;
  size_t size_ = 0;
  using Detail = patricia_trie_detail::Bitwise_Trie_Utils<Key>;
 
  [[nodiscard]] static std::unique_ptr<Node> clone_node(const Node * src)
    requires std::is_copy_constructible_v<Value>
  {
    if (src == nullptr)
      return nullptr;
    auto dst = src->leaf ? std::make_unique<Node>(src->key, *src->value)
                         : std::make_unique<Node>(src->bit_index);
    if (not src->leaf)
      {
        dst->child[0] = clone_node(src->child[0].get());
        dst->child[1] = clone_node(src->child[1].get());
      }
    return dst;
  }
 
  template <typename U>
  bool insert_impl(const Key key, U && value)
  {
    if (root_ == nullptr)
      {
        root_ = std::make_unique<Node>(key, std::forward<U>(value));
        size_ = 1;
        return true;
      }
 
    const Node * existing = Detail::leaf_for(root_.get(), key);
    if (existing->key == key)
      return false;
 
    const size_t diff_bit = Detail::first_differing_bit(key, existing->key);
    auto * link = &root_;
    while ((*link)->leaf == false and (*link)->bit_index < diff_bit)
      link = &(*link)->child[Detail::bit_at(key, (*link)->bit_index) ? 1 : 0];
 
    auto branch = std::make_unique<Node>(diff_bit);
    const size_t side = Detail::bit_at(key, diff_bit) ? 1 : 0;
    branch->child[side] = std::make_unique<Node>(key, std::forward<U>(value));
    branch->child[1 - side] = std::move(*link);
    *link = std::move(branch);
    ++size_;
    return true;
  }
 
public:
  PatriciaMap() = default;
 
  ~PatriciaMap() = default;
 
  PatriciaMap(const PatriciaMap & other)
    requires std::is_copy_constructible_v<Value>
    : root_(clone_node(other.root_.get())), size_(other.size_)
  {}
 
  PatriciaMap & operator=(const PatriciaMap & other)
    requires std::is_copy_constructible_v<Value>
  {
    if (this != &other)
      {
        root_ = clone_node(other.root_.get());
        size_ = other.size_;
      }
    return *this;
  }
 
  PatriciaMap(PatriciaMap && other) noexcept
    : root_(std::move(other.root_)), size_(other.size_)
  {
    other.size_ = 0;
  }
 
  PatriciaMap & operator=(PatriciaMap && other) noexcept
  {
    if (this != &other)
      {
        root_ = std::move(other.root_);
        size_ = other.size_;
        other.size_ = 0;
      }
    return *this;
  }
 
  [[nodiscard]] size_t size() const noexcept
  {
    return size_;
  }
 
  [[nodiscard]] bool is_empty() const noexcept
  {
    return size_ == 0;
  }
 
  void clear() noexcept
  {
    root_.reset();
    size_ = 0;
  }
 
  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)
  {
    Value * slot = find(key);
    if (slot != nullptr)
      *slot = std::move(value);
    else
      insert_impl(key, std::move(value));
  }
 
  bool erase(const Key key) noexcept
  {
    return Detail::erase_key(root_, size_, key);
  }
 
  [[nodiscard]] bool contains(const Key key) const noexcept
  {
    return find(key) != nullptr;
  }
 
  [[nodiscard]] const Value * find(const Key key) const noexcept
  {
    const Node * leaf = Detail::leaf_for(root_.get(), key);
    return (leaf != nullptr and leaf->key == key) ? &*leaf->value : nullptr;
  }
 
  [[nodiscard]] Value * find(const Key key) noexcept
  {
    Node * leaf = Detail::leaf_for(root_.get(), key);
    return (leaf != nullptr and leaf->key == key) ? &*leaf->value : nullptr;
  }
 
  [[nodiscard]] Array<Key> keys() const
  {
    Array<Key> result;
    result.reserve(size_);
    Detail::collect_keys(root_.get(), result);
    return result;
  }
 
  [[nodiscard]] bool check_invariants() const noexcept
  {
    size_t counted = 0;
    const bool ok = Detail::check_invariants_rec(root_.get(), 0, false, counted);
    return ok and counted == size_;
  }
};
 
} // namespace Aleph
 
#endif // TPL_PATRICIA_TRIE_H