aGrUM  0.13.2
gum::BinSearchTreeIterator< Val, Cmp, Node > Class Template Reference

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
ValThe values type to store in the binary search tree.
CmpThe compatator for sorting the binary search tree.
NodeThe nodes type used to store values in the binary search tree.

Definition at line 446 of file binSearchTree.h.

Constructor & Destructor Documentation

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.

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
fromThe gum::BinSearchTreeIterator to copy.
template<typename Val, class Cmp, class Node>
gum::BinSearchTreeIterator< Val, Cmp, Node >::~BinSearchTreeIterator ( )

Class destructor.

Member Function Documentation

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.

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
treeThe gum::BinSearchTree to iterate on.
current_nodeThe node pointed by this iterator.
add_to_iterator_listAdd this iterator to the iterator list.
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.

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.
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.
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
fromThe gum::BinSearchTreeIterator to test for inequality.
Returns
Returns true if the two gum::BinSearchTreeIterator are different.
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
UndefinedIteratorValueRaised if the iterator does not point to a valid node of the tree.
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.
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
}
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
fromthe gum::BinSearchTreeIterator to copy.
Returns
Returns this gum::BinSearchTreeIterator.
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
fromThe gum::BinSearchTreeIterator to test for equality.
Returns
Returns true if the two gum::BinSearchTreeIterator are equal.
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

template<typename Val, class Cmp, class Node>
friend class BinSearchTree< Val, Cmp, Node >
friend

To speed-up accesses.

Definition at line 613 of file binSearchTree.h.

Member Data Documentation

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 599 of file binSearchTree.h.

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 608 of file binSearchTree.h.

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 589 of file binSearchTree.h.

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 586 of file binSearchTree.h.

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 596 of file binSearchTree.h.

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 593 of file binSearchTree.h.

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 602 of file binSearchTree.h.

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 605 of file binSearchTree.h.


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