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 | List of all members
Aleph::HtdRbTreeRk< Key, Compare > Class Template Reference
Trees

Hybrid top-down/bottom-up red-black tree with rank support. More...

#include <tpl_hRbTreeRk.H>

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

Classes

struct  Iterator
 In-order iterator. More...
 

Public Types

using Color = unsigned char
 
using Node = RbNodeRk< Key >
 
using key_type = Key
 

Public Member Functions

Compare & key_comp () noexcept
 
const Compare & key_comp () const noexcept
 
Compare & get_compare () noexcept
 
constexpr const Compare & get_compare () const noexcept
 
 HtdRbTreeRk (Compare __cmp=Compare()) noexcept
 
void swap (HtdRbTreeRk &tree) noexcept
 
 HtdRbTreeRk (HtdRbTreeRk &&tree) noexcept
 
HtdRbTreeRk & operator= (HtdRbTreeRk &&tree) noexcept
 
 HtdRbTreeRk (const HtdRbTreeRk &)=delete
 
HtdRbTreeRk & operator= (const HtdRbTreeRk &)=delete
 
virtual ~HtdRbTreeRk ()=default
 
constexpr bool is_empty () const noexcept
 
size_t size () const noexcept
 O(1) size using root count.
 
void reset () noexcept
 
Node * insert (Node *p) noexcept
 
Node * search_or_insert (Node *p) noexcept
 
Node * insert_dup (Node *p) noexcept
 
Node * search (const Key &key) const noexcept
 
Node * remove (const Key &key) noexcept
 
Node *& getRoot () noexcept
 
Node * getRoot () const noexcept
 
Node * select (size_t i) const
 Select the i-th smallest element (0-indexed).
 
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 where key would be inserted.
 
Node * remove_pos (size_t i)
 Remove element at position i.
 
void split_pos (size_t pos, HtdRbTreeRk &t1, HtdRbTreeRk &t2)
 Split tree at position.
 
bool verify () const noexcept
 Verify red-black and rank invariants.
 

Private Member Functions

bool less (const Key &k1, const Key &k2) const noexcept
 
bool equals (const Key &k1, const Key &k2) const noexcept
 
void restoreRedCondition (Node *p, Node *&fp, Node *ffp, Node *fffp) noexcept
 
Node * searchFlipColorsAndInsert (Node *q) noexcept
 Insert with stack tracking for count updates.
 
Node * searchFlipColorsAndInsertDup (Node *q) noexcept
 
Node * searchAndBuildPath (const Key &key) noexcept
 
void findSuccAndSwap (Node *p, Node *&fp) noexcept
 
void balanceDownAndColor (Node *p, Node *&fp, Node *&sp) noexcept
 
void rotateNephewAndColor (Node *fp, Node *sp, Node *np) noexcept
 
void doubleRotateNephewAndColor (Node *fp, Node *sp, Node *snp) noexcept
 
void removeAndFixBlackCondition (Node *q) noexcept
 Remove node and fix red-black violations.
 
void init () noexcept
 

Static Private Member Functions

static Node * getSibling (Node *p, Node *fp) noexcept
 
static Node * rotate_to_right_rk (Node *p, Node *fp) noexcept
 Right rotation with count update.
 
static Node * rotate_to_left_rk (Node *p, Node *fp) noexcept
 Left rotation with count update.
 
static void flipColors (Node *p) noexcept
 
static void colorSiblingAsRed (Node *sp) noexcept
 
static void colorParentAndSibling (Node *fp, Node *sp) noexcept
 
static void updateCountRec (Node *p) noexcept
 Recursively update counts for entire subtree - O(n)
 
static bool verifyCountsRec (Node *p) noexcept
 

Private Attributes

Node headNode
 
Node headParent
 
Node headGrandParent
 
Node * head
 
Node * fHead
 
Node * ffHead
 
Node *& root
 
FixedStack< Node * > path {Node::MaxHeight}
 
Compare cmp
 

Detailed Description

template<class Key, class Compare = Aleph::less<Key>>
class Aleph::HtdRbTreeRk< Key, Compare >

Hybrid top-down/bottom-up red-black tree with rank support.

This class implements a self-balancing binary search tree with O(log n) rank operations (select, position). It combines:

  • Insertion: Top-down with proactive color flipping and stack tracking
  • Deletion: Bottom-up using a stack to track ancestors
  • Rank operations: Subtree counts maintained during all operations
