A Generic binary search tree. More...

#include <agrum/core/binSearchTree.h>

Public Member Functions

	BinSearchTreeIterator ()
	Class Constructors and Destructors. More...

	BinSearchTreeIterator (const BinSearchTreeIterator< Val, Cmp, Node > &from)
	Copy constructor: creates an iterator pointing toward the same tree. More...

	~BinSearchTreeIterator ()
	Class destructor. More...


BinSearchTreeIterator< Val, Cmp, Node > &	operator= (const BinSearchTreeIterator< Val, Cmp, Node > &from)
	Class operators. More...

const Val &	operator* () const
	Returns the value pointed to by the iterator. More...

BinSearchTreeIterator< Val, Cmp, Node > &	operator++ ()
	Point the iterator to the next value in the binary search tree. More...

BinSearchTreeIterator< Val, Cmp, Node > &	operator-- ()
	Point the iterator to the preceding value in the binary search tree. More...

bool	operator!= (const BinSearchTreeIterator< Val, Cmp, Node > &from) const
	Checks whether two iterators are pointing toward different elements. More...

bool	operator== (const BinSearchTreeIterator< Val, Cmp, Node > &from) const
	Checks whether two iterators are pointing toward identical elements. More...

Accessors / Modifiers
BinSearchTreeIterator< Val, Cmp, Node > &	up ()
	Makes the iterator move to its parent node. More...

BinSearchTreeIterator< Val, Cmp, Node > &	downLeft ()
	Makes the iterator move to the left child of the node it points to. More...

BinSearchTreeIterator< Val, Cmp, Node > &	downRight ()
	Makes the iterator move to the right child of the node it points to. More...

void	clear ()
	Detach the iterator from its current tree (if any) and reset it. More...

Protected Attributes
Node *	_node
	The current node pointed to by the iterator. More...

Node *	_next_node
	The next node to be used when _node=0 (if a ++ operator is applied). More...

Node *	_prev_node
	The preceding node to be used when _node=0 (if a – operator is applied). More...

Node *	_parent
	The parent to be used when _node=0 (if operation up is applied). More...

Node *	_left_child
	The left child to be used when _node=0 and leftdown() is applied. More...

Node *	_right_child
	The right child to be used when _node=0 and rightdown() is applied. More...

BinSearchTree< Val, Cmp, Node > *	_tree
	The binary search tree pointed to by the iterator. More...

BinSearchTreeIterator< Val, Cmp, Node > *	_next_iter
	The next iterator in the list of iterators of the binSearchTree. More...

Friends

class	BinSearchTree< Val, Cmp, Node >
	To speed-up accesses. More...

Detailed Description

template<typename Val, class Cmp, class Node>
class gum::BinSearchTreeIterator< Val, Cmp, Node >

A Generic binary search tree.

Template Parameters

Val	The values type to store in the binary search tree.
Cmp	The compatator for sorting the binary search tree.
Node	The nodes type used to store values in the binary search tree.

Definition at line 448 of file binSearchTree.h.

Constructor & Destructor Documentation

◆ BinSearchTreeIterator() [1/2]

template<typename Val, class Cmp, class Node>

gum::BinSearchTreeIterator< Val, Cmp, Node >::BinSearchTreeIterator ( )

Class Constructors and Destructors.

Basic constructor: returns an iterator pointing toward nothing.

◆ BinSearchTreeIterator() [2/2]

template<typename Val, class Cmp, class Node>

gum::BinSearchTreeIterator< Val, Cmp, Node >::BinSearchTreeIterator ( const BinSearchTreeIterator< Val, Cmp, Node > & from )

Copy constructor: creates an iterator pointing toward the same tree.

Parameters

from	The gum::BinSearchTreeIterator to copy.

◆ ~BinSearchTreeIterator()

template<typename Val, class Cmp, class Node>

gum::BinSearchTreeIterator< Val, Cmp, Node >::~BinSearchTreeIterator ( )

Class destructor.

Member Function Documentation

◆ _detachFromTree()

template<typename Val, class Cmp, class Node>

