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

Red-black tree with rank support (select/position operations). More...

#include <tpl_rbRk.H>

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

Collaboration diagram for Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >:

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

Public Types
typedef NodeType< Key >	Node
typedef Key	key_type

Public Member Functions
Compare &	key_comp () noexcept
Compare &	get_compare () noexcept
	Gen_Rb_Tree_Rk (Compare cmp_arg=Compare())
void	swap (Gen_Rb_Tree_Rk &tree) noexcept
	Gen_Rb_Tree_Rk (Gen_Rb_Tree_Rk &&tree) noexcept
Gen_Rb_Tree_Rk &	operator= (Gen_Rb_Tree_Rk &&tree) noexcept
virtual	~Gen_Rb_Tree_Rk ()=default
Node *	search (const Key &key)
Node *&	getRoot () noexcept
bool	is_empty () const noexcept
size_t	size () const noexcept
Node *	insert (Node *p)
Node *	search_or_insert (Node *p)
Node *	insert_dup (Node *p)
bool	verify () const
Node *	remove (const Key &key)
Node *	select (const size_t i) const
	Return the i-th node in order sense.
std::pair< long, Node * >	position (const Key &key) const noexcept
	Compute the inorder position of a key.
std::pair< long, Node * >	find_position (const Key &key) const noexcept
	Find the inorder position of a key in the tree.
void	join_exclusive (Gen_Rb_Tree_Rk &t) noexcept
	Join this tree exclusively with another tree.
Node *	split_key (const Key &key, Gen_Rb_Tree_Rk &t1, Gen_Rb_Tree_Rk &t2) noexcept
	Split tree by key.
void	split_key_dup (const Key &key, Gen_Rb_Tree_Rk &t1, Gen_Rb_Tree_Rk &t2) noexcept
	Split tree by key including duplicates.
void	split_pos (size_t pos, Gen_Rb_Tree_Rk &t1, Gen_Rb_Tree_Rk &t2) noexcept
	Split tree by inorder position.

Private Member Functions
Node *	search_and_stack_rb (const Key &key, signed char &cmp_result) noexcept
	Search for key and stack ancestors (optimistic duplicate detection)
Node *	search_dup_and_stack_rb (const Key &key, signed char &cmp_result)
Node *	rotate_to_right_rk (Node *p, Node *pp) noexcept
Node *	rotate_to_left_rk (Node *p, Node *pp) noexcept
void	fix_red_condition (Node *p)
void	find_succ_and_swap (Node *p, Node *&pp)
void	fix_black_condition (Node *p)
void	update_counters_after_insertion () noexcept
void	update_counters_after_deletion () noexcept
Node *	split_key_rec_rb (Node *p, const Key &key, Node *&t1, Node *&t2) noexcept
void	split_key_dup_rec_rb (Node *p, const Key &key, Node *&t1, Node *&t2) noexcept
void	split_pos_rec_rb (Node *p, size_t pos, Node *&t1, Node *&t2) noexcept

Static Private Member Functions
static size_t	black_height (Node *p) noexcept
static Node *	rotate_right_simple (Node *p) noexcept
static Node *	rotate_left_simple (Node *p) noexcept
static void	fix_red_violation (Node *&subtree_root) noexcept
static Node *	extract_min_rb (Node *&p) noexcept
static Node *	extract_max_rb (Node *&p) noexcept
static Node *	join_with_pivot_rb (Node *t1, size_t bh1, Node *pivot, Node *t2, size_t bh2) noexcept
static Node *	join_right_rb (Node *t1, size_t bh1, Node *pivot, Node *t2, size_t bh2) noexcept
static Node *	join_left_rb (Node *t1, size_t bh1, Node *pivot, Node *t2, size_t bh2) noexcept
static Node *	join_exclusive_rec_rb (Node *t1, size_t bh1, Node *t2, size_t bh2) noexcept

Private Attributes
Node	head_node
Node *	head
Node *&	root
FixedStack< Node * >	rb_stack
Compare	cmp

Static Private Attributes
static constexpr signed char	CmpLess = -1
static constexpr signed char	CmpEqual = 0
static constexpr signed char	CmpGreater = 1

Detailed Description

template<template< typename > class NodeType, typename Key, class Compare>
class Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >

Red-black tree with rank support (select/position operations).

This class extends the standard red-black tree with subtree size counts, enabling efficient O(log n) rank-based operations:

• select(i): Get the i-th smallest element (0-indexed)
• position(key): Get the rank/position of a key
• find_position(key): Get insertion position even if key doesn't exist
• split_pos(pos, t1, t2): Split tree at a position
• remove_pos(i): Remove element at position i

How it works:

Each node stores a count field representing the number of nodes in its subtree (including itself). Rotations update these counts to maintain the invariant. This adds O(1) overhead per rotation but enables O(log n) ranked operations.

Complexity:

• All basic operations (search, insert, remove): O(log n)
• Rank operations (select, position): O(log n)
• Space: O(n) + O(log n) for stack during operations

Example:

Rb_Tree_Rk<int> tree;
for (int i = 0; i < 100; ++i)
    tree.insert(new Rb_Tree_Rk<int>::Node(i));
 
// Get 50th smallest element
auto node = tree.select(49);  // 0-indexed, returns node with key 49
 
// Get position of key 42
auto [pos, found] = tree.position(42);  // pos = 42, found points to node

Template Parameters

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

See also

Gen_Rb_Tree Basic red-black tree without rank support.

GenTdRbTreeRk Top-down red-black with rank.

Definition at line 107 of file tpl_rbRk.H.

Member Typedef Documentation

key_type

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

typedef Key Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::key_type

Definition at line 458 of file tpl_rbRk.H.

Node

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

typedef NodeType<Key> Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::Node

Definition at line 111 of file tpl_rbRk.H.

Constructor & Destructor Documentation

Gen_Rb_Tree_Rk() [1/2]

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

Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::Gen_Rb_Tree_Rk ( Compare  cmp_arg = Compare() )

inline

Definition at line 464 of file tpl_rbRk.H.

Gen_Rb_Tree_Rk() [2/2]

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

Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::Gen_Rb_Tree_Rk ( Gen_Rb_Tree_Rk< NodeType, Key, Compare > &&  tree )

inlinenoexcept

Definition at line 475 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

~Gen_Rb_Tree_Rk()

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

virtual Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::~Gen_Rb_Tree_Rk ( )

virtualdefault

Member Function Documentation

black_height()

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

static size_t Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::black_height ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 679 of file tpl_rbRk.H.

References BLACK, COLOR, h, and Aleph::LLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos_rec_rb().

extract_max_rb()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_max_rb ( Node *&  p )

inlinestaticprivatenoexcept

Definition at line 873 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), RED, Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec_rb().

extract_min_rb()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_min_rb ( Node *&  p )

inlinestaticprivatenoexcept

