Aleph::Gen_Treap_Rk< NodeType, Key, Compare > Class Template Reference

Extended Treap with rank support for O(log n) indexed access. More...

#include <tpl_treapRk.H>

Inheritance diagram for Aleph::Gen_Treap_Rk< NodeType, Key, Compare >:

Classes
class	Iterator
	Iterator on nodes of the tree. More...

Public Types
using	Node = NodeType< Key >

Public Member Functions
void	set_seed (const unsigned long seed) noexcept
	Set the random number generator seed.
Compare &	key_comp () noexcept
	return the comparison criteria
Compare &	get_compare () noexcept
	Gen_Treap_Rk (const unsigned long seed, Compare __cmp=Compare())
	Initialize a treap with random seed and comparison criteria __cmp
	Gen_Treap_Rk (Compare __cmp=Compare())
	~Gen_Treap_Rk ()
void	swap (Gen_Treap_Rk &tree) noexcept
	Swap in constant time all the nodes of this with tree
Node *&	getRoot () noexcept
	Return the tree's root.
Node *	getRoot () const noexcept
Node *	search (const Key &key) const noexcept
	Search a key in a treap.
Node *	insert (Node *p) noexcept
	Insert a node in a treap.
Node *	insert_dup (Node *p) noexcept
	Insert a node in the tree.
Node *	search_or_insert (Node *p) noexcept
	Search or insert a key.
bool	verify () const
	Return true if the treap is consistent.
Node *	remove (const Key &key) noexcept
	Remove a key from the tree.
Node *	remove (const size_t beg, const size_t end)
	Remove from the treap all the keys between inorder position beg and end.
Node *	remove_pos (const size_t pos)
	Remove the node at the inorder position pos.
Node *	select (const size_t i) const
	Return the i-th node in order sense.
size_t	size () const noexcept
	Return the number of nodes contained in the tree.
bool	is_empty () const noexcept
	Return true if tree is empty.
std::pair< int, Node * >	position (const Key &key) const noexcept
	Compute the inorder position of a key.
std::pair< int, Node * >	find_position (const Key &key) const noexcept
	Find the inorder position of a key in the tree.
bool	split_key (const Key &key, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2) noexcept
	Split the tree according to a key.
void	split_key_dup (const Key &key, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2) noexcept
	Split the tree according to a key that could be in the tree.
void	split_pos (size_t pos, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2)
	Split the tree at the inorder position pos.
void	join (Gen_Treap_Rk &t, Gen_Treap_Rk &dup) noexcept
	Join this with t filtering the duplicated keys.
void	join_dup (Gen_Treap_Rk &t) noexcept
	Join this with t independently of the presence of duplicated keys.
void	join_exclusive (Gen_Treap_Rk &t) noexcept
	Join exclusive of this with t

Private Member Functions
void	init (unsigned int seed)
bool	insert (Node *&root, Node *p) noexcept
Node *	search_or_insert (Node *&root, Node *p) noexcept
Node *	insert_dup (Node *&root, Node *p) noexcept
Node *	remove (Node *&root, const Key &key) noexcept
void	join_dup (Node *&t1, Node *t2) noexcept
void	join (Node *&t1, Node *t2, Node *&dup) noexcept

Static Private Member Functions
static Node *	join_exclusive (Node *t1, Node *t2) noexcept
static Node *	remove_pos (Node *&root, const size_t pos) noexcept

Private Attributes
Node	head
	The type of node.
Node *	head_ptr
Node *&	tree_root
gsl_rng *	r
Compare	cmp

Detailed Description

template<template< class > class NodeType, class Key, class Compare>
class Aleph::Gen_Treap_Rk< NodeType, Key, Compare >

Extended Treap with rank support for O(log n) indexed access.

TreapRk is a Treap (tree + heap) that extends the basic treap with subtree size counters (COUNT), enabling O(log n) access by rank (inorder position). This allows treating the tree like a sorted dynamic array with efficient indexed operations.

Treap Properties (from base Treap):

• Keys follow BST ordering: left < parent < right
• Priorities follow max-heap ordering: parent priority > child priorities
• Priorities are randomly assigned at insertion time
• Expected O(log n) height due to randomization

