ZipTrie.hpp

Go to the documentation of this file.

 
#pragma once
 
#include "BitString.cuh"
 
#include <compare>   // For std::strong_ordering
#include <limits>    // For std::numeric_limits
#include <vector>    // For std::vector
#include <cmath>     // For std::log2
#include <random>    // For random rank generation
#include <fstream>   // For file output (to_dot)
#include <optional>  // For std::optional
#include <string>    // For std::string
#include <type_traits> // For std::conditional_t
#include <ostream>   // For std::ostream
#include <algorithm> // For std::max, std::min
#include <iostream>  // For std::cerr (used in to_dot error handling)
 
struct MemoryEfficientLCP
{
    uint8_t exp_of_2 = 0;
    uint8_t multiple = 0;
 
    auto operator<=>(const MemoryEfficientLCP&) const = default;
 
    unsigned value() const noexcept;
 
    std::ostream& print(std::ostream& os) const noexcept;
};
 
struct GeometricRank
{
    uint8_t geometric_rank;
    uint8_t uniform_rank;
 
    auto operator<=>(const GeometricRank&) const = default;
 
    static GeometricRank get_random();
};
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
class ZipTrie
{
public:
    using LCP_T = std::conditional_t<MEMORY_EFFICIENT, MemoryEfficientLCP, unsigned>;
    using KEY_T = BitString<CHAR_T, CHAR_SIZE_BITS>;
 
    ZipTrie(unsigned max_size, unsigned max_lcp_length) noexcept;
 
    int get_depth(const KEY_T* key) const noexcept;
 
    int height() const noexcept;
 
    double get_average_height() const noexcept;
 
    unsigned size() const noexcept;
 
    bool contains(const KEY_T* key) const noexcept;
 
    LCP_T lcp(const KEY_T* key) const noexcept;
 
    void insert(const KEY_T* key) noexcept;
 
    // bool remove(const KEY_T& key) noexcept;
 
    const RANK_T& get_root_rank() const noexcept;
 
    void set(const KEY_T* key, RANK_T rank, unsigned left, unsigned right, LCP_T predecessor_lcp, LCP_T successor_lcp) noexcept;
 
    void set_root_index(unsigned root_index) noexcept;
 
    struct SearchResults
    {
        bool contains;
        LCP_T max_lcp;
        int depth;
    };
 
    virtual SearchResults search(const KEY_T* key) const noexcept;
 
    void to_dot(const std::string& file_path) const noexcept;
 
protected:
    unsigned _root_index;
    unsigned _max_lcp_length; // TODO: Review if this is actively used or if _log_max_size suffices.
    uint8_t _log_max_size;
 
    static constexpr unsigned NULLPTR = std::numeric_limits<unsigned>::max();
 
    struct AncestorLCPs
    {
        LCP_T predecessor = {}; // Default initialize (0 for unsigned, {0,0} for MemoryEfficientLCP)
        LCP_T successor = {};   // Default initialize
    };
 
    struct Bucket
    {
        const KEY_T* key;
        RANK_T rank;
        unsigned left = NULLPTR;
        unsigned right = NULLPTR;
        AncestorLCPs ancestor_lcps = {};
    };
 
    std::vector<Bucket> _buckets;
 
    inline MemoryEfficientLCP get_memory_efficient_lcp(size_t num) const noexcept;
 
    template <typename CompareFunction>
    SearchResults search_recursive(const KEY_T* key, CompareFunction compare_func) const noexcept;
 
    template<typename CompareFunction>
    unsigned insert_recursive(Bucket* x, unsigned x_index, unsigned v_index, AncestorLCPs ancestor_lcps, CompareFunction compare_func) noexcept;
 
// Protected Member Variables and Helper Structures/Functions used internally
 
protected:
    struct ComparisonResult
    {
        std::strong_ordering comparison;
        LCP_T lcp;
    };
 
    std::optional<ComparisonResult> k_compare_prefix_check(
        const Bucket& v,
        const AncestorLCPs& ancestor_lcps,
        size_t& out_start_lcp_val) const noexcept;
 
    inline LCP_T convert_lcp(size_t val) const noexcept;
 
private:
    // Private helper methods used internally by public or protected methods.
 
    inline ComparisonResult k_compare(const KEY_T* x, const Bucket& v, const AncestorLCPs& ancestor_lcps) const noexcept;
 
    int height(unsigned node_index) const noexcept;
 
    uint64_t get_total_depth(unsigned node_index, uint64_t depth) const noexcept;
 