void gum::BinSearchTreeIterator< Val, Cmp, Node >::_detachFromTree ( )

private

a method to detach the current iterator from its tree's iterator's list.

◆ _initialize()

template<typename Val, class Cmp, class Node>

void gum::BinSearchTreeIterator< Val, Cmp, Node >::_initialize	(	const BinSearchTree< Val, Cmp, Node > *	tree,
		const Node *	current_node,
		bool	add_to_iterator_list
	)

private

A function called to initialize an iterator.

Assuming that the iterator has been constructed using the default constructor (i.e., it points toward no binary search tree), this method make it point toward one tree and, if needed, add it to the set of iterators of the tree.

Parameters

tree	The gum::BinSearchTree to iterate on.
current_node	The node pointed by this iterator.
add_to_iterator_list	Add this iterator to the iterator list.

◆ clear()

template<typename Val, class Cmp, class Node>

void gum::BinSearchTreeIterator< Val, Cmp, Node >::clear ( )

Detach the iterator from its current tree (if any) and reset it.

◆ downLeft()

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >& gum::BinSearchTreeIterator< Val, Cmp, Node >::downLeft ( )

Makes the iterator move to the left child of the node it points to.

Returns: Return this gum::BinSearchTreeIterator.

◆ downRight()

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >& gum::BinSearchTreeIterator< Val, Cmp, Node >::downRight ( )

Makes the iterator move to the right child of the node it points to.

Returns: Return this gum::BinSearchTreeIterator.

◆ operator!=()

template<typename Val, class Cmp, class Node>

bool gum::BinSearchTreeIterator< Val, Cmp, Node >::operator!= ( const BinSearchTreeIterator< Val, Cmp, Node > & from ) const

Checks whether two iterators are pointing toward different elements.

Parameters

from	The gum::BinSearchTreeIterator to test for inequality.

Returns: Returns true if the two gum::BinSearchTreeIterator are different.

◆ operator*()

template<typename Val, class Cmp, class Node>

const Val& gum::BinSearchTreeIterator< Val, Cmp, Node >::operator* ( ) const

Returns the value pointed to by the iterator.

Returns: Returns the value pointed to by the iterator.

Exceptions

UndefinedIteratorValue Raised if the iterator does not point to a valid node of the tree.

◆ operator++()

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >& gum::BinSearchTreeIterator< Val, Cmp, Node >::operator++ ( )

Point the iterator to the next value in the binary search tree.

A binary search tree stores data according to a complete weak order <=. A ++ operation on an iterator makes the latter point on the next value in the tree w.r.t. ordering <=.

Loops are guaranteed to parse the whole binary search tree as long as no element is added to or deleted from the tree while being in the loop. Deleting elements during the loop is guaranteed to never produce a segmentation fault.

for (iter = tree.begin(); iter != tree.end(); ++iter) {
  // some code
}

Returns: Returns this gum::BinSearchTreeIterator.

◆ operator--()

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >& gum::BinSearchTreeIterator< Val, Cmp, Node >::operator-- ( )

Point the iterator to the preceding value in the binary search tree.

A binary search tree stores data according to a complete weak order <=. A – operation on an iterator makes the latter point on the preceding value in the tree w.r.t. ordering <=.

Loops are guaranteed to parse the whole binary search tree as long as no element is added to or deleted from the tree while being in the loop. Deleting elements during the loop is guaranteed to never produce a segmentation fault.

for (iter = tre.rbegin(); iter != tree.rend(); --iter) {
  // some code
}

◆ operator=()

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >& gum::BinSearchTreeIterator< Val, Cmp, Node >::operator= ( const BinSearchTreeIterator< Val, Cmp, Node > & from )

Class operators.

Copy operator.

Parameters

from	the gum::BinSearchTreeIterator to copy.

Returns: Returns this gum::BinSearchTreeIterator.

◆ operator==()

template<typename Val, class Cmp, class Node>

bool gum::BinSearchTreeIterator< Val, Cmp, Node >::operator== ( const BinSearchTreeIterator< Val, Cmp, Node > & from ) const

