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>>
requires StrictWeakOrder<Compare, 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 94 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 97 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 716 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 98 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 723 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 739 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 483 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::HtdRbTreeRk< Key, Compare >::path, RED, 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 566 of file tpl_hRbTreeRk.H.

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

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), 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 534 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::HtdRbTreeRk< Key, Compare >::path, RED, 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 117 of file tpl_hRbTreeRk.H.

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

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 888 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::HtdRbTreeRk< Key, Compare >::find_position(), r, 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 430 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::FixedStack< T >::push(), 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 229 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, RED, and 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 721 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 720 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 853 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 852 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 120 of file tpl_hRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), LLINK, and 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 701 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 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 769 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), 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 804 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), 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 762 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 719 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 718 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 114 of file tpl_hRbTreeRk.H.

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

◆ 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 751 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 873 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::cmp, Aleph::divide_and_conquer_partition_dp(), Aleph::inorder_position(), 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 832 of file tpl_hRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::empty(), Aleph::HtdRbTreeRk< Key, Compare >::equals(), KEY, 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 902 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 592 of file tpl_hRbTreeRk.H.

References Aleph::HtdRbTreeRk< Key, Compare >::balanceDownAndColor(), BLACK, COLOR, Aleph::HtdRbTreeRk< Key, Compare >::colorParentAndSibling(), Aleph::HtdRbTreeRk< Key, Compare >::colorSiblingAsRed(), Aleph::divide_and_conquer_partition_dp(), Aleph::HtdRbTreeRk< Key, Compare >::doubleRotateNephewAndColor(), Aleph::FixedStack< T >::empty(), Aleph::HtdRbTreeRk< Key, Compare >::findSuccAndSwap(), Aleph::HtdRbTreeRk< Key, Compare >::getSibling(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), RED, 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 767 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 184 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), LLINK, RED, 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 160 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, and 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 135 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, and 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 513 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::HtdRbTreeRk< Key, Compare >::path, RED, 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 819 of file tpl_hRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::HtdRbTreeRk< Key, Compare >::equals(), KEY, LLINK, Aleph::RbNodeRk< Key >::NullPtr, 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 784 of file tpl_hRbTreeRk.H.

References COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::HtdRbTreeRk< Key, Compare >::insert(), KEY, 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 399 of file tpl_hRbTreeRk.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::HtdRbTreeRk< Key, Compare >::equals(), Aleph::HtdRbTreeRk< Key, Compare >::head, KEY, LLINK, Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::path, Aleph::FixedStack< T >::push(), 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 244 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), 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, LLINK, Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), 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 323 of file tpl_hRbTreeRk.H.

References BLACK, COLOR, Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), Aleph::HtdRbTreeRk< Key, Compare >::ffHead, Aleph::HtdRbTreeRk< Key, Compare >::fHead, Aleph::HtdRbTreeRk< Key, Compare >::flipColors(), Aleph::HtdRbTreeRk< Key, Compare >::head, KEY, LLINK, Aleph::RbNodeRk< Key >::NullPtr, RED, Aleph::HtdRbTreeRk< Key, Compare >::restoreRedCondition(), 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 863 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 765 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 920 of file tpl_hRbTreeRk.H.

References ah_out_of_range_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::RbNodeRk< Key >::NullPtr, Aleph::HtdRbTreeRk< Key, Compare >::remove_pos(), Aleph::HtdRbTreeRk< Key, Compare >::root, 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 733 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 577 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, 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 941 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 955 of file tpl_hRbTreeRk.H.

References Aleph::COUNT(), Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::RbNodeRk< Key >::NullPtr, 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 112 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 107 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 106 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 105 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 103 of file tpl_hRbTreeRk.H.

◆ headNode

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

Definition at line 101 of file tpl_hRbTreeRk.H.

◆ headParent

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

Definition at line 102 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 110 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 108 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: