GClasses

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>

List of all members.

Public Member Functions

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

Static Public Member Functions

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

Protected Member Functions

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

Protected Attributes

std::vector< GPriorityQueueEntrym_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