73 #ifndef OPENMESH_UTILS_HEAPT_HH 74 #define OPENMESH_UTILS_HEAPT_HH 99 template <
class HeapEntry>
103 bool less(
const HeapEntry& _e1,
const HeapEntry& _e2);
106 bool greater(
const HeapEntry& _e1,
const HeapEntry& _e2);
139 template <
class HeapEntry,
class HeapInterface=HeapEntry>
140 class HeapT :
private std::vector<HeapEntry>
143 typedef std::vector<HeapEntry> Base;
151 HeapT(
const HeapInterface& _interface)
152 : HeapVector(), interface_(_interface)
160 void clear() { HeapVector::clear(); }
163 bool empty()
const {
return HeapVector::empty(); }
166 size_t size()
const {
return HeapVector::size(); }
169 void reserve(
size_t _n) { HeapVector::reserve(_n); }
173 { interface_.set_heap_position(_h, -1); }
177 {
return interface_.get_heap_position(_h) != -1; }
197 reset_heap_position(entry(0));
200 entry(0, entry(size()-1));
211 void remove(HeapEntry _h)
213 int pos = interface_.get_heap_position(_h);
214 reset_heap_position(_h);
217 assert((
unsigned int) pos < size());
220 if ((
unsigned int) pos == size()-1)
226 entry(pos, entry(size()-1));
238 int pos = interface_.get_heap_position(_h);
240 assert((
unsigned int)pos < size());
250 for (i=0; i<size(); ++i)
252 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j)))
254 omerr() <<
"Heap condition violated\n";
257 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
259 omerr() <<
"Heap condition violated\n";
272 typedef std::vector<HeapEntry> HeapVector;
276 void upheap(
size_t _idx);
280 void downheap(
size_t _idx);
284 inline HeapEntry entry(
size_t _idx)
const 286 assert(_idx < size());
287 return (Base::operator[](_idx));
292 inline void entry(
size_t _idx, HeapEntry _h)
294 assert(_idx < size());
295 Base::operator[](_idx) = _h;
296 interface_.set_heap_position(_h,
int(_idx));
301 inline size_t parent(
size_t _i) {
return (_i-1)>>1; }
303 inline size_t left(
size_t _i) {
return (_i<<1)+1; }
305 inline size_t right(
size_t _i) {
return (_i<<1)+2; }
315 template <
class HeapEntry,
class HeapInterface>
320 HeapEntry h = entry(_idx);
323 while ((_idx>0) && interface_.less(h, entry(parentIdx=parent(_idx))))
325 entry(_idx, entry(parentIdx));
336 template <
class HeapEntry,
class HeapInterface>
341 HeapEntry h = entry(_idx);
347 childIdx = left(_idx);
348 if (childIdx >= s)
break;
350 if ((childIdx + 1 < s) && (interface_.less(entry(childIdx + 1), entry(childIdx))))
353 if (interface_.less(h, entry(childIdx)))
break;
355 entry(_idx, entry(childIdx));
367 #endif // OSG_HEAP_HH defined void clear()
clear the heap
Definition: HeapT.hh:160
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
void reserve(size_t _n)
reserve space for _n entries
Definition: HeapT.hh:169
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:176
bool empty() const
is heap empty?
Definition: HeapT.hh:163
size_t size() const
returns the size of heap
Definition: HeapT.hh:166
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
An efficient, highly customizable heap.
Definition: HeapT.hh:140
void update(HeapEntry _h)
update an entry: change the key and update the position to reestablish the heap property.
Definition: HeapT.hh:236
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:64
This class demonstrates the HeapInterface's interface.
Definition: HeapT.hh:100
bool check()
check heap condition
Definition: HeapT.hh:246
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:180
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:172
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:268
~HeapT()
Destructor.
Definition: HeapT.hh:156
HeapEntry front() const
get the first entry
Definition: HeapT.hh:187
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict less.
void pop_front()
delete the first entry
Definition: HeapT.hh:194
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
HeapT()
Constructor.
Definition: HeapT.hh:148
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition: HeapT.hh:151
This file provides the streams omlog, omout, and omerr.