OpenMesh

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

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
HeapT.hh
Go to the documentation of this file.
1 /*===========================================================================*\
2 * *
3 * OpenMesh *
4 * Copyright (C) 2001-2014 by Computer Graphics Group, RWTH Aachen *
5 * www.openmesh.org *
6 * *
7 *---------------------------------------------------------------------------*
8 * This file is part of OpenMesh. *
9 * *
10 * OpenMesh is free software: you can redistribute it and/or modify *
11 * it under the terms of the GNU Lesser General Public License as *
12 * published by the Free Software Foundation, either version 3 of *
13 * the License, or (at your option) any later version with the *
14 * following exceptions: *
15 * *
16 * If other files instantiate templates or use macros *
17 * or inline functions from this file, or you compile this file and *
18 * link it with other files to produce an executable, this file does *
19 * not by itself cause the resulting executable to be covered by the *
20 * GNU Lesser General Public License. This exception does not however *
21 * invalidate any other reasons why the executable file might be *
22 * covered by the GNU Lesser General Public License. *
23 * *
24 * OpenMesh is distributed in the hope that it will be useful, *
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
27 * GNU Lesser General Public License for more details. *
28 * *
29 * You should have received a copy of the GNU LesserGeneral Public *
30 * License along with OpenMesh. If not, *
31 * see <http://www.gnu.org/licenses/>. *
32 * *
33 \*===========================================================================*/
34
35 /*===========================================================================*\
36 * *
37 * $Revision: 990 $ *
38 * $Date: 2014-02-05 10:01:07 +0100 (Mi, 05. Feb 2014) $ *
39 * *
40 \*===========================================================================*/
41
60 //=============================================================================
61 //
62 // CLASS HeapT
63 //
64 //=============================================================================
65
66 #ifndef OPENMESH_UTILS_HEAPT_HH
67 #define OPENMESH_UTILS_HEAPT_HH
68
69
70 //== INCLUDES =================================================================
71
72 #include "Config.hh"
73 #include <vector>
74 #include <OpenMesh/Core/System/omstream.hh>
75
76 //== NAMESPACE ================================================================
77
78 namespace OpenMesh { // BEGIN_NS_OPENMESH
79 namespace Utils { // BEGIN_NS_UTILS
80
81 //== CLASS DEFINITION =========================================================
82
83
92 template <class HeapEntry>
93 struct HeapInterfaceT
94 {
96 bool less(const HeapEntry& _e1, const HeapEntry& _e2);
97
99 bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
100
102 int get_heap_position(const HeapEntry& _e);
103
105 void set_heap_position(HeapEntry& _e, int _i);
106 };
107
108
109
132 template <class HeapEntry, class HeapInterface=HeapEntry>
133 class HeapT : private std::vector<HeapEntry>
134 {
135 private:
136 typedef std::vector<HeapEntry> Base;
137
138 public:
139
141 HeapT() : HeapVector() {}
142
144 HeapT(const HeapInterface& _interface)
145 : HeapVector(), interface_(_interface)
146 {}
147
149 ~HeapT(){};
150
151
153 void clear() { HeapVector::clear(); }
154
156 bool empty() const { return HeapVector::empty(); }
157
159 size_t size() const { return HeapVector::size(); }
160
162 void reserve(size_t _n) { HeapVector::reserve(_n); }
163
165 void reset_heap_position(HeapEntry _h)
166 { interface_.set_heap_position(_h, -1); }
167
169 bool is_stored(HeapEntry _h)
170 { return interface_.get_heap_position(_h) != -1; }
171
173 void insert(HeapEntry _h)
174 {
175 this->push_back(_h);
176 upheap(size()-1);
177 }
178
180 HeapEntry front() const
181 {
182 assert(!empty());
183 return entry(0);
184 }
185
187 void pop_front()
188 {
189 assert(!empty());
190 reset_heap_position(entry(0));
191 if (size() > 1)
192 {
193 entry(0, entry(size()-1));
194 Base::pop_back();
195 downheap(0);
196 }
197 else
198 {
199 Base::pop_back();
200 }
201 }
202
204 void remove(HeapEntry _h)
205 {
206 int pos = interface_.get_heap_position(_h);
207 reset_heap_position(_h);
208
209 assert(pos != -1);
210 assert((unsigned int) pos < size());
211
212 // last item ?
213 if ((unsigned int) pos == size()-1)
214 {
215 Base::pop_back();
216 }
217 else
218 {
219 entry(pos, entry(size()-1)); // move last elem to pos
220 Base::pop_back();
221 downheap(pos);
222 upheap(pos);
223 }
224 }
225
229 void update(HeapEntry _h)
230 {
231 int pos = interface_.get_heap_position(_h);
232 assert(pos != -1);
233 assert((unsigned int)pos < size());
234 downheap(pos);
235 upheap(pos);
236 }
237
239 bool check()
240 {
241 bool ok(true);
242 unsigned int i, j;
243 for (i=0; i<size(); ++i)
244 {
245 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j)))
246 {
247 omerr() << "Heap condition violated\n";
248 ok=false;
249 }
250 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
251 {
252 omerr() << "Heap condition violated\n";
253 ok=false;
254 }
255 }
256 return ok;
257 }
258
259 protected:
261 HeapInterface interface_;
262
263 private:
264 // typedef
265 typedef std::vector<HeapEntry> HeapVector;
266
267
269 void upheap(size_t _idx);
270
271
273 void downheap(size_t _idx);
274
275
277 inline HeapEntry entry(size_t _idx) const
278 {
279 assert(_idx < size());
280 return (Base::operator[](_idx));
281 }
282
283
285 inline void entry(size_t _idx, HeapEntry _h)
286 {
287 assert(_idx < size());
288 Base::operator[](_idx) = _h;
289 interface_.set_heap_position(_h, int(_idx));
290 }
291
292
294 inline size_t parent(size_t _i) { return (_i-1)>>1; }
296 inline size_t left(size_t _i) { return (_i<<1)+1; }
298 inline size_t right(size_t _i) { return (_i<<1)+2; }
299
300 };
301
302
303
304
305 //== IMPLEMENTATION ==========================================================
306
307
308 template <class HeapEntry, class HeapInterface>
309 void
310 HeapT<HeapEntry, HeapInterface>::
311 upheap(size_t _idx)
312 {
313 HeapEntry h = entry(_idx);
314 size_t parentIdx;
315
316 while ((_idx>0) && interface_.less(h, entry(parentIdx=parent(_idx))))
317 {
318 entry(_idx, entry(parentIdx));
319 _idx = parentIdx;
320 }
321
322 entry(_idx, h);
323 }
324
325
326 //-----------------------------------------------------------------------------
327
328
329 template <class HeapEntry, class HeapInterface>
330 void
331 HeapT<HeapEntry, HeapInterface>::
332 downheap(size_t _idx)
333 {
334 HeapEntry h = entry(_idx);
335 size_t childIdx;
336 size_t s = size();
337
338 while(_idx < s)
339 {
340 childIdx = left(_idx);
341 if (childIdx >= s) break;
342
343 if ((childIdx + 1 < s) && (interface_.less(entry(childIdx + 1), entry(childIdx))))
344 ++childIdx;
345
346 if (interface_.less(h, entry(childIdx))) break;
347
348 entry(_idx, entry(childIdx));
349 _idx = childIdx;
350 }
351
352 entry(_idx, h);
353 }
354
355
356 //=============================================================================
357 } // END_NS_UTILS
358 } // END_NS_OPENMESH
359 //=============================================================================
360 #endif // OSG_HEAP_HH defined
361 //=============================================================================
362
OpenMesh::Utils::HeapT::HeapT
HeapT()
Constructor.
Definition: HeapT.hh:141
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:229
OpenMesh::Utils::HeapInterfaceT::set_heap_position
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
omstream.hh
This file provides the streams omlog, omout, and omerr.
OpenMesh::Utils::HeapT::reset_heap_position
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:165
OpenMesh::Utils::HeapT::check
bool check()
check heap condition
Definition: HeapT.hh:239
OpenMesh::Utils::HeapT::interface_
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:261
OpenMesh::Utils::HeapInterfaceT
This class demonstrates the HeapInterface's interface.
Definition: HeapT.hh:93
OpenMesh::Utils::HeapT::size
size_t size() const
returns the size of heap
Definition: HeapT.hh:159
OpenMesh::Utils::HeapT::reserve
void reserve(size_t _n)
reserve space for _n entries
Definition: HeapT.hh:162
OpenMesh::Utils::HeapT::~HeapT
~HeapT()
Destructor.
Definition: HeapT.hh:149
OpenMesh::Utils::HeapT::pop_front
void pop_front()
delete the first entry
Definition: HeapT.hh:187
OpenMesh::Utils::HeapT::insert
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:173
OpenMesh::Utils::HeapT::empty
bool empty() const
is heap empty?
Definition: HeapT.hh:156
OpenMesh::Utils::HeapT::clear
void clear()
clear the heap
Definition: HeapT.hh:153
OpenMesh::Utils::HeapInterfaceT::less
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict less.
OpenMesh::Utils::HeapT::front
HeapEntry front() const
get the first entry
Definition: HeapT.hh:180
OpenMesh::Utils::HeapInterfaceT::greater
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
Config.hh
OpenMesh::Utils::HeapT::HeapT
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition: HeapT.hh:144
OpenMesh::Utils::HeapT::is_stored
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:169
OpenMesh::Utils::HeapInterfaceT::get_heap_position
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
OpenMesh::Utils::HeapT
An efficient, highly customizable heap.
Definition: HeapT.hh:133