Data structure that represents a collection of leftist heaps. More...

#include <LheapSet.h>

Inheritance diagram for grafalgo::LheapSet:

Collaboration diagram for grafalgo::LheapSet:

Classes
struct	hnode
Public Member Functions
	LheapSet (int=100)
	Constructor for LheapSet class.
	~LheapSet ()
	Destructor for LheapSet class.
void	clear ()
	Remove all elements from heap.
void	resize (int)
	Resize a LheapSet object.
void	expand (int)
	Expand the space available for this LheapSet.
void	copyFrom (const LheapSet &)
	Copy into LheapSet from source.
keytyp	key (index) const
	Get the key of an item.
void	setkey (index, keytyp)
	Set the key of an item.
lheap	findmin (lheap) const
	Get the item with the smallest key in a heap.
lheap	meld (lheap, lheap)
	Combine two heaps.
lheap	insert (index, lheap)
	Insert a singleton item into a heap.
index	deletemin (lheap)
	Remove the item with smallest key from a heap.
string &	toString (string &) const
	Construct a string representation of this object.
string &	heap2string (lheap, string &) const
	Create a string representation of a single heap.
Protected Member Functions
string &	heap2string (lheap, bool, string &) const
	Recursive helper for constructing a string representation of a heap.
void	makeSpace (int)
	Allocate and initialize space for LheapSet.
void	freeSpace ()
	Free dynamic storage used by LheapSet.
Protected Attributes
struct grafalgo::LheapSet::hnode *	node

Detailed Description

Data structure that represents a collection of leftist heaps.

Heaps are defined on items (nodes) numbered 1..n, where n is specified at the time an object is constructed. Leftist heaps can be efficiently "melded"

Definition at line 26 of file LheapSet.h.

Constructor & Destructor Documentation

grafalgo::LheapSet::LheapSet ( int size = 100 )

Constructor for LheapSet class.

Parameters:

size	is the number of items in the constructed object

Definition at line 20 of file LheapSet.cpp.

Here is the call graph for this function:

grafalgo::LheapSet::~LheapSet ( )

Destructor for LheapSet class.

Definition at line 25 of file LheapSet.cpp.

Here is the call graph for this function:

Member Function Documentation

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

Remove all elements from heap.

Implements grafalgo::Adt.

Reimplemented in grafalgo::LlheapSet.

Definition at line 79 of file LheapSet.cpp.

Here is the caller graph for this function:

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

Copy into LheapSet from source.

Definition at line 47 of file LheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

index grafalgo::LheapSet::deletemin ( lheap 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 resulting heap

Definition at line 124 of file LheapSet.cpp.

Here is the call graph for this function:

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

Expand the space available for this LheapSet.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Reimplemented in grafalgo::LlheapSet.

Definition at line 72 of file LheapSet.cpp.

Here is the call graph for this function:

lheap grafalgo::LheapSet::findmin ( lheap h ) const [inline]

Get the item with the smallest key in a heap.

Parameters:

h	is the canonical element of some heap

Returns:: the index of the item in h with the smallest key

Definition at line 75 of file LheapSet.h.

void grafalgo::LheapSet::freeSpace ( ) [protected]

Free dynamic storage used by LheapSet.

Reimplemented in grafalgo::LlheapSet.

Definition at line 44 of file LheapSet.cpp.

Here is the caller graph for this function:

string & grafalgo::LheapSet::heap2string	(	lheap	h,
		string &	s
	)		const `[inline]`

Create a string representation of a single heap.

Parameters:

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

Returns:: s

Definition at line 82 of file LheapSet.h.

Here is the caller graph for this function:

string & grafalgo::LheapSet::heap2string	(	lheap	h,
		bool	isroot,
		string &	s
	)		const `[protected]`

Recursive helper for constructing a string representation of a heap.

Parameters:

h	is a node in one of the trees of the heap
isroot	is true if h is the canonical element of the heap
s	is a string in which the result is returned

Returns:: a reference to s

Definition at line 155 of file LheapSet.cpp.

Here is the call graph for this function:

lheap grafalgo::LheapSet::insert	(	index	i,
		lheap	h
	)

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

Reimplemented in grafalgo::LlheapSet.

Definition at line 114 of file LheapSet.cpp.

Here is the call graph for this function:

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

Get the key of an item.

Parameters:

i	is an item in a heap

Returns:: the key of i

Definition at line 63 of file LheapSet.h.

void grafalgo::LheapSet::makeSpace ( int size ) [protected]

Allocate and initialize space for LheapSet.

Parameters:

size	is number of index values to provide space for

Reimplemented in grafalgo::LlheapSet.

Definition at line 30 of file LheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

lheap grafalgo::LheapSet::meld	(	lheap	h1,
		lheap	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 92 of file LheapSet.cpp.

Here is the caller graph for this function:

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

Resize a LheapSet object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Reimplemented in grafalgo::LlheapSet.

Definition at line 60 of file LheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::LheapSet::setkey	(	index	i,
		keytyp	k
	)		`[inline]`

Set the key of an item.

Parameters:

i	is an item in a heap
k	is a new key value for i

Definition at line 69 of file LheapSet.h.

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

Construct 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.

Reimplemented in grafalgo::LlheapSet.

Definition at line 134 of file LheapSet.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/LheapSet.h
/Users/jst/src/grafalgo/cpp/dataStructures/heaps/LheapSet.cpp

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation