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

AVL balanced binary search tree with rank (order statistics). More...

#include <tpl_avlRk.H>

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

Classes

class  Iterator
 Iterator over the nodes. More...
 

Public Types

using Node = NodeType< Key >
 
using key_type = Key
 

Public Member Functions

constexpr Compare & key_comp () noexcept
 The key type.
 
constexpr Compare & get_compare () noexcept
 
 Gen_Avl_Tree_Rk (Compare cmf_fct=Compare()) noexcept
 
void swap (Gen_Avl_Tree_Rk &tree) noexcept
 Swap in constant time all the items of this with the items of tree.
 
virtual ~Gen_Avl_Tree_Rk () noexcept
 
constexpr Node *& getRoot () noexcept
 Return a modifiable reference to tree's root.
 
constexpr Node * getRoot () const noexcept
 Return a pointer to the tree's root.
 
size_t size () const noexcept
 Return the number of nodes in the tree.
 
constexpr bool is_empty () const noexcept
 Return true if tree is empty.
 
Node * search (const Key &key) const noexcept
 Search a node containing key; if found, then a pointer to the node containing it is returned; otherwise nullptr is returned.
 
Node * insert (Node *p) noexcept
 Insert the node pointed by p in the tree.
 
Node * search_or_insert (Node *p) noexcept
 Search or insert a key.
 
Node * insert_dup (Node *p) noexcept
 Insert the node p without testing for key duplicity.
 
Node * remove (const Key &key) noexcept
 Remove from tree the node containing key.
 
Node * select (const size_t i) const
 Return the i-th node in order sense.
 
std::pair< long, Node * > position (const Key &key) const noexcept
 Compute the inorder position of a key.
 
std::pair< long, Node * > find_position (const Key &key) const noexcept
 Find the inorder position of a key in the tree.
 
bool verify () const noexcept
 Return true if the tree is a valid AVL tree with correct counters.
 
void join_exclusive (Gen_Avl_Tree_Rk &t) noexcept
 Join this tree exclusively with another tree.
 
Node * split_key (const Key &key, Gen_Avl_Tree_Rk &t1, Gen_Avl_Tree_Rk &t2) noexcept
 Split tree by key.
 
void split_key_dup (const Key &key, Gen_Avl_Tree_Rk &t1, Gen_Avl_Tree_Rk &t2) noexcept
 Split tree by key including duplicates.
 
void split_pos (const size_t pos, Gen_Avl_Tree_Rk &t1, Gen_Avl_Tree_Rk &t2) noexcept
 Split tree by inorder position.
 

Private Types

enum  Rotation_Type { ROTATE_LEFT , ROTATE_RIGHT , DOUBLE_ROTATE_LEFT , DOUBLE_ROTATE_RIGHT }
 

Private Member Functions

bool avl_stack_at_base () noexcept
 
void clean_avl_stack () noexcept
 
Node * search_and_stack_avl (const Key &key, signed char &cmp_result) noexcept
 
Node * search_dup_and_stack_avl (const Key &key, signed char &cmp_result) noexcept
 
void restore_avl_after_insertion (Node *p) noexcept
 
Node * swapWithSuccessor (Node *p, Node *&pp) noexcept
 
void restore_avl_after_deletion (bool left_deficit) noexcept
 
void update_counters_after_insertion () noexcept
 
void update_counters_after_deletion () noexcept
 
Node * split_key_rec (Node *p, const Key &key, Node *&t1, Node *&t2) noexcept
 
void split_key_dup_rec (Node *p, const Key &key, Node *&t1, Node *&t2) noexcept
 
void split_pos_rec (Node *p, size_t pos, Node *&t1, Node *&t2) noexcept
 

Static Private Member Functions

static Node * rotateLeft (Node *p) noexcept
 
static Node * rotateRight (Node *p) noexcept
 
static Node * doubleRotateLeft (Node *p) noexcept
 
static Node * doubleRotateRight (Node *p) noexcept
 
static Rotation_Type rotation_type (Node *p) noexcept
 
static Node * restore_avl (Node *p, Node *pp) noexcept
 
static size_t avl_height (Node *p) noexcept
 
static Node * extract_min (Node *&p) noexcept
 
static Node * extract_max (Node *&p) noexcept
 
static Node * join_exclusive_rec (Node *t1, size_t h1, Node *t2, size_t h2) noexcept
 
