DREAM::AVLTreeNode

DREAM::AVLTreeNode< key_type, item_type > Class Template Reference

Class for one element in the AVLTree. More...

#include <AVLTree.h>

List of all members.

Public Member Functions

AVLTreeNode (key_type key, item_type item, AVLTreeNode< key_type, item_type > *parent=NULL)

Constructor.

~AVLTreeNode ()

Destructor.

void calculate_depth ()

Called when the node is on the path to a newly inserted or removed node.

uint depth ()

Returns the depth of the subtree from the given point.

AVLTreeNode< key_type, item_type > * left ()

Return the left child of the node.

const AVLTreeNode< key_type,
item_type > * left () const

Return the left child of the node.

void left (AVLTreeNode< key_type, item_type > *node_ptr)

Sets the left child of the node.

AVLTreeNode< key_type, item_type > * right ()

Return the right child of the node.

const AVLTreeNode< key_type,
item_type > * right () const

Return the right child of the node.

void right (AVLTreeNode< key_type, item_type > *node_ptr)

Sets the right child of the node.

AVLTreeNode< key_type, item_type > * parent ()

Returns the parent of the node.

const AVLTreeNode< key_type,
item_type > * parent () const

Returns the parent of the node.

void parent (AVLTreeNode< key_type, item_type > *node_ptr)

Sets the parent of the node.

AVLTreeNode< key_type, item_type > & operator= (AVLTreeNode< key_type, item_type > &node)

Assignment operator.

Public Attributes

key_type first

The key of the node.

item_type second

The item of the node.

Protected Member Functions

AVLTreeNode< key_type, item_type > * iter_next ()

++ operator.

AVLTreeNode< key_type, item_type > * iter_previous ()

-- operator.

const AVLTreeNode< key_type,
item_type > * iter_next () const

++ operator.

const AVLTreeNode< key_type,
item_type > * iter_previous () const

-- operator.

Protected Attributes

AVLTreeNode< key_type, item_type > * left_

The left child of the node.

AVLTreeNode< key_type, item_type > * right_

The right child of the node.

AVLTreeNode< key_type, item_type > * parent_

The parent of the node.

uint depth_

Stores the depth of the node's subtree.

uint depth_count_

Stores the number of nodes with the given depth.

Friends

class Iterator< AVLTreeNode< key_type, item_type > >

Allow iterators to manipulate protected members.

class Const_Iterator< AVLTreeNode< key_type, item_type > >

Allow iterators to manipulate protected members.

class AVLTree< key_type, item_type >

Allow AVLTree to manipulate protected members.

Detailed Description

template<class key_type, class item_type>
class DREAM::AVLTreeNode< key_type, item_type >

Class for one element in the AVLTree.

Definition at line 74 of file AVLTree.h.

Constructor & Destructor Documentation

template<class key_type, class item_type>

DREAM::AVLTreeNode< key_type, item_type >::AVLTreeNode	(	key_type	key,
		item_type	item,
		AVLTreeNode< key_type, item_type > *	parent = `NULL`
	)

Constructor.

Definition at line 66 of file AVLTree.cpp.

template<class key_type, class item_type>

DREAM::AVLTreeNode< key_type, item_type >::~AVLTreeNode ( )

Destructor.

Definition at line 72 of file AVLTree.cpp.

Member Function Documentation

template<class key_type, class item_type>

AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::iter_next ( ) [protected]

++ operator.

This operator does not actually change the node's value and should only be used from within Iterators.

Definition at line 122 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::left_.

template<class key_type, class item_type>

AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::iter_previous ( ) [protected]

-- operator.

This operator does not actually change the node's value and should only be used from within Iterators.

Definition at line 152 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::right_.

template<class key_type, class item_type>

const AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::iter_next ( ) const [protected]

++ operator.

This operator does not actually change the node's value and should only be used from within Iterators.

Definition at line 182 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::left_.

template<class key_type, class item_type>

const AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::iter_previous ( ) const [protected]

-- operator.

This operator does not actually change the node's value and should only be used from within Iterators.

Definition at line 212 of file AVLTree.cpp.

References DREAM::AVLTreeNode< key_type, item_type >::right_.

template<class key_type, class item_type>

void DREAM::AVLTreeNode< key_type, item_type >::calculate_depth ( )

Called when the node is on the path to a newly inserted or removed node.

It manages the depth_ and depth_count_ variables...

Definition at line 81 of file AVLTree.cpp.

Referenced by DREAM::AVLTree< key_type, item_type >::erase().

template<class key_type, class item_type>

uint DREAM::AVLTreeNode< key_type, item_type >::depth ( ) [inline]

Returns the depth of the subtree from the given point.

Definition at line 116 of file AVLTree.cpp.

template<class key_type, class item_type>

AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::left ( ) [inline]

Return the left child of the node.

Definition at line 242 of file AVLTree.cpp.

template<class key_type, class item_type>

const AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::left ( ) const [inline]

Return the left child of the node.

Definition at line 248 of file AVLTree.cpp.

template<class key_type, class item_type>

void DREAM::AVLTreeNode< key_type, item_type >::left ( AVLTreeNode< key_type, item_type > * node_ptr ) [inline]

