SkipTrie.hpp File Reference

Defines the SkipTrie class, a skip list based data structure optimized for string storage and retrieval. More...

#include <cmath>
#include <cstddef>
#include <memory>
#include <random>
#include <vector>
#include <unordered_map>
#include <fstream>
#include <string>
#include <sstream>
#include <compare>
#include "BitString.cuh"

Include dependency graph for SkipTrie.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	SkipTrie< CHAR_T, CHAR_SIZE_BITS >
	Implements a skip list data structure optimized for storing and retrieving BitString keys. More...
struct	SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Node
	Represents a single node within the SkipTrie structure. More...
struct	SkipTrie< CHAR_T, CHAR_SIZE_BITS >::NodeLCP
	Helper struct to return a Node pointer and an associated LCP value. More...
struct	SkipTrie< CHAR_T, CHAR_SIZE_BITS >::EqualOrSuccessor
	Helper struct to return a Node pointer, a flag indicating equality, and an LCP value. More...
struct	SkipTrie< CHAR_T, CHAR_SIZE_BITS >::ResultLCP
	Helper struct to return a comparison result (ordering) and an LCP value. More...
class	SkipTrie< CHAR_T, CHAR_SIZE_BITS >::Iterator
	Provides forward/backward iteration over the keys in the base level of the SkipTrie. More...

Enumerations
enum class	Direction { FORWARD , BACKWARD , INPLACE }
	Enumerates the possible traversal directions within the skip list structure. More...

Detailed Description

Defines the SkipTrie class, a skip list based data structure optimized for string storage and retrieval.

This file contains the definition of the SkipTrie template class, which uses a skip list structure combined with bit-level string representation (BitString) for efficient operations like insertion, search, and removal. It aims for logarithmic average time complexity by utilizing skip links and efficient LCP (Longest Common Prefix) calculations.

See also

BitString

Definition in file SkipTrie.hpp.

Enumeration Type Documentation

Direction

enum class Direction

strong

Enumerates the possible traversal directions within the skip list structure.

Used to indicate the direction of movement (forward or backward) or state (inplace) during operations like insertion or search.

Enumerator
FORWARD	Represents traversal towards the end of the list (successor nodes).
BACKWARD	Represents traversal towards the beginning of the list (predecessor nodes).
INPLACE	Indicates no traversal needed, typically when the exact key is found.

Definition at line 31 of file SkipTrie.hpp.

{
    FORWARD, 
    BACKWARD, 
    INPLACE 
};

Function Documentation

operator<<()

template<typename CHAR_T , unsigned CHAR_SIZE_BITS>

std::ostream & operator<< ( std::ostream &  os, const SkipTrie< CHAR_T, CHAR_SIZE_BITS > &  ssl  )

related

Definition at line 1032 of file SkipTrie.hpp.

                                                                                    {
    // Delegate to the print method.
    return ssl.print(os);
}