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

Top-down red-black tree with rank support (select/position). More...

#include <tpl_tdRbTreeRk.H>

Inheritance diagram for Aleph::GenTdRbTreeRk< NodeType, Key, Compare >:
[legend]
Collaboration diagram for Aleph::GenTdRbTreeRk< NodeType, Key, Compare >:
[legend]

Classes

struct  Iterator
 Iterator. More...
 

Public Types

using Node = NodeType< Key >
 
using key_type = Key
 
using compare_type = Compare
 

Public Member Functions

 GenTdRbTreeRk () noexcept
 Default constructor.
 
 GenTdRbTreeRk (const Compare &__cmp) noexcept
 Constructor with comparator.
 
 GenTdRbTreeRk (GenTdRbTreeRk &&other) noexcept
 Move constructor.
 
GenTdRbTreeRk & operator= (GenTdRbTreeRk &&other) noexcept
 Move assignment.
 
 GenTdRbTreeRk (const GenTdRbTreeRk &)=delete
 
GenTdRbTreeRk & operator= (const GenTdRbTreeRk &)=delete
 
void reset () noexcept
 Reset tree (does not free nodes)
 
void swap (GenTdRbTreeRk &other) noexcept
 Swap with another tree.
 
virtual ~GenTdRbTreeRk ()=default
 
size_t size () const noexcept
 Get number of nodes O(1)
 
bool is_empty () const noexcept
 Check if empty.
 
Compare & get_compare () noexcept
 Get comparator.
 
const Compare & get_compare () const noexcept
 
Node * insert (Node *p) noexcept
 Insert a node.
 
Node * insert_dup (Node *p) noexcept
 Insert a node allowing duplicates.
 
Node * search_or_insert (Node *p) noexcept
 Search or insert.
 
Node * search (const Key &key) const noexcept
 Search for a key.
 
Node * remove (const Key &key) noexcept
 Remove node with given key.
 
Node *& getRoot () noexcept
 Get root pointer.
 
Node * getRoot () const noexcept
 
Node * select (size_t i) const
 Select i-th node in order.
 
std::pair< long, Node * > position (const Key &key) const noexcept
 Find position of a key.
 
std::pair< long, Node * > find_position (const Key &key) const noexcept
 Find position of a key (even if not in tree).
 
Node * remove_pos (size_t i)
 Remove node at position i.
 
void split_pos (size_t pos, GenTdRbTreeRk &t1, GenTdRbTreeRk &t2) noexcept
 Split tree by position.
 
bool verify () const noexcept
 Verify tree properties.
 

Static Public Attributes

static constexpr size_t PATH_STACK_CAPACITY = 128
 

Private Member Functions

bool less (const Key &a, const Key &b) const noexcept
 Returns true if a < b according to comparator.
 
bool equals (const Key &a, const Key &b) const noexcept
 Returns true if a == b (neither a < b nor b < a)
 
void restoreRedCondition (Node *p, Node *&fp, Node *ffp, Node *fffp) noexcept
 Restore red-black property after color flip.
 
Node * searchFlipColorsAndInsert (Node *q) noexcept
 Search for insertion point, flipping colors proactively.
 
Node * searchFlipColorsAndInsertDup (Node *q) noexcept
 Search for insertion point allowing duplicates.
 
void colorRootAsRed () noexcept
 Color root red if safe.
 
Node * searchAndColorRed (const Key &key, Node *&fp, Node **stack, size_t &stack_len) noexcept
 Search for key while coloring nodes red for deletion.
 
void init () noexcept
 Initialize header nodes.
 
void split_pos_inorder (Node *p, size_t pos, GenTdRbTreeRk &t1, GenTdRbTreeRk &t2, size_t &count) noexcept
 

Static Private Member Functions

static Node * rotate_to_right_rk (Node *p, Node *pp) noexcept
 Rotate to right with counter update.
 
static Node * rotate_to_left_rk (Node *p, Node *pp) noexcept
 Rotate to left with counter update.
 
static void flipColors (Node *p) noexcept
 Flip colors with counter preservation.
 
static size_t updateCountRec (Node *p) noexcept
 Recursively update counts in subtree - O(n)
 
