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 
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>
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>
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
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
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 
HeapT()
Constructor.
Definition: HeapT.hh:146
An efficient, highly customizable heap.
Definition: HeapT.hh:138
size_t size() const
returns the size of heap
Definition: HeapT.hh:178
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:184
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:280
~HeapT()
Destructor.
Definition: HeapT.hh:161
bool check()
check heap condition
Definition: HeapT.hh:258
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry&#39;s: strict greater.
HeapEntry front() const
get the first entry
Definition: HeapT.hh:199
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:188
This class demonstrates the HeapInterface&#39;s interface.
Definition: HeapT.hh:98
void reserve(size_t _n)
reserve space for _n entries
Definition: HeapT.hh:181
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
void clear()
clear the heap
Definition: HeapT.hh:172
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:206
bool empty() const
is heap empty?
Definition: HeapT.hh:175
void update(HeapEntry _h)
update an entry: change the key and update the position to reestablish the heap property.
Definition: HeapT.hh:248
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:192
This file provides the streams omlog, omout, and omerr.

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