Definition at line 772 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), RED, Aleph::HTList::reset(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec_rb().

find_position()

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

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

inlinenoexcept

Find the inorder position of a key in the tree.

Parameters

[in]

key

to be searched

Returns

a pair with the position and the node pointer

Definition at line 666 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::maps(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_position().

find_succ_and_swap()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_succ_and_swap ( Node *  p, Node *&  pp  )

inlineprivate

Definition at line 297 of file tpl_rbRk.H.

References COLOR, Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove().

fix_black_condition()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_black_condition ( Node *  p )

inlineprivate

Definition at line 342 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_left_rk(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_right_rk(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove().

fix_red_condition()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition ( Node *  p )

inlineprivate

Definition at line 236 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::FixedStack< T >::empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_left_rk(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_right_rk().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

fix_red_violation()

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

static void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_violation ( Node *&  subtree_root )

inlinestaticprivatenoexcept

Definition at line 714 of file tpl_rbRk.H.

References BLACK, COLOR, l, Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_left_simple(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_right_simple().

get_compare()

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

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

inlinenoexcept

Definition at line 462 of file tpl_rbRk.H.

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

getRoot()

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

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

inlinenoexcept

Definition at line 502 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

insert()

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

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

inline

Definition at line 508 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpGreater, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess, COLOR, Aleph::FixedStack< T >::empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

insert_dup()

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

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

inline

Definition at line 560 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess, COLOR, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), KEY, Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by TEST(), and TEST().

is_empty()

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

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

inlinenoexcept

Definition at line 504 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

join_exclusive()

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

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

inlinenoexcept

Join this tree exclusively with another tree.

All keys in this tree must be less than all keys in t. After the operation, t becomes empty and this tree contains all nodes.

Parameters

[in,out]

t

tree to join with (will be empty after)

Note

O(m log(n+m)) time complexity where m is size of t

Definition at line 1327 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

join_exclusive_rec_rb()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec_rb ( Node *  t1, size_t  bh1, Node *  t2, size_t  bh2  )

inlinestaticprivatenoexcept

Definition at line 1126 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::black_height(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_max_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::extract_min_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), and Aleph::maps().

join_left_rb()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb ( Node *  t1, size_t  bh1, Node *  pivot, Node *  t2, size_t  bh2  )

inlinestaticprivatenoexcept

Definition at line 1061 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_left_simple(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_right_simple().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb().

join_right_rb()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb ( Node *  t1, size_t  bh1, Node *  pivot, Node *  t2, size_t  bh2  )

inlinestaticprivatenoexcept

Definition at line 990 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb(), Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_left_simple(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_right_simple().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb().

join_with_pivot_rb()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb ( Node *  t1, size_t  bh1, Node *  pivot, Node *  t2, size_t  bh2  )

inlinestaticprivatenoexcept

Definition at line 967 of file tpl_rbRk.H.

References COLOR, Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb(), Aleph::LLINK(), Aleph::maps(), RED, and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos_rec_rb().

key_comp()

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

Compare & Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::key_comp ( )

inlinenoexcept

Definition at line 460 of file tpl_rbRk.H.

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

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

operator=()

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

Gen_Rb_Tree_Rk & Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::operator= ( Gen_Rb_Tree_Rk< NodeType, Key, Compare > &&  tree )

inlinenoexcept

Definition at line 483 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

position()

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

std::pair< long, Node * > Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position ( const Key &  key ) const

inlinenoexcept

Compute the inorder position of a key.

Parameters

[in]

key

to be searched

Returns

a pair with the inorder position and the node pointer. If key is not found, position is -1.

Definition at line 651 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::inorder_position(), Aleph::maps(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), TEST(), and TEST().

remove()

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

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

inline

Definition at line 583 of file tpl_rbRk.H.

References BLACK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, COLOR, Aleph::FixedStack< T >::empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_succ_and_swap(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_black_condition(), Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::FixedStack< T >::top(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

rotate_left_simple()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_left_simple ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 702 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::LLINK(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_violation(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb().

rotate_right_simple()

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

static Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_right_simple ( Node *  p )

inlinestaticprivatenoexcept

Definition at line 692 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::LLINK(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_violation(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb().

rotate_to_left_rk()

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

Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_left_rk ( Node *  p, Node *  pp  )

inlineprivatenoexcept

Definition at line 214 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_black_condition(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition().

rotate_to_right_rk()

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

Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rotate_to_right_rk ( Node *  p, Node *  pp  )

inlineprivatenoexcept

Definition at line 191 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), and Aleph::RLINK().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_black_condition(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition().

search()

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

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

inline

Definition at line 496 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::maps(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

search_and_stack_rb()

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

Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb ( const Key &  key, signed char &  cmp_result  )

inlineprivatenoexcept

Search for key and stack ancestors (optimistic duplicate detection)

Definition at line 125 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpGreater, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::popn(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

search_dup_and_stack_rb()

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

Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb ( const Key &  key, signed char &  cmp_result  )

inlineprivate

Definition at line 164 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpGreater, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup().

search_or_insert()

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

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

inline

Definition at line 534 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpGreater, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess, COLOR, Aleph::FixedStack< T >::empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by TEST().

select()

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

Node * Aleph::Gen_Rb_Tree_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 i is greater or equal than the number of nodes of tree

Definition at line 640 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::select().

Referenced by TEST(), TEST(), and TEST().

size()

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

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

inlinenoexcept

Definition at line 506 of file tpl_rbRk.H.

References Aleph::COUNT(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

split_key()

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

Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key ( const Key &  key, Gen_Rb_Tree_Rk< NodeType, Key, Compare > &  t1, Gen_Rb_Tree_Rk< NodeType, Key, Compare > &  t2  )

inlinenoexcept

Split tree by key.

After the operation:

• t1 contains all keys < key
• t2 contains all keys > key
• This tree becomes empty

Parameters

[in]	key	the splitting key
[out]	t1	tree to receive keys < key
[out]	t2	tree to receive keys > key

Returns

pointer to node containing key, or nullptr if not found

Note

O(n) time complexity (simple iterative implementation)

Definition at line 1375 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::DynList< T >::insert(), Aleph::FixedStack< T >::is_empty(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), and TEST().

split_key_dup()

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

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

inlinenoexcept

Split tree by key including duplicates.

After the operation:

• t1 contains all keys <= key
• t2 contains all keys > key
• This tree becomes empty

Parameters

[in]	key	the splitting key
[out]	t1	tree to receive keys <= key
[out]	t2	tree to receive keys > key

Note

O(n) time complexity (simple iterative implementation)

Definition at line 1423 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::DynList< T >::insert(), Aleph::FixedStack< T >::is_empty(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

split_key_dup_rec_rb()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb ( Node *  p, const Key &  key, Node *&  t1, Node *&  t2  )

inlineprivatenoexcept

Definition at line 1221 of file tpl_rbRk.H.

References BLACK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::black_height(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, COLOR, Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), KEY, Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb().

split_key_rec_rb()

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

Node * Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb ( Node *  p, const Key &  key, Node *&  t1, Node *&  t2  )

inlineprivatenoexcept

Definition at line 1157 of file tpl_rbRk.H.

References BLACK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::black_height(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, COLOR, Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), KEY, Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb().

split_pos()

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

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

inlinenoexcept

Split tree by inorder position.

After the operation:

• t1 contains nodes at positions [0, pos)
• t2 contains nodes at positions [pos, size)
• This tree becomes empty

Parameters

[in]	pos	the splitting position (0-based)
[out]	t1	tree to receive positions [0, pos)
[out]	t2	tree to receive positions [pos, size)

Note

O(n) time complexity (simple iterative implementation)

Definition at line 1465 of file tpl_rbRk.H.

References Aleph::count(), Aleph::DynList< T >::insert(), Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), Aleph::RLINK(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size().

Referenced by TEST(), TEST(), and TEST().

split_pos_rec_rb()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos_rec_rb ( Node *  p, size_t  pos, Node *&  t1, Node *&  t2  )

inlineprivatenoexcept

Definition at line 1269 of file tpl_rbRk.H.

References BLACK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::black_height(), COLOR, Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), Aleph::LLINK(), Aleph::maps(), RED, Aleph::RLINK(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos_rec_rb().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos_rec_rb().

swap()

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

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

inlinenoexcept

Definition at line 469 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

update_counters_after_deletion()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion ( )

inlineprivatenoexcept

Definition at line 449 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove().

update_counters_after_insertion()

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

void Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion ( )

inlineprivatenoexcept

Definition at line 439 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

verify()

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

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

inline

Definition at line 581 of file tpl_rbRk.H.

References Aleph::check_rank_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::is_red_black_bst_rk(), Aleph::maps(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), TEST(), and TEST().

Member Data Documentation

cmp

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

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

private

Definition at line 119 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::operator=(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_rec_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::verify().

CmpEqual

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

constexpr signed char Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual = 0

staticconstexprprivate

Definition at line 121 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

CmpGreater

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

constexpr signed char Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpGreater = 1

staticconstexprprivate

Definition at line 122 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

CmpLess

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

constexpr signed char Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess = -1

staticconstexprprivate

Definition at line 120 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert().

head

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

Node* Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::head

private

Definition at line 116 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb().

head_node

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

Node Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::head_node

private

Definition at line 115 of file tpl_rbRk.H.

rb_stack

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

FixedStack<Node *> Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack

private

Definition at line 118 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_succ_and_swap(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_black_condition(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

root

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

Node*& Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::root

private

Definition at line 117 of file tpl_rbRk.H.

Referenced by Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::Gen_Rb_Tree_Rk(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_black_condition(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::operator=(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::size(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::split_pos(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::verify().

---

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

• tpl_rbRk.H