ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket Struct Reference

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

#include <ZipTrie.hpp>

Collaboration diagram for ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket:

Public Attributes
const KEY_T *	key
	Pointer to the key associated with this node.
RANK_T	rank
	The rank associated with this node, used for maintaining the Zip Tree (max-heap) property.
unsigned	left = NULLPTR
	Index of the left child in the _buckets vector, or NULLPTR if no left child.
unsigned	right = NULLPTR
	Index of the right child in the _buckets vector, or NULLPTR if no right child.
AncestorLCPs	ancestor_lcps = {}
	Stores the AncestorLCPs passed down from the parent during this node's insertion.

Detailed Description

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

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

Contains the key pointer, rank, child indices, and the ancestor LCPs as they were when this node was inserted.

Definition at line 351 of file ZipTrie.hpp.

Member Data Documentation

ancestor_lcps

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

AncestorLCPs ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket::ancestor_lcps = {}

Stores the AncestorLCPs passed down from the parent during this node's insertion.

These stored LCPs are compared against the AncestorLCPs of the current search path within the k_compare optimization.

See also

k_compare_prefix_check

Definition at line 371 of file ZipTrie.hpp.

{};

key

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

const KEY_T* ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket::key

Pointer to the key associated with this node.

Warning

The ZipTrie does not own the key data; it only stores the pointer. The caller must ensure the key's lifetime.

Definition at line 358 of file ZipTrie.hpp.

left

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 >::Bucket::left = NULLPTR

Index of the left child in the _buckets vector, or NULLPTR if no left child.

Definition at line 362 of file ZipTrie.hpp.

rank

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

RANK_T ZipTrie< CHAR_T, MEMORY_EFFICIENT, RANK_T, CHAR_SIZE_BITS >::Bucket::rank

The rank associated with this node, used for maintaining the Zip Tree (max-heap) property.

Definition at line 360 of file ZipTrie.hpp.

right

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 >::Bucket::right = NULLPTR

Index of the right child in the _buckets vector, or NULLPTR if no right child.

Definition at line 364 of file ZipTrie.hpp.

---

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

• src/ZipTrie.hpp