00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef PRIORITY_QUEUE_HEAP_H
00013 #define PRIORITY_QUEUE_HEAP_H
00014
00015 #include <sys/types.h>
00016 #include <string.h>
00017
00018 #include "assa/PriorityQueue_Impl.h"
00019
00020 namespace ASSA {
00021
00028 template< class T, class Compare >
00029 class PriorityQueue_Heap : public PriorityQueue_Impl< T, Compare >
00030 {
00031 public:
00032 PriorityQueue_Heap (size_t max_ = 0);
00033 PriorityQueue_Heap (size_t, const Compare&);
00034 PriorityQueue_Heap (const PriorityQueue_Heap&);
00035 ~PriorityQueue_Heap ();
00036
00037 PriorityQueue_Heap& operator= (const PriorityQueue_Heap&);
00038
00039 void insert (const T&);
00040 T pop ();
00041 const T& top () const;
00042 bool remove (T);
00043 size_t size ();
00044 T& operator[] (int idx);
00045
00046 protected:
00047 void upheap (size_t);
00048 void downheap (size_t);
00049 bool resize (size_t);
00050
00051 Compare m_comp;
00052
00053 private:
00054 void allocate (size_t);
00055
00056 T* m_queue;
00057 size_t m_size;
00058 size_t m_curr;
00059 size_t m_lwm;
00060 };
00061
00062 template< class T, class Compare>
00063 inline
00064 PriorityQueue_Heap<T, Compare>::
00065 PriorityQueue_Heap (size_t maxsz_)
00066 : m_curr (1), m_lwm (20)
00067 {
00068 trace("PriorityQueue_Heap::PriorityQueue_Heap");
00069 allocate (maxsz_);
00070 }
00071
00072 template< class T, class Compare>
00073 inline
00074 PriorityQueue_Heap<T, Compare>::
00075 PriorityQueue_Heap (size_t maxsz_, const Compare& x_)
00076 : m_comp (x_), m_curr (1), m_lwm (20)
00077 {
00078 allocate (maxsz_);
00079 }
00080
00081 template< class T, class Compare>
00082 inline void
00083 PriorityQueue_Heap<T, Compare>::
00084 allocate (size_t s_)
00085 {
00086 m_size = s_ > m_lwm ? s_ : m_lwm;
00087 m_queue = new T [m_size];
00088 }
00089
00090 template< class T, class Compare>
00091 inline
00092 PriorityQueue_Heap<T, Compare>::
00093 PriorityQueue_Heap (const PriorityQueue_Heap& h_)
00094 : m_comp (h_.m_comp), m_size (h_.m_size), m_curr (h_.m_curr),
00095 m_lwm (h_.m_lwm)
00096 {
00097 allocate (m_size);
00098 ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
00099 }
00100
00101 template< class T, class Compare>
00102 PriorityQueue_Heap<T, Compare>&
00103 PriorityQueue_Heap<T, Compare>::
00104 operator= (const PriorityQueue_Heap& h_)
00105 {
00106 delete [] m_queue;
00107 m_comp = h_.m_comp;
00108 m_size = h_.m_size;
00109 m_curr = h_.m_curr;
00110 m_lwm = h_.m_lwm;
00111 allocate (m_size);
00112 ::memcpy (m_queue, h_.m_queue, sizeof(T)*m_curr);
00113 return *this;
00114 }
00115
00116 template< class T, class Compare>
00117 inline
00118 PriorityQueue_Heap<T, Compare>::
00119 ~PriorityQueue_Heap ()
00120 {
00121 delete [] m_queue;
00122 }
00123
00124 template< class T, class Compare>
00125 void
00126 PriorityQueue_Heap<T, Compare>::
00127 insert (const T& t_)
00128 {
00129 if (m_curr+1 == m_size)
00130 resize (m_size*2);
00131
00132 m_queue [m_curr] = t_;
00133 upheap (m_curr);
00134 m_curr++;
00135 }
00136
00137 template< class T, class Compare>
00138 void
00139 PriorityQueue_Heap<T, Compare>::
00140 upheap (size_t k_)
00141 {
00142 T v = m_queue[k_];
00143 m_queue[0] = 0;
00144
00145 while ( k_/2 != 0 && m_comp (v, m_queue[k_/2]) ) {
00146 m_queue[k_] = m_queue[k_/2];
00147 k_ = k_/2;
00148 }
00149 m_queue[k_] = v;
00150 }
00151
00152 template< class T, class Compare>
00153 T
00154 PriorityQueue_Heap<T, Compare>::
00155 pop ()
00156 {
00157 T v = m_queue[1];
00158 m_queue[1] = m_queue[--m_curr];
00159
00160 downheap (1);
00161 if (m_curr*3 <= m_size && m_curr*2 > m_lwm) {
00162 resize (m_curr*2);
00163 }
00164 return v;
00165 }
00166
00167 template< class T, class Compare>
00168 inline const T&
00169 PriorityQueue_Heap<T, Compare>::
00170 top () const
00171 {
00172 return (const T&) m_queue[1];
00173 }
00174
00175 template< class T, class Compare>
00176 void
00177 PriorityQueue_Heap<T, Compare>::
00178 downheap (size_t k_)
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 }
00194
00195 template< class T, class Compare>
00196 bool
00197 PriorityQueue_Heap<T, Compare>::
00198 remove (T t_)
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)
00207 return false;
00208
00209 m_curr--;
00210 if (i == m_curr)
00211 return true;
00212
00213 m_queue[i] = m_queue[m_curr];
00214 downheap (i);
00215
00216 return true;
00217 }
00218
00219 template< class T, class Compare>
00220 inline size_t
00221 PriorityQueue_Heap<T, Compare>::
00222 size ()
00223 {
00224 return m_curr-1;
00225 }
00226
00227 template< class T, class Compare>
00228 bool
00229 PriorityQueue_Heap<T, Compare>::
00230 resize (size_t newsz_)
00231 {
00232 if (m_size == newsz_)
00233 return true;
00234
00235 T* new_chunk = new T[newsz_];
00236 ::memcpy (new_chunk, m_queue, m_curr * sizeof(T));
00237 delete [] m_queue;
00238 m_queue = new_chunk;
00239 m_size = newsz_;
00240 return true;
00241 }
00242
00243 template< class T, class Compare>
00244 T&
00245 PriorityQueue_Heap<T, Compare>::
00246 operator[] (int idx)
00247 {
00248 return m_queue[idx+1];
00249 }
00250
00251 }
00252
00253 #endif