    void to_dot_recursive(std::ofstream& os, unsigned node_index) const noexcept;
};
 
//-----------------------------------------------------------------------------
// ZipTrie Method Implementations
// (Definitions are usually placed in the header for templates)
//-----------------------------------------------------------------------------
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::ZipTrie(unsigned max_size, unsigned max_lcp_length) noexcept
    : _root_index(NULLPTR),
      _max_lcp_length(max_lcp_length),
      // Calculate log2(max_size) safely, handling max_size = 0 case.
      _log_max_size(max_size > 0 ? static_cast<uint8_t>(std::log2(static_cast<double>(max_size))) : 0)
{
    // Reserve space in the vector to potentially avoid reallocations if max_size is a good estimate.
    _buckets.reserve(max_size);
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
bool ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::contains(const KEY_T* key) const noexcept
{
    // Delegate the actual search logic to the search method.
    return search(key).contains;
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
typename ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::LCP_T ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::lcp(const KEY_T* key) const noexcept
{
    // Delegate the actual search logic to the search method.
    return search(key).max_lcp;
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
std::optional<typename ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::ComparisonResult> ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::k_compare_prefix_check(
    const Bucket& v,
    const AncestorLCPs& ancestor_lcps,
    size_t& out_start_lcp_val) const noexcept
{
    // Get the LCPs from the current search path.
    auto predecessor_lcp = ancestor_lcps.predecessor;
    auto successor_lcp = ancestor_lcps.successor;
 
    // Determine the maximum LCP encountered on the current search path.
    auto x_max_lcp = std::max(predecessor_lcp, successor_lcp);
    // Determine the corresponding LCP stored in node 'v' (from the path when 'v' was inserted).
    // If the search path's max LCP came from the predecessor side, use v's predecessor LCP, otherwise use v's successor LCP.
    auto corr_v_lcp = (predecessor_lcp > successor_lcp) ? v.ancestor_lcps.predecessor : v.ancestor_lcps.successor;
 
    // If the maximum LCP on the current path (x_max_lcp) differs from the
    // corresponding LCP recorded when node 'v' was inserted (corr_v_lcp)...
    if (x_max_lcp != corr_v_lcp)
    {
        // ...we can determine the order based on which LCP is larger and which path it came from.
        // The logic determines if x should be less or greater than v.
        // `(x_max_lcp > corr_v_lcp)` is true if the current path's LCP is longer.
        // `(predecessor_lcp > successor_lcp)` is true if the current path's max LCP came from the predecessor side.
        // If these booleans match, x is less; otherwise, x is greater.
        std::strong_ordering comparison_result =
            ((x_max_lcp > corr_v_lcp) == (predecessor_lcp > successor_lcp)) ? std::strong_ordering::less : std::strong_ordering::greater;
 
        // The resulting LCP for this comparison is the minimum of the two differing LCPs.
        LCP_T result_lcp = std::min(x_max_lcp, corr_v_lcp);
 
        // Return the determined comparison result and LCP. No need for full key comparison.
        return ComparisonResult{ comparison_result, result_lcp };
    }
 
    // If the LCPs matched (x_max_lcp == corr_v_lcp), we cannot decide the order yet.
    // We need to perform a full key comparison, but we know the keys match up to `x_max_lcp`.
    // Set the starting offset for the key comparison.
    if constexpr (MEMORY_EFFICIENT)
    {
        // If using approximate LCPs, get the actual value.
        out_start_lcp_val = x_max_lcp.value();
    }
    else
    {
        // If using exact LCPs (unsigned), the value is directly usable.
        out_start_lcp_val = x_max_lcp;
    }
 
    // Indicate that a full key comparison should proceed by returning nullopt.
    return std::nullopt;
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
typename ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::LCP_T ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::convert_lcp(size_t val) const noexcept
{
    if constexpr (MEMORY_EFFICIENT) {
        // If memory efficiency is enabled, call the approximation function.
        return get_memory_efficient_lcp(val);
    } else {
        // Otherwise, just cast the exact value to the LCP type (unsigned).
        // Ensure the value fits; consider potential truncation if LCP_T were smaller than size_t.
        return static_cast<LCP_T>(val);
    }
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
typename ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::ComparisonResult ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::k_compare(const KEY_T* x, const Bucket& v, const AncestorLCPs& ancestor_lcps) const noexcept
{
    size_t start_lcp_val = 0; // Initialize starting bit offset for comparison.
 
    // Attempt to determine the result based on ancestor LCPs first.
    if (auto prefix_result = k_compare_prefix_check(v, ancestor_lcps, start_lcp_val))
    {
        // If k_compare_prefix_check returned a result, use it directly.
        return *prefix_result;
    }
 
    // If prefix check didn't yield a result, perform sequential key comparison
    // starting from the calculated bit offset 'start_lcp_val'.
    // Assumes KEY_T has a method `seq_k_compare(const KEY_T& other, size_t start_offset)`
    // that returns a struct/pair like {std::strong_ordering, size_t actual_lcp}.
    auto [comparison, actual_lcp_val] = x->seq_k_compare(*v.key, start_lcp_val);
 
    // Convert the resulting exact LCP length to the appropriate LCP_T format.
    return { comparison, convert_lcp(actual_lcp_val) };
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
typename ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::SearchResults ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::search(const KEY_T* key) const noexcept
{
    // Define a lambda function that encapsulates the call to the standard k_compare method.
    // This lambda matches the signature required by search_recursive.
    auto sequential_compare = [&](const KEY_T* k, const Bucket& v, const AncestorLCPs& ancestor_lcps)
        {
            // Call the member function k_compare for the actual comparison logic.
            return this->k_compare(k, v, ancestor_lcps);
        };
 
    // Call the recursive search helper, passing the key and the comparison lambda.
    return search_recursive(key, sequential_compare);
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
template<typename CompareFunction>
typename ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::SearchResults ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::search_recursive(const KEY_T* key, CompareFunction compare_func) const noexcept
{
    // Handle empty trie case.
    if (_root_index == NULLPTR)
    {
        // Return not found, default LCP, depth -1.
        return { false, {}, -1 };
    }
 
    unsigned v_index = _root_index; // Start traversal at the root.
    AncestorLCPs ancestor_lcps = {}; // Initialize ancestor LCPs to zero/default at the root.
    int depth = 0; // Initialize depth counter.
 
    // Iterate down the trie until a null pointer is reached or the key is found.
    while (v_index != NULLPTR)
    {
        // Get a reference to the current node.
        const Bucket& v_node = _buckets[v_index];
 
        // Perform the comparison using the provided comparison function.
        auto [ comparison, lcp ] = compare_func(key, v_node, ancestor_lcps);
 
        // Check if the key is an exact match.
        if (comparison == std::strong_ordering::equal)
        {
            // Key found. Return true, the final LCP, and the current depth.
            return { true, lcp, depth };
        }
 
        // If not equal, decide whether to go left or right.
        if (comparison == std::strong_ordering::less)
        {
            // Go left. Update the successor LCP for the path: it's the maximum of the
            // current successor LCP and the LCP computed in this step.
            ancestor_lcps.successor = std::max(ancestor_lcps.successor, lcp);
            // Move to the left child.
            v_index = v_node.left;
        }
        else // comparison == std::strong_ordering::greater
        {
            // Go right. Update the predecessor LCP similarly.
            ancestor_lcps.predecessor = std::max(ancestor_lcps.predecessor, lcp);
            // Move to the right child.
            v_index = v_node.right;
        }
 
        // Increment depth for the next level.
        ++depth;
    }
 
    // Key not found after traversing the path.
    // Return false, the maximum LCP encountered along the path, and depth -1.
    return { false, std::max(ancestor_lcps.predecessor, ancestor_lcps.successor), -1 };
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
void ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::insert(const KEY_T* key) noexcept
{
    // Add a new bucket to the vector. Initialize with key and a new random rank.
    // Children and ancestor LCPs will be set during the recursive insertion.
    _buckets.push_back({ key, RANK_T::get_random() });
    // Get the index of the newly added bucket.
    unsigned new_node_index = _buckets.size() - 1;
 
    // Define the comparison function lambda, similar to the search method.
    auto sequential_compare = [&](const KEY_T* k, const Bucket& v, const AncestorLCPs& ancestor_lcps)
        {
            return this->k_compare(k, v, ancestor_lcps); // Use the standard k_compare
        };
 
    // Call the recursive insert helper to place the new node and update the tree structure.
    // Start recursion from the root (_root_index), passing the new node's pointer and index,
    // initial empty ancestor LCPs, and the comparison function.
    // Update the _root_index with the result, as the root might change due to the zip operation.
    _root_index = insert_recursive(&_buckets[new_node_index], new_node_index, _root_index, {}, sequential_compare);
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
template<typename CompareFunction>
unsigned ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::insert_recursive(Bucket* x, unsigned x_index, unsigned v_index, AncestorLCPs ancestor_lcps, CompareFunction compare_func) noexcept
{
    // Base case: Reached a null pointer, meaning this is the insertion spot.
    if (v_index == NULLPTR)
    {
        // Set the ancestor LCPs for the new node 'x' based on the path taken.
        x->ancestor_lcps = ancestor_lcps;
        // Return the index of the new node 'x', indicating it's the root of this (now non-empty) subtree.
        return x_index;
    }
 
    // Get a reference to the current node 'v'.
    Bucket& v_node = _buckets[v_index];
 
    // Compare the new key 'x->key' with the current node's key 'v_node.key'.
    auto [ comparison, lcp ] = compare_func(x->key, v_node, ancestor_lcps);
 
    // If keys are equal, the key already exists. Do not insert duplicates.
    // Return the current node's index, leaving the subtree unchanged.
    if (comparison == std::strong_ordering::equal)
    {
        // Note: Could potentially update value associated with key here if storing values.
        // Since we only store keys, we just return.
        // Also, need to handle the bucket pushed back in `insert`. A robust implementation
        // might check for existence *before* adding to _buckets or remove the unused bucket here.
        // Current implementation leaves the unused bucket if key exists.
        // We should pop the unused bucket here.
        if (x_index == _buckets.size() - 1) { // Check if it's the last one added
            _buckets.pop_back(); // Remove the unused bucket
        } // Else, if not the last, it's harder to remove without messing up indices.
 
        return v_index;
    }
 
    // Navigate left or right based on the comparison result.
    if (comparison == std::strong_ordering::less)
    {
        // Go left. Recursively insert into the left subtree.
        // Update the ancestor LCPs for the recursive call: predecessor stays the same,
        // successor becomes the max of the current path's successor and the LCP just computed.
        unsigned subroot_index = insert_recursive(x, x_index, v_node.left, { ancestor_lcps.predecessor, std::max(ancestor_lcps.successor, lcp) }, compare_func);
 
        // If the recursive call returned an index other than the original left child,
        // it means the structure below changed.
        if (subroot_index == x_index && x->rank >= v_node.rank)
        {
            v_node.left = x->right; // v adopts x's right child as its left child.
            x->right = v_index;     // x takes v as its right child.
            // Update LCPs stored *in the nodes* due to the structural change.
            // v's predecessor LCP is now the LCP computed between x and v.
            v_node.ancestor_lcps.predecessor = lcp;
            // x's ancestor LCPs become those passed into this level (ancestor_lcps).
            x->ancestor_lcps = ancestor_lcps;
            // Return x_index as the new root of this subtree.
            return x_index;
        }
        else
        {
            // Simply update v's left child pointer to the returned subtree root.
            v_node.left = subroot_index;
        }
        // If subroot_index == v_node.left, the left subtree structure didn't change relative to v.
    }
    else // comparison == std::strong_ordering::greater
    {
        // Go right. Recursively insert into the right subtree.
        // Update ancestor LCPs: successor stays same, predecessor updates.
        unsigned subroot_index = insert_recursive(x, x_index, v_node.right, { std::max(ancestor_lcps.predecessor, lcp), ancestor_lcps.successor }, compare_func);
 
        // If the recursive call returned an index other than the original right child.
        if (subroot_index == x_index && x->rank >= v_node.rank)
        {
            v_node.right = x->left; // v adopts x's left child as its right child.
            x->left = v_index;      // x takes v as its left child.
            // Update LCPs stored in the nodes.
            v_node.ancestor_lcps.successor = lcp; // v's successor LCP is now the computed LCP.
            x->ancestor_lcps = ancestor_lcps;     // x inherits parent's LCPs.
            // Return x_index as the new root.
            return x_index;
        }
        else
        {
            v_node.right = subroot_index;
        }
        // If subroot_index == v_node.right, the right subtree structure didn't change relative to v.
    }
 
    return v_index;
}
 
template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
unsigned ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::size() const noexcept
{
    // Simply return the current size of the underlying vector storing the nodes.
    // Note: This assumes no gaps or marked-deleted nodes if removal were implemented differently.
    // If duplicate keys caused buckets to be added but not used in `insert_recursive`,
    // this size might be slightly inflated compared to unique keys. Consider adjusting if duplicates are handled differently.
    return _buckets.size();
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
int ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::height() const noexcept
{
    // Delegate to the recursive helper function starting at the root index.
    return height(_root_index);
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
int ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::height(unsigned node_index) const noexcept
{
    // Base case: An empty subtree (represented by NULLPTR) has a height of -1.
    if (node_index == NULLPTR)
    {
        return -1;
    }
 
    // Recursive step: The height of a non-empty subtree is 1 (for the current node)
    // plus the maximum of the heights of its left and right subtrees.
    return std::max(height(_buckets[node_index].left), height(_buckets[node_index].right)) + 1;
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
int ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::get_depth(const KEY_T* key) const noexcept
{
    // Perform a standard search for the key and return the depth field from the results.
    // If the key is not found, search returns depth -1, which is correctly propagated here.
    return search(key).depth;
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
double ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::get_average_height() const noexcept
{
    // Get the total number of nodes.
    unsigned current_size = size();
    // Handle the case of an empty trie to avoid division by zero.
    if (current_size == 0)
    {
        return 0.0; // Average depth of an empty trie is 0.
    }
    // Calculate the sum of depths of all nodes using the recursive helper, starting at the root (depth 0).
    uint64_t total_depth_sum = get_total_depth(_root_index, 0);
    // Compute the average by dividing the total depth sum by the number of nodes.
    return static_cast<double>(total_depth_sum) / current_size;
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
uint64_t ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::get_total_depth(unsigned node_index, uint64_t depth) const noexcept
{
    // Base case: An empty subtree contributes 0 to the total depth sum.
    if (node_index == NULLPTR)
    {
        return 0;
    }
 
    // Recursive step: The total depth sum for the subtree rooted at node_index is:
    // - The depth of the current node (`depth`)
    // - Plus the total depth sum of the left subtree (nodes in the left subtree are one level deeper)
    // - Plus the total depth sum of the right subtree (nodes in the right subtree are one level deeper)
    return depth + get_total_depth(_buckets[node_index].left, depth + 1) + get_total_depth(_buckets[node_index].right, depth + 1);
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
MemoryEfficientLCP ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::get_memory_efficient_lcp(size_t num) const noexcept
{
    // Handle LCPs smaller than the log of max size directly.
    if (num < _log_max_size)
    {
        // Store the exact value in 'multiple', with exponent 0.
        return { 0, static_cast<uint8_t>(num) };
    }
 
    // Otherwise, calculate exponent and multiple for approximation.
    MemoryEfficientLCP lcp;
    lcp.exp_of_2 = std::log2(num / _log_max_size);
    lcp.multiple = num / (1u << lcp.exp_of_2);
 
    return lcp;
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
void ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::to_dot(const std::string& file_path) const noexcept
{
    // Attempt to open the specified file path for writing.
    std::ofstream os(file_path);
    if (!os) {
        // If the file cannot be opened, print an error message to standard error.
        std::cerr << "Error: Could not open file " << file_path << " for writing." << std::endl;
        return; // Exit the function if file opening failed.
    }
    // Write the standard DOT graph header.
    os << "digraph G {\n";
    // Define default node attributes (shape=record allows complex labels).
    os << "\tnode [shape=record, fontname=\"Arial\"];\n";
    // Define default edge attributes.
    os << "\tedge [fontname=\"Arial\"];\n";
    // Call the recursive helper function to write the nodes and edges, starting from the root.
    if (_root_index != NULLPTR) {
        to_dot_recursive(os, _root_index);
    } else {
        os << "\tlabel=\"Empty Trie\";\n"; // Indicate if the trie is empty
    }
    // Write the closing brace for the DOT graph definition.
    os << "}\n";
    // File stream `os` is automatically closed when it goes out of scope.
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
void ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::to_dot_recursive(std::ofstream& os, unsigned node_index) const noexcept
{
    // Base case: If the node index represents a null pointer, do nothing further down this path.
    if (node_index == NULLPTR)
    {
        return;
    }
 
    // Get a constant reference to the current node's data.
    const Bucket& node = _buckets[node_index];
 
    // Define the DOT representation for the current node.
    // Use a unique ID "node_<index>" for each node.
    // The label uses DOT's record shape syntax: { field1 | field2 | ... }
    // Display the Index, Key, Rank (geometric, uniform), and stored Ancestor LCPs (predecessor, successor).
    // Note: Assumes KEY_T and LCP_T have overloaded operator<< for printing.
    // Note: Explicitly cast uint8_t ranks to unsigned for printing numeric values.
    os << "\tnode_" << node_index << " [label=\"{Idx: " << node_index
       << "|Key: " << *node.key // Assumes KEY_T is printable
       << "|Rank: (" << static_cast<unsigned>(node.rank.geometric_rank) << "," << static_cast<unsigned>(node.rank.uniform_rank) << ")"
       << "|LCPs: (" << node.ancestor_lcps.predecessor << ", " << node.ancestor_lcps.successor << ")}\"];\n";
 
    // Process the left child.
    if (node.left != NULLPTR)
    {
        // Draw an edge from the current node to the left child node.
        // Label the edge " L" for clarity.
        os << "\tnode_" << node_index << " -> node_" << node.left << " [label=\" L\"];\n";
        // Recursively call the function for the left child.
        to_dot_recursive(os, node.left);
    }
    else
    {
        // Optional: Explicitly draw null pointers for visualization.
        // Create a small, invisible point node for the null left child.
        // os << "\tnull_left_" << node_index << " [shape=point, style=invis];\n";
        // Draw an edge to the null point.
        // os << "\tnode_" << node_index << " -> null_left_" << node_index << " [label=\" L\", style=dashed];\n";
    }
 
    // Process the right child.
    if (node.right != NULLPTR)
    {
        // Draw an edge from the current node to the right child node.
        // Label the edge " R".
        os << "\tnode_" << node_index << " -> node_" << node.right << " [label=\" R\"];\n";
        // Recursively call the function for the right child.
        to_dot_recursive(os, node.right);
    }
    else
    {
        // Optional: Explicitly draw null pointers for visualization.
        // os << "\tnull_right_" << node_index << " [shape=point, style=invis];\n";
        // os << "\tnode_" << node_index << " -> null_right_" << node_index << " [label=\" R\", style=dashed];\n";
    }
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
const RANK_T& ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::get_root_rank() const noexcept
{
    // Assert or check for empty trie might be useful here in a debug build.
    // Example: assert(_root_index != NULLPTR && "Cannot get rank of root in an empty trie.");
    return _buckets[_root_index].rank;
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
void ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::set(const KEY_T* key, RANK_T rank, unsigned left, unsigned right, LCP_T predecessor_lcp, LCP_T successor_lcp) noexcept
{
    _buckets.push_back({ key, rank, left, right, {predecessor_lcp, successor_lcp} });
}
 
template <typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T, unsigned CHAR_SIZE_BITS>
void ZipTrie<CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS>::set_root_index(unsigned root_index) noexcept
{
    _root_index = root_index;
}
 
 
//-----------------------------------------------------------------------------
// Standalone Function Implementations (related to structs defined earlier)
//-----------------------------------------------------------------------------
 
inline unsigned MemoryEfficientLCP::value() const noexcept
{
    // Calculate the value by left-shifting 1 by exp_of_2 and multiplying by multiple.
    // Ensure intermediate shift doesn't overflow if exp_of_2 is large, though unlikely for uint8_t.
    return (1u << exp_of_2) * multiple;
}
 
inline std::ostream& MemoryEfficientLCP::print(std::ostream& os) const noexcept
{
    // Cast uint8_t to unsigned for correct stream output as numbers.
    return os << "2^" << static_cast<unsigned>(exp_of_2) << "*" << static_cast<unsigned>(multiple);
}
 
inline std::ostream& operator<<(std::ostream& os, const MemoryEfficientLCP& lcp)
{
    // Delegate the actual printing logic to the struct's print method.
    return lcp.print(os);
}
 
inline GeometricRank GeometricRank::get_random()
{
    // Static generators ensure the sequence is consistent across calls within a single thread,
    // but also mean it's not thread-safe without external locking.
    static std::random_device rd; // Obtain a random seed from the hardware device
    static std::default_random_engine generator(rd()); // Seed the default random engine
    // static std::default_random_engine generator(1); // Use for deterministic testing (fixed seed)
    static std::geometric_distribution<uint8_t> g_dist(0.5); // p=0.5: ~50% chance of 0, ~25% of 1, etc.
    static std::uniform_int_distribution<uint8_t> u_dist(0, std::numeric_limits<uint8_t>::max()); // Uniform distribution over all possible uint8_t values
 
    // Generate and return a rank with both components
    return { g_dist(generator), u_dist(generator) };
}
 
 
inline std::ostream& operator<<(std::ostream& os, const GeometricRank& rank)
{
    // Cast uint8_t to unsigned for correct stream output as numbers.
    return os << "(" << static_cast<unsigned>(rank.geometric_rank) << ", "
           << static_cast<unsigned>(rank.uniform_rank) << ")";
}