GClasses::GPriorityQueue Class Reference

An implementation of a double-ended heap-based priority queue. (Note that the multimap STL class can also be used to implement a double-ended priority queue, but the STL does not currently provide a heap-based double-ended priority queue, which is asymptotically more efficient for insertions.) More...

#include <GPriorityQueue.h>

Public Member Functions
	GPriorityQueue (PointerComparer pCompareFunc, void *pThis)
	~GPriorityQueue ()
void	insert (void *pObj)
	Adds an item to the queue. More...
void *	maximum ()
	Returns the max item in the queue. More...
void *	minimum ()
	Returns the min item in the queue. More...
void	removeMax ()
	Removes the max item from the queue. More...
void	removeMin ()
	Removes the min item from the queue. More...
int	size ()
	Returns the number of items in the queue. More...

Static Public Member Functions
static void	test ()
	Performs unit tests for this class. Throws an exception if there is a failure. More...

Protected Member Functions
void	maxHeapBubbleDown (int index)
void	maxHeapBubbleUp (int index)
void	maxHeapSwap (int a, int b)
void	minHeapBubbleDown (int index)
void	minHeapBubbleUp (int index)
void	minHeapSwap (int a, int b)

Protected Attributes
std::vector< GPriorityQueueEntry >	m_entries
PointerComparer	m_pCompareFunc
void *	m_pThis

Detailed Description

An implementation of a double-ended heap-based priority queue. (Note that the multimap STL class can also be used to implement a double-ended priority queue, but the STL does not currently provide a heap-based double-ended priority queue, which is asymptotically more efficient for insertions.)

Constructor & Destructor Documentation

GClasses::GPriorityQueue::GPriorityQueue	(	PointerComparer	pCompareFunc,
		void *	pThis
	)

GClasses::GPriorityQueue::~GPriorityQueue

(

)

Member Function Documentation

void GClasses::GPriorityQueue::insert

(

void *

pObj

)

Adds an item to the queue.

void GClasses::GPriorityQueue::maxHeapBubbleDown ( int  index )

protected

void GClasses::GPriorityQueue::maxHeapBubbleUp ( int  index )

protected

void GClasses::GPriorityQueue::maxHeapSwap ( int  a, int  b  )

protected

void* GClasses::GPriorityQueue::maximum

(

)

Returns the max item in the queue.

void GClasses::GPriorityQueue::minHeapBubbleDown ( int  index )

protected

void GClasses::GPriorityQueue::minHeapBubbleUp ( int  index )

protected

void GClasses::GPriorityQueue::minHeapSwap ( int  a, int  b  )

protected

void* GClasses::GPriorityQueue::minimum

(

)

Returns the min item in the queue.

void GClasses::GPriorityQueue::removeMax

(

)

Removes the max item from the queue.

void GClasses::GPriorityQueue::removeMin

(

)

Removes the min item from the queue.

int GClasses::GPriorityQueue::size

(

)

Returns the number of items in the queue.

static void GClasses::GPriorityQueue::test ( )

static

Performs unit tests for this class. Throws an exception if there is a failure.

Member Data Documentation

std::vector<GPriorityQueueEntry> GClasses::GPriorityQueue::m_entries

protected

PointerComparer GClasses::GPriorityQueue::m_pCompareFunc

protected

void* GClasses::GPriorityQueue::m_pThis

protected