Lazy Collection of leftist heaps This version uses implicit deletion. More...

#include <LlheapSet.h>

Inheritance diagram for grafalgo::LlheapSet:

Collaboration diagram for grafalgo::LlheapSet:

Public Member Functions
	LlheapSet (int=26, delftyp=NULL)
	Constructor for the LlheapSet class.
	~LlheapSet ()
	Destructor for the LlheapSet class.
void	clear ()
	Remove all elements from heap.
void	resize (int)
	Resize a LlheapSet object.
void	expand (int)
	Expand the space available for this LlheapSet.
void	copyFrom (const LlheapSet &)
	Copy into LlheapSet from source.
index	findmin (lheap)
	Find the item with the smallest key in a heap.
lheap	lmeld (lheap, lheap)
	Perform a lazy meld on two heaps.
lheap	insert (index, lheap)
	Insert an item into a heap.
lheap	makeheap (List &)
	Buidl a heap from the items on a list.
string &	toString (string &) const
	Construct a string representation of this object.
string &	heap2string (index, string &) const
Private Member Functions
void	purge (lheap, List &)
	Remove "deleted nodes" from the top of a heap and construct a list of "sub-heaps" whose root nodes have not been deleted.
lheap	heapify (List &)
	Combine a list of heaps into a single heap.
string &	heap2string (index, bool, string &) const
void	makeSpace (int)
	Allocate and initialize space for LlheapSet.
void	freeSpace ()
	Free dynamic storage used by LlheapSet.
Private Attributes
int	dummy
	head of free dummy node list
delftyp	delf
	pointer to deleted function
List *	tmplst
	pointer to temporary list

Detailed Description

Lazy Collection of leftist heaps This version uses implicit deletion.

That is, the user provides a pointer to a function that accepts a single item argument and returns true if that item has been removed from a heap. Deleted items should not be re-inserted into another heap.

Definition at line 26 of file LlheapSet.h.

Constructor & Destructor Documentation

grafalgo::LlheapSet::LlheapSet	(	int	size = `26`,
		delftyp	f = `NULL`
	)

Constructor for the LlheapSet class.

Parameters:

size	is the number of items in the constructed object
delftyp	is pointer to a "deleted function" which takes a single item as its argment and returns true if that item should be considered deleted from the heap in which it is present

Definition at line 27 of file LlheapSet.cpp.

Here is the call graph for this function:

grafalgo::LlheapSet::~LlheapSet ( )

Destructor for the LlheapSet class.

Definition at line 32 of file LlheapSet.cpp.

Here is the call graph for this function:

Member Function Documentation

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

Remove all elements from heap.

Reimplemented from grafalgo::LheapSet.

Definition at line 86 of file LlheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Copy into LlheapSet from source.

Definition at line 54 of file LlheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Expand the space available for this LlheapSet.

Rebuilds old value in new space.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::LheapSet.

Definition at line 79 of file LlheapSet.cpp.

Here is the call graph for this function:

index grafalgo::LlheapSet::findmin ( lheap h )

Find the item with the smallest key in a heap.

Parameters:

h	is the canonical element of some heap

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

Definition at line 123 of file LlheapSet.cpp.

Here is the call graph for this function:

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

Free dynamic storage used by LlheapSet.

Reimplemented from grafalgo::LheapSet.

Definition at line 51 of file LlheapSet.cpp.

Here is the caller graph for this function:

lheap grafalgo::LlheapSet::heapify ( List & hlst ) [private]

Combine a list of heaps into a single heap.

Parameters:

hlst	is a list of heaps (more precisely, their canonical elements)

Returns:: the new heap obtained by combining all the heaps in the list into one heap

Definition at line 133 of file LlheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Insert an item into a heap.

Parameters:

i	is a singleton item
h	is the caonical element of some heap

Returns:: the canonical element of the heap obtained by inserting i into h

Reimplemented from grafalgo::LheapSet.

Definition at line 112 of file LlheapSet.cpp.

Here is the call graph for this function:

lheap grafalgo::LlheapSet::lmeld	(	lheap	h1,
		lheap	h2
	)

Perform a lazy meld on two heaps.

The lazy meld simply inserts a dummy node at the root of a new heap

Parameters:

h1	is the canonical element of a heap (the root node of its tree)
h2	is the canonical element of a heap

Returns:: the canonical element of the heap obtained by combining h1 and h2

Definition at line 100 of file LlheapSet.cpp.

lheap grafalgo::LlheapSet::makeheap ( List & hlst )

Buidl a heap from the items on a list.

Parameters:

hlst	is a list of singleton items (that is, single item heaps)

Returns:: the heap obtained by combining all the items into a single heap

Definition at line 168 of file LlheapSet.cpp.

Here is the call graph for this function:

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

Allocate and initialize space for LlheapSet.

Parameters:

size	is number of index values to provide space for

Reimplemented from grafalgo::LheapSet.

Definition at line 37 of file LlheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::LlheapSet::purge	(	lheap	h,
		List &	hlst
	)		`[private]`

Remove "deleted nodes" from the top of a heap and construct a list of "sub-heaps" whose root nodes have not been deleted.

This is a private helper function.

Parameters:

h	is the root of a "heap tree" is a list in which the result of the operation is returned; if h is a non-deleted node, it is removed and its children are purged.

Definition at line 150 of file LlheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

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

Resize a LlheapSet object.

The old value is discarded.

Parameters:

size	is the size of the resized object.

Reimplemented from grafalgo::LheapSet.

Definition at line 67 of file LlheapSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::LlheapSet::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

Reimplemented from grafalgo::LheapSet.

Definition at line 180 of file LlheapSet.cpp.

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

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

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation