OpenMesh
Loading...
Searching...
No Matches
HeapT.hh
Go to the documentation of this file.
1/* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openmesh.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenMesh. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 * ========================================================================= */
41
42/*===========================================================================*\
43 * *
44 * $Revision$ *
45 * $Date$ *
46 * *
47\*===========================================================================*/
48
67//=============================================================================
68//
69// CLASS HeapT
70//
71//=============================================================================
72
73#ifndef OPENMESH_UTILS_HEAPT_HH
74#define OPENMESH_UTILS_HEAPT_HH
75
76
77//== INCLUDES =================================================================
78
79#include "Config.hh"
80#include <vector>
82#if (defined(_MSC_VER) && (_MSC_VER >= 1900)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
83#include <utility>
84#endif
85
86//== NAMESPACE ================================================================
87
88namespace OpenMesh { // BEGIN_NS_OPENMESH
89namespace Utils { // BEGIN_NS_UTILS
90
91//== CLASS DEFINITION =========================================================
92
93
102template <class HeapEntry>
104{
106 bool less(const HeapEntry& _e1, const HeapEntry& _e2);
107
109 bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
110
112 int get_heap_position(const HeapEntry& _e);
113
115 void set_heap_position(HeapEntry& _e, int _i);
116};
117
118
119
142template <class HeapEntry, class HeapInterface=HeapEntry>
143class HeapT : private std::vector<HeapEntry>
144{
145private:
146 typedef std::vector<HeapEntry> Base;
147
148public:
149
151 HeapT() : HeapVector() {}
152
153#if (defined(_MSC_VER) && (_MSC_VER >= 1900)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
155 HeapT(HeapInterface _interface)
156 : HeapVector(), interface_(std::move(_interface))
157 {}
158#else
160 HeapT(const HeapInterface &_interface)
161 : HeapVector(), interface_(_interface)
162 {}
163#endif
164
167
168 HeapInterface &getInterface() {
169 return interface_;
170 }
171
172 const HeapInterface &getInterface() const {
173 return interface_;
174 }
175
177 void clear() { HeapVector::clear(); }
178
180 bool empty() const { return HeapVector::empty(); }
181
183 size_t size() const { return HeapVector::size(); }
184
186 void reserve(size_t _n) { HeapVector::reserve(_n); }
187
189 void reset_heap_position(HeapEntry _h)
190 { interface_.set_heap_position(_h, -1); }
191
193 bool is_stored(HeapEntry _h)
194 { return interface_.get_heap_position(_h) != -1; }
195
197 void insert(HeapEntry _h)
198 {
199 this->push_back(_h);
200 upheap(size()-1);
201 }
202
204 HeapEntry front() const
205 {
206 assert(!empty());
207 return HeapVector::front();
208 }
209
212 {
213 assert(!empty());
214 reset_heap_position(HeapVector::front());
215 if (size() > 1)
216 {
217 entry(0, entry(size()-1));
218 Base::pop_back();
219 downheap(0);
220 }
221 else
222 {
223 Base::pop_back();
224 }
225 }
226
228 void remove(HeapEntry _h)
229 {
230 int pos = interface_.get_heap_position(_h);
232
233 assert(pos != -1);
234 assert((unsigned int) pos < size());
235
236 // last item ?
237 if ((unsigned int) pos == size()-1)
238 {
239 Base::pop_back();
240 }
241 else
242 {
243 entry(pos, entry(size()-1)); // move last elem to pos
244 Base::pop_back();
245 downheap(pos);
246 upheap(pos);
247 }
248 }
249
253 void update(HeapEntry _h)
254 {
255 int pos = interface_.get_heap_position(_h);
256 assert(pos != -1);
257 assert((unsigned int)pos < size());
258 downheap(pos);
259 upheap(pos);
260 }
261
263 bool check()
264 {
265 bool ok(true);
266 unsigned int i, j;
267 for (i=0; i<size(); ++i)
268 {
269 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j)))
270 {
271 omerr() << "Heap condition violated\n";
272 ok=false;
273 }
274 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
275 {
276 omerr() << "Heap condition violated\n";
277 ok=false;
278 }
279 }
280 return ok;
281 }
282
283protected:
285 HeapInterface interface_;
286
287private:
288 // typedef
289 typedef std::vector<HeapEntry> HeapVector;
290
291
293 void upheap(size_t _idx);
294
295
297 void downheap(size_t _idx);
298
299
301 inline HeapEntry entry(size_t _idx) const
302 {
303 assert(_idx < size());
304 return (Base::operator[](_idx));
305 }
306
307
309 inline void entry(size_t _idx, HeapEntry _h)
310 {
311 assert(_idx < size());
312 Base::operator[](_idx) = _h;
313 interface_.set_heap_position(_h, int(_idx));
314 }
315
316
318 inline size_t parent(size_t _i) { return (_i-1)>>1; }
320 inline size_t left(size_t _i) { return (_i<<1)+1; }
322 inline size_t right(size_t _i) { return (_i<<1)+2; }
323
324};
325
326
327
328
329//== IMPLEMENTATION ==========================================================
330
331
332template <class HeapEntry, class HeapInterface>
333void
334HeapT<HeapEntry, HeapInterface>::
335upheap(size_t _idx)
336{
337 HeapEntry h = entry(_idx);
338 size_t parentIdx;
339
340 while ((_idx>0) && interface_.less(h, entry(parentIdx=parent(_idx))))
341 {
342 entry(_idx, entry(parentIdx));
343 _idx = parentIdx;
344 }
345
346 entry(_idx, h);
347}
348
349
350//-----------------------------------------------------------------------------
351
352
353template <class HeapEntry, class HeapInterface>
354void
355HeapT<HeapEntry, HeapInterface>::
356downheap(size_t _idx)
357{
358 const HeapEntry h = entry(_idx);
359 size_t childIdx;
360 const size_t s = size();
361
362 while(_idx < s)
363 {
364 childIdx = left(_idx);
365 if (childIdx >= s) break;
366
367 if ((childIdx + 1 < s) && (interface_.less(entry(childIdx + 1), entry(childIdx))))
368 ++childIdx;
369
370 if (interface_.less(h, entry(childIdx))) break;
371
372 entry(_idx, entry(childIdx));
373 _idx = childIdx;
374 }
375
376 entry(_idx, h);
377}
378
379
380//=============================================================================
381} // END_NS_UTILS
382} // END_NS_OPENMESH
383//=============================================================================
384#endif // OSG_HEAP_HH defined
385//=============================================================================
386
This file provides the streams omlog, omout, and omerr.
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:104
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict less.
An efficient, highly customizable heap.
Definition HeapT.hh:144
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition HeapT.hh:160
HeapT()
Constructor.
Definition HeapT.hh:151
size_t size() const
returns the size of heap
Definition HeapT.hh:183
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition HeapT.hh:189
bool check()
check heap condition
Definition HeapT.hh:263
bool empty() const
is heap empty?
Definition HeapT.hh:180
void update(HeapEntry _h)
update an entry: change the key and update the position to reestablish the heap property.
Definition HeapT.hh:253
~HeapT()
Destructor.
Definition HeapT.hh:166
void insert(HeapEntry _h)
insert the entry _h
Definition HeapT.hh:197
HeapEntry front() const
get the first entry
Definition HeapT.hh:204
void pop_front()
delete the first entry
Definition HeapT.hh:211
void reserve(size_t _n)
reserve space for _n entries
Definition HeapT.hh:186
void remove(HeapEntry _h)
remove an entry
Definition HeapT.hh:228
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition HeapT.hh:193
HeapInterface interface_
Instance of HeapInterface.
Definition HeapT.hh:285
void clear()
clear the heap
Definition HeapT.hh:177

Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .