Base iterator template for ranked binary search trees. More...

#include <tpl_binNodeXt.H>

Inheritance diagram for Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >:

Public Member Functions
	BinTreeXt_Iterator () noexcept

	BinTreeXt_Iterator (const TreeType &__tree) noexcept

	BinTreeXt_Iterator (const TreeType &__tree, Node *__curr) noexcept

	BinTreeXt_Iterator (const TreeType &__tree, const size_t pos) noexcept

	BinTreeXt_Iterator (const BinTreeXt_Iterator &itor) noexcept

BinTreeXt_Iterator &	operator= (const BinTreeXt_Iterator &itor) noexcept

void	reset_first () noexcept

void	reset_last () noexcept

void	end () noexcept

void	reset_to_key (const Key &key) noexcept

void	reset_to_node (Node *node) noexcept

void	reset_to_pos (const size_t pos) noexcept

Node *	get_curr_ne () const noexcept

Node *	get_curr () const noexcept

size_t	get_current_position () const

size_t	get_pos () const

bool	has_curr () const noexcept

void	prev ()

void	next_ne () noexcept

void	next ()

Node *	del ()

bool	operator== (const BinTreeXt_Iterator &itor) const noexcept

bool	operator!= (const BinTreeXt_Iterator &itor) const

Protected Attributes
TreeType *	tree_ptr

Node *	curr

int	curr_pos

Static Protected Attributes
static constexpr int	Pos_Not_Current = -1

static constexpr int	Pos_Empty_Container = -2

static constexpr int	Pos_Not_Updated = -3

Private Member Functions
bool	is_container_empty () const noexcept

bool	pos_updated () const noexcept

bool	curr_updated () const noexcept

void	update_pos () const noexcept

void	update_curr () const noexcept

Detailed Description

template<class TreeType, class Node, typename Key, class Compare>
class Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >

Base iterator template for ranked binary search trees.

This template provides a common implementation for iterators on trees that support O(log n) select and position operations via subtree counters.

The TreeType must provide:

getRoot() returning Node*&
key_comp() returning Compare&
remove(const Key&) returning Node*

Template Parameters

TreeType	the tree class type
Node	the node type
Key	the key type
Compare	comparison functor

Definition at line 1037 of file tpl_binNodeXt.H.

Constructor & Destructor Documentation

◆ BinTreeXt_Iterator() [1/5]

template<class TreeType , class Node , typename Key , class Compare >

Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::BinTreeXt_Iterator ( )

inlinenoexcept

Definition at line 1086 of file tpl_binNodeXt.H.

◆ BinTreeXt_Iterator() [2/5]

template<class TreeType , class Node , typename Key , class Compare >

Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::BinTreeXt_Iterator ( const TreeType & __tree )

inlinenoexcept