Complexity (ALL O(log n)):
  • search, insert, remove: O(log n)
  • select(i): O(log n) - get i-th smallest element
  • position(key): O(log n) - get rank of a key
  • find_position(key): O(log n) - get insertion position
  • size(): O(1)

This is the only implementation that achieves O(log n) for ALL operations including removal with rank support.

Template Parameters
KeyThe type of keys stored in the tree
CompareComparison functor (default: Aleph::less<Key>)
See also
HtdRbTree Hybrid tree without rank support
Gen_Rb_Tree_Rk Bottom-up tree with rank
GenTdRbTreeRk Top-down tree with rank (O(n) remove)
Author
Leandro Rabindranath León

Definition at line 92 of file tpl_hRbTreeRk.H.

Member Typedef Documentation

◆ Color

template<class Key , class Compare = Aleph::less<Key>>
using Aleph::HtdRbTreeRk< Key, Compare >::Color = unsigned char

Definition at line 95 of file tpl_hRbTreeRk.H.

◆ key_type

template<class Key , class Compare = Aleph::less<Key>>
using Aleph::HtdRbTreeRk< Key, Compare >::key_type = Key

Definition at line 714 of file tpl_hRbTreeRk.H.

◆ Node

template<class Key , class Compare = Aleph::less<Key>>
using Aleph::HtdRbTreeRk< Key, Compare >::Node = RbNodeRk<Key>

Definition at line 96 of file tpl_hRbTreeRk.H.

Constructor & Destructor Documentation

◆ HtdRbTreeRk() [1/3]

template<class Key , class Compare = Aleph::less<Key>>
Aleph::HtdRbTreeRk< Key, Compare >::HtdRbTreeRk ( Compare  __cmp = Compare())
inlinenoexcept

Definition at line 721 of file tpl_hRbTreeRk.H.

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

◆ HtdRbTreeRk() [2/3]

template<class Key , class Compare = Aleph::less<Key>>
Aleph::HtdRbTreeRk< Key, Compare >::HtdRbTreeRk ( HtdRbTreeRk< Key, Compare > &&  tree)
inlinenoexcept

Definition at line 737 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::init(), and Aleph::HtdRbTreeRk< Key, Compare >::swap().

◆ HtdRbTreeRk() [3/3]

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

◆ ~HtdRbTreeRk()

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

Member Function Documentation

◆ balanceDownAndColor()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::balanceDownAndColor ( Node *  p,
Node *&  fp,
Node *&  sp 
)
inlineprivatenoexcept

