GClasses
|
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 () | |
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< GPriorityQueueEntry > | m_entries |
PointerComparer | m_pCompareFunc |
void * | m_pThis |
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.)
GClasses::GPriorityQueue::GPriorityQueue | ( | PointerComparer | pCompareFunc, |
void * | pThis | ||
) |
GClasses::GPriorityQueue::~GPriorityQueue | ( | ) |
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.
std::vector<GPriorityQueueEntry> GClasses::GPriorityQueue::m_entries [protected] |
void* GClasses::GPriorityQueue::m_pThis [protected] |