Implements a zip trie, a data structure combining properties of tries and zip trees for storing strings efficiently. More...

#include <ZipTrie.hpp>

Inheritance diagram for ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >:

[legend]

Classes
struct	AncestorLCPs
	Stores the Longest Common Prefix (LCP) values associated with the path from the root down to a node's parent. More...

struct	Bucket
	Represents a single node (bucket) within the ZipTrie's internal storage. More...

struct	ComparisonResult
	Holds the result of comparing a search/insert key `x` with a node `v`'s key, considering the context of ancestor LCPs. More...

struct	SearchResults
	Holds the results returned by a search operation (`search` method). More...

Public Types
using	LCP_T = std::conditional_t< MEMORY_EFFICIENT, MemoryEfficientLCP, unsigned >
	The type used to store Longest Common Prefix values.

using	KEY_T = BitString< CHAR_T, CHAR_SIZE_BITS >
	The type used for keys, an instantiation of the `BitString` template.

Public Member Functions
	ZipTrie (unsigned max_size, unsigned max_lcp_length) noexcept
	Constructs an empty ZipTrie.

int	get_depth (const KEY_T *key) const noexcept
	Calculates the depth of a given key in the trie.

int	height () const noexcept
	Calculates the height of the trie.

double	get_average_height () const noexcept
	Calculates the average depth of all nodes currently in the trie.

unsigned	size () const noexcept
	Returns the number of nodes (keys) currently stored in the trie.

bool	contains (const KEY_T *key) const noexcept
	Checks if a key exists within the trie.

LCP_T	lcp (const KEY_T *key) const noexcept
	Finds the Longest Common Prefix (LCP) between the search key and the path taken in the trie.

void	insert (const KEY_T *key) noexcept
	Inserts a key into the zip trie.

const RANK_T &	get_root_rank () const noexcept
	Removes a node with a given key from the zip tree. (Not implemented)

void	set (const KEY_T *key, RANK_T rank, unsigned left, unsigned right, LCP_T predecessor_lcp, LCP_T successor_lcp) noexcept
	Directly adds a pre-constructed bucket to the internal storage vector.

void	set_root_index (unsigned root_index) noexcept
	Directly sets the root index of the trie.

virtual SearchResults	search (const KEY_T *key) const noexcept
	Performs a search for a key within the ZipTrie.

void	to_dot (const std::string &file_path) const noexcept
	Generates a DOT language representation of the trie structure for visualization.

Protected Member Functions
MemoryEfficientLCP	get_memory_efficient_lcp (size_t num) const noexcept
	Converts a standard LCP length (`size_t`) into the `MemoryEfficientLCP` format.

template<typename CompareFunction >
SearchResults	search_recursive (const KEY_T *key, CompareFunction compare_func) const noexcept
	Recursive helper function for the public `search` method.

template<typename CompareFunction >
unsigned	insert_recursive (Bucket *x, unsigned x_index, unsigned v_index, AncestorLCPs ancestor_lcps, CompareFunction compare_func) noexcept
	Recursive helper function for inserting a new node `x`.

std::optional< ComparisonResult >	k_compare_prefix_check (const Bucket &v, const AncestorLCPs &ancestor_lcps, size_t &out_start_lcp_val) const noexcept
	Performs an initial check based on ancestor LCPs before full key comparison (k-compare optimization).

LCP_T	convert_lcp (size_t val) const noexcept
	Converts an exact LCP length (e.g., number of matching characters/bits) to the `LCP_T` type.

Protected Attributes
unsigned	_root_index
	Index of the root node within the `_buckets` vector. Initialized to `NULLPTR` for an empty trie.

unsigned	_max_lcp_length
	Stores the maximum possible LCP length provided during construction.

uint8_t	_log_max_size
	Stores the approximate log base 2 of the `max_size` provided during construction.

std::vector< Bucket >	_buckets
	A contiguous vector storing all the nodes (`Bucket`s) of the trie.

Static Protected Attributes
static constexpr unsigned	NULLPTR = std::numeric_limits<unsigned>::max()
	Represents a null child pointer index using the maximum value of `unsigned`.

Private Member Functions
ComparisonResult	k_compare (const KEY_T *x, const Bucket &v, const AncestorLCPs &ancestor_lcps) const noexcept
	Compares a key `x` with the key in a node `v`, utilizing ancestor LCPs for optimization (k-compare).

int	height (unsigned node_index) const noexcept
	Recursive helper function to calculate the height of the subtree rooted at `node_index`.

uint64_t	get_total_depth (unsigned node_index, uint64_t depth) const noexcept
	Recursive helper function to calculate the sum of the depths of all nodes within a subtree.

void	to_dot_recursive (std::ofstream &os, unsigned node_index) const noexcept
	Recursive helper function to generate the DOT language representation for a subtree.

Detailed Description

template<typename CHAR_T, bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
class ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >

Implements a zip trie, a data structure combining properties of tries and zip trees for storing strings efficiently.

A zip trie stores keys (represented by BitString) and associated ranks (RANK_T). It maintains a tree structure based on both key prefixes (like a standard trie) and random ranks (like a zip tree). This combination aims to achieve balanced expected depth (logarithmic in the number of elements) while efficiently handling shared prefixes common in string datasets.

The structure relies on comparing keys based on their Longest Common Prefix (LCP) with ancestor paths (k_compare optimization) to navigate the trie efficiently, avoiding redundant character comparisons. 'Zip' operations based on node ranks ensure the max-heap property (the "zip property") is maintained with respect to ranks, leading to the balanced structure on average.

Template Parameters

CHAR_T	The underlying character type used in the keys (`BitString`). Typically `char` or `uint8_t`.
MEMORY_EFFICIENT	If true, uses `MemoryEfficientLCP` for storing LCP values, trading precision for memory savings. If false, uses `unsigned` for exact LCP storage.
RANK_T	The type used for node ranks (default: `GeometricRank`). Must provide a static `get_random()` method and support comparison operators (`<=>`).
CHAR_SIZE_BITS	The number of significant bits per character in `CHAR_T`. Defaults to `sizeof(CHAR_T) * 8`. Allows handling types where not all bits are used (e.g., 7-bit ASCII in an 8-bit char, 2-bit nucleotides in DNA strings).

See also: BitString; GeometricRank; MemoryEfficientLCP; k_compare; insert_recursive

Definition at line 125 of file ZipTrie.hpp.

Member Typedef Documentation

◆ KEY_T

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::KEY_T = BitString<CHAR_T, CHAR_SIZE_BITS>

The type used for keys, an instantiation of the BitString template.

See also: BitString

Definition at line 137 of file ZipTrie.hpp.

◆ LCP_T

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

using ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::LCP_T = std::conditional_t<MEMORY_EFFICIENT, MemoryEfficientLCP, unsigned>

The type used to store Longest Common Prefix values.

This is MemoryEfficientLCP if MEMORY_EFFICIENT is true, otherwise unsigned.

Definition at line 132 of file ZipTrie.hpp.

Constructor & Destructor Documentation

◆ ZipTrie()

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

Constructs an empty ZipTrie.

Parameters

max_size	Hint for reserving memory in the internal node storage (`_buckets`). Pre-allocating can potentially avoid reallocations during insertions if the size is known approximately.
max_lcp_length	The maximum possible LCP length (in characters or bits, depending on `BitString`) expected between any two keys. This is crucial for the scaling of `MemoryEfficientLCP` if enabled.

Note: Setting max_lcp_length accurately is important for the precision of approximate LCPs when MEMORY_EFFICIENT is true.; The constructor calculates _log_max_size based on max_size for LCP scaling.

Definition at line 558 of file ZipTrie.hpp.

    : _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);
}

Member Function Documentation

◆ contains()

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

Checks if a key exists within the trie.

Parameters

key	Pointer to the key to search for.

Returns: bool True if a node with the exact key exists, false otherwise.

See also: search

Definition at line 569 of file ZipTrie.hpp.

{
    // Delegate the actual search logic to the search method.
    return search(key).contains;
}

◆ convert_lcp()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

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

inlineprotectednoexcept

Converts an exact LCP length (e.g., number of matching characters/bits) to the LCP_T type.