static Node * join_with_pivot (Node *t1, const size_t h1, Node *pivot, Node *t2, const size_t h2) noexcept
 
static Node * join_right (Node *t1, const size_t h1, Node *pivot, Node *t2, const size_t h2) noexcept
 
static Node * join_left (Node *t1, const size_t h1, Node *pivot, Node *t2, const size_t h2) noexcept
 

Private Attributes

FixedStack< Node * > avl_stack
 The type of node.
 
Node head_node
 
Node * head_ptr
 
Node *& root
 
Compare cmp
 

Detailed Description

template<template< typename > class NodeType, typename Key, class Compare>
requires StrictWeakOrder<Compare, Key>
class Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >

AVL balanced binary search tree with rank (order statistics).

An AVL tree is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one. This guarantees O(log n) worst-case time complexity for search, insertion, and deletion operations.

The maximum height of an AVL tree with n nodes is bounded by: \( 1.4404 \lg{(n + 2)} - 0.3277 \)

This extended version maintains a count in each node representing the number of nodes in its subtree, enabling O(log n) operations for selecting by position and finding the position of a key.

Template Parameters
NodeTypeTemplate for the node type (typically AvlNodeRk).
KeyThe type of keys stored in the tree.
CompareComparison functor for ordering keys.
Complexity:
  • Search: O(log n) worst case
  • Insert: O(log n) worst case
  • Delete: O(log n) worst case
  • Select: O(log n) worst case
  • Position: O(log n) worst case
  • Space: O(n)
Example:
Avl_Tree_Rk<int> tree;
tree.insert(new Avl_Tree_Rk<int>::Node(42));
tree.insert(new Avl_Tree_Rk<int>::Node(17));
auto node = tree.select(0); // Get smallest element
auto [pos, found] = tree.position(42); // Get position of key 42
Aleph::Gen_Avl_Tree_Rk::insert
Node * insert(Node *p) noexcept
Insert the node pointed by p in the tree.
Definition tpl_avlRk.H:588
Aleph::Gen_Avl_Tree_Rk::Node
NodeType< Key > Node
Definition tpl_avlRk.H:115
Aleph::Gen_Avl_Tree_Rk::select
Node * select(const size_t i) const
Return the i-th node in order sense.
Definition tpl_avlRk.H:723
Aleph::Gen_Avl_Tree_Rk::position
std::pair< long, Node * > position(const Key &key) const noexcept
Compute the inorder position of a key.
Definition tpl_avlRk.H:734
Aleph::Avl_Tree_Rk
AVL binary search tree with nodes without virtual destructor and with subtree counters for select/pos...
Definition tpl_avlRk.H:1445
Note
This is a low-level implementation that manages raw nodes. For automatic memory management, use DynSetAvlTreeRk instead.
See also
Avl_Tree_Rk Convenient typedef with default node type.
Avl_Tree_Rk_Vtl Version with virtual destructor nodes.
tpl_avl.H Base AVL tree without rank operations.

Definition at line 112 of file tpl_avlRk.H.

Member Typedef Documentation

◆ key_type

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

Definition at line 535 of file tpl_avlRk.H.

◆ Node

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

Definition at line 115 of file tpl_avlRk.H.

Member Enumeration Documentation

◆ Rotation_Type

template<template< typename > class NodeType, typename Key , class Compare >
enum Aleph::Gen_Avl_Tree_Rk::Rotation_Type
private
Enumerator
ROTATE_LEFT 
ROTATE_RIGHT 
DOUBLE_ROTATE_LEFT 
DOUBLE_ROTATE_RIGHT 

Definition at line 353 of file tpl_avlRk.H.

Constructor & Destructor Documentation

◆ Gen_Avl_Tree_Rk()

template<template< typename > class NodeType, typename Key , class Compare >
Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Gen_Avl_Tree_Rk ( Compare  cmf_fct = Compare())
inlinenoexcept

Definition at line 543 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, and Aleph::FixedStack< T >::push().

◆ ~Gen_Avl_Tree_Rk()

template<template< typename > class NodeType, typename Key , class Compare >
virtual Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::~Gen_Avl_Tree_Rk ( )
inlinevirtualnoexcept

Definition at line 561 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base(), and Aleph::divide_and_conquer_partition_dp().

Member Function Documentation

◆ avl_height()

template<template< typename > class NodeType, typename Key , class Compare >
static size_t Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 767 of file tpl_avlRk.H.