Definition at line 1090 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_pos, Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::is_container_empty(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::Pos_Empty_Container.

◆ BinTreeXt_Iterator() [3/5]

template<class TreeType , class Node , typename Key , class Compare >

Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::BinTreeXt_Iterator	(	const TreeType &	__tree,
		Node *	__curr
	)

inlinenoexcept

Definition at line 1096 of file tpl_binNodeXt.H.

◆ BinTreeXt_Iterator() [4/5]

template<class TreeType , class Node , typename Key , class Compare >

Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::BinTreeXt_Iterator	(	const TreeType &	__tree,
		const size_t	pos
	)

inlinenoexcept

Definition at line 1101 of file tpl_binNodeXt.H.

◆ BinTreeXt_Iterator() [5/5]

template<class TreeType , class Node , typename Key , class Compare >

Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::BinTreeXt_Iterator ( const BinTreeXt_Iterator< TreeType, Node, Key, Compare > & itor )

inlinenoexcept

Definition at line 1106 of file tpl_binNodeXt.H.

Member Function Documentation

◆ curr_updated()

template<class TreeType , class Node , typename Key , class Compare >

bool Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_updated ( ) const

inlineprivatenoexcept

Definition at line 1061 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr.

Referenced by Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::del(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_curr_ne(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::operator==().

◆ del()

template<class TreeType , class Node , typename Key , class Compare >

Node * Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::del ( )

inline

Definition at line 1212 of file tpl_binNodeXt.H.

References ah_underflow_error_if, Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr, Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_updated(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::has_curr(), KEY, Aleph::maps(), Aleph::DynList< T >::remove(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::tree_ptr, and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_curr().

◆ end()

template<class TreeType , class Node , typename Key , class Compare >

void Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::end ( )

inlinenoexcept

Definition at line 1135 of file tpl_binNodeXt.H.

References put_itor_at_the_end().

◆ get_curr()

template<class TreeType , class Node , typename Key , class Compare >

Node * Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_curr ( ) const

inlinenoexcept

Definition at line 1165 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_curr_ne().

◆ get_curr_ne()

template<class TreeType , class Node , typename Key , class Compare >

Node * Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_curr_ne ( ) const

inlinenoexcept

Definition at line 1158 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr, Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_updated(), Aleph::maps(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_curr().

Referenced by Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_curr().

◆ get_current_position()

template<class TreeType , class Node , typename Key , class Compare >

size_t Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_current_position ( ) const

inline

Definition at line 1170 of file tpl_binNodeXt.H.

References ah_range_error_if, Aleph::COUNT(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_pos, Aleph::maps(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::pos_updated(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::tree_ptr, and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_pos().

Referenced by Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_pos().

◆ get_pos()

template<class TreeType , class Node , typename Key , class Compare >

size_t Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_pos ( ) const

inline

Definition at line 1182 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::get_current_position().

◆ has_curr()

template<class TreeType , class Node , typename Key , class Compare >

bool Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::has_curr ( ) const

inlinenoexcept

Definition at line 1184 of file tpl_binNodeXt.H.

References Aleph::COUNT(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_pos, Aleph::maps(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::pos_updated(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::tree_ptr, and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::update_pos().

Referenced by Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::del(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::next(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::prev().

◆ is_container_empty()

template<class TreeType , class Node , typename Key , class Compare >

bool Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::is_container_empty ( ) const

inlineprivatenoexcept

Definition at line 1051 of file tpl_binNodeXt.H.

References Aleph::COUNT(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::tree_ptr.

Referenced by Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::BinTreeXt_Iterator(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::operator==(), Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::reset_first(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::reset_last().

◆ next()

template<class TreeType , class Node , typename Key , class Compare >

void Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::next ( )

inline

Definition at line 1206 of file tpl_binNodeXt.H.

References ah_overflow_error_if, Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::has_curr(), Aleph::maps(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::next_ne().

◆ next_ne()

template<class TreeType , class Node , typename Key , class Compare >

void Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::next_ne ( )

inlinenoexcept

Definition at line 1200 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr, and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_pos.

Referenced by Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::next().

◆ operator!=()

template<class TreeType , class Node , typename Key , class Compare >

bool Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::operator!= ( const BinTreeXt_Iterator< TreeType, Node, Key, Compare > & itor ) const

inline

Definition at line 1246 of file tpl_binNodeXt.H.

References Aleph::maps().

◆ operator=()

template<class TreeType , class Node , typename Key , class Compare >

BinTreeXt_Iterator & Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::operator= ( const BinTreeXt_Iterator< TreeType, Node, Key, Compare > & itor )

inlinenoexcept

Definition at line 1110 of file tpl_binNodeXt.H.

References Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr, Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::curr_pos, Aleph::maps(), and Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::tree_ptr.

◆ operator==()

template<class TreeType , class Node , typename Key , class Compare >

bool Aleph::BinTreeXt_Iterator< TreeType, Node, Key, Compare >::operator== ( const BinTreeXt_Iterator< TreeType, Node, Key, Compare > & itor ) const