If MEMORY_EFFICIENT is true, this calls get_memory_efficient_lcp to perform the approximation. Otherwise (if MEMORY_EFFICIENT is false), it performs a simple static cast to unsigned (which is LCP_T).

Parameters

val	The exact LCP length (`size_t`) to convert.

Returns: LCP_T The LCP value in the appropriate storage format (MemoryEfficientLCP or unsigned).

See also: get_memory_efficient_lcp

Note: This function is conditionally compiled based on MEMORY_EFFICIENT.

Definition at line 636 of file ZipTrie.hpp.

{
    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);
    }
}

◆ get_average_height()

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

Calculates the average depth of all nodes currently in the trie.

This provides a measure of the average search cost. A perfectly balanced binary tree would have an average depth logarithmic in the number of nodes.

Returns: double The average depth. Returns 0.0 for an empty trie.

See also: get_total_depth

Definition at line 896 of file ZipTrie.hpp.

{
    // 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;
}

◆ get_depth()

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

Calculates the depth of a given key in the trie.

The depth is the number of edges from the root to the node containing the key. The root itself is at depth 0.

Parameters

key	Pointer to the key to search for.

Returns: int The depth of the key if found, or -1 if the key is not present in the trie.

See also: search

Definition at line 888 of file ZipTrie.hpp.

{
    // 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;
}

◆ get_memory_efficient_lcp()

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

inlineprotectednoexcept

Converts a standard LCP length (size_t) into the MemoryEfficientLCP format.

This is an internal helper function used only when MEMORY_EFFICIENT is true. It approximates the LCP value to fit into the smaller MemoryEfficientLCP struct, using _log_max_size for scaling the approximation.

Parameters

num	The exact LCP length (typically number of matching characters or bits) to convert.

Returns: MemoryEfficientLCP The approximate LCP value in the memory-efficient representation.

Note: This function is only compiled and used if MEMORY_EFFICIENT is true.

See also: convert_lcp

Definition at line 928 of file ZipTrie.hpp.

{
    // 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;
}

◆ get_root_rank()

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

Removes a node with a given key from the zip tree. (Not implemented)

Parameters

key	The key of the node to remove.

Returns: bool True if a node was found and removed, false otherwise.

Note: This functionality is declared but not implemented in the provided code. Implementing removal in zip trees/tries requires 'unzip' operation.

Gets the rank of the root node.

Returns: const RANK_T& A constant reference to the root node's rank.

Warning: Behavior is undefined if the trie is empty (_root_index == NULLPTR). Accessing _buckets[_root_index] would be invalid.

Definition at line 1031 of file ZipTrie.hpp.

{
    // 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;
}

◆ get_total_depth()

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

privatenoexcept

Recursive helper function to calculate the sum of the depths of all nodes within a subtree.

Used by get_average_height. Traverses the subtree and sums the depth of each node.

Parameters

node_index	Index of the root of the subtree.
depth	The depth of the `node_index` node itself (relative to the overall trie root).

Returns: uint64_t The sum of the depths of all nodes in the subtree rooted at node_index. Each node's depth contributes to the sum. Returns 0 for an empty subtree (NULLPTR).

See also: get_average_height()

Definition at line 912 of file ZipTrie.hpp.

{
    // 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);
}

◆ height() [1/2]

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

Calculates the height of the trie.

The height is the number of edges on the longest path from the root node to any leaf node. An empty trie has height -1. A trie with only a root node has height 0.

Returns: int The height of the trie.

Definition at line 867 of file ZipTrie.hpp.

{
    // Delegate to the recursive helper function starting at the root index.
    return height(_root_index);
}

◆ height() [2/2]

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

privatenoexcept

Recursive helper function to calculate the height of the subtree rooted at node_index.

Parameters

node_index Index of the root of the subtree in the _buckets vector.

Returns: int The height of the subtree (longest path from node_index to a leaf in its subtree). Returns -1 if node_index is NULLPTR (representing an empty subtree).

See also: height()

Definition at line 874 of file ZipTrie.hpp.

{
    // 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;
}

◆ insert()

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

Inserts a key into the zip trie.