static void updateCountsFromStack (Node **stack, size_t len) noexcept
 Update counts for nodes in stack (bottom-up) - O(log n) After rotations, nodes may have moved but their counts can be recalculated from their current children.
 
static Node * gotoLeftAndColorRed (Node *fp, Node *&ffp) noexcept
 Descend to left child for deletion, ensuring red.
 
static Node * gotoRightAndColorRed (Node *fp, Node *&ffp) noexcept
 Descend to right child for deletion, ensuring red.
 
static void findSuccAndSwap (Node *p, Node *&fp) noexcept
 Find successor and swap for deletion.
 
static void findPredAndSwap (Node *p, Node *&fp) noexcept
 Find predecessor and swap for deletion.
 
static void removeAndRendLeafRed (Node *p, Node *fp) noexcept
 Remove node, making it a red leaf.
 

Private Attributes

Node headNode
 Sentinel header node (parent of root)
 
Node headParent
 Sentinel grandparent node.
 
Node * head
 Pointer to header.
 
Node * fHead
 Pointer to header's parent.
 
Node *& root
 Reference to root (right child of head)
 
Compare cmp
 Comparison functor.
 

Detailed Description

template<template< class > class NodeType, typename Key, class Compare = Aleph::less<Key>>
requires StrictWeakOrder<Compare, Key>
class Aleph::GenTdRbTreeRk< NodeType, Key, Compare >

Top-down red-black tree with rank support (select/position).

This class extends the top-down red-black tree algorithm with subtree counters in each node, enabling O(log n) operations for:

  • select(i): Get the i-th smallest element
  • position(key): Get the rank/position of a key
  • find_position(key): Find position even if key doesn't exist
  • split_pos(pos, t1, t2): Split tree by position
Complexity:
  • search, select, position: O(log n)
  • insert: O(log n) - uses stack for count updates
  • remove: O(n) - swaps make incremental updates unreliable

For O(log n) remove with rank, use Rb_Tree_Rk (bottom-up) which tracks the full path during descent.

Advantages over bottom-up:
  • Single-pass descent for insert (rotations done on the way down)
  • O(1) size() operation
  • O(log n) indexed access (select)
  • O(log n) position queries
Template Parameters
NodeTypeNode template (typically RbNodeRk or RbNodeRkVtl).
KeyThe type of keys stored in the tree.
CompareComparison functor for ordering keys.
See also
Gen_Rb_Tree_Rk Bottom-up red-black tree with rank support.
GenTdRbTree Top-down red-black tree without rank support.

Definition at line 99 of file tpl_tdRbTreeRk.H.

Member Typedef Documentation

◆ compare_type

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
using Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::compare_type = Compare

Definition at line 104 of file tpl_tdRbTreeRk.H.

◆ key_type

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
using Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::key_type = Key

Definition at line 103 of file tpl_tdRbTreeRk.H.

◆ Node

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
using Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::Node = NodeType<Key>

Definition at line 102 of file tpl_tdRbTreeRk.H.

Constructor & Destructor Documentation

◆ GenTdRbTreeRk() [1/4]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::GenTdRbTreeRk ( )
inlinenoexcept

Default constructor.

Definition at line 696 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init().

◆ GenTdRbTreeRk() [2/4]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::GenTdRbTreeRk ( const Compare &  __cmp)
inlineexplicitnoexcept

Constructor with comparator.

Definition at line 703 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init().

◆ GenTdRbTreeRk() [3/4]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::GenTdRbTreeRk ( GenTdRbTreeRk< NodeType, Key, Compare > &&  other)
inlinenoexcept

Move constructor.

Definition at line 710 of file tpl_tdRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

◆ GenTdRbTreeRk() [4/4]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::GenTdRbTreeRk ( const GenTdRbTreeRk< NodeType, Key, Compare > &  )
delete

◆ ~GenTdRbTreeRk()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
virtual Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::~GenTdRbTreeRk ( )
virtualdefault

Member Function Documentation

◆ colorRootAsRed()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::colorRootAsRed ( )
inlineprivatenoexcept

Color root red if safe.

