Developer Documentation

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
62 //=============================================================================
63 //
64 // CLASS HeapT
65 //
66 //=============================================================================
67
68 #ifndef OPENMESH_UTILS_HEAPT_HH
69 #define OPENMESH_UTILS_HEAPT_HH
70
71
72 //== INCLUDES =================================================================
73
74 #include "Config.hh"
75 #include <vector>
76 #include <OpenMesh/Core/System/omstream.hh>
77 #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
78 #include <utility>
79 #endif
80
81 //== NAMESPACE ================================================================
82
83 namespace OpenMesh { // BEGIN_NS_OPENMESH
84 namespace Utils { // BEGIN_NS_UTILS
85
86 //== CLASS DEFINITION =========================================================
87
88
97 template <class HeapEntry>
98 struct HeapInterfaceT
99 {
101 bool less(const HeapEntry& _e1, const HeapEntry& _e2);
102
104 bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
105
107 int get_heap_position(const HeapEntry& _e);
108
110 void set_heap_position(HeapEntry& _e, int _i);
111 };
112
113
114
137 template <class HeapEntry, class HeapInterface=HeapEntry>
138 class HeapT : private std::vector<HeapEntry>
139 {
140 private:
141 typedef std::vector<HeapEntry> Base;
142
143 public:
144
146 HeapT() : HeapVector() {}
147
148 #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
149 HeapT(HeapInterface _interface)
151 : HeapVector(), interface_(std::move(_interface))
152 {}
153 #else
154 HeapT(const HeapInterface &_interface)
156 : HeapVector(), interface_(_interface)
157 {}
158 #endif
159
161 ~HeapT(){};
162
163 HeapInterface &getInterface() {
164 return interface_;
165 }
166
167 const HeapInterface &getInterface() const {
168 return interface_;
169 }
170
172 void clear() { HeapVector::clear(); }
173
175 bool empty() const { return HeapVector::empty(); }
176
178 size_t size() const { return HeapVector::size(); }
179
181 void reserve(size_t _n) { HeapVector::reserve(_n); }
182
184 void reset_heap_position(HeapEntry _h)
185 { interface_.set_heap_position(_h, -1); }
186
188 bool is_stored(HeapEntry _h)
189 { return interface_.get_heap_position(_h) != -1; }
190
192 void insert(HeapEntry _h)
193 {
194 this->push_back(_h);
195 upheap(size()-1);
196 }
197
199 HeapEntry front() const
200 {
201 assert(!empty());
202 return HeapVector::front();
203 }
204
206 void pop_front()
207 {
208 assert(!empty());
209 reset_heap_position(HeapVector::front());
210 if (size() > 1)
211 {
212 entry(0, entry(size()-1));
213 Base::pop_back();
214 downheap(0);
215 }
216 else
217 {
218 Base::pop_back();
219 }
220 }
221
223 void remove(HeapEntry _h)
224 {
225 int pos = interface_.get_heap_position(_h);
226 reset_heap_position(_h);
227
228 assert(pos != -1);
229 assert((unsigned int) pos < size());
230
231 // last item ?
232 if ((unsigned int) pos == size()-1)
233 {
234 Base::pop_back();
235 }
236 else
237 {
238 entry(pos, entry(size()-1)); // move last elem to pos
239 Base::pop_back();
240 downheap(pos);
241 upheap(pos);
242 }
243 }
244
248 void update(HeapEntry _h)
249 {
250 int pos = interface_.get_heap_position(_h);
251 assert(pos != -1);
252 assert((unsigned int)pos < size());
253 downheap(pos);
254 upheap(pos);
255 }
256
258 bool check()
259 {
260 bool ok(true);
261 unsigned int i, j;
262 for (i=0; i<size(); ++i)
263 {
264 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j)))
265 {
266 omerr() << "Heap condition violated\n";
267 ok=false;
268 }
269 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
270 {
271 omerr() << "Heap condition violated\n";
272 ok=false;
273 }
274 }
275 return ok;
276 }
277
278 protected:
280 HeapInterface interface_;
281
282 private:
283 // typedef
284 typedef std::vector<HeapEntry> HeapVector;
285
286
288 void upheap(size_t _idx);
289
290
292 void downheap(size_t _idx);
293
294
296 inline HeapEntry entry(size_t _idx) const
297 {
298 assert(_idx < size());
299 return (Base::operator[](_idx));
300 }
301
302
304 inline void entry(size_t _idx, HeapEntry _h)
305 {
306 assert(_idx < size());
307 Base::operator[](_idx) = _h;
308 interface_.set_heap_position(_h, int(_idx));
309 }
310
311
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; }
318
319 };
320
321
322
323
324 //== IMPLEMENTATION ==========================================================
325
326
327 template <class HeapEntry, class HeapInterface>
328 void
329 HeapT<HeapEntry, HeapInterface>::
330 upheap(size_t _idx)
331 {
332 HeapEntry h = entry(_idx);
333 size_t parentIdx;
334
335 while ((_idx>0) && interface_.less(h, entry(parentIdx=parent(_idx))))
336 {
337 entry(_idx, entry(parentIdx));
338 _idx = parentIdx;
339 }
340
341 entry(_idx, h);
342 }
343
344
345 //-----------------------------------------------------------------------------
346
347
348 template <class HeapEntry, class HeapInterface>
349 void
350 HeapT<HeapEntry, HeapInterface>::
351 downheap(size_t _idx)
352 {
353 const HeapEntry h = entry(_idx);
354 size_t childIdx;
355 const size_t s = size();
356
357 while(_idx < s)
358 {
359 childIdx = left(_idx);
360 if (childIdx >= s) break;
361
362 if ((childIdx + 1 < s) && (interface_.less(entry(childIdx + 1), entry(childIdx))))
363 ++childIdx;
364
365 if (interface_.less(h, entry(childIdx))) break;
366
367 entry(_idx, entry(childIdx));
368 _idx = childIdx;
369 }
370
371 entry(_idx, h);
372 }
373
374
375 //=============================================================================
376 } // END_NS_UTILS
377 } // END_NS_OPENMESH
378 //=============================================================================
379 #endif // OSG_HEAP_HH defined
380 //=============================================================================
381
OpenMesh::Utils::HeapT::entry
HeapEntry entry(size_t _idx) const
Get the entry at index _idx.
Definition: HeapT.hh:296
OpenMesh::Utils::HeapInterfaceT::greater
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry&#39;s: strict greater.
OpenMesh::Utils::HeapT::size
size_t size() const
returns the size of heap
Definition: HeapT.hh:178
OpenMesh::Utils::HeapT
Definition: HeapT.hh:138
OpenMesh::Utils::HeapT::upheap
void upheap(size_t _idx)
Upheap. Establish heap property.
Definition: HeapT.hh:330
OpenMesh::Utils::HeapT::downheap
void downheap(size_t _idx)
Downheap. Establish heap property.
Definition: HeapT.hh:351
OpenMesh::Utils::HeapT::left
size_t left(size_t _i)
Get left child&#39;s index.
Definition: HeapT.hh:315
OpenMesh::Utils::HeapT::parent
size_t parent(size_t _i)
Get parent&#39;s index.
Definition: HeapT.hh:313
OpenMesh::Utils::HeapT::empty
bool empty() const
is heap empty?
Definition: HeapT.hh:175
OpenMesh::Utils::HeapInterfaceT::less
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry&#39;s: strict less.
OpenMesh::Utils::HeapT::check
bool check()
check heap condition
Definition: HeapT.hh:258
OpenMesh::Utils::HeapT::reset_heap_position
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:184
OpenMesh::Utils::HeapT::right
size_t right(size_t _i)
Get right child&#39;s index.
Definition: HeapT.hh:317
OpenMesh::Utils::HeapT::reserve
void reserve(size_t _n)
reserve space for _n entries
Definition: HeapT.hh:181
OpenMesh::Utils::HeapT::~HeapT
~HeapT()
Destructor.
Definition: HeapT.hh:161
OpenMesh::Utils::HeapT::pop_front
void pop_front()
delete the first entry
Definition: HeapT.hh:206
OpenMesh::Utils::HeapT::insert
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:192
OpenMesh::Utils::HeapInterfaceT::get_heap_position
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
Config.hh
OpenMesh::Utils::HeapT::is_stored
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:188
Utils
Definition: NumberParsing.cc:46
OpenMesh::Utils::HeapT::entry
void entry(size_t _idx, HeapEntry _h)
Set entry _h to index _idx and update _h&#39;s heap position.
Definition: HeapT.hh:304
OpenMesh::Utils::HeapT::update
void update(HeapEntry _h)
Definition: HeapT.hh:248
OpenMesh::Utils::HeapT::interface_
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:280
OpenMesh::Utils::HeapT::HeapT
HeapT()
Constructor.
Definition: HeapT.hh:146
OpenMesh::Utils::HeapInterfaceT::set_heap_position
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
OpenMesh::Utils::HeapInterfaceT
Definition: HeapT.hh:98
OpenMesh::Utils::HeapT::clear
void clear()
clear the heap
Definition: HeapT.hh:172
OpenMesh::Utils::HeapT::front
HeapEntry front() const
get the first entry
Definition: HeapT.hh:199
OpenMesh
Definition: MeshItems.hh:59
omstream.hh