#include <PriorityQueue.h>
Public Types | |
| typedef std::list< Element > | ElementList |
| typedef ElementList::iterator | ElementListIterator |
|
typedef std::pair< ElementListIterator, int > | QueuePosition |
Public Member Functions | |
Constructors - Destructor | |
| PriorityQueue (unsigned _size=2000, double _inc_max=3) | |
| Constructs an empty priority queue. | |
| ~PriorityQueue () | |
| Destructs the priority queue. | |
Access/Modif the queue | |
| bool | empty () const |
| True if the queue is empty. | |
| QueuePosition | push (const Element &e, double t) |
| Adds e to the queue, with a priority t, return the position where the elt has been inserted. | |
| void | pop () |
| Remove the element with the lowest priority. | |
| const Element & | top () |
| Returns the element with the lowest priority. | |
| QueuePosition | increase_priority (const Element &e, QueuePosition &pos, double t_new) |
| Increases to t_new the priority of the element e. | |
| void | clear () |
| Clear the queue, remove all elements. | |
| unsigned | size () const |
| Number of elements in the queue. | |
| void | print () const |
| print the queue for debugging purpose | |
Implementation of a priority queue containing elements of type Elements. Complexity of insertion and removal in O(1) thanks to an untidy priority queue implementation. see for more details "O(N) Implementation of the Fast Marching Algorithm" - Liron Yatziv, Alberto Bartesaghi, Guillermo Sapiro
The only constraint is that you have to insert elements in the queue with priority :
Definition at line 32 of file PriorityQueue.h.
| PriorityQueue | ( | unsigned | _size = 2000, |
|
| double | _inc_max = 3 | |||
| ) | [inline] |
Constructs an empty priority queue.
| _size | number of quantization level of the priority |
| _inc_max | max increment over the minimal point in the queue |
Definition at line 96 of file PriorityQueue.h.
00097 : m_size(_size), m_t0(0), m_i0(0), m_nb_elem(0),m_inc_max(_inc_max) 00098 { 00099 m_tab = new ElementList[_size]; 00100 m_delta = _inc_max / static_cast<double>(_size); 00101 }