A new node (Bucket) is created for the key, assigned a random rank using RANK_T::get_random(), and added to the internal _buckets storage. The insert_recursive helper method is then called to place this new node into the correct position according to key order (search tree property) and perform zip operations based on rank comparisons to maintain the max-heap property (max-heap property). The provided key pointer is stored directly in the node; the zip trie does not take ownership.

Parameters

key	Pointer to the new key to insert. Must be non-null and point to a valid `KEY_T` object.

Warning: Key Lifetime: The lifetime of the object pointed to by key must exceed the lifetime of the zip trie or at least until the key is removed (if removal were implemented). The trie stores only the pointer.; Uniqueness: Assumes keys are unique. Inserting a key that already exists (or compares as equal) results in the insertion being effectively skipped by insert_recursive, leaving the tree structure unchanged. However, the new bucket added in this function might remain unused in the _buckets vector.

See also: insert_recursive; RANK_T::get_random

Definition at line 743 of file ZipTrie.hpp.

{
    // 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);
}

◆ insert_recursive()

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
	)

protectednoexcept

Recursive helper function for inserting a new node x.

Traverses the trie based on key comparisons (compare_func) and LCPs, updating ancestor_lcps along the path. When the correct insertion position (a NULLPTR link) is found, it inserts the node x. During the backtracking phase (as the recursion unwinds), it performs 'zip' operations to maintain the max-heap property based on ranks. If the rank of the newly inserted node x (or the root of the subtree returned by the recursive call) is higher than or equal to the rank of the current node v, the higher-ranked node is promoted. The function updates node LCPs (ancestor_lcps member) during operations to reflect the structural changes.

Template Parameters

CompareFunction A callable type for comparing keys, same signature as in search_recursive.

Parameters

x	Pointer to the new bucket being inserted (already present in `_buckets`).
x_index	Index of the new bucket `x` in the `_buckets` vector.
v_index	Index of the current node (`v`) being visited in the recursion. Starts with `_root_index`.
ancestor_lcps	LCPs inherited from the path above `v_index`. These are updated based on the traversal direction.
compare_func	The comparison function to use.

Returns: unsigned The index of the root of the modified subtree after potential insertion and updates. This will be either v_index (if no update occurred at this level or insertion happened deeper) or x_index (if x was promoted up to become the new root of this subtree).

Note: If compare_func determines the key already exists (returns equal), the insertion is aborted for that path, and v_index is returned, leaving the subtree rooted at v unchanged.

Definition at line 766 of file ZipTrie.hpp.

{
    // 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;
}

◆ k_compare()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

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

inlineprivatenoexcept

Compares a key x with the key in a node v, utilizing ancestor LCPs for optimization (k-compare).

This is the primary comparison function used for navigating the Zip Trie during search and insertion. It first calls k_compare_prefix_check to attempt to determine the comparison result solely based on the LCP information stored along the ancestor paths. If k_compare_prefix_check returns std::nullopt (meaning the LCP check was inconclusive), this function proceeds to perform a direct comparison of the key data (x->key vs v.key) using BitString::seq_k_compare. Crucially, the BitString comparison starts from the bit/character offset (out_start_lcp_val) determined by the prefix check, avoiding redundant comparisons of the already-matched prefix.

Parameters

x	Pointer to the key being searched for or inserted.
v	Constant reference to the current node (`Bucket`) being compared against.
ancestor_lcps	The LCPs computed along the path from the root down to `v`'s parent.

Returns: ComparisonResult A struct containing the relative ordering (comparison) of x vs v and the calculated Longest Common Prefix (lcp) between them in the context of this comparison (converted to LCP_T format).

See also: k_compare_prefix_check; BitString::seq_k_compare; convert_lcp

Definition at line 649 of file ZipTrie.hpp.

{
    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) };
}

◆ k_compare_prefix_check()

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

protectednoexcept

Performs an initial check based on ancestor LCPs before full key comparison (k-compare optimization).

This is a core optimization in zip trie navigation. It compares the LCPs accumulated along the current search path (ancestor_lcps) with the LCPs stored in the current node v (v.ancestor_lcps, which were the path LCPs when v was inserted). If these path LCPs differ significantly (x_max_lcp != corr_v_lcp), the relative order of the search key x and node v can often be determined without comparing the actual key data (x->key vs v.key). This check exploits the property that if the LCP context differs, the branching decision made when v was inserted must differ from the decision needed for x.

