A skip list implementation for efficient chunk searching. More...

#include <advanced_structures.hpp>

Collaboration diagram for advanced_structures::ChunkSkipList< T >:

Classes
struct	Node

Public Member Functions
	ChunkSkipList (int max_lvl=16, float prob=0.5)
	Constructs a new ChunkSkipList object.

void	insert (const T &value)
	Inserts a value into the skip list.

bool	search (const T &value) const
	Searches for a value in the skip list.

Private Member Functions
int	random_level ()
	Generates a random level for node insertion.

Private Attributes
int	current_level

std::shared_ptr< Node >	head

int	max_level

float	p

Detailed Description

template<typename T>
class advanced_structures::ChunkSkipList< T >

A skip list implementation for efficient chunk searching.

Template Parameters

T	The type of elements stored in the skip list

Definition at line 151 of file advanced_structures.hpp.

Constructor & Destructor Documentation

◆ ChunkSkipList()

template<typename T >

advanced_structures::ChunkSkipList< T >::ChunkSkipList	(	int	max_lvl = `16`,
		float	prob = `0.5`
	)

inline

Constructs a new ChunkSkipList object.

Parameters

max_lvl	Maximum level of the skip list
prob	Probability factor for level generation

Definition at line 182 of file advanced_structures.hpp.

        : max_level(max_lvl), p(prob), current_level(1) {
        head = std::make_shared<Node>(T(), max_level);
    }

References advanced_structures::ChunkSkipList< T >::head, and advanced_structures::ChunkSkipList< T >::max_level.

Member Function Documentation

◆ insert()

template<typename T >

void advanced_structures::ChunkSkipList< T >::insert ( const T & value )

inline

Inserts a value into the skip list.

Parameters

value The value to insert

Definition at line 191 of file advanced_structures.hpp.

                                {
        std::vector<std::shared_ptr<Node>> update(max_level);
        auto current = head;
 
        for (int i = current_level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
 
        int new_level = random_level();
        if (new_level > current_level) {
            for (int i = current_level; i < new_level; i++) {
                update[i] = head;
            }
            current_level = new_level;
        }
 
        auto new_node = std::make_shared<Node>(value, new_level);
        for (int i = 0; i < new_level; i++) {
            new_node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = new_node;
        }
    }

References advanced_structures::ChunkSkipList< T >::current_level, advanced_structures::ChunkSkipList< T >::head, advanced_structures::ChunkSkipList< T >::max_level, and advanced_structures::ChunkSkipList< T >::random_level().

Referenced by TEST_F(), and TEST_F().

◆ random_level()

template<typename T >

int advanced_structures::ChunkSkipList< T >::random_level ( )

inlineprivate

Generates a random level for node insertion.

Returns: The random level

Definition at line 168 of file advanced_structures.hpp.

                       {
        int lvl = 1;
        while ((static_cast<float>(rand()) / RAND_MAX) < p && lvl < max_level) {
            lvl++;
        }
        return lvl;
    }

References advanced_structures::ChunkSkipList< T >::max_level, and advanced_structures::ChunkSkipList< T >::p.

Referenced by advanced_structures::ChunkSkipList< T >::insert().

◆ search()

template<typename T >

bool advanced_structures::ChunkSkipList< T >::search ( const T & value ) const

inline

Searches for a value in the skip list.

Parameters

value The value to search for

Returns: True if the value is found, false otherwise

Definition at line 222 of file advanced_structures.hpp.

                                      {
        auto current = head;
        for (int i = current_level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        return current && current->value == value;
    }