GeometricRank Struct Reference

Represents a rank used in zip-zip trees, typically generated randomly for balancing. More...

#include <ZipTrie.hpp>

Public Member Functions
auto	operator<=> (const GeometricRank &) const =default
	Default comparison operator.

Static Public Member Functions
static GeometricRank	get_random ()
	Generates a random rank using static random number generators.

Public Attributes
uint8_t	geometric_rank
	Rank component following a geometric distribution (primary rank). Higher values are less likely.
uint8_t	uniform_rank
	Rank component following a uniform distribution (used for tie-breaking).

Related Symbols
(Note that these are not member symbols.)
std::ostream &	operator<< (std::ostream &os, const GeometricRank &rank)
	Overloaded stream insertion operator (<<) for GeometricRank.

Detailed Description

Represents a rank used in zip-zip trees, typically generated randomly for balancing.

Combines a geometric and a uniform random component for tie-breaking. The geometric component helps achieve logarithmic expected depth in the zip tree/trie structure, while the uniform component ensures rank uniqueness with high probability, preventing arbitrary choices during 'zip' operations when geometric ranks are equal. This structure is crucial for maintaining the max-heap property based on ranks.

Definition at line 72 of file ZipTrie.hpp.

Member Function Documentation

get_random()

GeometricRank GeometricRank::get_random ( )

inlinestatic

Generates a random rank using static random number generators.

The geometric component helps achieve logarithmic expected depth, while the uniform component ensures uniqueness with high probability.

Returns

GeometricRank A randomly generated rank.

Warning

Uses static generators internally. This means successive calls produce different random numbers, but it is not thread-safe if called from multiple threads concurrently without external locking.

Definition at line 1083 of file ZipTrie.hpp.

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

operator<=>()

auto GeometricRank::operator<=> ( const GeometricRank &  ) const

default

Default comparison operator.

Compares geometric_rank first, then uniform_rank for tie-breaking.

Note

Higher ranks are considered "greater" in the context of the max-heap property used in zipping.

Friends And Related Symbol Documentation

operator<<()

std::ostream & operator<< ( std::ostream &  os, const GeometricRank &  rank  )

related

Overloaded stream insertion operator (<<) for GeometricRank.

Allows printing GeometricRank objects directly to output streams (e.g., std::cout << rank;). Formats the output as "(geometric, uniform)".

Parameters

os	The output stream (e.g., std::cout, std::ofstream).
rank	The GeometricRank object to print.

Returns

std::ostream& Reference to the output stream after printing.

Definition at line 1107 of file ZipTrie.hpp.

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

Member Data Documentation

geometric_rank

uint8_t GeometricRank::geometric_rank

Rank component following a geometric distribution (primary rank). Higher values are less likely.

Definition at line 75 of file ZipTrie.hpp.

uniform_rank

uint8_t GeometricRank::uniform_rank

Rank component following a uniform distribution (used for tie-breaking).

Definition at line 77 of file ZipTrie.hpp.

---

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

• src/ZipTrie.hpp