Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes | List of all members
Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare > Class Template Reference
Trees

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 >:
[legend]
Collaboration diagram for Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >:
[legend]

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>
requires StrictWeakOrder<Compare, Key>
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
Aleph::Gen_Rb_Tree_Rk::select
Node * select(const size_t i) const
Return the i-th node in order sense.
Definition tpl_rbRk.H:646
Aleph::Gen_Rb_Tree_Rk::insert
Node * insert(Node *p)
Definition tpl_rbRk.H:514
Aleph::Gen_Rb_Tree_Rk::position
std::pair< long, Node * > position(const Key &key) const noexcept
Compute the inorder position of a key.
Definition tpl_rbRk.H:657
Aleph::Gen_Rb_Tree_Rk::Node
NodeType< Key > Node
Definition tpl_rbRk.H:113
Aleph::Rb_Tree_Rk
Red-Black binary search tree with nodes without virtual destructor and with subtree counters for sele...
Definition tpl_rbRk.H:1551
Template Parameters
NodeTypeNode template (RbNodeRk or RbNodeRkVtl).
KeyThe type of keys stored in the tree.
CompareComparison 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 109 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 464 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 113 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 470 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 481 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 685 of file tpl_rbRk.H.

References BLACK, COLOR, h, and 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 879 of file tpl_rbRk.H.

References Aleph::and, BLACK, COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, RED, and 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 778 of file tpl_rbRk.H.

References Aleph::and, BLACK, COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, RED, and 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]keyto be searched
Returns
a pair with the position and the node pointer

Definition at line 672 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::find_position(), r, 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 303 of file tpl_rbRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, 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 348 of file tpl_rbRk.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, 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 242 of file tpl_rbRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, 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 720 of file tpl_rbRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), l, LLINK, r, RED, 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 468 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 508 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 514 of file tpl_rbRk.H.

References Aleph::and, 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::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), KEY, LLINK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, 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 566 of file tpl_rbRk.H.

References Aleph::and, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpLess, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), KEY, LLINK, RED, 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 510 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]ttree to join with (will be empty after)
Note
O(m log(n+m)) time complexity where m is size of t

Definition at line 1333 of file tpl_rbRk.H.

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

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

◆ 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 1132 of file tpl_rbRk.H.

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

◆ 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 1067 of file tpl_rbRk.H.

References Aleph::and, BLACK, COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), LLINK, RED, 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 996 of file tpl_rbRk.H.

References Aleph::and, BLACK, COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb(), LLINK, RED, 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 973 of file tpl_rbRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_left_rb(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_right_rb(), LLINK, RED, and 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 466 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 489 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]keyto be searched
Returns
a pair with the inorder position and the node pointer. If key is not found, position is -1.

Definition at line 657 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::inorder_position(), 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 589 of file tpl_rbRk.H.

References BLACK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::CmpEqual, COLOR, Aleph::divide_and_conquer_partition_dp(), 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(), LLINK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, 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 708 of file tpl_rbRk.H.

References Aleph::COUNT(), LLINK, and 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 698 of file tpl_rbRk.H.

References Aleph::COUNT(), LLINK, and 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 220 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, and 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 197 of file tpl_rbRk.H.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, and 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 502 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), 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 127 of file tpl_rbRk.H.

References Aleph::and, 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::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::head, KEY, LLINK, Aleph::FixedStack< T >::popn(), Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, 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 170 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::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::head, KEY, LLINK, Aleph::FixedStack< T >::push(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, 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 540 of file tpl_rbRk.H.

References Aleph::and, 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::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::empty(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::fix_red_condition(), KEY, LLINK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::rb_stack, RED, 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]iinorder position of node to be selected
Returns
a pointer to the i-th node inorder sense
Exceptions
out_of_rangeif i is greater or equal than the number of nodes of tree

Definition at line 646 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 512 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]keythe splitting key
[out]t1tree to receive keys < key
[out]t2tree 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 1381 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), KEY, LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), 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]keythe splitting key
[out]t1tree to receive keys <= key
[out]t2tree to receive keys > key
Note
O(n) time complexity (simple iterative implementation)

Definition at line 1429 of file tpl_rbRk.H.

References Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), KEY, LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), 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 1227 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::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), KEY, LLINK, RED, 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 1163 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::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), KEY, LLINK, RED, 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]posthe splitting position (0-based)
[out]t1tree to receive positions [0, pos)
[out]t2tree to receive positions [pos, size)
Note
O(n) time complexity (simple iterative implementation)

Definition at line 1471 of file tpl_rbRk.H.

References Aleph::count(), Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), 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 1275 of file tpl_rbRk.H.

References BLACK, Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::black_height(), COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::join_with_pivot_rb(), LLINK, RED, 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 475 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 455 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 445 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 587 of file tpl_rbRk.H.

References Aleph::and, Aleph::check_rank_tree(), Aleph::Gen_Rb_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::is_red_black_bst_rk(), 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 121 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 123 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 124 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 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 >::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 118 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 117 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 120 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 119 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: