Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree > Class Template Reference

Generic B+ Tree with configurable minimum degree. More...

#include <tpl_bplus_tree.H>

Collaboration diagram for Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >:

Classes
class	Iterator
	Lazy iterator over ordered leaf keys. More...

Public Types
using	key_type = Key
	Stored key type.

Public Member Functions
	Gen_BPlus_Tree (const Compare &cmp=Compare())
	Construct an empty B+ Tree.
template<std::input_iterator It>
	Gen_BPlus_Tree (It first, It last, const Compare &cmp=Compare())
	Construct a B+ Tree from an iterator range.
	Gen_BPlus_Tree (std::initializer_list< Key > init, const Compare &cmp=Compare())
	Construct a B+ Tree from an initializer list.
	Gen_BPlus_Tree (const Gen_BPlus_Tree &other)
	Copy constructor performing a deep copy.
	Gen_BPlus_Tree (Gen_BPlus_Tree &&other)=default
	Move constructor.
Gen_BPlus_Tree &	operator= (const Gen_BPlus_Tree &other)
	Copy assignment.
Gen_BPlus_Tree &	operator= (Gen_BPlus_Tree &&other)=default
	Move assignment.
const Compare &	key_comp () const noexcept
	Return the comparison object (read-only).
const Compare &	get_compare () const noexcept
	Return the comparison object (read-only).
bool	empty () const noexcept
	Return whether the tree has no keys.
bool	is_empty () const noexcept
	Synonym for empty() in traditional Aleph style.
size_t	size () const noexcept
	Return the number of stored keys.
size_t	height () const noexcept
	Return the current tree height.
void	clear () noexcept
	Remove every key from the tree.
bool	contains (const Key &key) const
	Return whether a key is present.
bool	search (const Key &key) const
	Synonym for contains().
bool	insert (const Key &key)
	Insert a key if it is not already present.
bool	insert (Key &&key)
	Insert a key by move if it is not already present.
bool	remove (const Key &key)
	Remove a key if present.
std::optional< Key >	min_key () const
	Return the minimum key, if any.
std::optional< Key >	max_key () const
	Return the maximum key, if any.
std::optional< Key >	lower_bound (const Key &key) const
	Return the first key not less than key.
std::optional< Key >	upper_bound (const Key &key) const
	Return the first key strictly greater than key.
Iterator	get_it () const noexcept
	Return a lazy iterator over the full key order.
Iterator	get_range_it (const Key &first, const Key &last) const
	Return a lazy iterator over an inclusive key range.
Array< Key >	range (const Key &first, const Key &last) const
	Collect all keys in the inclusive range [first, last].
Array< Key >	keys () const
	Materialize the tree contents in sorted order.
bool	verify () const
	Verify structural B+ Tree invariants.

Private Types
using	Node = detail::BPlusTreeNode< Key >

Private Member Functions
size_t	lower_bound_index (const Array< Key > &keys, const Key &key) const
size_t	upper_bound_index (const Array< Key > &keys, const Key &key) const
size_t	child_index (const Node *node, const Key &key) const
bool	equals (const Key &lhs, const Key &rhs) const
bool	strictly_sorted (const Array< Key > &keys) const
template<std::input_iterator It>
void	insert_range (It first, It last)
const Node *	leftmost_leaf (const Node *node) const noexcept
const Node *	rightmost_leaf (const Node *node) const noexcept
const Key *	subtree_min_ptr (const Node *node) const noexcept
const Key *	subtree_max_ptr (const Node *node) const noexcept
const Key &	subtree_min (const Node *node) const
size_t	height_of (const Node *node) const noexcept
void	rebuild_separators (Node *node) const
std::unique_ptr< Node >	clone_node (const Node *node, Node *&prev_leaf) const
const Node *	find_leaf (const Key &key) const
bool	contains_in (const Node *node, const Key &key) const
void	split_child (Node *parent, const size_t idx)
void	insert_nonfull (Node *node, const Key &key)
void	borrow_from_prev (Node *parent, const size_t idx)
void	borrow_from_next (Node *parent, const size_t idx)
void	merge_children (Node *parent, const size_t left_idx)
void	fix_underflow (Node *parent, const size_t idx)
bool	remove_from (Node *node, const Key &key)
bool	verify_leaf_chain () const
bool	verify_node (const Node *node, const std::optional< Key > &min_key, const std::optional< Key > &max_key, const size_t depth, size_t &leaf_depth, size_t &counted) const

