12 #ifndef PRIORITY_QUEUE_HEAP_H
13 #define PRIORITY_QUEUE_HEAP_H
15 #include <sys/types.h>
28 template<
class T,
class Compare >
41 const T&
top ()
const;
62 template<
class T,
class Compare>
66 : m_curr (1), m_lwm (20)
68 trace(
"PriorityQueue_Heap::PriorityQueue_Heap");
72 template<
class T,
class Compare>
76 : m_comp (x_), m_curr (1), m_lwm (20)
81 template<
class T,
class Compare>
86 m_size = s_ > m_lwm ? s_ : m_lwm;
87 m_queue =
new T [m_size];
90 template<
class T,
class Compare>
94 : m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
101 template<
class T,
class Compare>
112 ::memcpy (m_queue, h_.
m_queue,
sizeof(T)*m_curr);
116 template<
class T,
class Compare>
124 template<
class T,
class Compare>
129 if (m_curr+1 == m_size)
132 m_queue [m_curr] = t_;
137 template<
class T,
class Compare>
145 while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
146 m_queue[k_] = m_queue[k_/2];
152 template<
class T,
class Compare>
158 m_queue[1] = m_queue[--m_curr];
161 if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
167 template<
class T,
class Compare>
172 return (
const T&) m_queue[1];
175 template<
class T,
class Compare>
183 while (k_ <= m_curr/2) {
185 if (j < m_curr && m_comp (m_queue[j+1], m_queue[j]))
187 if (m_comp (v, m_queue[j]))
189 m_queue[k_] = m_queue[j];
195 template<
class T,
class Compare>
202 for (i=1; i < m_curr; i++)
203 if (m_queue[i] == t_)
213 m_queue[i] = m_queue[m_curr];
219 template<
class T,
class Compare>
227 template<
class T,
class Compare>
232 if (m_size == newsz_)
235 T* new_chunk =
new T[newsz_];
236 ::memcpy (new_chunk, m_queue, m_curr *
sizeof(T));
243 template<
class T,
class Compare>
248 return m_queue[idx+1];
#define trace(s)
trace() is used to trace function call chain in C++ program.
Interface class that defines Implementor of the Bridge pattern.
PriorityQueue_Heap & operator=(const PriorityQueue_Heap &)
size_t m_curr
Array's size.
size_t m_size
Array of queued pointers.
size_t m_lwm
Next free slot in array.
PriorityQueue_Heap(size_t max_=0)
Class PriorityQueue_Impl.