Pyrogenesis  trunk
Classes | Public Member Functions | Public Attributes | List of all members
PriorityQueueList< ID, R, H, CMP > Class Template Reference

Priority queue implemented as an unsorted array. More...

#include <PriorityQueue.h>

Classes

struct  Item
 

Public Member Functions

void push (const Item &item)
 
Itemfind (ID id)
 
void promote (ID id, R oldrank, R newrank, H newh)
 
Item pop ()
 
bool empty ()
 
size_t size ()
 
void clear ()
 

Public Attributes

std::vector< Itemm_List
 

Detailed Description

template<typename ID, typename R, typename H, typename CMP = std::less<R>>
class PriorityQueueList< ID, R, H, CMP >

Priority queue implemented as an unsorted array.

This means pop() is O(n), but push and promote are O(1), and n is typically small (average around 50-100 in some rough tests). It seems fractionally slower than a binary heap in optimised builds, but is much simpler and less susceptible to MSVC's painfully slow debug STL.

Member Function Documentation

template<typename ID , typename R , typename H , typename CMP = std::less<R>>
void PriorityQueueList< ID, R, H, CMP >::clear ( )
inline
template<typename ID , typename R , typename H , typename CMP = std::less<R>>
bool PriorityQueueList< ID, R, H, CMP >::empty ( )
inline
template<typename ID , typename R , typename H , typename CMP = std::less<R>>
Item* PriorityQueueList< ID, R, H, CMP >::find ( ID  id)
inline
template<typename ID , typename R , typename H , typename CMP = std::less<R>>
Item PriorityQueueList< ID, R, H, CMP >::pop ( )
inline
template<typename ID , typename R , typename H , typename CMP = std::less<R>>
void PriorityQueueList< ID, R, H, CMP >::promote ( ID  id,
R  oldrank,
R  newrank,
newh 
)
inline
template<typename ID , typename R , typename H , typename CMP = std::less<R>>
void PriorityQueueList< ID, R, H, CMP >::push ( const Item item)
inline
template<typename ID , typename R , typename H , typename CMP = std::less<R>>
size_t PriorityQueueList< ID, R, H, CMP >::size ( )
inline

Member Data Documentation

template<typename ID , typename R , typename H , typename CMP = std::less<R>>
std::vector<Item> PriorityQueueList< ID, R, H, CMP >::m_List

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