#include <HeapTreeType.H>

Inheritance diagram for HeapTreeType< HT_TYPE >:

Collaboration diagram for HeapTreeType< HT_TYPE >:

Public Member Functions
	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())

virtual void	deleteElements (void)

Protected Member Functions
void	swap (unsigned int one, unsigned int two)

Protected Attributes
int	unsortedCount

Private Member Functions
void	swapIfBigger (unsigned int index)

Private Attributes
float	base

Detailed Description

template<class HT_TYPE>
class HeapTreeType< HT_TYPE >

HeapTreeType for constant variables Implementation of a min. HeapTreeType 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.

Whilst this HeapTreeType 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.

A simplistic '<' is used for comparison and it is assumed that the HT_TYPE is capable of being compared in this way, e.g. when HT_TYPE in int.

Template Parameters

HT_TYPE the type of the HeapTreeType

Examples:: HeapTreeSort.C.

Definition at line 67 of file HeapTreeType.H.

Constructor & Destructor Documentation

◆ HeapTreeType()

template<class HT_TYPE>

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

inline

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

Definition at line 118 of file HeapTreeType.H.

Member Function Documentation

◆ add()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::add ( HT_TYPE value )

inline

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

Parameters

value The variable to add.

Definition at line 127 of file HeapTreeType.H.

◆ deleteElements()

template<class HT_TYPE>

virtual void HeapTreeType< HT_TYPE >::deleteElements ( void )

inlinevirtual

Delete reset the unsortedCount

Reimplemented in HeapTree< HT_TYPE >.

Definition at line 265 of file HeapTreeType.H.

Here is the caller graph for this function:

◆ dump()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::dump ( void )

inline

Run through the vector and output (to cout) the HT_TYPE tree element.

Definition at line 218 of file HeapTreeType.H.

◆ dumpDereference()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::dumpDereference ( )

inline

Run through the vector and output (to cout) the HT_TYPE tree element.

Definition at line 225 of file HeapTreeType.H.

◆ dumpLPR()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::dumpLPR ( HeapTreeCell & cell )

inline

Given a cell, dump to cout the children.

Definition at line 232 of file HeapTreeType.H.

◆ findCell() [1/2]

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::findCell	(	unsigned int	index,
		HeapTreeCell &	cell
	)

inline

Completes a cell, which instructs the layer and location within the layer of the HT_TYPE element at index.

Parameters

index	[in] The HT_TYPE element vector index to find the HeapTreeCell representation of.
cell	[out] The resulting 'tree co-ordinates' of the element at vectorial index.

Definition at line 151 of file HeapTreeType.H.

◆ findCell() [2/2]

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::findCell	(	HT_TYPE *	index,
		HeapTreeCell &	cell
	)

inline

Given an element, find the 'tree co-ordinate' location and store in cell

Parameters

[in]	index	The element to located the tree co-ordinates of
[out]	cell	The resulting 'tree co-ordinates' of the element at vectorial index.

Definition at line 159 of file HeapTreeType.H.

◆ findChildren()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::findChildren	(	unsigned int	parent,
		HeapTreeCell &	childL,
		HeapTreeCell &	childR
	)

inline

Given a parent's vector index, return the children't 'tree co-ordinatees'

Parameters

parent	The parent's vector index.
childL	The left child's level and level index.
childR	The right child's level and level index.

Definition at line 202 of file HeapTreeType.H.

Here is the caller graph for this function:

◆ findIndex()

template<class HT_TYPE>

unsigned int HeapTreeType< HT_TYPE >::findIndex ( HeapTreeCell & cell )

inline

Given 'tree co-ordinates', return the vector index.

Parameters

cell	Tree co-ordinates. The level and level index of the tree element.

Returns: The index in the vector matching the tree co-ordinates.

Definition at line 176 of file HeapTreeType.H.

Here is the caller graph for this function:

◆ findParent()

template<class HT_TYPE>

unsigned int HeapTreeType< HT_TYPE >::findParent ( unsigned int index )

inline

Given a child's index, return the parent's index.

Parameters

index The child's index

Returns: The parent's index

Definition at line 185 of file HeapTreeType.H.

Here is the caller graph for this function:

◆ resize()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::resize	(	size_t	s,
		HT_TYPE	c = `HT_TYPE()`
	)

inline

Calls the vector<HT_TYPE>::resize method.

Definition at line 259 of file HeapTreeType.H.

◆ sort()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::sort ( void )

inline

Sort a HeapTreeType using the sort algorithm.

Definition at line 245 of file HeapTreeType.H.

◆ swap()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::swap	(	unsigned int	one,
		unsigned int	two
	)

inlineprotected

Swap two elements in the heap tree.

Parameters

one	The index of the one to swap with two.
two	The index of the two to swap with one.

Definition at line 110 of file HeapTreeType.H.

Here is the caller graph for this function:

◆ swapIfBigger()

template<class HT_TYPE>

void HeapTreeType< HT_TYPE >::swapIfBigger ( unsigned int index )

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.

Definition at line 75 of file HeapTreeType.H.

Member Data Documentation

◆ base

template<class HT_TYPE>

float HeapTreeType< HT_TYPE >::base

private

Definition at line 68 of file HeapTreeType.H.

◆ unsortedCount

template<class HT_TYPE>

int HeapTreeType< HT_TYPE >::unsortedCount

protected

Definition at line 104 of file HeapTreeType.H.

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

/tmp/gtkiostream/include/mffm/HeapTreeType.H

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

template<class HT_TYPE> class HeapTreeType< HT_TYPE >

Constructor & Destructor Documentation

◆ HeapTreeType()

Member Function Documentation

◆ add()

◆ deleteElements()

◆ dump()

◆ dumpDereference()

◆ dumpLPR()

◆ findCell() [1/2]

◆ findCell() [2/2]

◆ findChildren()

◆ findIndex()

◆ findParent()

◆ resize()

◆ sort()

◆ swap()

◆ swapIfBigger()

Member Data Documentation

◆ base

◆ unsortedCount

template<class HT_TYPE>
class HeapTreeType< HT_TYPE >