Rank Extension:

Each node maintains COUNT = size of subtree rooted at that node. This enables:

• select(i): Get the i-th smallest element, O(log n)
• position(key): Get the rank of a key, O(log n)
• remove_pos(i): Remove element at position i, O(log n)
• split_pos(i): Split tree at position i, O(log n)

Comparison with Other Trees:

• TreapRk vs Treap: TreapRk adds rank support (O(1) space per node)
• TreapRk vs Rand_Tree: Similar functionality, but TreapRk is typically faster by a constant factor (bottom-up vs top-down balancing)
• TreapRk vs Splay_Tree_Rk: TreapRk has expected (not amortized) complexity; Splay_Tree_Rk adapts to access patterns but lacks guarantees

Template Parameters

NodeType	Node template (typically Treap_Rk_Node).
Key	The type of keys stored in the tree.
Compare	Comparison functor for ordering keys.

Complexity:

• Search: O(log n) expected
• Insert: O(log n) expected
• Delete: O(log n) expected
• Select (by rank): O(log n) expected
• Position (get rank): O(log n) expected
• Remove by position: O(log n) expected
• Split: O(log n) expected
• Join: O(log n) expected
• Space: O(n) + O(1) per node for priority and COUNT

Random Number Generator:

Uses GSL (GNU Scientific Library) Mersenne Twister (mt19937) by default. Seed can be set via set_seed() for reproducible behavior.

Example:

TreapRk<int> tree;
 
// Insert nodes
tree.insert(new TreapRk<int>::Node(42));
tree.insert(new TreapRk<int>::Node(17));
tree.insert(new TreapRk<int>::Node(99));
tree.insert(new TreapRk<int>::Node(8));
 
// Ranked access (treat as sorted array)
auto smallest = tree.select(0);     // Get 0th element (8)
auto median = tree.select(tree.size() / 2);  // Get median
 
// Find position/rank of a key
size_t pos = tree.position(42);  // Returns rank of 42
 
// Remove by position
auto removed = tree.remove_pos(1);  // Remove 2nd smallest
delete removed;
 
// Split at position
TreapRk<int> left, right;
tree.split_pos(2, left, right);  // Split after 2nd element
 
// Join trees
tree.join(left, right);

Note

This is a low-level implementation managing raw nodes. For automatic memory management, use DynSetTreapRk.

All operations maintain COUNT values for ranked operations.

Faster than Rand_Tree by a constant factor.

See also

TreapRk Convenient typedef for TreapRk<Key, Compare>.

Treap Basic treap without rank support (slightly faster, less space).

Rand_Tree Alternative randomized tree with rank support.

Splay_Tree_Rk Self-adjusting alternative with rank support.

DynSetTreapRk High-level wrapper with automatic memory management.

Definition at line 180 of file tpl_treapRk.H.

Member Typedef Documentation

Node

template<template< class > class NodeType, class Key , class Compare >

using Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 184 of file tpl_treapRk.H.

Constructor & Destructor Documentation

Gen_Treap_Rk() [1/2]

template<template< class > class NodeType, class Key , class Compare >

Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Gen_Treap_Rk ( const unsigned long  seed, Compare  __cmp = Compare()  )

inline

Initialize a treap with random seed and comparison criteria __cmp

Definition at line 217 of file tpl_treapRk.H.

References Aleph::init.

Gen_Treap_Rk() [2/2]

template<template< class > class NodeType, class Key , class Compare >

Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Gen_Treap_Rk ( Compare  __cmp = Compare() )

inline

Definition at line 223 of file tpl_treapRk.H.

~Gen_Treap_Rk()

template<template< class > class NodeType, class Key , class Compare >

Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::~Gen_Treap_Rk ( )

inline

Definition at line 228 of file tpl_treapRk.H.

References Aleph::maps(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r.

Member Function Documentation

find_position()

template<template< class > class NodeType, class Key , class Compare >

std::pair< int, Node * > Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::find_position ( const Key &  key ) const

inlinenoexcept

Find the inorder position of a key in the tree.

find_position(key) determines the inorder position that has or had key in the tree. Themethod return a tuple with a position and a node pointer.

If key is found then its inorder position is returned along with a pointer to the node containing it.

Otherwise, the the tuple returns the position that would have key if this was in the tree and the parent node that the key would had. At this regard, there are three cases:

1. if key is lesser than the minimum key of tree, then first is -1 and the node is one with the smallest key.
2. If key is greater than the maximum key in the tree, then first is the number of keys and the node is one with the maximum key in the tree.
3. For any other case, first is the inorder position that would have key if this was in the tree and second is the node whose key is inmediataly greater than key.

Parameters

[in]

key

to be searched

Returns

a pair with the inorder position and and related node

Definition at line 614 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::find_position(), Aleph::maps(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::find_position(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::reset_to_key().

get_compare()

template<template< class > class NodeType, class Key , class Compare >

Compare & Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::get_compare ( )

inlinenoexcept

Definition at line 213 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::key_comp().

getRoot() [1/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::getRoot ( ) const

inlinenoexcept

Definition at line 245 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

getRoot() [2/2]

template<template< class > class NodeType, class Key , class Compare >

Node *& Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::getRoot ( )

inlinenoexcept

Return the tree's root.

Definition at line 243 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::get_current_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::has_curr(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::is_container_empty(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::reset_last(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::update_curr(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::update_pos(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::verify(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::verify().

init()

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::init ( unsigned int  seed )

inlineprivate

Definition at line 194 of file tpl_treapRk.H.

References ah_bad_alloc_if, Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::head_ptr, Aleph::maps(), Aleph::Min_Priority, Aleph::PRIO(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r.

insert() [1/2]

template<template< class > class NodeType, class Key , class Compare >

bool Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert ( Node *&  root, Node *  p  )

inlineprivatenoexcept

Definition at line 261 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::PRIO(), Aleph::RLINK(), root(), Aleph::rotate_to_left_xt(), and Aleph::rotate_to_right_xt().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join().

insert() [2/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert ( Node *  p )

inlinenoexcept

Insert a node in a treap.

insert(p) inserta el nodo p en el treap this.

Parameters

[in]

p

pointer to the node to be inserted

Returns

if p->get_key() is not in the tree, then p is inserted and this node pointer is returned. Otherwise, it is returned nullptr.

Definition at line 379 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::maps(), Aleph::PRIO(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

insert_dup() [1/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup ( Node *&  root, Node *  p  )

inlineprivatenoexcept

Definition at line 343 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::PRIO(), Aleph::RLINK(), root(), Aleph::rotate_to_left_xt(), and Aleph::rotate_to_right_xt().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup().

insert_dup() [2/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup ( Node *  p )

inlinenoexcept

Insert a node in the tree.

This method does not fail. It always inserts.

Parameters

[in]

p

pointer to the node to insert

Returns

the p pointer

Definition at line 395 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::maps(), Aleph::PRIO(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

is_empty()

template<template< class > class NodeType, class Key , class Compare >

bool Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::is_empty ( ) const

inlinenoexcept

Return true if tree is empty.

Definition at line 568 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

join() [1/2]

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join ( Gen_Treap_Rk< NodeType, Key, Compare > &  t, Gen_Treap_Rk< NodeType, Key, Compare > &  dup  )

inlinenoexcept

Join this with t filtering the duplicated keys.

join(t, dup) produces a random tree result of join of this and t. The resulting tree is stored in this.

Nodes containing duplicated keys are inserted in the randomized tree dup. The nodes could belong to any of two trees

Parameters

[in]	t	ramdomized tree to join with this
[out]	dup	ramdomized tree where nodes containing duplicated keys are inserted

Definition at line 712 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

join() [2/2]

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join ( Node *&  t1, Node *  t2, Node *&  dup  )

inlineprivatenoexcept

Definition at line 678 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), KEY, l, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join().

join_dup() [1/2]

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup ( Gen_Treap_Rk< NodeType, Key, Compare > &  t )

inlinenoexcept

Join this with t independently of the presence of duplicated keys.

join(t) produces a treap result of join of this and t. The resulting tree is stored in this.

Parameters

[in]

t

ramdomized tree to join with this keys are inserted

Definition at line 726 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

join_dup() [2/2]

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup ( Node *&  t1, Node *  t2  )

inlineprivatenoexcept

Definition at line 666 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup(), l, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup().

join_exclusive() [1/2]

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive ( Gen_Treap_Rk< NodeType, Key, Compare > &  t )

inlinenoexcept

Join exclusive of this with t

Exclusive means that all the keys of this are lesser than all the keys of t. This knowlege allows a more effcient way for joining that when the keys ranks are overlapped. However, use very carefully because the algorithm does not perform any check and the result would be incorrect.

Parameters

[in]

t

ramdomized tree to exclusively join with this keys are inserted

Definition at line 743 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

join_exclusive() [2/2]

template<template< class > class NodeType, class Key , class Compare >

static Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive ( Node *  t1, Node *  t2  )

inlinestaticprivatenoexcept

Definition at line 430 of file tpl_treapRk.H.

References Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::LLINK(), Aleph::maps(), Aleph::PRIO(), and Aleph::RLINK().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos().

key_comp()

template<template< class > class NodeType, class Key , class Compare >

Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::key_comp ( )

inlinenoexcept

return the comparison criteria

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 210 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::get_compare().

remove() [1/3]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove ( const Key &  key )

inlinenoexcept

Remove a key from the tree.

Parameters

[in]

key

to remove

Returns

a valid pointer to the removed node if key was found in the tree, nullptr otherwise

Definition at line 484 of file tpl_treapRk.H.

References Aleph::maps(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::HTList::reset(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

remove() [2/3]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove ( const size_t  beg, const size_t  end  )

inline

Remove from the treap all the keys between inorder position beg and end.

Parameters

[in]	beg	beggining inorder position
[in]	end	ending inorder position

Returns

a pointer to a tree root containing all the removed nodes

Exceptions

range_error

if the range is invalid

Definition at line 503 of file tpl_treapRk.H.

References ah_range_error_if, Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::maps(), Aleph::split_pos_rec(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

remove() [3/3]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove ( Node *&  root, const Key &  key  )

inlineprivatenoexcept

Definition at line 449 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::del(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove().

remove_pos() [1/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos ( const size_t  pos )

inline

Remove the node at the inorder position pos.

Parameters

[in]

pos

inorder position of node to be removed

Returns

a vaid pointer to the removed node

Exceptions

out_of_range

if pos is greater or equal than the number of nodes of tree

Definition at line 545 of file tpl_treapRk.H.

References ah_out_of_range_error_if, Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

remove_pos() [2/2]

template<template< class > class NodeType, class Key , class Compare >

static Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos ( Node *&  root, const size_t  pos  )

inlinestaticprivatenoexcept

Definition at line 521 of file tpl_treapRk.H.

References Aleph::COUNT(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos(), Aleph::RLINK(), and root().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos().

search()

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search ( const Key &  key ) const

inlinenoexcept

Search a key in a treap.

Parameters

[in]

key

to be searched

Returns

a pointer to the node containing key if this is found; otherwise, nullptr is returned

Definition at line 253 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::maps(), Aleph::searchInBinTree(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

search_or_insert() [1/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert ( Node *&  root, Node *  p  )

inlineprivatenoexcept

Definition at line 299 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::PRIO(), Aleph::RLINK(), root(), Aleph::rotate_to_left_xt(), Aleph::rotate_to_right_xt(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert().

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert().

search_or_insert() [2/2]

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert ( Node *  p )

inlinenoexcept

Search or insert a key.

search_or_insert(p) searches in the tree the key KEY(p). If this key is found, then a pointer to the node containing it is returned. Otherwise, p is inserted.

Parameters

[in]

p

node containing a key to be searched and eventually inserted

Returns

if the key contained in p is found, then a pointer to the containing key in the tree is returned. Otherwise, p is inserted and returned

Definition at line 416 of file tpl_treapRk.H.

References Aleph::maps(), Aleph::PRIO(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

select()

template<template< class > class NodeType, class Key , class Compare >

Node * Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::select ( const size_t  i ) const

inline

Return the i-th node in order sense.

Parameters

[in]

i

inorder position of node to be selected

Returns

a pointer to the i-th node inorder sense

Exceptions

out_of_range

if pos is greater or equal than the number of nodes of tree

Definition at line 559 of file tpl_treapRk.H.

References Aleph::select(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

set_seed()

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::set_seed ( const unsigned long  seed )

inlinenoexcept

Set the random number generator seed.

Definition at line 207 of file tpl_treapRk.H.

References Aleph::maps(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r.

size()

template<template< class > class NodeType, class Key , class Compare >

size_t Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::size ( ) const

inlinenoexcept

Return the number of nodes contained in the tree.

Definition at line 565 of file tpl_treapRk.H.

References Aleph::COUNT(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

split_key()

template<template< class > class NodeType, class Key , class Compare >

bool Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key ( const Key &  key, Gen_Treap_Rk< NodeType, Key, Compare > &  t1, Gen_Treap_Rk< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split the tree according to a key.

Parameters

[in]	key	for splitting
[out]	t1	tree with keys lesser than key
[out]	t2	tree with keys greater than key

Returns

true if tree was split; that is if key is not in the tree. Otherwise, if key is in the tree, false is returned

Definition at line 632 of file tpl_treapRk.H.

References Aleph::maps(), Aleph::split_key_rec_xt(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

split_key_dup()

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key_dup ( const Key &  key, Gen_Treap_Rk< NodeType, Key, Compare > &  t1, Gen_Treap_Rk< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split the tree according to a key that could be in the tree.

split_dup(key, t1, t2) splits the tree according to key in two trees t1 which contains the key lesser than key and t2 which contains the keys greater or equal than key.

Parameters

[in]	key	for splitting
[out]	t1	resulting tree with the keys lesser than key
[out]	t2	resulting tree with the keys greater or equal than key

Definition at line 648 of file tpl_treapRk.H.

References Aleph::maps(), Aleph::split_key_dup_rec_xt(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

split_pos()

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_pos ( size_t  pos, Gen_Treap_Rk< NodeType, Key, Compare > &  t1, Gen_Treap_Rk< NodeType, Key, Compare > &  t2  )

inline

Split the tree at the inorder position pos.

Parameters

[in]	pos	inorder position where to split
[out]	t1	tree where the rank of keys \([0, pos)\) will be put
[out]	t2	tree where the rank of keys \([pos, n]\) will be put

Definition at line 659 of file tpl_treapRk.H.

References Aleph::maps(), Aleph::split_pos_rec(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

swap()

template<template< class > class NodeType, class Key , class Compare >

void Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::swap ( Gen_Treap_Rk< NodeType, Key, Compare > &  tree )

inlinenoexcept

Swap in constant time all the nodes of this with tree

Definition at line 235 of file tpl_treapRk.H.

References Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp, Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r, and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

verify()

template<template< class > class NodeType, class Key , class Compare >

bool Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::verify ( ) const

inline

Return true if the treap is consistent.

Definition at line 426 of file tpl_treapRk.H.

References Aleph::is_treap(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root.

Member Data Documentation

cmp

template<template< class > class NodeType, class Key , class Compare >

Compare Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::cmp

private

Definition at line 192 of file tpl_treapRk.H.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::update_pos().

head

template<template< class > class NodeType, class Key , class Compare >

Node Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::head

private

The type of node.

Definition at line 188 of file tpl_treapRk.H.

head_ptr

template<template< class > class NodeType, class Key , class Compare >

Node* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::head_ptr

private

Definition at line 189 of file tpl_treapRk.H.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::init().

r

template<template< class > class NodeType, class Key , class Compare >

gsl_rng* Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::r

private

Definition at line 191 of file tpl_treapRk.H.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::~Gen_Treap_Rk(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::init(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::set_seed(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::Iterator::verify().

tree_root

template<template< class > class NodeType, class Key , class Compare >

Node*& Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::tree_root

private

Definition at line 190 of file tpl_treapRk.H.

Referenced by Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::is_empty(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::remove_pos(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::size(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::split_pos(), Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Treap_Rk< NodeType, Key, Compare >::verify().

---

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

• tpl_treapRk.H