A Generic binary search tree. More...

#include <agrum/tools/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 442 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

◆ 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.

◆ 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.

◆ 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.

◆ 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.

◆ 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 609 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 595 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 604 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 585 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 582 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 592 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 589 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 598 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 601 of file binSearchTree.h.

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

agrum/tools/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

◆ clear()

◆ detachFromTree_()

◆ downLeft()

◆ downRight()

◆ initialize_()

◆ 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 >