68 #ifndef OPENMESH_UTILS_HEAPT_HH
69 #define OPENMESH_UTILS_HEAPT_HH
77 #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
97 template <
class HeapEntry>
101 bool less(
const HeapEntry& _e1,
const HeapEntry& _e2);
104 bool greater(
const HeapEntry& _e1,
const HeapEntry& _e2);
137 template <
class HeapEntry,
class HeapInterface=HeapEntry>
138 class HeapT :
private std::vector<HeapEntry>
141 typedef std::vector<HeapEntry> Base;
148 #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
149 HeapT(HeapInterface _interface)
151 : HeapVector(),
interface_(std::move(_interface))
154 HeapT(
const HeapInterface &_interface)
163 HeapInterface &getInterface() {
167 const HeapInterface &getInterface()
const {
172 void clear() { HeapVector::clear(); }
175 bool empty()
const {
return HeapVector::empty(); }
178 size_t size()
const {
return HeapVector::size(); }
181 void reserve(
size_t _n) { HeapVector::reserve(_n); }
189 {
return interface_.get_heap_position(_h) != -1; }
202 return HeapVector::front();
212 entry(0, entry(
size()-1));
229 assert((
unsigned int) pos <
size());
232 if ((
unsigned int) pos ==
size()-1)
238 entry(pos, entry(
size()-1));
252 assert((
unsigned int)pos <
size());
262 for (i=0; i<
size(); ++i)
264 if (((j=left(i))<
size()) &&
interface_.greater(entry(i), entry(j)))
266 omerr() <<
"Heap condition violated\n";
269 if (((j=right(i))<
size()) &&
interface_.greater(entry(i), entry(j)))
271 omerr() <<
"Heap condition violated\n";
284 typedef std::vector<HeapEntry> HeapVector;
288 void upheap(
size_t _idx);
292 void downheap(
size_t _idx);
296 inline HeapEntry entry(
size_t _idx)
const
298 assert(_idx <
size());
299 return (Base::operator[](_idx));
304 inline void entry(
size_t _idx, HeapEntry _h)
306 assert(_idx <
size());
307 Base::operator[](_idx) = _h;
313 inline size_t parent(
size_t _i) {
return (_i-1)>>1; }
315 inline size_t left(
size_t _i) {
return (_i<<1)+1; }
317 inline size_t right(
size_t _i) {
return (_i<<1)+2; }
327 template <
class HeapEntry,
class HeapInterface>
329 HeapT<HeapEntry, HeapInterface>::
332 HeapEntry h = entry(_idx);
335 while ((_idx>0) && interface_.less(h, entry(parentIdx=parent(_idx))))
337 entry(_idx, entry(parentIdx));
348 template <
class HeapEntry,
class HeapInterface>
350 HeapT<HeapEntry, HeapInterface>::
351 downheap(
size_t _idx)
353 const HeapEntry h = entry(_idx);
355 const size_t s = size();
359 childIdx = left(_idx);
360 if (childIdx >= s)
break;
362 if ((childIdx + 1 < s) && (interface_.less(entry(childIdx + 1), entry(childIdx))))
365 if (interface_.less(h, entry(childIdx)))
break;
367 entry(_idx, entry(childIdx));
379 #endif // OSG_HEAP_HH defined