Definition at line 481 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTreeRk< Key, Compare >::path, RED, Aleph::RLINK(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_left_rk(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_right_rk(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ colorParentAndSibling()

template<class Key , class Compare = Aleph::less<Key>>
static void Aleph::HtdRbTreeRk< Key, Compare >::colorParentAndSibling ( Node *  fp,
Node *  sp 
)
inlinestaticprivatenoexcept

Definition at line 564 of file tpl_hRbTreeRk.H.

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

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ colorSiblingAsRed()

template<class Key , class Compare = Aleph::less<Key>>
static void Aleph::HtdRbTreeRk< Key, Compare >::colorSiblingAsRed ( Node *  sp)
inlinestaticprivatenoexcept

Definition at line 558 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::maps(), and RED.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ doubleRotateNephewAndColor()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::doubleRotateNephewAndColor ( Node *  fp,
Node *  sp,
Node *  snp 
)
inlineprivatenoexcept

Definition at line 532 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTreeRk< Key, Compare >::path, RED, Aleph::RLINK(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_left_rk(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_right_rk(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ equals()

template<class Key , class Compare = Aleph::less<Key>>
bool Aleph::HtdRbTreeRk< Key, Compare >::equals ( const Key &  k1,
const Key &  k2 
) const
inlineprivatenoexcept

Definition at line 115 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp, and Aleph::maps().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::remove(), Aleph::HtdRbTreeRk< Key, Compare >::search(), Aleph::HtdRbTreeRk< Key, Compare >::searchAndBuildPath(), and Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsert().

◆ find_position()

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

Find position where key would be inserted.

Works even if key doesn't exist in the tree.

Parameters
keyKey to find position for
Returns
Pair of (position, node). Node is nullptr if key not found.

Definition at line 886 of file tpl_hRbTreeRk.H.

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

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

◆ findSuccAndSwap()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::findSuccAndSwap ( Node *  p,
Node *&  fp 
)
inlineprivatenoexcept

Definition at line 428 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ flipColors()

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

Definition at line 227 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, RED, and Aleph::RLINK().

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

◆ get_compare() [1/2]

template<class Key , class Compare = Aleph::less<Key>>
constexpr const Compare & Aleph::HtdRbTreeRk< Key, Compare >::get_compare ( ) const
inlineconstexprnoexcept

Definition at line 719 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp.

◆ get_compare() [2/2]

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

Definition at line 718 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp.

◆ getRoot() [1/2]

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

Definition at line 851 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::root.

◆ getRoot() [2/2]

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

Definition at line 850 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::root.

◆ getSibling()

template<class Key , class Compare = Aleph::less<Key>>
static Node * Aleph::HtdRbTreeRk< Key, Compare >::getSibling ( Node *  p,
Node *  fp 
)
inlinestaticprivatenoexcept

Definition at line 118 of file tpl_hRbTreeRk.H.

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

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ init()

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

Definition at line 699 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::HtdRbTreeRk< Key, Compare >::ffHead, Aleph::HtdRbTreeRk< Key, Compare >::fHead, Aleph::HtdRbTreeRk< Key, Compare >::head, Aleph::RbNodeRk< Key >::NullPtr, and Aleph::RLINK().

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

◆ insert()

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

Definition at line 767 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::root, and Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsert().

Referenced by HtdRbTreeRkTest::insert_range(), and Aleph::HtdRbTreeRk< Key, Compare >::search_or_insert().

◆ insert_dup()

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

Definition at line 802 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::root, and Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsertDup().

◆ is_empty()

template<class Key , class Compare = Aleph::less<Key>>
constexpr bool Aleph::HtdRbTreeRk< Key, Compare >::is_empty ( ) const
inlineconstexprnoexcept

Definition at line 760 of file tpl_hRbTreeRk.H.

References Aleph::RbNodeRk< Key >::NullPtr, and Aleph::HtdRbTreeRk< Key, Compare >::root.

◆ key_comp() [1/2]

template<class Key , class Compare = Aleph::less<Key>>
const Compare & Aleph::HtdRbTreeRk< Key, Compare >::key_comp ( ) const
inlinenoexcept

Definition at line 717 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp.

◆ key_comp() [2/2]

template<class Key , class Compare = Aleph::less<Key>>
Compare & Aleph::HtdRbTreeRk< Key, Compare >::key_comp ( )
inlinenoexcept

Definition at line 716 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp.

◆ less()

template<class Key , class Compare = Aleph::less<Key>>
bool Aleph::HtdRbTreeRk< Key, Compare >::less ( const Key &  k1,
const Key &  k2 
) const
inlineprivatenoexcept

Definition at line 112 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp, and Aleph::maps().

◆ operator=() [1/2]

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

◆ operator=() [2/2]

template<class Key , class Compare = Aleph::less<Key>>
HtdRbTreeRk & Aleph::HtdRbTreeRk< Key, Compare >::operator= ( HtdRbTreeRk< Key, Compare > &&  tree)
inlinenoexcept

Definition at line 749 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::swap().

◆ position()

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

Find position of a key.

Parameters
keyKey to find
Returns
Pair of (position, node). Position is -1 if not found.

Definition at line 871 of file tpl_hRbTreeRk.H.

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

◆ remove()

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

Definition at line 830 of file tpl_hRbTreeRk.H.

References Aleph::FixedStack< T >::empty(), Aleph::HtdRbTreeRk< Key, Compare >::equals(), KEY, Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition(), Aleph::RbNodeRk< Key >::reset(), Aleph::HtdRbTreeRk< Key, Compare >::root, and Aleph::HtdRbTreeRk< Key, Compare >::searchAndBuildPath().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::remove_pos().

◆ remove_pos()

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

Remove element at position i.

Parameters
iPosition (0-indexed)
Returns
Removed node
Exceptions
std::out_of_rangeif i >= size()

Definition at line 900 of file tpl_hRbTreeRk.H.

References ah_out_of_range_error_if, KEY, Aleph::HtdRbTreeRk< Key, Compare >::remove(), Aleph::HtdRbTreeRk< Key, Compare >::select(), and Aleph::HtdRbTreeRk< Key, Compare >::size().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::split_pos().

◆ removeAndFixBlackCondition()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition ( Node *  q)
inlineprivatenoexcept

Remove node and fix red-black violations.

After BST deletion and red-black fixing, recalculates all counts. The count update is O(n) due to the complexity of tracking all affected nodes during deletion with swaps and rotations.

Definition at line 590 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::balanceDownAndColor(), BLACK, COLOR, Aleph::HtdRbTreeRk< Key, Compare >::colorParentAndSibling(), Aleph::HtdRbTreeRk< Key, Compare >::colorSiblingAsRed(), Aleph::HtdRbTreeRk< Key, Compare >::doubleRotateNephewAndColor(), Aleph::FixedStack< T >::empty(), Aleph::HtdRbTreeRk< Key, Compare >::findSuccAndSwap(), Aleph::HtdRbTreeRk< Key, Compare >::getSibling(), Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), RED, Aleph::RLINK(), Aleph::HtdRbTreeRk< Key, Compare >::root, Aleph::HtdRbTreeRk< Key, Compare >::rotateNephewAndColor(), Aleph::FixedStack< T >::top(), and Aleph::HtdRbTreeRk< Key, Compare >::updateCountRec().

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

◆ reset()

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

Definition at line 765 of file tpl_hRbTreeRk.H.

References Aleph::RbNodeRk< Key >::NullPtr, and Aleph::HtdRbTreeRk< Key, Compare >::root.

◆ restoreRedCondition()

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

Definition at line 182 of file tpl_hRbTreeRk.H.

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

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

◆ rotate_to_left_rk()

template<class Key , class Compare = Aleph::less<Key>>
static Node * Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_left_rk ( Node *  p,
Node *  fp 
)
inlinestaticprivatenoexcept

Left rotation with count update.

Definition at line 158 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, and Aleph::RLINK().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::balanceDownAndColor(), Aleph::HtdRbTreeRk< Key, Compare >::doubleRotateNephewAndColor(), Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), and Aleph::HtdRbTreeRk< Key, Compare >::rotateNephewAndColor().

◆ rotate_to_right_rk()

template<class Key , class Compare = Aleph::less<Key>>
static Node * Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_right_rk ( Node *  p,
Node *  fp 
)
inlinestaticprivatenoexcept

Right rotation with count update.

After rotation:

  • q becomes parent of p
  • q.count = p.count (takes p's position)
  • p.count = 1 + LCOUNT + RCOUNT

Definition at line 133 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, and Aleph::RLINK().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::balanceDownAndColor(), Aleph::HtdRbTreeRk< Key, Compare >::doubleRotateNephewAndColor(), Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), and Aleph::HtdRbTreeRk< Key, Compare >::rotateNephewAndColor().

◆ rotateNephewAndColor()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::rotateNephewAndColor ( Node *  fp,
Node *  sp,
Node *  np 
)
inlineprivatenoexcept

Definition at line 511 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::FixedStack< T >::is_empty(), Aleph::LLINK(), Aleph::maps(), Aleph::HtdRbTreeRk< Key, Compare >::path, RED, Aleph::RLINK(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_left_rk(), Aleph::HtdRbTreeRk< Key, Compare >::rotate_to_right_rk(), and Aleph::FixedStack< T >::top().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition().

◆ search()

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

Definition at line 817 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::equals(), KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::RLINK(), and Aleph::HtdRbTreeRk< Key, Compare >::root.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::search_or_insert().

◆ search_or_insert()

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

Definition at line 782 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::HtdRbTreeRk< Key, Compare >::insert(), KEY, Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::root, and Aleph::HtdRbTreeRk< Key, Compare >::search().

◆ searchAndBuildPath()

template<class Key , class Compare = Aleph::less<Key>>
Node * Aleph::HtdRbTreeRk< Key, Compare >::searchAndBuildPath ( const Key &  key)
inlineprivatenoexcept

Definition at line 397 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::equals(), Aleph::HtdRbTreeRk< Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::FixedStack< T >::push(), Aleph::RLINK(), and Aleph::HtdRbTreeRk< Key, Compare >::root.

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

◆ searchFlipColorsAndInsert()

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

Insert with stack tracking for count updates.

Uses a stack to track the path during insertion, then updates counts bottom-up after all rotations are complete.

Definition at line 242 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::HtdRbTreeRk< Key, Compare >::equals(), Aleph::HtdRbTreeRk< Key, Compare >::ffHead, Aleph::HtdRbTreeRk< Key, Compare >::fHead, Aleph::HtdRbTreeRk< Key, Compare >::flipColors(), Aleph::HtdRbTreeRk< Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), Aleph::RLINK(), and Aleph::HtdRbTreeRk< Key, Compare >::root.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::insert().

◆ searchFlipColorsAndInsertDup()

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

Definition at line 321 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::HtdRbTreeRk< Key, Compare >::ffHead, Aleph::HtdRbTreeRk< Key, Compare >::fHead, Aleph::HtdRbTreeRk< Key, Compare >::flipColors(), Aleph::HtdRbTreeRk< Key, Compare >::head, KEY, Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), Aleph::RLINK(), and Aleph::HtdRbTreeRk< Key, Compare >::root.

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

◆ select()

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

Select the i-th smallest element (0-indexed).

Parameters
iPosition (0 = smallest)
Returns
Pointer to node at position i
Exceptions
std::out_of_rangeif i >= size()

Definition at line 861 of file tpl_hRbTreeRk.H.

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

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::remove_pos().

◆ size()

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

O(1) size using root count.

Definition at line 763 of file tpl_hRbTreeRk.H.

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

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::remove_pos(), and Aleph::HtdRbTreeRk< Key, Compare >::split_pos().

◆ split_pos()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::split_pos ( size_t  pos,
HtdRbTreeRk< Key, Compare > &  t1,
HtdRbTreeRk< Key, Compare > &  t2 
)
inline

Split tree at position.

After split:

  • t1 contains elements at positions [0, pos)
  • t2 contains elements at positions [pos, size())
  • this tree becomes empty
Parameters
posSplit position
t1Tree for left part
t2Tree for right part

Definition at line 918 of file tpl_hRbTreeRk.H.

References ah_out_of_range_error_if, Aleph::DynList< T >::insert(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::remove_pos(), Aleph::HTList::reset(), Aleph::HtdRbTreeRk< Key, Compare >::root, Aleph::HTList::size(), and Aleph::HtdRbTreeRk< Key, Compare >::size().

◆ swap()

template<class Key , class Compare = Aleph::less<Key>>
void Aleph::HtdRbTreeRk< Key, Compare >::swap ( HtdRbTreeRk< Key, Compare > &  tree)
inlinenoexcept

Definition at line 731 of file tpl_hRbTreeRk.H.

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

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::HtdRbTreeRk(), and Aleph::HtdRbTreeRk< Key, Compare >::operator=().

◆ updateCountRec()

template<class Key , class Compare = Aleph::less<Key>>
static void Aleph::HtdRbTreeRk< Key, Compare >::updateCountRec ( Node *  p)
inlinestaticprivatenoexcept

Recursively update counts for entire subtree - O(n)

Definition at line 575 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::RLINK(), and Aleph::HtdRbTreeRk< Key, Compare >::updateCountRec().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition(), and Aleph::HtdRbTreeRk< Key, Compare >::updateCountRec().

◆ verify()

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

Verify red-black and rank invariants.

Returns
true if all invariants hold

Definition at line 939 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp, Aleph::is_red_black_bst_rk(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::root, and Aleph::HtdRbTreeRk< Key, Compare >::verifyCountsRec().

◆ verifyCountsRec()

template<class Key , class Compare = Aleph::less<Key>>
static bool Aleph::HtdRbTreeRk< Key, Compare >::verifyCountsRec ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 953 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::LLINK(), Aleph::maps(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::RLINK(), and Aleph::HtdRbTreeRk< Key, Compare >::verifyCountsRec().

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::verify(), and Aleph::HtdRbTreeRk< Key, Compare >::verifyCountsRec().

Member Data Documentation

◆ cmp

template<class Key , class Compare = Aleph::less<Key>>
Compare Aleph::HtdRbTreeRk< Key, Compare >::cmp
private

Definition at line 110 of file tpl_hRbTreeRk.H.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::equals(), Aleph::HtdRbTreeRk< Key, Compare >::find_position(), Aleph::HtdRbTreeRk< Key, Compare >::get_compare(), Aleph::HtdRbTreeRk< Key, Compare >::get_compare(), Aleph::HtdRbTreeRk< Key, Compare >::key_comp(), Aleph::HtdRbTreeRk< Key, Compare >::key_comp(), Aleph::HtdRbTreeRk< Key, Compare >::less(), Aleph::HtdRbTreeRk< Key, Compare >::position(), Aleph::HtdRbTreeRk< Key, Compare >::swap(), and Aleph::HtdRbTreeRk< Key, Compare >::verify().

◆ ffHead

template<class Key , class Compare = Aleph::less<Key>>
Node* Aleph::HtdRbTreeRk< Key, Compare >::ffHead
private

Definition at line 105 of file tpl_hRbTreeRk.H.

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

◆ fHead

template<class Key , class Compare = Aleph::less<Key>>
Node* Aleph::HtdRbTreeRk< Key, Compare >::fHead
private

Definition at line 104 of file tpl_hRbTreeRk.H.

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

◆ head

template<class Key , class Compare = Aleph::less<Key>>
Node* Aleph::HtdRbTreeRk< Key, Compare >::head
private

Definition at line 103 of file tpl_hRbTreeRk.H.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::init(), Aleph::HtdRbTreeRk< Key, Compare >::searchAndBuildPath(), Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsert(), and Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsertDup().

◆ headGrandParent

template<class Key , class Compare = Aleph::less<Key>>
Node Aleph::HtdRbTreeRk< Key, Compare >::headGrandParent
private

Definition at line 101 of file tpl_hRbTreeRk.H.

◆ headNode

template<class Key , class Compare = Aleph::less<Key>>
Node Aleph::HtdRbTreeRk< Key, Compare >::headNode
private

Definition at line 99 of file tpl_hRbTreeRk.H.

◆ headParent

template<class Key , class Compare = Aleph::less<Key>>
Node Aleph::HtdRbTreeRk< Key, Compare >::headParent
private

Definition at line 100 of file tpl_hRbTreeRk.H.

◆ path

template<class Key , class Compare = Aleph::less<Key>>
FixedStack<Node *> Aleph::HtdRbTreeRk< Key, Compare >::path {Node::MaxHeight}
private

Definition at line 108 of file tpl_hRbTreeRk.H.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::balanceDownAndColor(), Aleph::HtdRbTreeRk< Key, Compare >::doubleRotateNephewAndColor(), Aleph::HtdRbTreeRk< Key, Compare >::findSuccAndSwap(), Aleph::HtdRbTreeRk< Key, Compare >::remove(), Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition(), Aleph::HtdRbTreeRk< Key, Compare >::rotateNephewAndColor(), and Aleph::HtdRbTreeRk< Key, Compare >::searchAndBuildPath().

◆ root

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

Definition at line 106 of file tpl_hRbTreeRk.H.

Referenced by Aleph::HtdRbTreeRk< Key, Compare >::find_position(), Aleph::HtdRbTreeRk< Key, Compare >::getRoot(), Aleph::HtdRbTreeRk< Key, Compare >::getRoot(), Aleph::HtdRbTreeRk< Key, Compare >::insert(), Aleph::HtdRbTreeRk< Key, Compare >::insert_dup(), Aleph::HtdRbTreeRk< Key, Compare >::is_empty(), Aleph::HtdRbTreeRk< Key, Compare >::position(), Aleph::HtdRbTreeRk< Key, Compare >::remove(), Aleph::HtdRbTreeRk< Key, Compare >::removeAndFixBlackCondition(), Aleph::HtdRbTreeRk< Key, Compare >::reset(), Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), Aleph::HtdRbTreeRk< Key, Compare >::search(), Aleph::HtdRbTreeRk< Key, Compare >::search_or_insert(), Aleph::HtdRbTreeRk< Key, Compare >::searchAndBuildPath(), Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsert(), Aleph::HtdRbTreeRk< Key, Compare >::searchFlipColorsAndInsertDup(), Aleph::HtdRbTreeRk< Key, Compare >::select(), Aleph::HtdRbTreeRk< Key, Compare >::size(), Aleph::HtdRbTreeRk< Key, Compare >::split_pos(), Aleph::HtdRbTreeRk< Key, Compare >::swap(), and Aleph::HtdRbTreeRk< Key, Compare >::verify().

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