Sets the left child of the node.

Definition at line 254 of file AVLTree.cpp.

template<class key_type, class item_type>

AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::right ( ) [inline]

Return the right child of the node.

Definition at line 260 of file AVLTree.cpp.

template<class key_type, class item_type>

const AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::right ( ) const [inline]

Return the right child of the node.

Definition at line 266 of file AVLTree.cpp.

template<class key_type, class item_type>

void DREAM::AVLTreeNode< key_type, item_type >::right ( AVLTreeNode< key_type, item_type > * node_ptr ) [inline]

Sets the right child of the node.

Definition at line 272 of file AVLTree.cpp.

template<class key_type, class item_type>

AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::parent ( ) [inline]

Returns the parent of the node.

Definition at line 278 of file AVLTree.cpp.

template<class key_type, class item_type>

const AVLTreeNode< key_type, item_type > * DREAM::AVLTreeNode< key_type, item_type >::parent ( ) const [inline]

Returns the parent of the node.

Definition at line 284 of file AVLTree.cpp.

template<class key_type, class item_type>

void DREAM::AVLTreeNode< key_type, item_type >::parent ( AVLTreeNode< key_type, item_type > * node_ptr ) [inline]

Sets the parent of the node.

Definition at line 290 of file AVLTree.cpp.

template<class key_type, class item_type>

AVLTreeNode< key_type, item_type > & DREAM::AVLTreeNode< key_type, item_type >::operator= ( AVLTreeNode< key_type, item_type > & node )

Assignment operator.

Definition at line 296 of file AVLTree.cpp.

Friends And Related Function Documentation

template<class key_type, class item_type>

friend class Iterator< AVLTreeNode< key_type, item_type > > [friend]

Allow iterators to manipulate protected members.

Definition at line 167 of file AVLTree.h.

template<class key_type, class item_type>

friend class Const_Iterator< AVLTreeNode< key_type, item_type > > [friend]

Allow iterators to manipulate protected members.

Definition at line 170 of file AVLTree.h.

template<class key_type, class item_type>

friend class AVLTree< key_type, item_type > [friend]

Allow AVLTree to manipulate protected members.

Definition at line 173 of file AVLTree.h.

Member Data Documentation

template<class key_type, class item_type>

AVLTreeNode<key_type, item_type>* DREAM::AVLTreeNode< key_type, item_type >::left_ [protected]

The left child of the node.

Definition at line 99 of file AVLTree.h.

Referenced by DREAM::AVLTree< key_type, item_type >::balance_right(), DREAM::AVLTree< key_type, item_type >::begin(), DREAM::AVLTree< key_type, item_type >::find(), DREAM::AVLTree< key_type, item_type >::get_smaller_node(), DREAM::AVLTree< key_type, item_type >::insert(), and DREAM::AVLTreeNode< key_type, item_type >::iter_next().

template<class key_type, class item_type>

AVLTreeNode<key_type, item_type>* DREAM::AVLTreeNode< key_type, item_type >::right_ [protected]

The right child of the node.

Definition at line 102 of file AVLTree.h.

Referenced by DREAM::AVLTree< key_type, item_type >::balance_right(), DREAM::AVLTree< key_type, item_type >::find(), DREAM::AVLTree< key_type, item_type >::get_larger_node(), DREAM::AVLTree< key_type, item_type >::insert(), and DREAM::AVLTreeNode< key_type, item_type >::iter_previous().

template<class key_type, class item_type>

AVLTreeNode<key_type, item_type>* DREAM::AVLTreeNode< key_type, item_type >::parent_ [protected]

The parent of the node.

Definition at line 105 of file AVLTree.h.

Referenced by DREAM::AVLTree< key_type, item_type >::balance_right(), DREAM::AVLTree< key_type, item_type >::erase(), DREAM::AVLTree< key_type, item_type >::get_larger_node(), and DREAM::AVLTree< key_type, item_type >::get_smaller_node().

template<class key_type, class item_type>

uint DREAM::AVLTreeNode< key_type, item_type >::depth_ [protected]

Stores the depth of the node's subtree.

Definition at line 108 of file AVLTree.h.

template<class key_type, class item_type>

uint DREAM::AVLTreeNode< key_type, item_type >::depth_count_ [protected]

Stores the number of nodes with the given depth.

The use of this variable allows us to decrease the depth of trees when no more nodes are available with the give depth.

Definition at line 113 of file AVLTree.h.

template<class key_type, class item_type>

key_type DREAM::AVLTreeNode< key_type, item_type >::first

The key of the node.

Definition at line 161 of file AVLTree.h.

Referenced by DREAM::AVLTree< key_type, item_type >::find(), and DREAM::AVLTree< key_type, item_type >::insert().

template<class key_type, class item_type>

item_type DREAM::AVLTreeNode< key_type, item_type >::second

The item of the node.

Definition at line 164 of file AVLTree.h.

Referenced by DREAM::AVLTree< key_type, item_type >::insert().

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

src/datastructures/AVLTree.h
src/datastructures/AVLTree.cpp

Generated on Fri Jul 27 18:30:04 2007 for DREAM by

doxygen

1.5.1