HeapTree< HT_TYPE > Class Template Reference

#include <HeapTree.H>

Inheritance diagram for HeapTree< HT_TYPE >:

Collaboration diagram for HeapTree< HT_TYPE >:

Public Member Functions
	HeapTree (int baseIn=2)
	Constructor - currrently only supports baseIn=2 : to be expanded in the future. More...
void	add (HT_TYPE *value, HTCompareMethod compare)
void	sort (HTCompareMethod compare)
void	sort (LinkList< HT_TYPE *> &ll, HTCompareMethod compare)
void	deleteElements (void)
Public Member Functions inherited from HeapTreeType< HT_TYPE *>
	HeapTreeType (int baseIn=2)
	Constructor - currrently only supports baseIn=2 : to be expanded in the future. More...
void	add (HT_TYPE * value)
void	findCell (unsigned int index, HeapTreeCell &cell)
void	findCell (HT_TYPE * *index, HeapTreeCell &cell)
unsigned int	findIndex (HeapTreeCell &cell)
unsigned int	findParent (unsigned int index)
void	findChildren (unsigned int parent, HeapTreeCell &childL, HeapTreeCell &childR)
void	dump ()
void	dumpDereference ()
void	dumpLPR (HeapTreeCell &cell)
void	sort (void)
void	resize (size_t s, HT_TYPE * c=HT_TYPE *())

Private Types
typedef int(HT_TYPE::*	HTCompareMethod) (const HT_TYPE &) const

Private Member Functions
void	swapIfBigger (unsigned int index, HTCompareMethod compare)

Additional Inherited Members
Protected Member Functions inherited from HeapTreeType< HT_TYPE *>
void	swap (unsigned int one, unsigned int two)
Protected Attributes inherited from HeapTreeType< HT_TYPE *>
int	unsortedCount

Detailed Description

template<class HT_TYPE>
class HeapTree< HT_TYPE >

HeapTree Implementation of a min. HeapTree with an included sort method. It obeys the following properties : shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right. heap property: each node is greater than or equal to each of its children according to a comparison predicate 'compare' defined for the data structure. In this case, the 'compare' predicate defines a minimum heap tree (smallest at the top).

Whilst this HeapTree inherits from vector, certain operators can not be exposed to the user, consequently inheritance is protected.

A concept for expansion to non-binary heap trees is sought in the future, it is currently not supported.

Template Parameters

HT_TYPE

the type of the HeapTree

Examples:

HeapTreeSort.C.

Definition at line 36 of file HeapTree.H.

Member Typedef Documentation

HTCompareMethod

template<class HT_TYPE>

typedef int(HT_TYPE::* HeapTree< HT_TYPE >::HTCompareMethod) (const HT_TYPE &) const

private

The comparison typedefinition Assumes HT_TYPE is a pointer type.

Definition at line 40 of file HeapTree.H.

Constructor & Destructor Documentation

HeapTree()

template<class HT_TYPE>

HeapTree< HT_TYPE >::HeapTree ( int  baseIn = 2 )

inline

Constructor - currrently only supports baseIn=2 : to be expanded in the future.

Definition at line 89 of file HeapTree.H.

Member Function Documentation

add()

template<class HT_TYPE>

void HeapTree< HT_TYPE >::add ( HT_TYPE *  value, HTCompareMethod  compare  )

inline

HeapTree add, which ensures that both shape and heap properties are satisfied.

Parameters

value	The variable to add.
compare	The comparison predicate. If NULL, use the '<' logical operator. If compare!=NULL, assume HT_TYPE is a pointer type and evaluate (*parent).compare(*child)

Definition at line 97 of file HeapTree.H.

Here is the call graph for this function:

Here is the caller graph for this function:

deleteElements()

template<class HT_TYPE>

void HeapTree< HT_TYPE >::deleteElements ( void  )

inlinevirtual

Delete the pointers in the vector

Reimplemented from HeapTreeType< HT_TYPE *>.

Definition at line 152 of file HeapTree.H.

Here is the call graph for this function:

sort() [1/2]

template<class HT_TYPE>

void HeapTree< HT_TYPE >::sort ( HTCompareMethod  compare )

inline

Sort a HeapTree using the bubble sort algorithm.

Parameters

compare

The comparison predicate. If NULL, use the '<' logical operator. If compare!=NULL, assume HT_TYPE is a pointer type and evaluate (*parent).compare(*child)

Definition at line 120 of file HeapTree.H.

Here is the call graph for this function:

sort() [2/2]

template<class HT_TYPE>

void HeapTree< HT_TYPE >::sort ( LinkList< HT_TYPE *> &  ll, HTCompareMethod  compare  )

inline

convenience method to sort a LinkList The HT_TYPE::compare method must exist and be valid. Returns the same ll, with members sorted.

Parameters

ll	A LinkList with members to sort.
compare	The comparison method to execute during evaluation.

Definition at line 139 of file HeapTree.H.

Here is the call graph for this function:

swapIfBigger()

template<class HT_TYPE>

void HeapTree< HT_TYPE >::swapIfBigger ( unsigned int  index, HTCompareMethod  compare  )

inlineprivate

Swaps the parent with it's children. If the parent evaluates to be bigger then it's child, then swap the parent and child. If both children are smaller, find the smallest child and swap with the parent.

Parameters

index	The index of the parent for evaluation.
compare	The comparison predicate. If NULL, use the '<' logical operator. If compare!=NULL, assume HT_TYPE is a pointer type and evaluate (*parent).compare(*child)

Definition at line 48 of file HeapTree.H.

Here is the call graph for this function:

Here is the caller graph for this function:

---

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

• /tmp/gtkiostream/include/mffm/HeapTree.H