Static Private Member Functions
template<typename T , typename U >
static void	insert_at (Array< T > &array, const size_t idx, U &&value)
template<typename T >
static T	erase_at (Array< T > &array, const size_t idx)
template<typename T >
static void	truncate (Array< T > &array, const size_t new_size)
template<typename T >
static void	append_copy_range (Array< T > &dst, const Array< T > &src, const size_t from)
template<typename T >
static void	append_move_range (Array< T > &dst, Array< T > &src, const size_t from)

Private Attributes
std::unique_ptr< Node >	root_
size_t	size_ = 0
Compare	cmp_

Static Private Attributes
static constexpr size_t	MaxKeys = 2 * MinDegree - 1
static constexpr size_t	MinKeys = MinDegree - 1

Detailed Description

template<typename Key, class Compare = Aleph::less<Key>, size_t MinDegree = 16>
requires StrictWeakOrder<Compare, Key>
class Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >

Generic B+ Tree with configurable minimum degree.

Gen_BPlus_Tree models an ordered set of unique keys. All payload keys are stored in leaves, while internal nodes keep only separator keys. This organization is specially convenient for page-oriented indexes, database style range scans, and any workload where ordered iteration matters as much as point lookups.

Template Parameters

Key	Key type stored in the tree.
Compare	Strict weak ordering used to sort keys.
MinDegree	Minimum degree t of the B+ Tree. Valid values are t >= 2.

Complexity

• Search: O(log n)
• Insert: O(log n)
• Remove: O(log n)
• lower_bound()/upper_bound(): O(log n)
• range(): O(log n + k), where k is the number of reported keys
• keys(): O(n)
• get_range_it(): O(log n) setup, then O(1) amortized per increment

Example

BPlus_Tree<int> tree = {40, 10, 90, 30, 50, 70};
 
auto hit = tree.lower_bound(45);   // 50
auto band = tree.range(25, 70);    // 30, 40, 50, 70
 
tree.remove(40);
auto ordered = tree.keys();

Note

This tree stores unique keys. Duplicate inserts return false.

For a classic B-Tree where internal nodes also store user keys, see Aleph::B_Tree.

Thread Safety

Instances are not synchronized. Concurrent access to the same tree requires external synchronization.

Exception Safety

Read-only operations do not allocate, except when materializing returned Array<Key> results. Mutating operations preserve leaf links and search invariants if Compare and Key operations do not throw in the middle of internal node updates; allocation failures propagate as std::bad_alloc.

Definition at line 134 of file tpl_bplus_tree.H.

Member Typedef Documentation

key_type

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

using Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::key_type = Key

Stored key type.

Definition at line 598 of file tpl_bplus_tree.H.

Node

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

using Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Node = detail::BPlusTreeNode<Key>

private

Definition at line 139 of file tpl_bplus_tree.H.

Constructor & Destructor Documentation

Gen_BPlus_Tree() [1/5]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree ( const Compare &  cmp = Compare() )

inlineexplicit

Construct an empty B+ Tree.

Parameters

cmp	Comparison functor used to sort keys.

Exceptions

Nothing.

Definition at line 730 of file tpl_bplus_tree.H.

Gen_BPlus_Tree() [2/5]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<std::input_iterator It>

Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree ( It  first, It  last, const Compare &  cmp = Compare()  )

inline

Construct a B+ Tree from an iterator range.

Parameters

first	First element to insert.
last	One-past-the-end iterator.
cmp	Comparison functor used to sort keys.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 738 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_range().

Gen_BPlus_Tree() [3/5]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree ( std::initializer_list< Key >  init, const Compare &  cmp = Compare()  )

inline

Construct a B+ Tree from an initializer list.

Parameters

init	Keys to insert.
cmp	Comparison functor used to sort keys.

Exceptions

std::bad_alloc

if internal storage allocation fails.

Definition at line 748 of file tpl_bplus_tree.H.

Gen_BPlus_Tree() [4/5]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree ( const Gen_BPlus_Tree< Key, Compare, MinDegree > &  other )

inline

Copy constructor performing a deep copy.

Parameters

other

Tree to copy.

Exceptions

std::bad_alloc

if cloning internal nodes fails.

Definition at line 756 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clone_node(), Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_.

Gen_BPlus_Tree() [5/5]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree ( Gen_BPlus_Tree< Key, Compare, MinDegree > &&  other )

default

Move constructor.

Parameters

other

Tree to move from.

Member Function Documentation

append_copy_range()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<typename T >

static void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::append_copy_range ( Array< T > &  dst, const Array< T > &  src, const size_t  from  )

inlinestaticprivate

Definition at line 220 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::merge_children(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

append_move_range()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<typename T >

static void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::append_move_range ( Array< T > &  dst, Array< T > &  src, const size_t  from  )

inlinestaticprivate

Definition at line 227 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::merge_children(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

borrow_from_next()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_next ( Node *  parent, const size_t  idx  )

inlineprivate

Definition at line 407 of file tpl_bplus_tree.H.

References Aleph::Array< T >::append(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::erase_at(), Aleph::Array< T >::get_first(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow().

borrow_from_prev()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_prev ( Node *  parent, const size_t  idx  )

inlineprivate

Definition at line 386 of file tpl_bplus_tree.H.

References Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators(), and Aleph::Array< T >::remove_last().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow().

child_index()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::child_index ( const Node *  node, const Key &  key  ) const

inlineprivate

Definition at line 164 of file tpl_bplus_tree.H.

References Aleph::detail::BPlusTreeNode< Key >::keys, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound_index().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from().

clear()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clear ( )

inlinenoexcept

Remove every key from the tree.

Exceptions

Nothing.

Definition at line 850 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

clone_node()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

std::unique_ptr< Node > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clone_node ( const Node *  node, Node *&  prev_leaf  ) const

inlineprivate

Definition at line 297 of file tpl_bplus_tree.H.

References Aleph::detail::BPlusTreeNode< Key >::children, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clone_node(), Aleph::copy(), Aleph::divide_and_conquer_partition_dp(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators(), and Aleph::Array< T >::reserve().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clone_node().

contains()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains ( const Key &  key ) const

inline

Return whether a key is present.

Parameters

key	Key to search.

Returns

true if the key exists, otherwise false.

Exceptions

Any	exception propagated by Compare.

Definition at line 861 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains_in(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::search().

contains_in()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains_in ( const Node *  node, const Key &  key  ) const

inlineprivate

Definition at line 328 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::equals(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains().

empty()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::empty ( ) const

inlinenoexcept

Return whether the tree has no keys.

Returns

true if empty, otherwise false.

Exceptions

Nothing.

Definition at line 815 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::is_empty().

equals()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::equals ( const Key &  lhs, const Key &  rhs  ) const

inlineprivate

Definition at line 169 of file tpl_bplus_tree.H.

References Aleph::detail::bplus_equiv(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, and Aleph::divide_and_conquer_partition_dp().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains_in(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound_index(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

erase_at()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<typename T >

static T Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::erase_at ( Array< T > &  array, const size_t  idx  )

inlinestaticprivate

Definition at line 202 of file tpl_bplus_tree.H.

References Aleph::close_gap(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::remove_last(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::merge_children(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from().

find_leaf()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Node * Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf ( const Key &  key ) const

inlineprivate

Definition at line 320 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::child_index(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::detail::BPlusTreeNode< Key >::leaf, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::Iterator(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains_in(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound().

fix_underflow()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow ( Node *  parent, const size_t  idx  )

inlineprivate

Definition at line 448 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::merge_children(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MinKeys, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from().

get_compare()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Compare & Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::get_compare ( ) const

inlinenoexcept

Return the comparison object (read-only).

Returns

Constant reference to the comparison functor.

Note

Alias for key_comp(). Immutable after construction.

Exceptions

Nothing.

Definition at line 806 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::key_comp().

get_it()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Iterator Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::get_it ( ) const

inlinenoexcept

Return a lazy iterator over the full key order.

Returns

Iterator positioned at the first key, or exhausted if empty.

Exceptions

Nothing.

Definition at line 1020 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys().

get_range_it()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Iterator Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::get_range_it ( const Key &  first, const Key &  last  ) const

inline

Return a lazy iterator over an inclusive key range.

Parameters

first	Lower endpoint, inclusive.
last	Upper endpoint, inclusive.

Returns

Iterator positioned at the first key in the range.

Exceptions

std::invalid_argument	if last < first according to Compare.
Any	exception propagated by Compare.

Definition at line 1032 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::range().

height()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height ( ) const

inlinenoexcept

Return the current tree height.

Returns

0 for an empty tree, otherwise the number of node levels.

Exceptions

Nothing.

Definition at line 842 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height_of(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height_of().

height_of()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height_of ( const Node *  node ) const

inlineprivatenoexcept

Definition at line 273 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height().

insert() [1/2]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert ( const Key &  key )

inline

Insert a key if it is not already present.

Parameters

key	Key to insert.

Returns

true if insertion happened, false if it was duplicate.

Exceptions

std::bad_alloc	if node growth fails.
Any	exception propagated by Compare or Key copy/move operations.

Definition at line 883 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains(), Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MaxKeys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_range().

insert() [2/2]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert ( Key &&  key )

inline

Insert a key by move if it is not already present.

Parameters

key	Key to insert.

Returns

true if insertion happened, false if it was duplicate.

Exceptions

std::bad_alloc	if node growth fails.
Any	exception propagated by Compare or Key move/copy operations.

Definition at line 916 of file tpl_bplus_tree.H.

References Aleph::copy(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert().

insert_at()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<typename T , typename U >

static void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_at ( Array< T > &  array, const size_t  idx, U &&  value  )

inlinestaticprivate

Definition at line 188 of file tpl_bplus_tree.H.

References Aleph::Array< T >::append(), Aleph::open_gap(), Aleph::Array< T >::putn(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

insert_nonfull()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull ( Node *  node, const Key &  key  )

inlineprivate

Definition at line 366 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::child_index(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MaxKeys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull().

insert_range()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<std::input_iterator It>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_range ( It  first, It  last  )

inlineprivate

Definition at line 182 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree().

is_empty()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::is_empty ( ) const

inlinenoexcept

Synonym for empty() in traditional Aleph style.

Returns

true if empty, otherwise false.

Exceptions

Nothing.

Definition at line 824 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::empty().

key_comp()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Compare & Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::key_comp ( ) const

inlinenoexcept

Return the comparison object (read-only).

Returns

Constant reference to the comparison functor.

Note

The comparator is immutable after construction to preserve tree order.

Exceptions

Nothing.

Definition at line 796 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::get_compare().

keys()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Array< Key > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys ( ) const

inline

Materialize the tree contents in sorted order.

Returns

Ordered array containing every stored key.

Exceptions

std::bad_alloc	if the result array cannot grow.
Any	exception propagated by Key copy construction.

Definition at line 1060 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::get_it(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::has_curr(), Aleph::Array< T >::reserve(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::strictly_sorted(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound_index(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

leftmost_leaf()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Node * Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::leftmost_leaf ( const Node *  node ) const

inlineprivatenoexcept

Definition at line 234 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), and Aleph::detail::BPlusTreeNode< Key >::leaf.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min_ptr(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain().

lower_bound()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

std::optional< Key > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound ( const Key &  key ) const

inline

Return the first key not less than key.

Parameters

key	Probe key.

Returns

Matching lower bound or std::nullopt if none exists.

Exceptions

Any	exception propagated by Compare or Key copy construction.

Definition at line 975 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::detail::BPlusTreeNode< Key >::next, and Aleph::Array< T >::size().

lower_bound_index()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index ( const Array< Key > &  keys, const Key &  key  ) const

inlineprivate

Definition at line 148 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::Iterator(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains_in(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from().

max_key()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

std::optional< Key > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::max_key ( ) const

inline

Return the maximum key, if any.

Returns

Largest key in the tree or std::nullopt if empty.

Exceptions

Any	exception propagated by Key copy construction.

Definition at line 962 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_max_ptr().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

merge_children()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::merge_children ( Node *  parent, const size_t  left_idx  )

inlineprivate

Definition at line 428 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::append_copy_range(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::append_move_range(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::erase_at(), GenericItems< Container, T >::keys(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::detail::BPlusTreeNode< Key >::next, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow().

min_key()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

std::optional< Key > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::min_key ( ) const

inline

Return the minimum key, if any.

Returns

Smallest key in the tree or std::nullopt if empty.

Exceptions

Any	exception propagated by Key copy construction.

Definition at line 950 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min_ptr().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

operator=() [1/2]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Gen_BPlus_Tree & Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::operator= ( const Gen_BPlus_Tree< Key, Compare, MinDegree > &  other )

inline

Copy assignment.

Parameters

other

Tree to copy from.

Returns

*this.

Definition at line 771 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

operator=() [2/2]

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Gen_BPlus_Tree & Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::operator= ( Gen_BPlus_Tree< Key, Compare, MinDegree > &&  other )

default

Move assignment.

Parameters

other

Tree to move from.

Returns

*this.

range()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Array< Key > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::range ( const Key &  first, const Key &  last  ) const

inline

Collect all keys in the inclusive range [first, last].

Parameters

first	Lower endpoint, inclusive.
last	Upper endpoint, inclusive.

Returns

Ordered array with every key in the requested range.

Exceptions

std::invalid_argument	if last < first according to Compare.
std::bad_alloc	if the result array cannot grow.
Any	exception propagated by Compare or Key copy construction.

Definition at line 1045 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::get_range_it(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::has_curr(), and Aleph::Array< T >::reserve().

rebuild_separators()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators ( Node *  node ) const

inlineprivate

Definition at line 286 of file tpl_bplus_tree.H.

References Aleph::Array< T >::append(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::empty(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Array< T >::reserve(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clone_node(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::merge_children(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

remove()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove ( const Key &  key )

inline

Remove a key if present.

Parameters

key	Key to erase.

Returns

true if the key was removed, otherwise false.

Exceptions

Any	exception propagated by Compare or Key assignments.

Definition at line 927 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

remove_from()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from ( Node *  node, const Key &  key  )

inlineprivate

Definition at line 474 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::child_index(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::equals(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::erase_at(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove_from().

rightmost_leaf()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Node * Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rightmost_leaf ( const Node *  node ) const

inlineprivatenoexcept

Definition at line 242 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), and Aleph::detail::BPlusTreeNode< Key >::leaf.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_max_ptr().

search()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::search ( const Key &  key ) const

inline

Synonym for contains().

Parameters

key	Key to search.

Returns

true if the key exists, otherwise false.

Exceptions

Any	exception propagated by Compare.

Definition at line 871 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains().

size()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size ( ) const

inlinenoexcept

Return the number of stored keys.

Returns

Number of unique keys stored in the tree.

Exceptions

Nothing.

Definition at line 833 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

split_child()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child ( Node *  parent, const size_t  idx  )

inlineprivate

Definition at line 341 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::append_copy_range(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::append_move_range(), Aleph::detail::BPlusTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MinKeys, Aleph::detail::BPlusTreeNode< Key >::next, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::truncate().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull().

strictly_sorted()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::strictly_sorted ( const Array< Key > &  keys ) const

inlineprivate

Definition at line 174 of file tpl_bplus_tree.H.

References Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

subtree_max_ptr()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Key * Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_max_ptr ( const Node *  node ) const

inlineprivatenoexcept

Definition at line 258 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::Array< T >::is_empty(), Aleph::detail::BPlusTreeNode< Key >::keys, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rightmost_leaf().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::max_key(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

subtree_min()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Key & Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min ( const Node *  node ) const

inlineprivate

Definition at line 266 of file tpl_bplus_tree.H.

References ah_runtime_error_unless, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min_ptr().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators().

subtree_min_ptr()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

const Key * Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min_ptr ( const Node *  node ) const

inlineprivatenoexcept

Definition at line 250 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_first(), Aleph::Array< T >::is_empty(), Aleph::detail::BPlusTreeNode< Key >::keys, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::leftmost_leaf().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::min_key(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

truncate()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

template<typename T >

static void Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::truncate ( Array< T > &  array, const size_t  new_size  )

inlinestaticprivate

Definition at line 214 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::remove_last(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child().

upper_bound()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

std::optional< Key > Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound ( const Key &  key ) const

inline

Return the first key strictly greater than key.

Parameters

key	Probe key.

Returns

Matching upper bound or std::nullopt if none exists.

Exceptions

Any	exception propagated by Compare or Key copy construction.

Definition at line 998 of file tpl_bplus_tree.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), Aleph::detail::BPlusTreeNode< Key >::next, Aleph::Array< T >::size(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound_index().

upper_bound_index()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound_index ( const Array< Key > &  keys, const Key &  key  ) const

inlineprivate

Definition at line 156 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::equals(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), and Aleph::Array< T >::size().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::child_index(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound().

verify()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify ( ) const

inline

Verify structural B+ Tree invariants.

Returns

true if the tree is structurally valid, otherwise false.

Exceptions

Any	exception propagated by Compare.

Definition at line 1074 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

verify_leaf_chain()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain ( ) const

inlineprivate

Definition at line 495 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_first(), Aleph::Array< T >::get_last(), Aleph::Array< T >::is_empty(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::leftmost_leaf(), Aleph::detail::BPlusTreeNode< Key >::next, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify().

verify_node()

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

bool Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node ( const Node *  node, const std::optional< Key > &  min_key, const std::optional< Key > &  max_key, const size_t  depth, size_t &  leaf_depth, size_t &  counted  ) const

inlineprivate

Definition at line 528 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::detail::BPlusTreeNode< Key >::children, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::equals(), Aleph::Array< T >::get_first(), Aleph::Array< T >::get_last(), Aleph::Array< T >::is_empty(), Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), Aleph::detail::BPlusTreeNode< Key >::leaf, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::max_key(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MaxKeys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::min_key(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MinKeys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_, Aleph::Array< T >::size(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::strictly_sorted(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_max_ptr(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min_ptr(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

Member Data Documentation

cmp_

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

Compare Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_

private

Definition at line 146 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::Iterator(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::equals(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::key_comp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::operator=(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::skip_past_end(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::strictly_sorted(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::upper_bound_index(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

MaxKeys

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

constexpr size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MaxKeys = 2 * MinDegree - 1

staticconstexprprivate

Definition at line 141 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_nonfull(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

MinKeys

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

constexpr size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::MinKeys = MinDegree - 1

staticconstexprprivate

Definition at line 142 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::fix_underflow(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::split_child(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

root_

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

std::unique_ptr<Node> Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::root_

private

Definition at line 144 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Gen_BPlus_Tree(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clear(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::contains(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::height(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::max_key(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::min_key(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::operator=(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

size_

template<typename Key , class Compare = Aleph::less<Key>, size_t MinDegree = 16>

size_t Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size_ = 0

private

Definition at line 145 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::clear(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::empty(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::operator=(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::remove(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::size(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain().

---

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

• tpl_bplus_tree.H