Parameters

	v	The current node (`Bucket`) being considered.
	ancestor_lcps	The LCPs accumulated along the current search/insert path down to `v`'s parent.
[out]	out_start_lcp_val	If a full key comparison is needed (returns `std::nullopt`), this parameter is populated with the length (number of characters/bits) from which the actual key comparison (`BitString::seq_k_compare`) should start. This avoids re-comparing the prefix already known to match based on the LCP check.

Returns

std::optional<ComparisonResult>

If the comparison can be decided based on LCPs alone: returns a ComparisonResult containing the determined ordering (less or greater) and the minimum of the differing LCPs (std::min(x_max_lcp, corr_v_lcp)).
If a full key comparison is required (because x_max_lcp == corr_v_lcp): returns std::nullopt.

See also: k_compare

Definition at line 583 of file ZipTrie.hpp.

{
    // 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;
}

◆ lcp()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

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

Finds the Longest Common Prefix (LCP) between the search key and the path taken in the trie.

If the key is found (search(key).contains == true), this returns the LCP between the search key and the found key (which is typically the key's full length, assuming k_compare calculates full LCP on equality). If the key is not found (search(key).contains == false), it returns the LCP between the search key and the path leading to the point where the search terminated (i.e., the maximum LCP computed along the search path).

Parameters

key	Pointer to the key to search for.

Returns: LCP_T The calculated LCP value, potentially approximate if MEMORY_EFFICIENT is true.

See also: search

Definition at line 576 of file ZipTrie.hpp.

{
    // Delegate the actual search logic to the search method.
    return search(key).max_lcp;
}

◆ search()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

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

virtualnoexcept

Performs a search for a key within the ZipTrie.

Traverses the trie based on key comparisons (k_compare), updating ancestor LCPs along the path. The k_compare function utilizes stored LCP information to potentially avoid full key comparisons.

Parameters

key	Pointer to the key to search for.

Returns: SearchResults A struct containing the outcome: whether the key was found (contains), the calculated maximum LCP along the path (max_lcp), and the depth if found (depth).

See also: search_recursive; k_compare

Reimplemented in ParallelZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >.

Definition at line 671 of file ZipTrie.hpp.

{
    // 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);
}

◆ search_recursive()

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T , unsigned CHAR_SIZE_BITS>

template<typename CompareFunction >

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

protectednoexcept

Recursive helper function for the public search method.

Implements the core traversal logic iteratively (using a while loop) based on the results of the provided comparison function. It tracks the depth and updates ancestor LCPs along the path.

Template Parameters

CompareFunction A callable type (e.g., lambda, function pointer) that takes (const KEY_T* key, const Bucket& v_node, const AncestorLCPs& ancestor_lcps) and returns a ComparisonResult. This allows customizing the comparison logic if needed, although typically it wraps k_compare.

Parameters

key	The key being searched for.
compare_func	The comparison function to use for navigating the trie.

Returns: SearchResults The result of the search operation, including found status, max LCP, and depth.

Definition at line 687 of file ZipTrie.hpp.

{
    // 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 };
}

◆ set()

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

Directly adds a pre-constructed bucket to the internal storage vector.

Warning: Testing/Internal Use Only: Intended for testing or specific initialization scenarios. This method bypasses the standard insertion logic (insert), including rank generation and maintaining the zip trie properties (key order, rank heap property). Using it improperly will likely corrupt the trie structure.

Parameters

key	Pointer to the key for the new bucket.
rank	The rank to assign to the new bucket.
left	Index of the left child (use `NULLPTR` for none).
right	Index of the right child (use `NULLPTR` for none).
predecessor_lcp	The ancestor LCP with the predecessor path for this bucket.
successor_lcp	The ancestor LCP with the successor path for this bucket.

Definition at line 1039 of file ZipTrie.hpp.

{
    _buckets.push_back({ key, rank, left, right, {predecessor_lcp, successor_lcp} });
}

◆ set_root_index()

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

Directly sets the root index of the trie.

Warning: Testing/Internal Use Only: Intended for testing or specific initialization scenarios. This method bypasses the standard insertion logic. Using it improperly can lead to an invalid zip trie state (e.g., pointing to an invalid index or violating zip trie properties). Ensure the root_index points to a valid, intended root node within _buckets.

Parameters

root_index The index in _buckets to set as the new root.

Definition at line 1045 of file ZipTrie.hpp.

{
    _root_index = root_index;
}

◆ size()

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

Returns the number of nodes (keys) currently stored in the trie.

Returns: unsigned The number of nodes.

Note: If duplicate keys are inserted, the current implementation might add a bucket but not link it, potentially inflating this count slightly compared to the number of unique, reachable keys.

Definition at line 857 of file ZipTrie.hpp.

{
    // 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();
}

◆ to_dot()

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

Generates a DOT language representation of the trie structure for visualization.

Writes the DOT output to the specified file. This file can then be processed by tools like Graphviz (e.g., dot -Tpng input.dot -o output.png) to create a visual diagram of the trie, showing nodes (with keys, ranks, LCPs) and their parent-child relationships.

Parameters

file_path The path (including filename) where the output DOT file should be written.

Note: If the file cannot be opened, an error message is printed to std::cerr.

See also: to_dot_recursive

Definition at line 946 of file ZipTrie.hpp.

{
    // 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.
}

◆ to_dot_recursive()

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

privatenoexcept

Recursive helper function to generate the DOT language representation for a subtree.

Called by the public to_dot method. It defines the current node and its edges to its children in the DOT format and then recursively calls itself for the children. Includes node index, key, rank, and stored ancestor LCPs in the node label.

Parameters

os	The output file stream (`std::ofstream`) to write the DOT commands to.
node_index	Index of the root of the subtree to output.

See also: to_dot()

Definition at line 973 of file ZipTrie.hpp.

{
    // 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";
    }
}

Member Data Documentation

◆ _buckets

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

std::vector<Bucket> ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_buckets

protected

A contiguous vector storing all the nodes (Buckets) of the trie.

Node relationships (parent/child) are managed via indices (_root_index, left, right) within this vector, forming the tree structure implicitly.

Definition at line 379 of file ZipTrie.hpp.

◆ _log_max_size

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

uint8_t ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_log_max_size

protected

Stores the approximate log base 2 of the max_size provided during construction.

Note: Used for scaling LCP values when MEMORY_EFFICIENT is true.

See also: get_memory_efficient_lcp

Definition at line 323 of file ZipTrie.hpp.

◆ _max_lcp_length

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_max_lcp_length

protected

Stores the maximum possible LCP length provided during construction.

Note: Primarily used for scaling calculations if MEMORY_EFFICIENT is true.

Definition at line 317 of file ZipTrie.hpp.

◆ _root_index

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::_root_index

protected

Index of the root node within the _buckets vector. Initialized to NULLPTR for an empty trie.

Definition at line 312 of file ZipTrie.hpp.

◆ NULLPTR

template<typename CHAR_T , bool MEMORY_EFFICIENT, typename RANK_T = GeometricRank, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>

constexpr unsigned ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::NULLPTR = std::numeric_limits<unsigned>::max()

staticconstexprprotected

Represents a null child pointer index using the maximum value of unsigned.

Definition at line 326 of file ZipTrie.hpp.

The documentation for this class was generated from the following file:

src/ZipTrie.hpp

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ KEY_T

◆ LCP_T

Constructor & Destructor Documentation

◆ ZipTrie()

Member Function Documentation

◆ contains()

◆ convert_lcp()

◆ get_average_height()

◆ get_depth()

◆ get_memory_efficient_lcp()

◆ get_root_rank()

◆ get_total_depth()

◆ height() [1/2]

◆ height() [2/2]

◆ insert()

◆ insert_recursive()

◆ k_compare()

◆ k_compare_prefix_check()

◆ lcp()

◆ search()

◆ search_recursive()

◆ set()

◆ set_root_index()

◆ size()

◆ to_dot()

◆ to_dot_recursive()

Member Data Documentation

◆ _buckets

◆ _log_max_size

◆ _max_lcp_length

◆ _root_index

◆ NULLPTR