JASS::binary_tree< KEY, ELEMENT >::iterator Class Reference

Iterate over the binary tree. More...

#include <binary_tree.h>

Collaboration diagram for JASS::binary_tree< KEY, ELEMENT >::iterator:

Public Member Functions
	iterator (node *current)
	Constructor.
const std::pair< const KEY &, const ELEMENT & >	operator* () const
	Return a reference to the object at the current location. More...
bool	operator!= (const iterator &other) const
	Compare two iterator objects for non-equality. More...
void	get_left_most (void)
	Set the current pointer to the left-most node beneath the current location.
iterator &	operator++ ()
	Increment this iterator.

Private Attributes
node *	location
	The node that is currently being examined.

Detailed Description

template<typename KEY, typename ELEMENT>
class JASS::binary_tree< KEY, ELEMENT >::iterator

Iterate over the binary tree.

This is an adaptation of the algorithm given by polygenelubricants on stackoverflow here: http://stackoverflow.com/questions/2942517/how-do-i-iterate-over-binary-tree The details of which are given on that thread but repeated here:

    What you're looking for is a successor algorithm.

    Here's how it can be defined:

    *First rule: The first node in the tree is the leftmost node in the tree.
    *Next rule: The successor of a node is:
        *Next-R rule: If it has a right subtree, the leftmost node in the right subtree.
        *Next-U rule: Otherwise, traverse up the tree
            *If you make a right turn (i.e. this node was a left child), then that parent node is the successor
            *If you make a left turn (i.e. this node was a right child), continue going up.
            *If you can't go up anymore, then there's no successor
            
    As you can see, for this to work, you need a parent node pointer.

Source code in Java is provided in that thread.

Member Function Documentation

operator!=()

template<typename KEY, typename ELEMENT>

bool JASS::binary_tree< KEY, ELEMENT >::iterator::operator!= ( const iterator &  other ) const

inline

Compare two iterator objects for non-equality.

Parameters

other

[in] The iterator object to compare to.

Returns

true if they differ, else false.

operator*()

template<typename KEY, typename ELEMENT>

const std::pair<const KEY &, const ELEMENT &> JASS::binary_tree< KEY, ELEMENT >::iterator::operator* ( ) const

inline

Return a reference to the object at the current location.

Returns

The current object.

---

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

• source/binary_tree.h