advanced_structures::ChunkTreap< T > Class Template Reference

A treap implementation for efficient chunk searching and manipulation. More...

#include <advanced_structures.hpp>

Collaboration diagram for advanced_structures::ChunkTreap< T >:

Classes
struct	Node

Public Member Functions
	ChunkTreap ()
void	insert (T value)
bool	search (T value) const

Private Member Functions
std::shared_ptr< Node >	insert (std::shared_ptr< Node > node, T value, int priority)
std::shared_ptr< Node >	rotate_left (std::shared_ptr< Node > node)
std::shared_ptr< Node >	rotate_right (std::shared_ptr< Node > node)
bool	search (const std::shared_ptr< Node > &node, T value) const

Private Attributes
std::mt19937	gen
std::shared_ptr< Node >	root

Detailed Description

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

A treap implementation for efficient chunk searching and manipulation.

Template Parameters

T	The type of elements stored in the treap

Definition at line 426 of file advanced_structures.hpp.

Constructor & Destructor Documentation

ChunkTreap()

template<typename T >

advanced_structures::ChunkTreap< T >::ChunkTreap ( )

inline

Definition at line 488 of file advanced_structures.hpp.

: root(nullptr), gen(std::random_device{}()) {}

Member Function Documentation

insert() [1/2]

template<typename T >

std::shared_ptr< Node > advanced_structures::ChunkTreap< T >::insert ( std::shared_ptr< Node >  node, T  value, int  priority  )

inlineprivate

Definition at line 454 of file advanced_structures.hpp.

                                                                                {
        if (!node) {
            return std::make_shared<Node>(value, priority);
        }
 
        if (value < node->value) {
            node->left = insert(node->left, value, priority);
            if (node->left->priority > node->priority) {
                node = rotate_right(node);
            }
        } else {
            node->right = insert(node->right, value, priority);
            if (node->right->priority > node->priority) {
                node = rotate_left(node);
            }
        }
        return node;
    }

References advanced_structures::ChunkTreap< T >::insert(), advanced_structures::ChunkTreap< T >::rotate_left(), and advanced_structures::ChunkTreap< T >::rotate_right().

Referenced by advanced_structures::ChunkTreap< T >::insert(), advanced_structures::ChunkTreap< T >::insert(), and TEST().

insert() [2/2]

template<typename T >

void advanced_structures::ChunkTreap< T >::insert ( T  value )

inline

Definition at line 490 of file advanced_structures.hpp.

                         {
        int priority = std::uniform_int_distribution<>(1, 100)(gen);
        root = insert(root, value, priority);
    }

References advanced_structures::ChunkTreap< T >::gen, advanced_structures::ChunkTreap< T >::insert(), and advanced_structures::ChunkTreap< T >::root.

rotate_left()

template<typename T >

std::shared_ptr< Node > advanced_structures::ChunkTreap< T >::rotate_left ( std::shared_ptr< Node >  node )

inlineprivate

Definition at line 447 of file advanced_structures.hpp.

                                                              {
        auto new_root = node->right;
        node->right = new_root->left;
        new_root->left = node;
        return new_root;
    }

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

rotate_right()

template<typename T >

std::shared_ptr< Node > advanced_structures::ChunkTreap< T >::rotate_right ( std::shared_ptr< Node >  node )

inlineprivate

Definition at line 440 of file advanced_structures.hpp.

                                                               {
        auto new_root = node->left;
        node->left = new_root->right;
        new_root->right = node;
        return new_root;
    }

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

search() [1/2]

template<typename T >

bool advanced_structures::ChunkTreap< T >::search ( const std::shared_ptr< Node > &  node, T  value  ) const

inlineprivate

Definition at line 473 of file advanced_structures.hpp.

                                                                {
        if (!node) {
            return false;
        }
        if (node->value == value) {
            return true;
        }
        if (value < node->value) {
            return search(node->left, value);
        } else {
            return search(node->right, value);
        }
    }

References advanced_structures::ChunkTreap< T >::search().

Referenced by advanced_structures::ChunkTreap< T >::search(), advanced_structures::ChunkTreap< T >::search(), and TEST().

search() [2/2]

template<typename T >

bool advanced_structures::ChunkTreap< T >::search ( T  value ) const

inline

Definition at line 495 of file advanced_structures.hpp.

                               {
        return search(root, value);
    }

References advanced_structures::ChunkTreap< T >::root, and advanced_structures::ChunkTreap< T >::search().

Member Data Documentation

gen

template<typename T >

std::mt19937 advanced_structures::ChunkTreap< T >::gen

private

Definition at line 438 of file advanced_structures.hpp.

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

root

template<typename T >

std::shared_ptr<Node> advanced_structures::ChunkTreap< T >::root

private

Definition at line 437 of file advanced_structures.hpp.

Referenced by advanced_structures::ChunkTreap< T >::insert(), and advanced_structures::ChunkTreap< T >::search().

---

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

• advanced_structures.hpp