OpenMesh
 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$ *
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 __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
83 #include <utility>
84 #endif
85 
86 //== NAMESPACE ================================================================
87 
88 namespace OpenMesh { // BEGIN_NS_OPENMESH
89 namespace Utils { // BEGIN_NS_UTILS
90 
91 //== CLASS DEFINITION =========================================================
92 
93 
102 template <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 
142 template <class HeapEntry, class HeapInterface=HeapEntry>
143 class HeapT : private std::vector<HeapEntry>
144 {
145 private:
146  typedef std::vector<HeapEntry> Base;
147 
148 public:
149 
151  HeapT() : HeapVector() {}
152 
153 #if __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__)
154  HeapT(HeapInterface _interface)
156  : HeapVector(), interface_(std::move(_interface))
157  {}
158 #else
159  HeapT(const HeapInterface &_interface)
161  : HeapVector(), interface_(_interface)
162  {}
163 #endif
164 
166  ~HeapT(){};
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 
211  void pop_front()
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 
283 protected:
285  HeapInterface interface_;
286 
287 private:
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 
332 template <class HeapEntry, class HeapInterface>
333 void
334 HeapT<HeapEntry, HeapInterface>::
335 upheap(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 
353 template <class HeapEntry, class HeapInterface>
354 void
355 HeapT<HeapEntry, HeapInterface>::
356 downheap(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 
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:285
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
This class demonstrates the HeapInterface's interface.
Definition: HeapT.hh:103
void pop_front()
delete the first entry
Definition: HeapT.hh:211
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict less.
void reserve(size_t _n)
reserve space for _n entries
Definition: HeapT.hh:186
HeapT()
Constructor.
Definition: HeapT.hh:151
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:189
size_t size() const
returns the size of heap
Definition: HeapT.hh:183
This file provides the streams omlog, omout, and omerr.
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
void update(HeapEntry _h)
update an entry: change the key and update the position to reestablish the heap property.
Definition: HeapT.hh:253
bool empty() const
is heap empty?
Definition: HeapT.hh:180
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:197
bool check()
check heap condition
Definition: HeapT.hh:263
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:193
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:64
An efficient, highly customizable heap.
Definition: HeapT.hh:143
HeapEntry front() const
get the first entry
Definition: HeapT.hh:204
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
STL namespace.
void clear()
clear the heap
Definition: HeapT.hh:177
~HeapT()
Destructor.
Definition: HeapT.hh:166

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