FibonacciHeapNode< Data, Key > Class Template Reference

A template Fibonacci heap node class. More...

#include <FiboHeap.hpp>

Public Member Functions
Key	key () const
	Return node's key. More...
Data	data () const
	Return node's data. More...

Private Member Functions
	FibonacciHeapNode ()
	Default constructor. More...
	FibonacciHeapNode (Data d, Key k)
	Constructor. More...
bool	isSingle () const
	Check if the node is single. More...
void	insert (FibonacciHeapNode< Data, Key > *other)
	Inserts a new node after this node. More...
void	remove ()
	Removes the node from the list. More...
void	addChild (FibonacciHeapNode< Data, Key > *other)
	Add a child to the node. More...
void	removeChild (FibonacciHeapNode< Data, Key > *other)
	Remove a child node. More...
void	printTree (ostream &out) const
	Print the tree of nodes starting from the current one acting as the root. More...
void	printAll (ostream &out) const
	Print every tree of nodes on the same level as the current one. More...

Private Attributes
Key	myKey
	key associated to the node More...
Data	myData
	data stored in the node More...
uint	degree
	number of children. used in the deletemin algorithm. More...
bool	mark
	mark used in the decreaseKey algorithm. More...
FibonacciHeapNode< Data, Key > *	previous
	pointer to the previous node More...
FibonacciHeapNode< Data, Key > *	next
	pointer to the next node More...
FibonacciHeapNode< Data, Key > *	child
	pointer to the first child in the list of children More...
FibonacciHeapNode< Data, Key > *	parent
	pointer to the parent More...

Friends
template<typename D , typename K >
class	FibonacciHeap
ostream &	operator<< (ostream &out, const FibonacciHeapNode &n)
	Overload of '<<'. More...

Detailed Description

template<typename Data, typename Key>
class FibonacciHeapNode< Data, Key >

A template Fibonacci heap node class.

Nodes used by the Fibonacci heap data structure, implemented in a circular doubly linked list.

Constructor & Destructor Documentation

template<typename Data, typename Key>

FibonacciHeapNode< Data, Key >::FibonacciHeapNode ( )

inlineprivate

Default constructor.

template<typename Data, typename Key>

FibonacciHeapNode< Data, Key >::FibonacciHeapNode ( Data  d, Key  k  )

inlineprivate

Constructor.

Parameters

d	the data stored in the node
k	the key associated to data

Member Function Documentation

template<typename Data, typename Key>

void FibonacciHeapNode< Data, Key >::addChild ( FibonacciHeapNode< Data, Key > *  other )

inlineprivate

Add a child to the node.

Fibonacci-Heap-Link(other,current) operatation.

Parameters

other

a child node to link to the current one

template<typename Data, typename Key>

Data FibonacciHeapNode< Data, Key >::data ( ) const

inline

Return node's data.

Returns

data

template<typename Data, typename Key>

void FibonacciHeapNode< Data, Key >::insert ( FibonacciHeapNode< Data, Key > *  other )

inlineprivate

Inserts a new node after this node.

For example: given 1->2->3->4->1, insert a->b->c->d->a after node 3: result: 1->2->3->a->b->c->d->4->1

template<typename Data, typename Key>

bool FibonacciHeapNode< Data, Key >::isSingle ( ) const

inlineprivate

Check if the node is single.

Returns

true if the node is single, false otherwise

template<typename Data, typename Key>

Key FibonacciHeapNode< Data, Key >::key ( ) const

inline

Return node's key.

Returns

key

template<typename Data, typename Key>

void FibonacciHeapNode< Data, Key >::printAll ( ostream &  out ) const

inlineprivate

Print every tree of nodes on the same level as the current one.

Parameters

out	an output stream

template<typename Data, typename Key>

void FibonacciHeapNode< Data, Key >::printTree ( ostream &  out ) const

inlineprivate

Print the tree of nodes starting from the current one acting as the root.

Parameters

out	an output stream

template<typename Data, typename Key>

void FibonacciHeapNode< Data, Key >::remove ( )

inlineprivate

Removes the node from the list.

template<typename Data, typename Key>

void FibonacciHeapNode< Data, Key >::removeChild ( FibonacciHeapNode< Data, Key > *  other )

inlineprivate

Remove a child node.

Parameters

other

a child node to remove from current one

Friends And Related Function Documentation

template<typename Data, typename Key>

template<typename D , typename K >

friend class FibonacciHeap

friend

template<typename Data, typename Key>

ostream& operator<< ( ostream &  out, const FibonacciHeapNode< Data, Key > &  n  )

friend

Overload of '<<'.

Parameters

out	an output stream
n	a Fibonacci node

Returns

an output stream

Member Data Documentation

template<typename Data, typename Key>

FibonacciHeapNode<Data,Key>* FibonacciHeapNode< Data, Key >::child

private

pointer to the first child in the list of children

template<typename Data, typename Key>

uint FibonacciHeapNode< Data, Key >::degree

private

number of children. used in the deletemin algorithm.

template<typename Data, typename Key>

bool FibonacciHeapNode< Data, Key >::mark

private

mark used in the decreaseKey algorithm.

template<typename Data, typename Key>

Data FibonacciHeapNode< Data, Key >::myData

private

data stored in the node

template<typename Data, typename Key>

Key FibonacciHeapNode< Data, Key >::myKey

private

key associated to the node

template<typename Data, typename Key>

FibonacciHeapNode<Data,Key>* FibonacciHeapNode< Data, Key >::next

private

pointer to the next node

template<typename Data, typename Key>

FibonacciHeapNode<Data,Key>* FibonacciHeapNode< Data, Key >::parent

private

pointer to the parent

template<typename Data, typename Key>

FibonacciHeapNode<Data,Key>* FibonacciHeapNode< Data, Key >::previous

private

pointer to the previous node

---

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

• /home/johan/Documents/UNamur/VirtualBelgium/Workspace/VirtualBelgium/include/FiboHeap.hpp