| OpenMesh

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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: 1258 $ *
45 * $Date: 2015-04-28 15:07:46 +0200 (Di, 28 Apr 2015) $ *
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>
81 #include <OpenMesh/Core/System/omstream.hh>
82
83 //== NAMESPACE ================================================================
84
85 namespace OpenMesh { // BEGIN_NS_OPENMESH
86 namespace Utils { // BEGIN_NS_UTILS
87
88 //== CLASS DEFINITION =========================================================
89
90
99 template <class HeapEntry>
100 struct HeapInterfaceT
101 {
103 bool less(const HeapEntry& _e1, const HeapEntry& _e2);
104
106 bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
107
109 int get_heap_position(const HeapEntry& _e);
110
112 void set_heap_position(HeapEntry& _e, int _i);
113 };
114
115
116
139 template <class HeapEntry, class HeapInterface=HeapEntry>
140 class HeapT : private std::vector<HeapEntry>
141 {
142 private:
143 typedef std::vector<HeapEntry> Base;
144
145 public:
146
148 HeapT() : HeapVector() {}
149
151 HeapT(const HeapInterface& _interface)
152 : HeapVector(), interface_(_interface)
153 {}
154
156 ~HeapT(){};
157
158
160 void clear() { HeapVector::clear(); }
161
163 bool empty() const { return HeapVector::empty(); }
164
166 size_t size() const { return HeapVector::size(); }
167
169 void reserve(size_t _n) { HeapVector::reserve(_n); }
170
172 void reset_heap_position(HeapEntry _h)
173 { interface_.set_heap_position(_h, -1); }
174
176 bool is_stored(HeapEntry _h)
177 { return interface_.get_heap_position(_h) != -1; }
178
180 void insert(HeapEntry _h)
181 {
182 this->push_back(_h);
183 upheap(size()-1);
184 }
185
187 HeapEntry front() const
188 {
189 assert(!empty());
190 return entry(0);
191 }
192
194 void pop_front()
195 {
196 assert(!empty());
197 reset_heap_position(entry(0));
198 if (size() > 1)
199 {
200 entry(0, entry(size()-1));
201 Base::pop_back();
202 downheap(0);
203 }
204 else
205 {
206 Base::pop_back();
207 }
208 }
209
211 void remove(HeapEntry _h)
212 {
213 int pos = interface_.get_heap_position(_h);
214 reset_heap_position(_h);
215
216 assert(pos != -1);
217 assert((unsigned int) pos < size());
218
219 // last item ?
220 if ((unsigned int) pos == size()-1)
221 {
222 Base::pop_back();
223 }
224 else
225 {
226 entry(pos, entry(size()-1)); // move last elem to pos
227 Base::pop_back();
228 downheap(pos);
229 upheap(pos);
230 }
231 }
232
236 void update(HeapEntry _h)
237 {
238 int pos = interface_.get_heap_position(_h);
239 assert(pos != -1);
240 assert((unsigned int)pos < size());
241 downheap(pos);
242 upheap(pos);
243 }
244
246 bool check()
247 {
248 bool ok(true);
249 unsigned int i, j;
250 for (i=0; i<size(); ++i)
251 {
252 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j)))
253 {
254 omerr() << "Heap condition violated\n";
255 ok=false;
256 }
257 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
258 {
259 omerr() << "Heap condition violated\n";
260 ok=false;
261 }
262 }
263 return ok;
264 }
265
266 protected:
268 HeapInterface interface_;
269
270 private:
271 // typedef
272 typedef std::vector<HeapEntry> HeapVector;
273
274
276 void upheap(size_t _idx);
277
278
280 void downheap(size_t _idx);
281
282
284 inline HeapEntry entry(size_t _idx) const
285 {
286 assert(_idx < size());
287 return (Base::operator[](_idx));
288 }
289
290
292 inline void entry(size_t _idx, HeapEntry _h)
293 {
294 assert(_idx < size());
295 Base::operator[](_idx) = _h;
296 interface_.set_heap_position(_h, int(_idx));
297 }
298
299
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; }
306
307 };
308
309
310
311
312 //== IMPLEMENTATION ==========================================================
313
314
315 template <class HeapEntry, class HeapInterface>
316 void
317 HeapT<HeapEntry, HeapInterface>::
318 upheap(size_t _idx)
319 {
320 HeapEntry h = entry(_idx);
321 size_t parentIdx;
322
323 while ((_idx>0) && interface_.less(h, entry(parentIdx=parent(_idx))))
324 {
325 entry(_idx, entry(parentIdx));
326 _idx = parentIdx;
327 }
328
329 entry(_idx, h);
330 }
331
332
333 //-----------------------------------------------------------------------------
334
335
336 template <class HeapEntry, class HeapInterface>
337 void
338 HeapT<HeapEntry, HeapInterface>::
339 downheap(size_t _idx)
340 {
341 HeapEntry h = entry(_idx);
342 size_t childIdx;
343 size_t s = size();
344
345 while(_idx < s)
346 {
347 childIdx = left(_idx);
348 if (childIdx >= s) break;
349
350 if ((childIdx + 1 < s) && (interface_.less(entry(childIdx + 1), entry(childIdx))))
351 ++childIdx;
352
353 if (interface_.less(h, entry(childIdx))) break;
354
355 entry(_idx, entry(childIdx));
356 _idx = childIdx;
357 }
358
359 entry(_idx, h);
360 }
361
362
363 //=============================================================================
364 } // END_NS_UTILS
365 } // END_NS_OPENMESH
366 //=============================================================================
367 #endif // OSG_HEAP_HH defined
368 //=============================================================================
369
OpenMesh::Utils::HeapT::insert
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:180
OpenMesh::Utils::HeapT::clear
void clear()
clear the heap
Definition: HeapT.hh:160
OpenMesh::Utils::HeapT::empty
bool empty() const
is heap empty?
Definition: HeapT.hh:163
Config.hh
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:64
OpenMesh::Utils::HeapT::front
HeapEntry front() const
get the first entry
Definition: HeapT.hh:187
OpenMesh::Utils::HeapInterfaceT::set_heap_position
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
OpenMesh::Utils::HeapT
An efficient, highly customizable heap.
Definition: HeapT.hh:140
OpenMesh::Utils::HeapT::is_stored
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:176
OpenMesh::Utils::HeapT::update
void update(HeapEntry _h)
update an entry: change the key and update the position to reestablish the heap property.
Definition: HeapT.hh:236
OpenMesh::Utils::HeapT::HeapT
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition: HeapT.hh:151
OpenMesh::Utils::HeapInterfaceT::greater
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
OpenMesh::Utils::HeapT::check
bool check()
check heap condition
Definition: HeapT.hh:246
OpenMesh::Utils::HeapInterfaceT
This class demonstrates the HeapInterface's interface.
Definition: HeapT.hh:100
OpenMesh::Utils::HeapInterfaceT::get_heap_position
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
OpenMesh::Utils::HeapT::interface_
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:268
OpenMesh::Utils::HeapT::reserve
void reserve(size_t _n)
reserve space for _n entries
Definition: HeapT.hh:169
OpenMesh::Utils::HeapT::HeapT
HeapT()
Constructor.
Definition: HeapT.hh:148
omstream.hh
This file provides the streams omlog, omout, and omerr.
OpenMesh::Utils::HeapInterfaceT::less
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict less.
OpenMesh::Utils::HeapT::reset_heap_position
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:172
OpenMesh::Utils::HeapT::size
size_t size() const
returns the size of heap
Definition: HeapT.hh:166
OpenMesh::Utils::HeapT::~HeapT
~HeapT()
Destructor.
Definition: HeapT.hh:156
OpenMesh::Utils::HeapT::pop_front
void pop_front()
delete the first entry
Definition: HeapT.hh:194