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-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>
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>
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);
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 
HeapEntry front() const
get the first entry
Definition: HeapT.hh:180
~HeapT()
Destructor.
Definition: HeapT.hh:149
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:162
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:56
size_t size() const
returns the size of heap
Definition: HeapT.hh:159
HeapT()
Constructor.
Definition: HeapT.hh:141
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
void clear()
clear the heap
Definition: HeapT.hh:153
void update(HeapEntry _h)
update an entry: change the key and update the position to reestablish the heap property.
Definition: HeapT.hh:229
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:261
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:169
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:173
This class demonstrates the HeapInterface's interface.
Definition: HeapT.hh:93
bool empty() const
is heap empty?
Definition: HeapT.hh:156
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition: HeapT.hh:144
This file provides the streams omlog, omout, and omerr.
void pop_front()
delete the first entry
Definition: HeapT.hh:187
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:165
bool check()
check heap condition
Definition: HeapT.hh:239
An efficient, highly customizable heap.
Definition: HeapT.hh:133

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