Represents a single node within the SkipTrie structure. More...

#include <SkipTrie.hpp>

Collaboration diagram for SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Node:

[legend]

Public Member Functions
size_t	lcp (Direction direction) const noexcept
	Calculates the longest common prefix (LCP) with the neighbor node in the specified direction.

Node *	next_node (Direction direction) const noexcept
	Retrieves the neighboring node in the specified direction on the same level.

Public Attributes
const KEY_T *	key = nullptr
	Pointer to the key associated with this node. The SkipTrie does not own the key data.

std::shared_ptr< Node >	next {nullptr}
	Shared pointer to the next node on the same level.

Node *	prev = nullptr
	Raw pointer to the previous node on the same level.

std::shared_ptr< Node >	down {nullptr}
	Shared pointer to the corresponding node on the level below. Null for base level nodes.

size_t	lcp_next {0}
	The Longest Common Prefix (LCP) length between this node's key and the next node's key on the same level.

Detailed Description

template<typename CHAR_T, unsigned CHAR_SIZE_BITS = sizeof(CHAR_T) * 8>
struct SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Node

Represents a single node within the SkipTrie structure.

Each node stores a pointer to a key, pointers to its neighbors (next, previous, down), and the Longest Common Prefix (LCP) length with its immediate successor on the same level.

Definition at line 223 of file SkipTrie.hpp.

Member Function Documentation

◆ lcp()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

size_t SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Node::lcp ( Direction direction ) const

noexcept

Calculates the longest common prefix (LCP) with the neighbor node in the specified direction.

Parameters

direction The direction (FORWARD or BACKWARD) relative to this node.

Returns: size_t The LCP length with the neighbor in the given direction. Returns 0 if there is no neighbor in that direction (e.g., lcp(BACKWARD) for the first node).

Definition at line 545 of file SkipTrie.hpp.

{
    if (direction == Direction::FORWARD)
    {
        // LCP with the next node is stored directly.
        return lcp_next;
    }
 
    // LCP with the previous node is stored in the previous node's lcp_next.
    return prev ? prev->lcp_next : 0;
}

◆ next_node()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Node * SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Node::next_node ( Direction direction ) const

noexcept

Retrieves the neighboring node in the specified direction on the same level.

Parameters

direction The direction (FORWARD or BACKWARD) to retrieve the neighbor from.

Returns: Node* A pointer to the neighboring node, or nullptr if no neighbor exists in that direction (e.g., next_node(FORWARD) for the tail sentinel).

Definition at line 558 of file SkipTrie.hpp.

{
    if (direction == Direction::FORWARD)
    {
        return next.get();
    }
 
    return prev;
}