Checks whether two iterators are pointing toward identical elements.

Parameters

from	The gum::BinSearchTreeIterator to test for equality.

Returns: Returns true if the two gum::BinSearchTreeIterator are equal.

◆ up()

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >& gum::BinSearchTreeIterator< Val, Cmp, Node >::up ( )

Makes the iterator move to its parent node.

Returns: Return this gum::BinSearchTreeIterator.

Friends And Related Function Documentation

◆ BinSearchTree< Val, Cmp, Node >

template<typename Val, class Cmp, class Node>

friend class BinSearchTree< Val, Cmp, Node >

friend

To speed-up accesses.

Definition at line 615 of file binSearchTree.h.

Member Data Documentation

◆ _left_child

template<typename Val, class Cmp, class Node>

Node* gum::BinSearchTreeIterator< Val, Cmp, Node >::_left_child

protected

The left child to be used when _node=0 and leftdown() is applied.

Definition at line 601 of file binSearchTree.h.

◆ _next_iter

template<typename Val, class Cmp, class Node>

BinSearchTreeIterator< Val, Cmp, Node >* gum::BinSearchTreeIterator< Val, Cmp, Node >::_next_iter

protected

The next iterator in the list of iterators of the binSearchTree.

Definition at line 610 of file binSearchTree.h.

◆ _next_node

template<typename Val, class Cmp, class Node>

Node* gum::BinSearchTreeIterator< Val, Cmp, Node >::_next_node

protected

The next node to be used when _node=0 (if a ++ operator is applied).

Definition at line 591 of file binSearchTree.h.

◆ _node

template<typename Val, class Cmp, class Node>

Node* gum::BinSearchTreeIterator< Val, Cmp, Node >::_node

protected

The current node pointed to by the iterator.

Definition at line 588 of file binSearchTree.h.

◆ _parent

template<typename Val, class Cmp, class Node>

Node* gum::BinSearchTreeIterator< Val, Cmp, Node >::_parent

protected

The parent to be used when _node=0 (if operation up is applied).

Definition at line 598 of file binSearchTree.h.

◆ _prev_node

template<typename Val, class Cmp, class Node>

Node* gum::BinSearchTreeIterator< Val, Cmp, Node >::_prev_node

protected

The preceding node to be used when _node=0 (if a – operator is applied).

Definition at line 595 of file binSearchTree.h.

◆ _right_child

template<typename Val, class Cmp, class Node>

Node* gum::BinSearchTreeIterator< Val, Cmp, Node >::_right_child

protected

The right child to be used when _node=0 and rightdown() is applied.

Definition at line 604 of file binSearchTree.h.

◆ _tree

template<typename Val, class Cmp, class Node>

BinSearchTree< Val, Cmp, Node >* gum::BinSearchTreeIterator< Val, Cmp, Node >::_tree

protected

The binary search tree pointed to by the iterator.

Definition at line 607 of file binSearchTree.h.

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

agrum/core/binSearchTree.h

Public Member Functions

Protected Attributes

Friends

Detailed Description

template<typename Val, class Cmp, class Node> class gum::BinSearchTreeIterator< Val, Cmp, Node >

Constructor & Destructor Documentation

◆ BinSearchTreeIterator() [1/2]

◆ BinSearchTreeIterator() [2/2]

◆ ~BinSearchTreeIterator()

Member Function Documentation

◆ _detachFromTree()

◆ _initialize()

◆ clear()

◆ downLeft()

◆ downRight()

◆ operator!=()

◆ operator*()

◆ operator++()

◆ operator--()

◆ operator=()

◆ operator==()

◆ up()

Friends And Related Function Documentation

◆ BinSearchTree< Val, Cmp, Node >

Member Data Documentation

◆ _left_child

◆ _next_iter

◆ _next_node

◆ _node

◆ _parent

◆ _prev_node

◆ _right_child

◆ _tree

template<typename Val, class Cmp, class Node>
class gum::BinSearchTreeIterator< Val, Cmp, Node >