References DIFF, h, LLINK, and RLINK.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

◆ avl_stack_at_base()

template<template< typename > class NodeType, typename Key , class Compare >
bool Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base ( )
inlineprivatenoexcept

Definition at line 124 of file tpl_avlRk.H.

References Aleph::and, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::FixedStack< T >::base(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, Aleph::FixedStack< T >::is_empty(), and Aleph::FixedStack< T >::size().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::~Gen_Avl_Tree_Rk(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl().

◆ clean_avl_stack()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack ( )
inlineprivatenoexcept

Definition at line 131 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::FixedStack< T >::base(), Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, Aleph::FixedStack< T >::is_empty(), Aleph::FixedStack< T >::popn(), Aleph::FixedStack< T >::push(), and Aleph::FixedStack< T >::size().

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

◆ doubleRotateLeft()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 275 of file tpl_avlRk.H.

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

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

◆ doubleRotateRight()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 315 of file tpl_avlRk.H.

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

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

◆ extract_max()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max ( Node *&  p)
inlinestaticprivatenoexcept

Definition at line 840 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec().

◆ extract_min()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min ( Node *&  p)
inlinestaticprivatenoexcept

Definition at line 784 of file tpl_avlRk.H.

References Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec().

◆ find_position()

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

Find the inorder position of a key in the tree.

Parameters
[in]keyto be searched
Returns
a pair with the position and the node pointer

Definition at line 749 of file tpl_avlRk.H.

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

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

◆ get_compare()

template<template< typename > class NodeType, typename Key , class Compare >
constexpr Compare & Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::get_compare ( )
inlineconstexprnoexcept

Definition at line 541 of file tpl_avlRk.H.

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

◆ getRoot() [1/2]

template<template< typename > class NodeType, typename Key , class Compare >
constexpr Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot ( ) const
inlineconstexprnoexcept

Return a pointer to the tree's root.

Definition at line 567 of file tpl_avlRk.H.

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

◆ getRoot() [2/2]

template<template< typename > class NodeType, typename Key , class Compare >
constexpr Node *& Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot ( )
inlineconstexprnoexcept

Return a modifiable reference to tree's root.

Definition at line 564 of file tpl_avlRk.H.

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

Referenced by TEST().

◆ insert()

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

Insert the node pointed by p in the tree.

Parameters
[in]pthe node to be inserted
Returns
p if KEY(p) is not found in the tree, nullptr otherwise.

Definition at line 588 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

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

◆ insert_dup()

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

Insert the node p without testing for key duplicity.

Definition at line 642 of file tpl_avlRk.H.

References Aleph::CmpEqual, Aleph::CmpLess, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by TEST(), and TEST().

◆ is_empty()

template<template< typename > class NodeType, typename Key , class Compare >
constexpr bool Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty ( ) const
inlineconstexprnoexcept

Return true if tree is empty.

Definition at line 573 of file tpl_avlRk.H.

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

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

◆ join_exclusive()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive ( Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t)
inlinenoexcept

Join this tree exclusively with another tree.

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

Parameters
[in,out]ttree to join with (will be empty after)
Note
O(m log(n+m)) time complexity where m is size of t

Definition at line 1217 of file tpl_avlRk.H.

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

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

◆ join_exclusive_rec()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec ( Node *  t1,
size_t  h1,
Node *  t2,
size_t  h2 
)
inlinestaticprivatenoexcept

Definition at line 894 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot().

◆ join_left()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left ( Node *  t1,
const size_t  h1,
Node *  pivot,
Node *  t2,
const size_t  h2 
)
inlinestaticprivatenoexcept

Definition at line 1003 of file tpl_avlRk.H.

References Aleph::and, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot().

◆ join_right()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right ( Node *  t1,
const size_t  h1,
Node *  pivot,
Node *  t2,
const size_t  h2 
)
inlinestaticprivatenoexcept

Definition at line 950 of file tpl_avlRk.H.

References Aleph::and, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot().

◆ join_with_pivot()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot ( Node *  t1,
const size_t  h1,
Node *  pivot,
Node *  t2,
const size_t  h2 
)
inlinestaticprivatenoexcept

Definition at line 925 of file tpl_avlRk.H.

References Aleph::and, Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), LLINK, and RLINK.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

◆ key_comp()

template<template< typename > class NodeType, typename Key , class Compare >
Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::key_comp ( )
inlineconstexprnoexcept

The key type.

Return a reference to the comparison criteria

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 538 of file tpl_avlRk.H.

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

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

◆ position()

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

Compute the inorder position of a key.

Parameters
[in]keyto be searched
Returns
a pair with the inorder position and the node pointer. If the key is not found, the position is -1.

Definition at line 734 of file tpl_avlRk.H.

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

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

◆ remove()

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

Remove from tree the node containing key.

Returns the removed node if the key is found; nullptr otherwise.

Definition at line 662 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::CmpEqual, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr, LLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor(), Aleph::FixedStack< T >::top(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion().

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

◆ restore_avl()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl ( Node *  p,
Node *  pp 
)
inlinestaticprivatenoexcept

Definition at line 378 of file tpl_avlRk.H.

References AH_ERROR, DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_LEFT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_RIGHT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateLeft(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::doubleRotateRight(), LLINK, RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_LEFT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_RIGHT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotation_type().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion().

◆ restore_avl_after_deletion()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion ( bool  left_deficit)
inlineprivatenoexcept

Definition at line 490 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), DIFF, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::popn(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

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

◆ restore_avl_after_insertion()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion ( Node *  p)
inlineprivatenoexcept

Definition at line 398 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), DIFF, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::FixedStack< T >::pop(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

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

◆ rotateLeft()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateLeft ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 225 of file tpl_avlRk.H.

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

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_min(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_right(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

◆ rotateRight()

template<template< typename > class NodeType, typename Key , class Compare >
static Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotateRight ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 250 of file tpl_avlRk.H.

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

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::extract_max(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_left(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

◆ rotation_type()

template<template< typename > class NodeType, typename Key , class Compare >
static Rotation_Type Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::rotation_type ( Node *  p)
inlinestaticprivatenoexcept

Definition at line 358 of file tpl_avlRk.H.

References DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_LEFT, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::DOUBLE_ROTATE_RIGHT, LLINK, RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_LEFT, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::ROTATE_RIGHT.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl().

◆ search()

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

Search a node containing key; if found, then a pointer to the node containing it is returned; otherwise nullptr is returned.

Definition at line 577 of file tpl_avlRk.H.

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

Referenced by TEST().

◆ search_and_stack_avl()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl ( const Key &  key,
signed char &  cmp_result 
)
inlineprivatenoexcept

Definition at line 150 of file tpl_avlRk.H.

References Aleph::and, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::FixedStack< T >::popn(), Aleph::FixedStack< T >::push(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::FixedStack< T >::size(), and Aleph::FixedStack< T >::top().

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

◆ search_dup_and_stack_avl()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl ( const Key &  key,
signed char &  cmp_result 
)
inlineprivatenoexcept

Definition at line 196 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::FixedStack< T >::push(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::FixedStack< T >::top().

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

◆ search_or_insert()

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

Search or insert a key.

Parameters
[in]pthe node whose key must be searched and eventually inserted
Returns
if p is inserted, this value is returned; otherwise, a pointer to the node containing KEY(p) is returned.

Definition at line 618 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::CmpEqual, Aleph::CmpGreater, Aleph::CmpLess, Aleph::divide_and_conquer_partition_dp(), KEY, LLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

Referenced by TEST().

◆ select()

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

Return the i-th node in order sense.

Parameters
[in]iinorder position of node to be selected
Returns
a pointer to the i-th node inorder sense
Exceptions
out_of_rangeif i is greater or equal than the number of nodes of tree

Definition at line 723 of file tpl_avlRk.H.

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

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

◆ size()

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

Return the number of nodes in the tree.

Definition at line 570 of file tpl_avlRk.H.

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

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

◆ split_key()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key ( const Key &  key,
Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t1,
Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t2 
)
inlinenoexcept

Split tree by key.

After the operation:

  • t1 contains all keys < key
  • t2 contains all keys > key
  • This tree becomes empty
Parameters
[in]keythe splitting key
[out]t1tree to receive keys < key
[out]t2tree to receive keys > key
Returns
pointer to node containing key, or nullptr if not found
Note
O(n) time complexity (simple iterative implementation)

Definition at line 1267 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), KEY, LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST(), and TEST().

◆ split_key_dup()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup ( const Key &  key,
Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t1,
Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  t2 
)
inlinenoexcept

Split tree by key including duplicates.

After the operation:

  • t1 contains all keys <= key
  • t2 contains all keys > key
  • This tree becomes empty
Parameters
[in]keythe splitting key
[out]t1tree to receive keys <= key
[out]t2tree to receive keys > key
Note
O(n) time complexity (simple iterative implementation)

Definition at line 1317 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), KEY, LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

Referenced by TEST().

◆ split_key_dup_rec()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec ( Node *  p,
const Key &  key,
Node *&  t1,
Node *&  t2 
)
inlineprivatenoexcept

Definition at line 1115 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), KEY, LLINK, RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec().

◆ split_key_rec()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec ( Node *  p,
const Key &  key,
Node *&  t1,
Node *&  t2 
)
inlineprivatenoexcept

Definition at line 1054 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp, Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), KEY, LLINK, RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec().

◆ split_pos()

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

Split tree by inorder position.

After the operation:

  • t1 contains nodes at positions [0, pos)
  • t2 contains nodes at positions [pos, size)
  • This tree becomes empty
Parameters
[in]posthe splitting position (0-based)
[out]t1tree to receive positions [0, pos)
[out]t2tree to receive positions [pos, size)
Note
O(n) time complexity (simple iterative implementation)

Definition at line 1361 of file tpl_avlRk.H.

References Aleph::count(), Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::FixedStack< T >::is_empty(), LLINK, Aleph::FixedStack< T >::pop(), Aleph::FixedStack< T >::push(), RLINK, Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size().

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

◆ split_pos_rec()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec ( Node *  p,
size_t  pos,
Node *&  t1,
Node *&  t2 
)
inlineprivatenoexcept

Definition at line 1162 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_height(), Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_with_pivot(), LLINK, RLINK, and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos_rec().

◆ swap()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swap ( Gen_Avl_Tree_Rk< NodeType, Key, Compare > &  tree)
inlinenoexcept

Swap in constant time all the items of this with the items of tree.

Parameters
[in]treethe tree to swap with this

Definition at line 555 of file tpl_avlRk.H.

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

◆ swapWithSuccessor()

template<template< typename > class NodeType, typename Key , class Compare >
Node * Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor ( Node *  p,
Node *&  pp 
)
inlineprivatenoexcept

Definition at line 439 of file tpl_avlRk.H.

References Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack, Aleph::COUNT(), DIFF, Aleph::divide_and_conquer_partition_dp(), LLINK, Aleph::FixedStack< T >::push(), RLINK, and Aleph::FixedStack< T >::top().

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

◆ update_counters_after_deletion()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion ( )
inlineprivatenoexcept

Definition at line 527 of file tpl_avlRk.H.

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

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

◆ update_counters_after_insertion()

template<template< typename > class NodeType, typename Key , class Compare >
void Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion ( )
inlineprivatenoexcept

Definition at line 517 of file tpl_avlRk.H.

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

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

◆ verify()

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

Return true if the tree is a valid AVL tree with correct counters.

Definition at line 760 of file tpl_avlRk.H.

References Aleph::and, Aleph::check_rank_tree(), Aleph::is_avl_rk(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::root.

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

Member Data Documentation

◆ avl_stack

template<template< typename > class NodeType, typename Key , class Compare >
FixedStack<Node *> Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack
private

The type of node.

Definition at line 118 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Gen_Avl_Tree_Rk(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_insertion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swapWithSuccessor(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_deletion(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::update_counters_after_insertion().

◆ cmp

template<template< typename > class NodeType, typename Key , class Compare >
Compare Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::cmp
private

Definition at line 122 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::key_comp(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup_rec(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_rec(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swap().

◆ head_node

template<template< typename > class NodeType, typename Key , class Compare >
Node Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_node
private

Definition at line 119 of file tpl_avlRk.H.

◆ head_ptr

template<template< typename > class NodeType, typename Key , class Compare >
Node* Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::head_ptr
private

Definition at line 120 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::Gen_Avl_Tree_Rk(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::avl_stack_at_base(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::clean_avl_stack(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove().

◆ root

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

Definition at line 121 of file tpl_avlRk.H.

Referenced by Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::find_position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::getRoot(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::insert_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::is_empty(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::join_exclusive(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::position(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::remove(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::restore_avl_after_deletion(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_dup_and_stack_avl(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::search_or_insert(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::select(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::size(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_key_dup(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::split_pos(), Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::swap(), and Aleph::Gen_Avl_Tree_Rk< NodeType, Key, Compare >::verify().

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