Lazy iterator over ordered leaf keys. More...

#include <tpl_bplus_tree.H>

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

Public Member Functions
	Iterator () noexcept=default
	Construct an exhausted iterator.

	Iterator (const Gen_BPlus_Tree &tree) noexcept
	Construct an iterator over the full key order.

	Iterator (const Gen_BPlus_Tree &tree, const Key &first, const Key &last)
	Construct an iterator over the inclusive range [`first`, `last`].

bool	has_curr () const noexcept
	Return whether the iterator still points to a key.

const Key &	get_curr () const
	Return the current key.

void	next_ne ()
	Advance to the next key.

void	next ()
	Synonym for next_ne().

const Key &	operator* () const
	Dereference the iterator.

const Key *	operator-> () const
	Member-access shorthand for the current key.

Private Member Functions
void	skip_past_end ()

Private Attributes
const Gen_BPlus_Tree *	tree_ = nullptr

const Node *	leaf_ = nullptr

size_t	idx_ = 0

std::optional< Key >	last_

Detailed Description

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

Lazy iterator over ordered leaf keys.

The iterator walks the leaf chain directly and therefore avoids materializing an intermediate Array<Key>. Any mutation of the owning tree invalidates all iterators.

Definition at line 606 of file tpl_bplus_tree.H.

Constructor & Destructor Documentation

◆ Iterator() [1/3]

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

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

defaultnoexcept

Construct an exhausted iterator.

Exceptions

Nothing.

◆ Iterator() [2/3]

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

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

inlineexplicitnoexcept

Construct an iterator over the full key order.

Parameters

tree	Tree whose leaf chain will be traversed.

Exceptions

Nothing.

Definition at line 643 of file tpl_bplus_tree.H.

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

◆ Iterator() [3/3]

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

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

inline

Construct an iterator over the inclusive range [first, last].

Parameters

tree	Tree whose leaf chain will be traversed.
first	Lower bound, inclusive.
last	Upper bound, inclusive.

Exceptions

std::invalid_argument	If `last < first`.
Any	exception propagated by `Compare`.

Definition at line 656 of file tpl_bplus_tree.H.

References ah_invalid_argument_if, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::find_leaf(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::idx_, Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::leaf_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::lower_bound_index(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::skip_past_end().

Member Function Documentation

◆ get_curr()

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

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

inline

Return the current key.

Returns: Reference to the current key in the owning tree.

Exceptions

std::underflow_error If the iterator is exhausted.

Definition at line 681 of file tpl_bplus_tree.H.

References ah_underflow_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::has_curr(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::idx_, Aleph::detail::BPlusTreeNode< Key >::keys, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::leaf_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::operator*(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::operator->().

◆ has_curr()

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

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

inlinenoexcept

Return whether the iterator still points to a key.

Returns: true if there is a current key, otherwise false.

Exceptions

Nothing.

Definition at line 672 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::leaf_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::tree_.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::get_curr(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::keys(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::next_ne(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::range().

◆ next()

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

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

inline

Synonym for next_ne().

Exceptions

std::underflow_error	If the iterator is exhausted.
Any	exception propagated by `Compare`.

Definition at line 702 of file tpl_bplus_tree.H.

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

◆ next_ne()

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

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

inline

Advance to the next key.

Exceptions

std::underflow_error	If the iterator is exhausted.
Any	exception propagated by `Compare`.

Definition at line 691 of file tpl_bplus_tree.H.

References ah_underflow_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::has_curr(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::idx_, and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::skip_past_end().

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

◆ operator*()

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

const Key & Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::operator* ( ) const

inline

Dereference the iterator.

Returns: Reference to the current key.

Exceptions

std::underflow_error If the iterator is exhausted.

Definition at line 711 of file tpl_bplus_tree.H.

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

◆ operator->()

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

const Key * Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::operator-> ( ) const

inline

Member-access shorthand for the current key.

Returns: Pointer to the current key.

Exceptions

std::underflow_error If the iterator is exhausted.

Definition at line 720 of file tpl_bplus_tree.H.

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

◆ skip_past_end()

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

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

inlineprivate

Definition at line 613 of file tpl_bplus_tree.H.

References Aleph::and, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::cmp_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::idx_, Aleph::detail::BPlusTreeNode< Key >::keys, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::last_, Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::leaf_, Aleph::detail::BPlusTreeNode< Key >::next, Aleph::Array< T >::size(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::tree_.

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

Member Data Documentation

◆ idx_

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

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

private

Definition at line 610 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::Iterator(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::get_curr(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::next_ne(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::skip_past_end().

◆ last_

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

std::optional<Key> Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::last_

private

Definition at line 611 of file tpl_bplus_tree.H.

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

◆ leaf_

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

const Node* Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::leaf_ = nullptr

private

Definition at line 609 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::Iterator(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::get_curr(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::has_curr(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::skip_past_end().

◆ tree_

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

const Gen_BPlus_Tree* Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::tree_ = nullptr

private

Definition at line 608 of file tpl_bplus_tree.H.

Referenced by Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::has_curr(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::Iterator::skip_past_end().

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

tpl_bplus_tree.H

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Iterator() [1/3]

◆ Iterator() [2/3]

◆ Iterator() [3/3]

Member Function Documentation

◆ get_curr()

◆ has_curr()

◆ next()

◆ next_ne()

◆ operator*()

◆ operator->()

◆ skip_past_end()

Member Data Documentation

◆ idx_

◆ last_

◆ leaf_

◆ tree_