Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
HeapT.hh
1 /*===========================================================================*\
2  * *
3  * OpenFlipper *
4  * Copyright (c) 2001-2015, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openflipper.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenFlipper. *
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  * $Author$ *
46  * $Date$ *
47  * *
48 \*===========================================================================*/
49 
50 
51 
52 
53 //=============================================================================
54 //
55 // CLASS HeapT
56 //
57 //=============================================================================
58 
59 #ifndef ACG_HEAP_HH
60 #define ACG_HEAP_HH
61 
62 
63 //== INCLUDES =================================================================
64 
65 #include <vector>
66 #include "../Config/ACGDefines.hh"
67 
68 
69 //== NAMESPACE ================================================================
70 
71 
72 namespace ACG {
73 
74 
75 //== CLASS DEFINITION =========================================================
76 
77 
86 template <class HeapEntry>
88 {
90  bool less(const HeapEntry& _e1, const HeapEntry& _e2);
91 
93  bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
94 
96  int get_heap_position(const HeapEntry& _e);
97 
99  void set_heap_position(HeapEntry& _e, int _i);
100 };
101 
102 
103 
120 template <class HeapEntry, class HeapInterface=HeapEntry>
121 class ACGDLLEXPORT HeapT : private std::vector<HeapEntry>
122 {
123 public:
124 
125  typedef std::vector<HeapEntry> Base;
126 
127 
129  HeapT() : HeapVector() {}
130 
132  HeapT(const HeapInterface& _interface)
133  : HeapVector(), interface_(_interface)
134  {}
135 
137  ~HeapT(){};
138 
139 
141  void clear() { HeapVector::clear(); }
142 
144  bool empty() { return HeapVector::empty(); }
145 
147  unsigned int size() { return HeapVector::size(); }
148 
150  void reserve(unsigned int _n) { HeapVector::reserve(_n); }
151 
153  void reset_heap_position(HeapEntry _h)
154  { interface_.set_heap_position(_h, -1); }
155 
157  bool is_stored(HeapEntry _h)
158  { return interface_.get_heap_position(_h) != -1; }
159 
161  void insert(HeapEntry _h) { this->push_back(_h); upheap(size()-1); }
162 
164  HeapEntry front() { assert(!empty()); return entry(0); }
165 
167  void pop_front()
168  {
169  assert(!empty());
170  interface_.set_heap_position(entry(0), -1);
171  if (size() > 1)
172  {
173  entry(0, entry(size()-1));
174  this->resize(size()-1);
175  downheap(0);
176  }
177  else this->resize(size()-1);
178  }
179 
181  void remove(HeapEntry _h)
182  {
183  int pos = interface_.get_heap_position(_h);
184  interface_.set_heap_position(_h, -1);
185 
186  assert(pos != -1);
187  assert((unsigned int) pos < size());
188 
189  // last item ?
190  if ((unsigned int) pos == size()-1)
191  resize(size()-1);
192 
193  else {
194  entry(pos, entry(size()-1)); // move last elem to pos
195  resize(size()-1);
196  downheap(pos);
197  upheap(pos);
198  }
199  }
200 
204  void update(HeapEntry _h)
205  {
206  int pos = interface_.get_heap_position(_h);
207  assert(pos != -1);
208  assert((unsigned int)pos < size());
209  downheap(pos);
210  upheap(pos);
211  }
212 
214  bool check()
215  {
216  bool ok(true);
217  unsigned int i, j;
218  for (i=0; i<size(); ++i)
219  {
220  if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j))) {
221  std::cerr << "Heap condition violated\n";
222  ok=false;
223  }
224  if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j))){
225  std::cerr << "Heap condition violated\n";
226  ok=false;
227  }
228  }
229  return ok;
230  }
231 
232 
233 private:
234 
235  // typedef
236  typedef std::vector<HeapEntry> HeapVector;
237 
238 
240  void upheap(unsigned int _idx);
241 
242 
244  void downheap(unsigned int _idx);
245 
246 
248  inline HeapEntry entry(unsigned int _idx) {
249  assert(_idx < size());
250  return (Base::operator[](_idx));
251  }
252 
253 
255  inline void entry(unsigned int _idx, HeapEntry _h) {
256  assert(_idx < size());
257  Base::operator[](_idx) = _h;
258  interface_.set_heap_position(_h, _idx);
259  }
260 
261 
263  inline unsigned int parent(unsigned int _i) { return (_i-1)>>1; }
265  inline unsigned int left(unsigned int _i) { return (_i<<1)+1; }
267  inline unsigned int right(unsigned int _i) { return (_i<<1)+2; }
268 
269 
271  HeapInterface interface_;
272 };
273 
274 
275 
276 
277 //== IMPLEMENTATION ==========================================================
278 
279 
280 template <class HeapEntry, class HeapInterface>
281 void
283 upheap(unsigned int _idx)
284 {
285  HeapEntry h = entry(_idx);
286  unsigned int parentIdx;
287 
288  while ((_idx>0) &&
289  interface_.less(h, entry(parentIdx=parent(_idx))))
290  {
291  entry(_idx, entry(parentIdx));
292  _idx = parentIdx;
293  }
294 
295  entry(_idx, h);
296 }
297 
298 
299 //-----------------------------------------------------------------------------
300 
301 
302 template <class HeapEntry, class HeapInterface>
303 void
305 downheap(unsigned int _idx)
306 {
307  HeapEntry h = entry(_idx);
308  unsigned int childIdx;
309  unsigned int s = size();
310 
311  while(_idx < s)
312  {
313  childIdx = left(_idx);
314  if (childIdx >= s) break;
315 
316  if ((childIdx+1 < s) &&
317  (interface_.less(entry(childIdx+1), entry(childIdx))))
318  ++childIdx;
319 
320  if (interface_.less(h, entry(childIdx))) break;
321 
322  entry(_idx, entry(childIdx));
323  _idx = childIdx;
324  }
325 
326  entry(_idx, h);
327 }
328 
329 
330 //=============================================================================
331 } // namespace ACG
332 //=============================================================================
333 #endif // ACG_HEAP_HH defined
334 //=============================================================================
335 
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict greater.
Namespace providing different geometric functions concerning angles.
Definition: DBSCANT.cc:51
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
void update(HeapEntry _h)
Definition: HeapT.hh:204
unsigned int parent(unsigned int _i)
Get parent's index.
Definition: HeapT.hh:263
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:153
HeapEntry front()
get the first entry
Definition: HeapT.hh:164
HeapEntry entry(unsigned int _idx)
Get the entry at index _idx.
Definition: HeapT.hh:248
bool empty()
is heap empty?
Definition: HeapT.hh:144
void reserve(unsigned int _n)
reserve space for _n entries
Definition: HeapT.hh:150
void upheap(unsigned int _idx)
Upheap. Establish heap property.
Definition: HeapT.hh:283
bool check()
check heap condition
Definition: HeapT.hh:214
unsigned int size()
returns the size of heap
Definition: HeapT.hh:147
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition: HeapT.hh:132
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:157
~HeapT()
Destructor.
Definition: HeapT.hh:137
unsigned int left(unsigned int _i)
Get left child's index.
Definition: HeapT.hh:265
unsigned int right(unsigned int _i)
Get right child's index.
Definition: HeapT.hh:267
void pop_front()
delete the first entry
Definition: HeapT.hh:167
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry's: strict less.
void downheap(unsigned int _idx)
Downheap. Establish heap property.
Definition: HeapT.hh:305
HeapT()
Constructor.
Definition: HeapT.hh:129
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:271
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:161
void clear()
clear the heap
Definition: HeapT.hh:141
void entry(unsigned int _idx, HeapEntry _h)
Set entry _h to index _idx and update _h's heap position.
Definition: HeapT.hh:255