GClasses
GClasses::GPriorityQueue Class Reference

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

#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< GPriorityQueueEntrym_entries
 
PointerComparer m_pCompareFunc
 
void * m_pThis
 

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