The FheapSet class represents a collection of Fibonacci heaps. More...

#include <FheapSet.h>

Inheritance diagram for grafalgo::FheapSet:

Collaboration diagram for grafalgo::FheapSet:

Classes
struct	Fnode
Public Member Functions
	FheapSet (int=26)
	Constructor for FheapSet class.
	~FheapSet ()
	Destructor for FheapSet class.
void	clear ()
	Convert all heaps to singletons.
void	resize (int)
	Resize a FheapSet object.
void	expand (int)
	Expand the space available for this FheapSet.
void	copyFrom (const FheapSet &)
	Copy into FheapSet from source.
keytyp	key (index) const
	Get the key of an item in a heap.
void	setKey (index, keytyp)
	Set the key of a singleton item.
fheap	findmin (fheap) const
	Find the item with smallest key in a heap.
fheap	meld (fheap, fheap)
	Combine two heaps.
fheap	decreasekey (index, keytyp, fheap)
	Decrease the key of some item.
fheap	deletemin (fheap)
	Remove the item with smallest key from a heap.
fheap	insert (index, fheap)
	Insert an item into a heap.
fheap	insert (index, fheap, keytyp)
	Insert a singleton item into a heap.
fheap	remove (index, fheap)
	Remove an item from a heap.
string &	toString (string &) const
	Create a string representation of this object.
string &	heap2string (fheap, string &) const
	Create a string representation of a heap.
Private Member Functions
string &	heap2string (fheap, bool, string &) const
void	makeSpace (int)
	Allocate and initialize space for FheapSet.
void	freeSpace ()
	Free dynamic storage used by FheapSet.
Private Attributes
Fnode *	node
	node[u] contains fields for node u
ClistSet *	sibs
	collection of sibling lists
int	rvec [MAXRANK+1]
	temporary vector of ranks
List *	tmpq
	temporary queue used
Static Private Attributes
static const int	MAXRANK = 32

Detailed Description

The FheapSet class represents a collection of Fibonacci heaps.

The heaps are defined over nodes numbered 1..n where n is specified when the object is constructed. Each node is in one heap at a time.

Definition at line 27 of file FheapSet.h.

Constructor & Destructor Documentation

grafalgo::FheapSet::FheapSet ( int size = 26 )

Constructor for FheapSet class.

Parameters:

size	is the number of items in the constructed object

Definition at line 23 of file FheapSet.cpp.

Here is the call graph for this function:

grafalgo::FheapSet::~FheapSet ( )

Destructor for FheapSet class.

Definition at line 26 of file FheapSet.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::FheapSet::clear ( ) [virtual]

Convert all heaps to singletons.

Implements grafalgo::Adt.

Definition at line 88 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::FheapSet::copyFrom ( const FheapSet & source )

Copy into FheapSet from source.

Definition at line 50 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

fheap grafalgo::FheapSet::decreasekey	(	index	i,
		keytyp	delta,
		fheap	h
	)

Decrease the key of some item.

Parameters:

i	is the index of an item in some heap
delta	is an increment to be subtracted from the key of i
h	is the heap containing i

Returns:: the canonical element of the heap that results from reducing i's key by delta

Definition at line 130 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

fheap grafalgo::FheapSet::deletemin ( fheap h )

Remove the item with smallest key from a heap.

Parameters:

h	is the canonical element of some heap

Returns:: the canonical element of the heap that results from removing the item with the smallest key

Definition at line 151 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::FheapSet::expand ( int size ) [virtual]

Expand the space available for this FheapSet.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 81 of file FheapSet.cpp.

Here is the call graph for this function:

fheap grafalgo::FheapSet::findmin ( fheap h ) const [inline]

Find the item with smallest key in a heap.

Parameters:

h	is the canonical element of some heap

Returns:: the the index of item in h that has the smallest key

Definition at line 92 of file FheapSet.h.

void grafalgo::FheapSet::freeSpace ( ) [private]

Free dynamic storage used by FheapSet.

Definition at line 47 of file FheapSet.cpp.

Here is the caller graph for this function:

string & grafalgo::FheapSet::heap2string	(	fheap	h,
		string &	s
	)		const

Create a string representation of a heap.

Parameters:

h	is the canonical element of some heap
s	is a string in which the result is returned

Returns:: a reference to s

Definition at line 247 of file FheapSet.cpp.

Here is the caller graph for this function:

fheap grafalgo::FheapSet::insert	(	index	i,
		fheap	h
	)		`[inline]`

Insert an item into a heap.

Parameters:

i	is the index of a singleton item.

Returns:: the key of i

Definition at line 86 of file FheapSet.h.

Here is the call graph for this function:

fheap grafalgo::FheapSet::insert	(	index	i,
		fheap	h,
		keytyp	x
	)

Insert a singleton item into a heap.

Parameters:

i	is a singleton item
h	is the canonical element of a heap
x	is key value under which i is to be inserted

Returns:: the canonical element of the heap that results from inserting i into h

Definition at line 117 of file FheapSet.cpp.

Here is the call graph for this function:

keytyp grafalgo::FheapSet::key ( index i ) const [inline]

Get the key of an item in a heap.

Parameters:

i	is the index of an item in some heap

Returns:: the key of i

Definition at line 71 of file FheapSet.h.

Here is the caller graph for this function:

void grafalgo::FheapSet::makeSpace ( int size ) [private]

Allocate and initialize space for FheapSet.

Parameters:

size	is number of index values to provide space for

Definition at line 31 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

fheap grafalgo::FheapSet::meld	(	fheap	h1,
		fheap	h2
	)

Combine two heaps.

Parameters:

h1	is the canonical element of a heap
h2	is the canonical element of a heap
return	the canonical element of the heap obtained by combining h1 and h2

Definition at line 102 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

fheap grafalgo::FheapSet::remove	(	index	i,
		fheap	h
	)

Remove an item from a heap.

Parameters:

i	is the index of an item in some heap
h	is the canonical element of the heap containing i

Returns:: the heap that results from removing i from h

Definition at line 205 of file FheapSet.cpp.

Here is the call graph for this function:

void grafalgo::FheapSet::resize ( int size ) [virtual]

Resize a FheapSet object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 69 of file FheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::FheapSet::setKey	(	index	i,
		keytyp	k
	)		`[inline]`

Set the key of a singleton item.

Parameters:

i	is the index of a singleton item.

Returns:: the key of i

Definition at line 77 of file FheapSet.h.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::FheapSet::toString ( string & s ) const [virtual]

Create a string representation of this object.

Parameters:

s	is a string in which the result is returned

Returns:: a reference to s

Implements grafalgo::Adt.

Definition at line 219 of file FheapSet.cpp.

Here is the call graph for this function:

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

/Users/jst/src/grafalgo/cpp/include/FheapSet.h
/Users/jst/src/grafalgo/cpp/dataStructures/heaps/FheapSet.cpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation