Lazy iterator over ordered keys stored in leaf pages. More...

#include <tpl_file_bplus_tree.H>

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

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

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

	Iterator (const tree_type &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 tree_type *	tree_ = nullptr

page_id_t	leaf_id_ = 0

size_t	idx_ = 0

std::optional< Key >	last_

Detailed Description

template<typename Key, class Compare = Aleph::less<Key>, size_t MinDegree = 16, typename Codec = detail::Paged_Value_Codec<Key>>
class Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator

Lazy iterator over ordered keys stored in leaf pages.

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 2160 of file tpl_file_bplus_tree.H.

Constructor & Destructor Documentation

◆ Iterator() [1/3]

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

Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::Iterator ( )

defaultnoexcept

Construct an empty iterator.

Exceptions

Nothing.

◆ Iterator() [2/3]

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

Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::Iterator ( const tree_type & tree )

inlineexplicitnoexcept

Construct an iterator over the full key order.

Parameters

tree	Tree whose leaves will be traversed.

Exceptions

Nothing.

Definition at line 2198 of file tpl_file_bplus_tree.H.

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

◆ Iterator() [3/3]

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

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

inline

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

Parameters

tree	Tree whose leaves 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 2211 of file tpl_file_bplus_tree.H.

References ah_invalid_argument_if, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::cmp_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::find_leaf_page(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::idx_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::leaf_id_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::lower_bound_index(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::page(), and Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::skip_past_end().

Member Function Documentation

◆ get_curr()

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

const Key & Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::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 2237 of file tpl_file_bplus_tree.H.

References ah_underflow_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::has_curr(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::idx_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Page::keys, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::leaf_id_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::page(), and Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::tree_.

Referenced by Aleph::Gen_File_BPlus_Map< Key, Value, Compare, MinDegree, KeyCodec, ValueCodec >::Iterator::get_curr(), Aleph::Gen_File_BPlus_Map< Key, Value, Compare, MinDegree, KeyCodec, ValueCodec >::Iterator::get_key(), Aleph::Gen_File_BPlus_Map< Key, Value, Compare, MinDegree, KeyCodec, ValueCodec >::Iterator::get_value(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::operator*(), and Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::operator->().

◆ has_curr()

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

bool Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::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 2228 of file tpl_file_bplus_tree.H.

References Aleph::and, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::leaf_id_, and Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::tree_.

Referenced by Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::get_curr(), Aleph::Gen_File_BPlus_Map< Key, Value, Compare, MinDegree, KeyCodec, ValueCodec >::Iterator::has_curr(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::keys(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::next_ne(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::range(), and TEST().

◆ next()

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

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

inline

Synonym for next_ne().

Exceptions

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

Definition at line 2260 of file tpl_file_bplus_tree.H.

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

◆ next_ne()

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

void Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::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 2248 of file tpl_file_bplus_tree.H.

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

Referenced by Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::next(), and Aleph::Gen_File_BPlus_Map< Key, Value, Compare, MinDegree, KeyCodec, ValueCodec >::Iterator::next_ne().

◆ operator*()

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

const Key & Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::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 2269 of file tpl_file_bplus_tree.H.

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

◆ operator->()

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

const Key * Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::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 2278 of file tpl_file_bplus_tree.H.

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

◆ skip_past_end()

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

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

inlineprivate

Definition at line 2167 of file tpl_file_bplus_tree.H.

References Aleph::and, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::cmp_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::idx_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::last_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::leaf_id_, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Page::link, Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::page(), and Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::tree_.

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

Member Data Documentation

◆ idx_

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

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

private

Definition at line 2164 of file tpl_file_bplus_tree.H.

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

◆ last_

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

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

private

Definition at line 2165 of file tpl_file_bplus_tree.H.

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

◆ leaf_id_

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

page_id_t Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::leaf_id_ = 0

private

Definition at line 2163 of file tpl_file_bplus_tree.H.

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

◆ tree_

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

const tree_type* Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::Iterator::tree_ = nullptr

private

Definition at line 2162 of file tpl_file_bplus_tree.H.

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

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

tpl_file_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_id_

◆ tree_