Humble Framework for SkyOS
Main Page | Modules | Class Hierarchy | Alphabetical List | Data Structures | Directories | File List | Data Fields | Globals | Related Pages

HTreeNode< T > Class Template Reference
[Abstract Data Types]

#include <HTree.h>

Inheritance diagram for HTreeNode< T >:

HObj

Detailed Description

template<class T>
class HTreeNode< T >

The HTreeNode template class manages a single node in the tree, which stores pointers to the left, right, and parent nodes, a balance factor, and the user-defined data type.

Definition at line 31 of file HTree.h.

Public Member Functions

const T & GetData () const
ErrCode SetData (const T &data)
 Updates the data embedded in the node.
uint32 GetDepth (void) const
 Returns the depth beneath the current node.
uint32 GetCount (void) const
 Returns the count of nodes beneath the current node.
HTreeNodePtr GetFirst (void)
HTreeNodePtr GetLast (void)
HTreeNodePtr GetNext (void)
HTreeNodePtr GetPrev (void)
HTreeNodePtr GetRoot (void)
HTreeNodePtr Search (T const &data)
 HTreeNode (const T &data, HTreeNodePtr pn=NULL)

Static Public Member Functions

static int Compare (const T &t1, const T &t2)

Protected Types

enum  Balance { BAL_LEFT, BAL_EVEN, BAL_RIGHT }

Protected Member Functions

void afterDelete (void)
void afterInsert (void)
HTreeNodePtr getInsertPos (const T &data, HTreeNodePtr &pnFound)
void rotateLeft (void)
void rotateRight ()
void rotateLeftLeft (void)
void rotateRightRight (void)
bool hasParent (void) const
bool hasLeftSibling () const
bool hasRightSibling () const
bool isLeftSibling () const
bool isRightSibling () const
HTreeNode & operator= (HTreeNode< T > const &)

Protected Attributes

T m_data
 The user-defined data type.
Balance m_balance
 The "balance factor" of this node.
HTreeNodePtr m_pnLeft
 Ptr to the node's left child.
HTreeNodePtr m_pnRight
 Ptr to the node's right child.
HTreeNodePtr m_pnParent
 Ptr to the node's parent.

Friends

class HTree< T >

Member Function Documentation

template<class T>
void HTreeNode< T >::afterDelete (  void   )  [protected]
 

Rebalances the sub-tree after a node is deleted

Definition at line 58 of file HTree.h.

template<class T>
void HTreeNode< T >::afterInsert (  void   )  [protected]
 

Rebalances sub-tree after node insertion

Definition at line 181 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::getInsertPos (  const T &  data,
HTreeNodePtr &  pnFound
)  [protected]
 

Finds the insertion point in tree

Returns:
ptr to insertion node, or NULL if already in tree
Parameters:
data data to be inserted
pnFound [out] node data found in (only valid if NULL result)

Definition at line 236 of file HTree.h.

template<class T>
void HTreeNode< T >::rotateLeft (  void   )  [protected]
 

Performs a "rotate left" action on the current sub-tree.

Definition at line 255 of file HTree.h.

template<class T>
void HTreeNode< T >::rotateRight (   )  [protected]
 

Performs a "rotate right" action on the current sub-tree.

Definition at line 296 of file HTree.h.

template<class T>
void HTreeNode< T >::rotateLeftLeft (  void   )  [protected]
 

Performs a "double rotate left" action on the current sub-tree.

Definition at line 337 of file HTree.h.

template<class T>
void HTreeNode< T >::rotateRightRight (  void   )  [protected]
 

Performs a "double rotate right" action on the current sub-tree.

Definition at line 390 of file HTree.h.

template<class T>
bool HTreeNode< T >::hasParent (  void   )  const [protected]
 

Evaluates to true if the node has a valid parent (all except root node)

Returns:
True if the node has a valid parent.

Definition at line 445 of file HTree.h.

template<class T>
bool HTreeNode< T >::hasLeftSibling (   )  const [protected]
 

Evaluates to true if the node has a valid left child.

Returns:
True if the node has a valid left child.

Definition at line 453 of file HTree.h.

template<class T>
bool HTreeNode< T >::hasRightSibling (   )  const [protected]
 

Evaluates to true if the node has a valid right child.

Returns:
True if the node has a valid right child.

Definition at line 461 of file HTree.h.

template<class T>
bool HTreeNode< T >::isLeftSibling (   )  const [protected]
 

Evaluates to true if the node is the left child of it's parent.

Returns:
True if the node is a left child

Definition at line 469 of file HTree.h.

template<class T>
bool HTreeNode< T >::isRightSibling (   )  const [protected]
 

Evaluates to true if the node is the right child of it's parent

Returns:
True if the node is a right child

Definition at line 477 of file HTree.h.

template<class T>
const T& HTreeNode< T >::GetData (   )  const
 

Returns the data embedded in the node

Returns:
Data associated with this node

Definition at line 493 of file HTree.h.

template<class T>
ErrCode HTreeNode< T >::SetData (  const T &  data  ) 
 

This method changes the data for this node, after verifying that it is equal to the existing node. Keep in mind that the Compare() function typically only compares whatever 'key' fields are contained inside the data structure. The key fields must remain the same—or the tree will be manually thrown out of balance—but any other fields can be freely changed.

Returns:
NO_ERROR on success, error code otherwise
Parameters:
data Data to be associated with this node

Definition at line 508 of file HTree.h.

template<class T>
uint32 HTreeNode< T >::GetDepth (  void   )  const
 

Traverses the tree to compute the depth of the sub-tree from this node downwards. Minimum value will always be 1 (for this node).

Returns:
Depth

Definition at line 528 of file HTree.h.

template<class T>
uint32 HTreeNode< T >::GetCount (  void   )  const
 

Traverses the tree to count the number of nodes from the current node down.

Returns:
Number of nodes

Definition at line 546 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::GetFirst (  void   ) 
 

Returns the first (minimum value) node in this sub-tree.

Returns:
Left-most node in sub-tree

Definition at line 564 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::GetLast (  void   ) 
 

Returns the last (maximum value) node in this sub-tree.

Returns:
Right-most node in sub-tree

Definition at line 579 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::GetNext (  void   ) 
 

Returns the next node in ordered sequence

Returns:
ptr to next node, or NULL if at right-most node

Definition at line 594 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::GetPrev (  void   ) 
 

Returns the previous node in ordered sequence

Returns:
ptr to previous node, or NULL if at left-most node

Definition at line 620 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::GetRoot (  void   ) 
 

Returns the root node of the tree

Returns:
ptr to root node

Definition at line 646 of file HTree.h.

template<class T>
HTreeNodePtr HTreeNode< T >::Search (  T const &  data  ) 
 

Search the tree for a given node

Returns:
ptr to node or NULL if not found
Parameters:
data data to search for

Definition at line 662 of file HTree.h.

template<class T>
static int HTreeNode< T >::Compare (  const T &  t1,
const T &  t2
)  [static]
 

Helper function to compare two nodes in the tree.

Returns:
negative if t1 LT t2, zero if t1 EQ t2, or positive if t1 GT t2
Parameters:
t1 left node to compare
t2 right node to compare

Definition at line 684 of file HTree.h.

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

2006.01.09-16:37