OpenMesh
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>
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>
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
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
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 
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&#39;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&#39;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&#39;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.

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