Definition at line 616 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, LLINK, RED, RLINK, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed().

◆ equals()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
bool Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::equals ( const Key &  a,
const Key &  b 
) const
inlineprivatenoexcept

Returns true if a == b (neither a < b nor b < a)

Definition at line 124 of file tpl_tdRbTreeRk.H.

References Aleph::and, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::cmp, and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert().

◆ find_position()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
std::pair< long, Node * > Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::find_position ( const Key &  key) const
inlinenoexcept

Find position of a key (even if not in tree).

Returns
Pair of (position, node pointer).

Definition at line 895 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::find_position(), r, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

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

◆ findPredAndSwap()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findPredAndSwap ( Node *  p,
Node *&  fp 
)
inlinestaticprivatenoexcept

Find predecessor and swap for deletion.

Definition at line 563 of file tpl_tdRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoRightAndColorRed(), LLINK, pred, and RLINK.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::removeAndRendLeafRed().

◆ findSuccAndSwap()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findSuccAndSwap ( Node *  p,
Node *&  fp 
)
inlinestaticprivatenoexcept

Find successor and swap for deletion.

Definition at line 509 of file tpl_tdRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoRightAndColorRed(), LLINK, and RLINK.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::removeAndRendLeafRed().

◆ flipColors()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::flipColors ( Node *  p)
inlinestaticprivatenoexcept

Flip colors with counter preservation.

Definition at line 220 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, and RLINK.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ get_compare() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
const Compare & Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::get_compare ( ) const
inlinenoexcept

Definition at line 757 of file tpl_tdRbTreeRk.H.

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

◆ get_compare() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Compare & Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::get_compare ( )
inlinenoexcept

Get comparator.

Definition at line 756 of file tpl_tdRbTreeRk.H.

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

◆ getRoot() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::getRoot ( ) const
inlinenoexcept

Definition at line 867 of file tpl_tdRbTreeRk.H.

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

◆ getRoot() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node *& Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::getRoot ( )
inlinenoexcept

Get root pointer.

Definition at line 866 of file tpl_tdRbTreeRk.H.

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

◆ gotoLeftAndColorRed()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoLeftAndColorRed ( Node *  fp,
Node *&  ffp 
)
inlinestaticprivatenoexcept

Descend to left child for deletion, ensuring red.

Definition at line 397 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, RLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_left_rk(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_right_rk().

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findSuccAndSwap(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed().

◆ gotoRightAndColorRed()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoRightAndColorRed ( Node *  fp,
Node *&  ffp 
)
inlinestaticprivatenoexcept

Descend to right child for deletion, ensuring red.

Definition at line 453 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, RLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_left_rk(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_right_rk().

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findSuccAndSwap(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed().

◆ init()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init ( )
inlineprivatenoexcept

Initialize header nodes.

Definition at line 685 of file tpl_tdRbTreeRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::head, and RLINK.

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

◆ insert()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::insert ( Node *  p)
inlinenoexcept

Insert a node.

Returns
Pointer to inserted node, or nullptr if duplicate.

Definition at line 762 of file tpl_tdRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), RED, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert().

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

◆ insert_dup()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::insert_dup ( Node *  p)
inlinenoexcept

Insert a node allowing duplicates.

Returns
Pointer to inserted node.

Definition at line 780 of file tpl_tdRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), RED, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ is_empty()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
bool Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::is_empty ( ) const
inlinenoexcept

Check if empty.

Definition at line 753 of file tpl_tdRbTreeRk.H.

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

◆ less()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
bool Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::less ( const Key &  a,
const Key &  b 
) const
inlineprivatenoexcept

Returns true if a < b according to comparator.

Definition at line 118 of file tpl_tdRbTreeRk.H.

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

◆ operator=() [1/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
GenTdRbTreeRk & Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::operator= ( const GenTdRbTreeRk< NodeType, Key, Compare > &  )
delete

◆ operator=() [2/2]

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
GenTdRbTreeRk & Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::operator= ( GenTdRbTreeRk< NodeType, Key, Compare > &&  other)
inlinenoexcept

Move assignment.

Definition at line 720 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

◆ position()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
std::pair< long, Node * > Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::position ( const Key &  key) const
inlinenoexcept

Find position of a key.

Returns
Pair of (position, node pointer). Position is -1 if not found.

Definition at line 884 of file tpl_tdRbTreeRk.H.

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

◆ remove()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove ( const Key &  key)
inlinenoexcept

Remove node with given key.

Returns
Pointer to removed node, or nullptr if not found.
Note
Count update uses stack collected during search - O(log n) amortized, but may need full recalc after complex swaps.

Definition at line 837 of file tpl_tdRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::equals(), KEY, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::PATH_STACK_CAPACITY, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::removeAndRendLeafRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountRec().

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

◆ remove_pos()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove_pos ( size_t  i)
inline

Remove node at position i.

Parameters
iZero-based position.
Returns
Pointer to removed node.

Definition at line 907 of file tpl_tdRbTreeRk.H.

References KEY, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::select().

◆ removeAndRendLeafRed()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::removeAndRendLeafRed ( Node *  p,
Node *  fp 
)
inlinestaticprivatenoexcept

Remove node, making it a red leaf.

Definition at line 665 of file tpl_tdRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findPredAndSwap(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::findSuccAndSwap(), LLINK, and RLINK.

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

◆ reset()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::reset ( )
inlinenoexcept

Reset tree (does not free nodes)

Definition at line 735 of file tpl_tdRbTreeRk.H.

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

◆ restoreRedCondition()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::restoreRedCondition ( Node *  p,
Node *&  fp,
Node *  ffp,
Node *  fffp 
)
inlineprivatenoexcept

Restore red-black property after color flip.

Definition at line 174 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, RLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_left_rk(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_right_rk().

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ rotate_to_left_rk()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_left_rk ( Node *  p,
Node *  pp 
)
inlinestaticprivatenoexcept

Rotate to left with counter update.

Definition at line 152 of file tpl_tdRbTreeRk.H.

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

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoRightAndColorRed(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::restoreRedCondition().

◆ rotate_to_right_rk()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::rotate_to_right_rk ( Node *  p,
Node *  pp 
)
inlinestaticprivatenoexcept

Rotate to right with counter update.

Definition at line 130 of file tpl_tdRbTreeRk.H.

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

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoRightAndColorRed(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::restoreRedCondition().

◆ search()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search ( const Key &  key) const
inlinenoexcept

Search for a key.

Returns
Pointer to node, or nullptr if not found.

Definition at line 820 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::equals(), KEY, LLINK, RLINK, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

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

◆ search_or_insert()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search_or_insert ( Node *  p)
inlinenoexcept

Search or insert.

Returns
Inserted node or existing node with same key.

Definition at line 798 of file tpl_tdRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), KEY, RED, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert().

◆ searchAndColorRed()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed ( const Key &  key,
Node *&  fp,
Node **  stack,
size_t &  stack_len 
)
inlineprivatenoexcept

Search for key while coloring nodes red for deletion.

Also collects visited nodes in stack for count updates.

Definition at line 627 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::colorRootAsRed(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::equals(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoLeftAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::gotoRightAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::head, KEY, LLINK, RLINK, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

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

◆ searchFlipColorsAndInsert()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert ( Node *  q)
inlineprivatenoexcept

Search for insertion point, flipping colors proactively.

Uses stack to track path for O(log n) count updates.

Returns
Inserted node or nullptr if duplicate

Definition at line 233 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::equals(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::flipColors(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::head, KEY, LLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::PATH_STACK_CAPACITY, RED, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::restoreRedCondition(), RLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountsFromStack().

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

◆ searchFlipColorsAndInsertDup()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup ( Node *  q)
inlineprivatenoexcept

Search for insertion point allowing duplicates.

Uses stack for O(log n) count updates.

Definition at line 306 of file tpl_tdRbTreeRk.H.

References Aleph::and, BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::fHead, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::flipColors(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::head, KEY, LLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::PATH_STACK_CAPACITY, RED, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::restoreRedCondition(), RLINK, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountsFromStack().

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

◆ select()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node * Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::select ( size_t  i) const
inline

Select i-th node in order.

Parameters
iZero-based position.
Returns
Pointer to i-th node.
Exceptions
out_of_rangeif i >= size().

Definition at line 876 of file tpl_tdRbTreeRk.H.

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

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

◆ size()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
size_t Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::size ( ) const
inlinenoexcept

Get number of nodes O(1)

Definition at line 750 of file tpl_tdRbTreeRk.H.

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

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

◆ split_pos()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos ( size_t  pos,
GenTdRbTreeRk< NodeType, Key, Compare > &  t1,
GenTdRbTreeRk< NodeType, Key, Compare > &  t2 
)
inlinenoexcept

Split tree by position.

Parameters
posSplit position.
t1Receives nodes [0, pos).
t2Receives nodes [pos, size).

Definition at line 920 of file tpl_tdRbTreeRk.H.

References Aleph::count(), Aleph::divide_and_conquer_partition_dp(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root, Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::size(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos_inorder().

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ split_pos_inorder()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos_inorder ( Node *  p,
size_t  pos,
GenTdRbTreeRk< NodeType, Key, Compare > &  t1,
GenTdRbTreeRk< NodeType, Key, Compare > &  t2,
size_t &  count 
)
inlineprivatenoexcept

Definition at line 946 of file tpl_tdRbTreeRk.H.

References Aleph::count(), Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos_inorder().

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos_inorder().

◆ swap()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::swap ( GenTdRbTreeRk< NodeType, Key, Compare > &  other)
inlinenoexcept

Swap with another tree.

Definition at line 741 of file tpl_tdRbTreeRk.H.

References Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root.

◆ updateCountRec()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static size_t Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountRec ( Node *  p)
inlinestaticprivatenoexcept

Recursively update counts in subtree - O(n)

Definition at line 371 of file tpl_tdRbTreeRk.H.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, RLINK, and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountRec().

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountRec().

◆ updateCountsFromStack()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
static void Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::updateCountsFromStack ( Node **  stack,
size_t  len 
)
inlinestaticprivatenoexcept

Update counts for nodes in stack (bottom-up) - O(log n) After rotations, nodes may have moved but their counts can be recalculated from their current children.

Definition at line 385 of file tpl_tdRbTreeRk.H.

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

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ verify()

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
bool Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::verify ( ) const
inlinenoexcept

Verify tree properties.

Definition at line 970 of file tpl_tdRbTreeRk.H.

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

Referenced by TEST(), and TEST().

Member Data Documentation

◆ cmp

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Compare Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::cmp
private

Comparison functor.

Definition at line 115 of file tpl_tdRbTreeRk.H.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::equals(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::find_position(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::get_compare(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::get_compare(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::less(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::operator=(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::position(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::swap(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::verify().

◆ fHead

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node* Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::fHead
private

Pointer to header's parent.

Definition at line 113 of file tpl_tdRbTreeRk.H.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ head

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node* Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::head
private

Pointer to header.

Definition at line 112 of file tpl_tdRbTreeRk.H.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::init(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ headNode

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::headNode
private

Sentinel header node (parent of root)

Definition at line 110 of file tpl_tdRbTreeRk.H.

◆ headParent

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::headParent
private

Sentinel grandparent node.

Definition at line 111 of file tpl_tdRbTreeRk.H.

◆ PATH_STACK_CAPACITY

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
constexpr size_t Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::PATH_STACK_CAPACITY = 128
staticconstexpr

Definition at line 105 of file tpl_tdRbTreeRk.H.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup().

◆ root

template<template< class > class NodeType, typename Key , class Compare = Aleph::less<Key>>
Node*& Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::root
private

Reference to root (right child of head)

Definition at line 114 of file tpl_tdRbTreeRk.H.

Referenced by Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::GenTdRbTreeRk(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::colorRootAsRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::find_position(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::getRoot(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::getRoot(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::insert(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::insert_dup(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::is_empty(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::operator=(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::position(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::remove(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::reset(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::restoreRedCondition(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::search_or_insert(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchAndColorRed(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsert(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::searchFlipColorsAndInsertDup(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::select(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::size(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::split_pos(), Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::swap(), and Aleph::GenTdRbTreeRk< NodeType, Key, Compare >::verify().

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