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

#include <tpl_b_tree.H>

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

Public Types
using	key_type = Key
	Stored key type.

Public Member Functions
	Gen_B_Tree (const Compare &cmp=Compare())
	Construct an empty B-Tree.

template<std::input_iterator It>
	Gen_B_Tree (It first, It last, const Compare &cmp=Compare())
	Construct a B-Tree from an iterator range.

	Gen_B_Tree (std::initializer_list< Key > init, const Compare &cmp=Compare())
	Construct a B-Tree from an initializer list.

	Gen_B_Tree (const Gen_B_Tree &other)
	Copy constructor performing a deep copy.

	Gen_B_Tree (Gen_B_Tree &&other)=default
	Move constructor.

Gen_B_Tree &	operator= (const Gen_B_Tree &other)
	Copy assignment.

Gen_B_Tree &	operator= (Gen_B_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`.

Array< Key >	keys () const
	Materialize the tree contents in sorted order.

bool	verify () const
	Verify structural B-Tree invariants.

Private Types
using	Node = detail::BTreeNode< 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

bool	equals (const Key &lhs, const Key &rhs) const

template<std::input_iterator It>
void	insert_range (It first, It last)

std::unique_ptr< Node >	clone_node (const Node *node) const

size_t	height_of (const Node *node) const noexcept

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)

std::optional< Key >	min_in (const Node *node) const

std::optional< Key >	max_in (const Node *node) const

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 idx)

size_t	ensure_child_has_extra (Node *parent, const size_t idx)

bool	remove_from (Node *node, const Key &key)

void	collect_keys (const Node *node, Array< Key > &out) 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_B_Tree< Key, Compare, MinDegree >

Generic B-Tree with configurable minimum degree.

Gen_B_Tree models an ordered set of unique keys. Unlike the raw binary-tree types in Aleph-w, this container owns its internal nodes and stores keys directly in them, which makes it a higher-level tree suited for page-like branching factors.

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(): O(log n)
upper_bound(): O(log n)
keys(): O(n)

Example: B_Tree<int> tree;

tree.insert(40);

tree.insert(10);

tree.insert(90);

if (tree.contains(10))

std::cout << "found\n";

tree.remove(40);

auto ordered = tree.keys();

Aleph::Gen_B_Tree
Generic B-Tree with configurable minimum degree.
Definition tpl_b_tree.H:134

Aleph::Gen_B_Tree::remove
bool remove(const Key &key)
Remove a key if present.
Definition tpl_b_tree.H:768

Aleph::Gen_B_Tree::insert
bool insert(const Key &key)
Insert a key if it is not already present.
Definition tpl_b_tree.H:723

Aleph::Gen_B_Tree::contains
bool contains(const Key &key) const
Return whether a key is present.
Definition tpl_b_tree.H:700

Aleph::Gen_B_Tree::keys
Array< Key > keys() const
Materialize the tree contents in sorted order.
Definition tpl_b_tree.H:877

Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133

Note: This tree stores unique keys. Duplicate inserts return false.; For leaf-linked range scans, see Aleph::BPlus_Tree.

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

Exception Safety: Read-only operations do not allocate. Mutating operations preserve the tree 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 133 of file tpl_b_tree.H.

Member Typedef Documentation

◆ key_type

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

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

Stored key type.

Definition at line 554 of file tpl_b_tree.H.

◆ Node

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

using Aleph::Gen_B_Tree< Key, Compare, MinDegree >::Node = detail::BTreeNode<Key>

private

Definition at line 138 of file tpl_b_tree.H.

Constructor & Destructor Documentation

◆ Gen_B_Tree() [1/5]

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

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

inlineexplicit

Construct an empty B-Tree.

Parameters

cmp	Comparison functor used to sort keys.

Exceptions

Nothing.

Note: O(1).

Definition at line 561 of file tpl_b_tree.H.

◆ Gen_B_Tree() [2/5]

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

template<std::input_iterator It>

Aleph::Gen_B_Tree< Key, Compare, MinDegree >::Gen_B_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.

Note: O(m log m) where m = distance(first, last).

Definition at line 570 of file tpl_b_tree.H.

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

◆ Gen_B_Tree() [3/5]

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

Aleph::Gen_B_Tree< Key, Compare, MinDegree >::Gen_B_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.

Note: O(m log m) where m = init.size().

Definition at line 581 of file tpl_b_tree.H.

◆ Gen_B_Tree() [4/5]

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

Aleph::Gen_B_Tree< Key, Compare, MinDegree >::Gen_B_Tree ( const Gen_B_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.

Note: O(n) time and space.

Definition at line 590 of file tpl_b_tree.H.

◆ Gen_B_Tree() [5/5]

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

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

default

Move constructor.

Parameters

other Tree to move from.

Note: O(1).

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_B_Tree< Key, Compare, MinDegree >::append_copy_range	(	Array< T > &	dst,
		const Array< T > &	src,
		const size_t	from
	)

inlinestaticprivate

Definition at line 218 of file tpl_b_tree.H.

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

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::merge_children(), and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::append_move_range	(	Array< T > &	dst,
		Array< T > &	src,
		const size_t	from
	)

inlinestaticprivate

Definition at line 225 of file tpl_b_tree.H.

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

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

◆ borrow_from_next()

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

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

inlineprivate

Definition at line 369 of file tpl_b_tree.H.

References Aleph::Array< T >::append(), Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::erase_at(), Aleph::Array< T >::get_first(), Aleph::detail::BTreeNode< Key >::keys, and Aleph::detail::BTreeNode< Key >::leaf.

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

◆ borrow_from_prev()

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

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

inlineprivate

Definition at line 353 of file tpl_b_tree.H.

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

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

◆ clear()

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

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

inlinenoexcept

Remove every key from the tree.

Exceptions

Nothing.

Note: O(n).

Definition at line 688 of file tpl_b_tree.H.

References Aleph::Gen_B_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::clone_node ( const Node * node ) const

inlineprivate

Definition at line 232 of file tpl_b_tree.H.

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

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

◆ collect_keys()

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

void Aleph::Gen_B_Tree< Key, Compare, MinDegree >::collect_keys	(	const Node *	node,
		Array< Key > &	out
	)		const

inlineprivate

Definition at line 471 of file tpl_b_tree.H.

References Aleph::detail::BTreeNode< Key >::children, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::collect_keys(), Aleph::divide_and_conquer_partition_dp(), Aleph::detail::BTreeNode< Key >::keys, Aleph::detail::BTreeNode< Key >::leaf, and Aleph::Array< T >::size().

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::collect_keys(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::keys().

◆ contains()

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

bool Aleph::Gen_B_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`.

Note: O(log n).

Definition at line 700 of file tpl_b_tree.H.

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

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

◆ contains_in()

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

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

inlineprivate

Definition at line 261 of file tpl_b_tree.H.

References Aleph::and, Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::equals(), Aleph::detail::BTreeNode< Key >::keys, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::keys(), Aleph::detail::BTreeNode< Key >::leaf, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::lower_bound_index(), and Aleph::Array< T >::size().

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

◆ empty()

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

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

inlinenoexcept

Return whether the tree has no keys.

Returns: true if empty, otherwise false.

Exceptions

Nothing.

Note: O(1).

Definition at line 649 of file tpl_b_tree.H.

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

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

◆ ensure_child_has_extra()

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

size_t Aleph::Gen_B_Tree< Key, Compare, MinDegree >::ensure_child_has_extra	(	Node *	parent,
		const size_t	idx
	)

inlineprivate

Definition at line 400 of file tpl_b_tree.H.

References Aleph::and, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::merge_children().

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

◆ equals()

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

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

inlineprivate

Definition at line 175 of file tpl_b_tree.H.

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

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

◆ erase_at()

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

template<typename T >

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

inlinestaticprivate

Definition at line 200 of file tpl_b_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_B_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::merge_children(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::remove_from().

◆ get_compare()

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

const Compare & Aleph::Gen_B_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 639 of file tpl_b_tree.H.

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

◆ height()

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

size_t Aleph::Gen_B_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.

Note: O(log n).

Definition at line 679 of file tpl_b_tree.H.

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

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

◆ height_of()

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

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

inlineprivatenoexcept

Definition at line 248 of file tpl_b_tree.H.

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

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

◆ insert() [1/2]

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

bool Aleph::Gen_B_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.

Note: O(log n).

Definition at line 723 of file tpl_b_tree.H.

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

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

◆ insert() [2/2]

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

bool Aleph::Gen_B_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.

Note: O(log n).

Definition at line 756 of file tpl_b_tree.H.

References Aleph::copy(), and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::insert_at	(	Array< T > &	array,
		const size_t	idx,
		U &&	value
	)

inlinestaticprivate

Definition at line 186 of file tpl_b_tree.H.

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

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

◆ insert_nonfull()

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

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

inlineprivate

Definition at line 296 of file tpl_b_tree.H.

References Aleph::detail::BTreeNode< Key >::children, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::cmp_, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::insert_nonfull(), Aleph::detail::BTreeNode< Key >::keys, Aleph::detail::BTreeNode< Key >::leaf, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::MaxKeys, and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::split_child().

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::insert(), and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::insert_range	(	It	first,
		It	last
	)

inlineprivate

Definition at line 180 of file tpl_b_tree.H.

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

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

◆ is_empty()

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

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

inlinenoexcept

Synonym for empty() in traditional Aleph style.

Returns: true if empty, otherwise false.

Exceptions

Nothing.

Note: O(1).

Definition at line 659 of file tpl_b_tree.H.

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

◆ key_comp()

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

const Compare & Aleph::Gen_B_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 629 of file tpl_b_tree.H.

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

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

◆ keys()

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

Array< Key > Aleph::Gen_B_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.

Note: O(n) time and space.

Definition at line 877 of file tpl_b_tree.H.

References Aleph::Gen_B_Tree< Key, Compare, MinDegree >::collect_keys(), Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::reserve(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::root_, and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::size_.

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

◆ lower_bound()

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

std::optional< Key > Aleph::Gen_B_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.

Note: O(log n).

Definition at line 829 of file tpl_b_tree.H.

References Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::detail::BTreeNode< Key >::keys, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::keys(), Aleph::detail::BTreeNode< Key >::leaf, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::root_, and Aleph::Array< T >::size().

◆ lower_bound_index()

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

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

inlineprivate

Definition at line 147 of file tpl_b_tree.H.

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

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

◆ max_in()

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

std::optional< Key > Aleph::Gen_B_Tree< Key, Compare, MinDegree >::max_in ( const Node * node ) const

inlineprivate

Definition at line 334 of file tpl_b_tree.H.

References Aleph::and, Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_last(), Aleph::Array< T >::is_empty(), Aleph::detail::BTreeNode< Key >::keys, and Aleph::detail::BTreeNode< Key >::leaf.

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::max_key(), and Aleph::Gen_B_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_B_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.

Note: O(log n).

Definition at line 818 of file tpl_b_tree.H.

References Aleph::Gen_B_Tree< Key, Compare, MinDegree >::max_in(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::root_.

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

◆ merge_children()

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

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

inlineprivate

Definition at line 385 of file tpl_b_tree.H.

References Aleph::Array< T >::append(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::append_copy_range(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::append_move_range(), Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::erase_at(), GenericItems< Container, T >::keys(), Aleph::detail::BTreeNode< Key >::keys, and Aleph::detail::BTreeNode< Key >::leaf.

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::ensure_child_has_extra(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::remove_from().

◆ min_in()

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

std::optional< Key > Aleph::Gen_B_Tree< Key, Compare, MinDegree >::min_in ( const Node * node ) const

inlineprivate

Definition at line 315 of file tpl_b_tree.H.

References Aleph::and, Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Array< T >::get_first(), Aleph::Array< T >::is_empty(), Aleph::detail::BTreeNode< Key >::keys, and Aleph::detail::BTreeNode< Key >::leaf.

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::min_key(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::remove_from().

◆ min_key()

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

std::optional< Key > Aleph::Gen_B_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.

Note: O(log n).

Definition at line 808 of file tpl_b_tree.H.

References Aleph::Gen_B_Tree< Key, Compare, MinDegree >::min_in(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::root_.

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

◆ operator=() [1/2]

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

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

inline

Copy assignment.

Parameters

other Tree to copy from.

Returns: *this.

Note: O(n) time and space (copy-and-swap).

Definition at line 603 of file tpl_b_tree.H.

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

◆ operator=() [2/2]

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

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

default

Move assignment.

Parameters

other Tree to move from.

Returns: *this.

Note: O(1).

◆ remove()

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

bool Aleph::Gen_B_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.

Note: O(log n).

Definition at line 768 of file tpl_b_tree.H.

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

◆ remove_from()

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

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

inlineprivate

Definition at line 427 of file tpl_b_tree.H.

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

◆ search()

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

bool Aleph::Gen_B_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`.

Note: O(log n).

Definition at line 711 of file tpl_b_tree.H.

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

◆ size()

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

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

inlinenoexcept

Return the number of stored keys.

Returns: Number of unique keys stored in the tree.

Exceptions

Nothing.

Note: O(1).

Definition at line 669 of file tpl_b_tree.H.

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

◆ split_child()

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

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

inlineprivate

Definition at line 276 of file tpl_b_tree.H.

References Aleph::Gen_B_Tree< Key, Compare, MinDegree >::append_copy_range(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::append_move_range(), Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::detail::BTreeNode< Key >::keys, Aleph::detail::BTreeNode< Key >::leaf, Aleph::median(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::MinKeys, and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::truncate().

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

◆ truncate()

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

template<typename T >

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

inlinestaticprivate

Definition at line 212 of file tpl_b_tree.H.

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

Referenced by Aleph::Gen_B_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_B_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.

Note: O(log n).

Definition at line 853 of file tpl_b_tree.H.

References Aleph::detail::BTreeNode< Key >::children, Aleph::divide_and_conquer_partition_dp(), Aleph::detail::BTreeNode< Key >::keys, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::keys(), Aleph::detail::BTreeNode< Key >::leaf, Aleph::Gen_B_Tree< Key, Compare, MinDegree >::root_, Aleph::Array< T >::size(), and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::upper_bound_index	(	const Array< Key > &	keys,
		const Key &	key
	)		const

inlineprivate

Definition at line 161 of file tpl_b_tree.H.

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

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

◆ verify()

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

bool Aleph::Gen_B_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`.

Note: O(n).

Definition at line 890 of file tpl_b_tree.H.

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

◆ verify_node()

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

bool Aleph::Gen_B_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 491 of file tpl_b_tree.H.

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::verify(), and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::cmp_

private

Definition at line 145 of file tpl_b_tree.H.

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::equals(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::insert_nonfull(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::key_comp(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::lower_bound_index(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::operator=(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::upper_bound_index(), and Aleph::Gen_B_Tree< Key, Compare, MinDegree >::verify_node().

◆ MaxKeys

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

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

staticconstexprprivate

Definition at line 140 of file tpl_b_tree.H.

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

◆ MinKeys

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

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

staticconstexprprivate

Definition at line 141 of file tpl_b_tree.H.

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::split_child(), and Aleph::Gen_B_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_B_Tree< Key, Compare, MinDegree >::root_

private

Definition at line 143 of file tpl_b_tree.H.

◆ size_

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

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

private

Definition at line 144 of file tpl_b_tree.H.

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

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

tpl_b_tree.H

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ key_type

◆ Node

Constructor & Destructor Documentation

◆ Gen_B_Tree() [1/5]

◆ Gen_B_Tree() [2/5]

◆ Gen_B_Tree() [3/5]

◆ Gen_B_Tree() [4/5]

◆ Gen_B_Tree() [5/5]

Member Function Documentation

◆ append_copy_range()

◆ append_move_range()

◆ borrow_from_next()

◆ borrow_from_prev()

◆ clear()

◆ clone_node()

◆ collect_keys()

◆ contains()

◆ contains_in()

◆ empty()

◆ ensure_child_has_extra()

◆ equals()

◆ erase_at()

◆ get_compare()

◆ height()

◆ height_of()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_at()

◆ insert_nonfull()

◆ insert_range()

◆ is_empty()

◆ key_comp()

◆ keys()

◆ lower_bound()

◆ lower_bound_index()

◆ max_in()

◆ max_key()

◆ merge_children()

◆ min_in()

◆ min_key()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove()

◆ remove_from()

◆ search()

◆ size()

◆ split_child()

◆ truncate()

◆ upper_bound()

◆ upper_bound_index()

◆ verify()

◆ verify_node()

Member Data Documentation

◆ cmp_

◆ MaxKeys

◆ MinKeys

◆ root_

◆ size_