Developer Documentation

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
45
46
47 //=============================================================================
48 //
49 // CLASS HeapT
50 //
51 //=============================================================================
52
53 #ifndef ACG_HEAP_HH
54 #define ACG_HEAP_HH
55
56
57 //== INCLUDES =================================================================
58
59 #include <vector>
60 #include "../Config/ACGDefines.hh"
61
62
63 //== NAMESPACE ================================================================
64
65
66 namespace ACG {
67
68
69 //== CLASS DEFINITION =========================================================
70
71
80 template <class HeapEntry>
81 struct HeapInterfaceT
82 {
84 bool less(const HeapEntry& _e1, const HeapEntry& _e2);
85
87 bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
88
90 int get_heap_position(const HeapEntry& _e);
91
93 void set_heap_position(HeapEntry& _e, int _i);
94 };
95
96
97
114 template <class HeapEntry, class HeapInterface=HeapEntry>
115 class ACGDLLEXPORT HeapT : private std::vector<HeapEntry>
116 {
117 public:
118
119 typedef std::vector<HeapEntry> Base;
120
121
123 HeapT() : HeapVector() {}
124
126 HeapT(const HeapInterface& _interface)
127 : HeapVector(), interface_(_interface)
128 {}
129
131 ~HeapT(){};
132
133
135 void clear() { HeapVector::clear(); }
136
138 bool empty() { return HeapVector::empty(); }
139
141 unsigned int size() { return HeapVector::size(); }
142
144 void reserve(unsigned int _n) { HeapVector::reserve(_n); }
145
147 void reset_heap_position(HeapEntry _h)
148 { interface_.set_heap_position(_h, -1); }
149
151 bool is_stored(HeapEntry _h)
152 { return interface_.get_heap_position(_h) != -1; }
153
155 void insert(HeapEntry _h) { this->push_back(_h); upheap(size()-1); }
156
158 HeapEntry front() { assert(!empty()); return entry(0); }
159
161 void pop_front()
162 {
163 assert(!empty());
164 interface_.set_heap_position(entry(0), -1);
165 if (size() > 1)
166 {
167 entry(0, entry(size()-1));
168 this->resize(size()-1);
169 downheap(0);
170 }
171 else this->resize(size()-1);
172 }
173
175 void remove(HeapEntry _h)
176 {
177 int pos = interface_.get_heap_position(_h);
178 interface_.set_heap_position(_h, -1);
179
180 assert(pos != -1);
181 assert((unsigned int) pos < size());
182
183 // last item ?
184 if ((unsigned int) pos == size()-1)
185 resize(size()-1);
186
187 else {
188 entry(pos, entry(size()-1)); // move last elem to pos
189 resize(size()-1);
190 downheap(pos);
191 upheap(pos);
192 }
193 }
194
198 void update(HeapEntry _h)
199 {
200 int pos = interface_.get_heap_position(_h);
201 assert(pos != -1);
202 assert((unsigned int)pos < size());
203 downheap(pos);
204 upheap(pos);
205 }
206
208 bool check()
209 {
210 bool ok(true);
211 unsigned int i, j;
212 for (i=0; i<size(); ++i)
213 {
214 if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j))) {
215 std::cerr << "Heap condition violated\n";
216 ok=false;
217 }
218 if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j))){
219 std::cerr << "Heap condition violated\n";
220 ok=false;
221 }
222 }
223 return ok;
224 }
225
226
227 private:
228
229 // typedef
230 typedef std::vector<HeapEntry> HeapVector;
231
232
234 void upheap(unsigned int _idx);
235
236
238 void downheap(unsigned int _idx);
239
240
242 inline HeapEntry entry(unsigned int _idx) {
243 assert(_idx < size());
244 return (Base::operator[](_idx));
245 }
246
247
249 inline void entry(unsigned int _idx, HeapEntry _h) {
250 assert(_idx < size());
251 Base::operator[](_idx) = _h;
252 interface_.set_heap_position(_h, _idx);
253 }
254
255
257 inline unsigned int parent(unsigned int _i) { return (_i-1)>>1; }
259 inline unsigned int left(unsigned int _i) { return (_i<<1)+1; }
261 inline unsigned int right(unsigned int _i) { return (_i<<1)+2; }
262
263
265 HeapInterface interface_;
266 };
267
268
269
270
271 //== IMPLEMENTATION ==========================================================
272
273
274 template <class HeapEntry, class HeapInterface>
275 void
276 HeapT<HeapEntry, HeapInterface>::
277 upheap(unsigned int _idx)
278 {
279 HeapEntry h = entry(_idx);
280 unsigned int parentIdx;
281
282 while ((_idx>0) &&
283 interface_.less(h, entry(parentIdx=parent(_idx))))
284 {
285 entry(_idx, entry(parentIdx));
286 _idx = parentIdx;
287 }
288
289 entry(_idx, h);
290 }
291
292
293 //-----------------------------------------------------------------------------
294
295
296 template <class HeapEntry, class HeapInterface>
297 void
298 HeapT<HeapEntry, HeapInterface>::
299 downheap(unsigned int _idx)
300 {
301 HeapEntry h = entry(_idx);
302 unsigned int childIdx;
303 unsigned int s = size();
304
305 while(_idx < s)
306 {
307 childIdx = left(_idx);
308 if (childIdx >= s) break;
309
310 if ((childIdx+1 < s) &&
311 (interface_.less(entry(childIdx+1), entry(childIdx))))
312 ++childIdx;
313
314 if (interface_.less(h, entry(childIdx))) break;
315
316 entry(_idx, entry(childIdx));
317 _idx = childIdx;
318 }
319
320 entry(_idx, h);
321 }
322
323
324 //=============================================================================
325 } // namespace ACG
326 //=============================================================================
327 #endif // ACG_HEAP_HH defined
328 //=============================================================================
329
ACG::HeapInterfaceT::greater
bool greater(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry&#39;s: strict greater.
ACG::HeapT::~HeapT
~HeapT()
Destructor.
Definition: HeapT.hh:131
ACG
Namespace providing different geometric functions concerning angles.
Definition: BaseObjectData.hh:68
ACG::HeapT::HeapT
HeapT(const HeapInterface &_interface)
Construct with a given HeapIterface.
Definition: HeapT.hh:126
ACG::HeapT::HeapT
HeapT()
Constructor.
Definition: HeapT.hh:123
ACG::HeapInterfaceT
Definition: HeapT.hh:81
ACG::HeapT::upheap
void upheap(unsigned int _idx)
Upheap. Establish heap property.
Definition: HeapT.hh:277
ACG::HeapT::check
bool check()
check heap condition
Definition: HeapT.hh:208
ACG::HeapT::clear
void clear()
clear the heap
Definition: HeapT.hh:135
ACG::HeapT::pop_front
void pop_front()
delete the first entry
Definition: HeapT.hh:161
ACG::HeapT::parent
unsigned int parent(unsigned int _i)
Get parent&#39;s index.
Definition: HeapT.hh:257
ACG::HeapT::left
unsigned int left(unsigned int _i)
Get left child&#39;s index.
Definition: HeapT.hh:259
ACG::HeapT::entry
void entry(unsigned int _idx, HeapEntry _h)
Set entry _h to index _idx and update _h&#39;s heap position.
Definition: HeapT.hh:249
ACG::HeapInterfaceT::less
bool less(const HeapEntry &_e1, const HeapEntry &_e2)
Comparison of two HeapEntry&#39;s: strict less.
ACG::HeapT
Definition: HeapT.hh:115
ACG::HeapT::front
HeapEntry front()
get the first entry
Definition: HeapT.hh:158
ACG::HeapT::downheap
void downheap(unsigned int _idx)
Downheap. Establish heap property.
Definition: HeapT.hh:299
ACG::HeapT::empty
bool empty()
is heap empty?
Definition: HeapT.hh:138
ACG::HeapT::reset_heap_position
void reset_heap_position(HeapEntry _h)
reset heap position to -1 (not in heap)
Definition: HeapT.hh:147
ACG::HeapT::reserve
void reserve(unsigned int _n)
reserve space for _n entries
Definition: HeapT.hh:144
ACG::HeapT::update
void update(HeapEntry _h)
Definition: HeapT.hh:198
ACG::HeapT::size
unsigned int size()
returns the size of heap
Definition: HeapT.hh:141
ACG::HeapInterfaceT::get_heap_position
int get_heap_position(const HeapEntry &_e)
Get the heap position of HeapEntry _e.
ACG::HeapT::right
unsigned int right(unsigned int _i)
Get right child&#39;s index.
Definition: HeapT.hh:261
ACG::HeapT::is_stored
bool is_stored(HeapEntry _h)
is an entry in the heap?
Definition: HeapT.hh:151
ACG::HeapT::interface_
HeapInterface interface_
Instance of HeapInterface.
Definition: HeapT.hh:265
ACG::HeapInterfaceT::set_heap_position
void set_heap_position(HeapEntry &_e, int _i)
Set the heap position of HeapEntry _e.
ACG::HeapT::insert
void insert(HeapEntry _h)
insert the entry _h
Definition: HeapT.hh:155
ACG::HeapT::entry
HeapEntry entry(unsigned int _idx)
Get the entry at index _idx.
Definition: HeapT.hh:242