libassa
3.5.0
|
00001 // -*- c++ -*- 00002 //------------------------------------------------------------------------------ 00003 // PriorityQueue_Heap.h 00004 //------------------------------------------------------------------------------ 00005 // Copyright (c) 1999 by Vladislav Grinchenko 00006 // 00007 // This library is free software; you can redistribute it and/or 00008 // modify it under the terms of the GNU Library General Public 00009 // License as published by the Free Software Foundation; either 00010 // version 2 of the License, or (at your option) any later version. 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) // if array filled up 00130 resize (m_size*2); // then resize array 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) // 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 } 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 } // end namespace ASSA 00252 00253 #endif /* PRIORITY_QUEUE_HEAP_H */