#include <PriorityQueue_Heap.h>
Public Member Functions | |
PriorityQueue_Heap (size_t max_=0) | |
PriorityQueue_Heap (size_t, const Compare &) | |
PriorityQueue_Heap (const PriorityQueue_Heap &) | |
~PriorityQueue_Heap () | |
PriorityQueue_Heap & | operator= (const PriorityQueue_Heap &) |
void | insert (const T &) |
T | pop () |
const T & | top () const |
bool | remove (T) |
size_t | size () |
T & | operator[] (int idx) |
Protected Member Functions | |
void | upheap (size_t) |
void | downheap (size_t) |
bool | resize (size_t) |
Protected Attributes | |
Compare | m_comp |
Private Member Functions | |
void | allocate (size_t) |
Private Attributes | |
T * | m_queue |
size_t | m_size |
Array of queued pointers. | |
size_t | m_curr |
Array's size. | |
size_t | m_lwm |
Next free slot in array. |
Definition at line 29 of file PriorityQueue_Heap.h.
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap | ( | size_t | max_ = 0 |
) | [inline] |
Definition at line 65 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::allocate(), and trace.
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap | ( | size_t | maxsz_, | |
const Compare & | x_ | |||
) | [inline] |
Definition at line 75 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::allocate().
ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap | ( | const PriorityQueue_Heap< T, Compare > & | h_ | ) | [inline] |
ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap | ( | ) | [inline] |
Definition at line 119 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_queue.
00120 { 00121 delete [] m_queue; 00122 }
void ASSA::PriorityQueue_Heap< T, Compare >::allocate | ( | size_t | s_ | ) | [inline, private] |
Definition at line 84 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_lwm, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, and ASSA::PriorityQueue_Heap< T, Compare >::m_size.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::operator=(), and ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap().
void ASSA::PriorityQueue_Heap< T, Compare >::downheap | ( | size_t | k_ | ) | [inline, protected] |
Definition at line 178 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_comp, ASSA::PriorityQueue_Heap< T, Compare >::m_curr, and ASSA::PriorityQueue_Heap< T, Compare >::m_queue.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::pop(), and ASSA::PriorityQueue_Heap< T, Compare >::remove().
00179 { 00180 register size_t j; 00181 T v = m_queue[k_]; 00182 00183 while (k_ <= m_curr/2) { 00184 j = 2*k_; 00185 if (j < m_curr && m_comp (m_queue[j+1], m_queue[j])) 00186 j++; 00187 if (m_comp (v, m_queue[j])) 00188 break; 00189 m_queue[k_] = m_queue[j]; 00190 k_ = j; 00191 } 00192 m_queue[k_] = v; 00193 }
void ASSA::PriorityQueue_Heap< T, Compare >::insert | ( | const T & | t_ | ) | [inline, virtual] |
Implements ASSA::PriorityQueue_Impl< T, Compare >.
Definition at line 127 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_curr, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, ASSA::PriorityQueue_Heap< T, Compare >::m_size, ASSA::PriorityQueue_Heap< T, Compare >::resize(), and ASSA::PriorityQueue_Heap< T, Compare >::upheap().
PriorityQueue_Heap< T, Compare > & ASSA::PriorityQueue_Heap< T, Compare >::operator= | ( | const PriorityQueue_Heap< T, Compare > & | h_ | ) | [inline] |
Definition at line 104 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::m_comp, ASSA::PriorityQueue_Heap< T, Compare >::m_curr, ASSA::PriorityQueue_Heap< T, Compare >::m_lwm, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, and ASSA::PriorityQueue_Heap< T, Compare >::m_size.
T & ASSA::PriorityQueue_Heap< T, Compare >::operator[] | ( | int | idx | ) | [inline, virtual] |
Implements ASSA::PriorityQueue_Impl< T, Compare >.
Definition at line 246 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_queue.
00247 { 00248 return m_queue[idx+1]; 00249 }
T ASSA::PriorityQueue_Heap< T, Compare >::pop | ( | ) | [inline, virtual] |
Implements ASSA::PriorityQueue_Impl< T, Compare >.
Definition at line 155 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::m_curr, ASSA::PriorityQueue_Heap< T, Compare >::m_lwm, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, ASSA::PriorityQueue_Heap< T, Compare >::m_size, and ASSA::PriorityQueue_Heap< T, Compare >::resize().
bool ASSA::PriorityQueue_Heap< T, Compare >::remove | ( | T | t_ | ) | [inline, virtual] |
Implements ASSA::PriorityQueue_Impl< T, Compare >.
Definition at line 198 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::m_curr, and ASSA::PriorityQueue_Heap< T, Compare >::m_queue.
00199 { 00200 register size_t i; 00201 00202 for (i=1; i < m_curr; i++) 00203 if (m_queue[i] == t_) 00204 break; 00205 00206 if (i == m_curr) // not found 00207 return false; 00208 00209 m_curr--; 00210 if (i == m_curr) // last element in queue 00211 return true; 00212 00213 m_queue[i] = m_queue[m_curr]; 00214 downheap (i); 00215 00216 return true; 00217 }
bool ASSA::PriorityQueue_Heap< T, Compare >::resize | ( | size_t | newsz_ | ) | [inline, protected] |
Definition at line 230 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_curr, ASSA::PriorityQueue_Heap< T, Compare >::m_queue, and ASSA::PriorityQueue_Heap< T, Compare >::m_size.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::insert(), and ASSA::PriorityQueue_Heap< T, Compare >::pop().
size_t ASSA::PriorityQueue_Heap< T, Compare >::size | ( | ) | [inline, virtual] |
Implements ASSA::PriorityQueue_Impl< T, Compare >.
Definition at line 222 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_curr.
00223 { 00224 return m_curr-1; 00225 }
const T & ASSA::PriorityQueue_Heap< T, Compare >::top | ( | ) | const [inline, virtual] |
Implements ASSA::PriorityQueue_Impl< T, Compare >.
Definition at line 170 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_queue.
00171 { 00172 return (const T&) m_queue[1]; 00173 }
void ASSA::PriorityQueue_Heap< T, Compare >::upheap | ( | size_t | k_ | ) | [inline, protected] |
Definition at line 140 of file PriorityQueue_Heap.h.
References ASSA::PriorityQueue_Heap< T, Compare >::m_comp, and ASSA::PriorityQueue_Heap< T, Compare >::m_queue.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::insert().
Compare ASSA::PriorityQueue_Heap< T, Compare >::m_comp [protected] |
Definition at line 51 of file PriorityQueue_Heap.h.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), and ASSA::PriorityQueue_Heap< T, Compare >::upheap().
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_curr [private] |
Array's size.
Definition at line 58 of file PriorityQueue_Heap.h.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::insert(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), ASSA::PriorityQueue_Heap< T, Compare >::pop(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), ASSA::PriorityQueue_Heap< T, Compare >::remove(), ASSA::PriorityQueue_Heap< T, Compare >::resize(), and ASSA::PriorityQueue_Heap< T, Compare >::size().
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_lwm [private] |
Next free slot in array.
Definition at line 59 of file PriorityQueue_Heap.h.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), and ASSA::PriorityQueue_Heap< T, Compare >::pop().
T* ASSA::PriorityQueue_Heap< T, Compare >::m_queue [private] |
Definition at line 56 of file PriorityQueue_Heap.h.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::downheap(), ASSA::PriorityQueue_Heap< T, Compare >::insert(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), ASSA::PriorityQueue_Heap< T, Compare >::operator[](), ASSA::PriorityQueue_Heap< T, Compare >::pop(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), ASSA::PriorityQueue_Heap< T, Compare >::remove(), ASSA::PriorityQueue_Heap< T, Compare >::resize(), ASSA::PriorityQueue_Heap< T, Compare >::top(), ASSA::PriorityQueue_Heap< T, Compare >::upheap(), and ASSA::PriorityQueue_Heap< T, Compare >::~PriorityQueue_Heap().
size_t ASSA::PriorityQueue_Heap< T, Compare >::m_size [private] |
Array of queued pointers.
Definition at line 57 of file PriorityQueue_Heap.h.
Referenced by ASSA::PriorityQueue_Heap< T, Compare >::allocate(), ASSA::PriorityQueue_Heap< T, Compare >::insert(), ASSA::PriorityQueue_Heap< T, Compare >::operator=(), ASSA::PriorityQueue_Heap< T, Compare >::pop(), ASSA::PriorityQueue_Heap< T, Compare >::PriorityQueue_Heap(), and ASSA::PriorityQueue_Heap< T, Compare >::resize().