00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00035
00036
00037
00038
00039
00040
00041 #ifndef OPENMESH_UTILS_HEAPT_HH
00042 #define OPENMESH_UTILS_HEAPT_HH
00043
00044
00045
00046
00047 #include "Config.hh"
00048 #include <vector>
00049 #include <OpenMesh/Core/System/omstream.hh>
00050
00051
00052
00053 namespace OpenMesh {
00054 namespace Utils {
00055
00056
00057
00058
00067 template <class HeapEntry>
00068 struct HeapInterfaceT
00069 {
00071 bool less(const HeapEntry& _e1, const HeapEntry& _e2);
00072
00074 bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
00075
00077 int get_heap_position(const HeapEntry& _e);
00078
00080 void set_heap_position(HeapEntry& _e, int _i);
00081 };
00082
00083
00084
00106 template <class HeapEntry, class HeapInterface=HeapEntry>
00107 class HeapT : private std::vector<HeapEntry>
00108 {
00109 public:
00110
00112 HeapT() : HeapVector() {}
00113
00115 HeapT(const HeapInterface& _interface)
00116 : HeapVector(), interface_(_interface)
00117 {}
00118
00120 ~HeapT(){};
00121
00122
00124 void clear() { HeapVector::clear(); }
00125
00127 bool empty() { return HeapVector::empty(); }
00128
00130 unsigned int size() { return HeapVector::size(); }
00131
00133 void reserve(unsigned int _n) { HeapVector::reserve(_n); }
00134
00136 void reset_heap_position(HeapEntry _h)
00137 { interface_.set_heap_position(_h, -1); }
00138
00140 bool is_stored(HeapEntry _h)
00141 { return interface_.get_heap_position(_h) != -1; }
00142
00144 void insert(HeapEntry _h) { push_back(_h); upheap(size()-1); }
00145
00147 HeapEntry front() { assert(!empty()); return entry(0); }
00148
00150 void pop_front()
00151 {
00152 assert(!empty());
00153 interface_.set_heap_position(entry(0), -1);
00154 if (size() > 1)
00155 {
00156 entry(0, entry(size()-1));
00157 resize(size()-1);
00158 downheap(0);
00159 }
00160 else resize(size()-1);
00161 }
00162
00164 void remove(HeapEntry _h)
00165 {
00166 int pos = interface_.get_heap_position(_h);
00167 interface_.set_heap_position(_h, -1);
00168
00169 assert(pos != -1);
00170 assert((unsigned int) pos < size());
00171
00172
00173 if ((unsigned int) pos == size()-1)
00174 resize(size()-1);
00175
00176 else {
00177 entry(pos, entry(size()-1));
00178 resize(size()-1);
00179 downheap(pos);
00180 upheap(pos);
00181 }
00182 }
00183
00187 void update(HeapEntry _h)
00188 {
00189 int pos = interface_.get_heap_position(_h);
00190 assert(pos != -1);
00191 assert((unsigned int)pos < size());
00192 downheap(pos);
00193 upheap(pos);
00194 }
00195
00197 bool check()
00198 {
00199 bool ok(true);
00200 unsigned int i, j;
00201 for (i=0; i<size(); ++i)
00202 {
00203 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j)))
00204 {
00205 omerr << "Heap condition violated\n";
00206 ok=false;
00207 }
00208 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
00209 {
00210 omerr << "Heap condition violated\n";
00211 ok=false;
00212 }
00213 }
00214 return ok;
00215 }
00216
00217
00218 private:
00219
00220
00221 typedef std::vector<HeapEntry> HeapVector;
00222
00223
00225 void upheap(unsigned int _idx);
00226
00227
00229 void downheap(unsigned int _idx);
00230
00231
00233 inline HeapEntry entry(unsigned int _idx) {
00234 assert(_idx < size());
00235 return (operator[](_idx));
00236 }
00237
00238
00240 inline void entry(unsigned int _idx, HeapEntry _h) {
00241 assert(_idx < size());
00242 operator[](_idx) = _h;
00243 interface_.set_heap_position(_h, _idx);
00244 }
00245
00246
00248 inline unsigned int parent(unsigned int _i) { return (_i-1)>>1; }
00250 inline unsigned int left(unsigned int _i) { return (_i<<1)+1; }
00252 inline unsigned int right(unsigned int _i) { return (_i<<1)+2; }
00253
00254
00256 HeapInterface interface_;
00257 };
00258
00259
00260
00261
00262
00263
00264
00265 template <class HeapEntry, class HeapInterface>
00266 void
00267 HeapT<HeapEntry, HeapInterface>::
00268 upheap(unsigned int _idx)
00269 {
00270 HeapEntry h = entry(_idx);
00271 unsigned int parentIdx;
00272
00273 while ((_idx>0) &&
00274 interface_.less(h, entry(parentIdx=parent(_idx))))
00275 {
00276 entry(_idx, entry(parentIdx));
00277 _idx = parentIdx;
00278 }
00279
00280 entry(_idx, h);
00281 }
00282
00283
00284
00285
00286
00287 template <class HeapEntry, class HeapInterface>
00288 void
00289 HeapT<HeapEntry, HeapInterface>::
00290 downheap(unsigned int _idx)
00291 {
00292 HeapEntry h = entry(_idx);
00293 unsigned int childIdx;
00294 unsigned int s = size();
00295
00296 while(_idx < s)
00297 {
00298 childIdx = left(_idx);
00299 if (childIdx >= s) break;
00300
00301 if ((childIdx+1 < s) &&
00302 (interface_.less(entry(childIdx+1), entry(childIdx))))
00303 ++childIdx;
00304
00305 if (interface_.less(h, entry(childIdx))) break;
00306
00307 entry(_idx, entry(childIdx));
00308 _idx = childIdx;
00309 }
00310
00311 entry(_idx, h);
00312 }
00313
00314
00315
00316 }
00317 }
00318
00319 #endif // OSG_HEAP_HH defined
00320
00321