1 //
2 // Copyright (C) 2004 Tanguy Fautr�.
3 // For conditions of distribution and use,
4 // see copyright notice in tri_stripper.h
5 //
6 //////////////////////////////////////////////////////////////////////
7 // SVN: $Id: heap_array.h 86 2005-06-08 17:47:27Z gpsnoopy $
8 //////////////////////////////////////////////////////////////////////
9
10 #ifndef TRI_STRIPPER_HEADER_GUARD_HEAP_ARRAY_H
11 #define TRI_STRIPPER_HEADER_GUARD_HEAP_ARRAY_H
12
13 #include <vector>
14
15
16
17
18 namespace triangle_stripper {
19
20 namespace detail {
21
22
23
24
25 // mutable heap
26 // can be interfaced pretty muck like an array
27 template <class T, class CmpT = std::less<T> >
28 class heap_array
29 {
30 public:
31
32 // Pre = PreCondition, Post = PostCondition
33
heap_array()34 heap_array() : m_Locked(false) { } // Post: ((size() == 0) && ! locked())
35
36 void clear(); // Post: ((size() == 0) && ! locked())
37
38 void reserve(size_t Size);
39 size_t size() const;
40
41 bool empty() const;
42 bool locked() const;
43 bool removed(size_t i) const; // Pre: (valid(i))
44 bool valid(size_t i) const;
45
46 size_t position(size_t i) const; // Pre: (valid(i))
47
48 const T & top() const; // Pre: (! empty())
49 const T & peek(size_t i) const; // Pre: (! removed(i))
50 const T & operator [] (size_t i) const; // Pre: (! removed(i))
51
52 void lock(); // Pre: (! locked()) Post: (locked())
53 size_t push(const T & Elem); // Pre: (! locked())
54
55 void pop(); // Pre: (locked() && ! empty())
56 void erase(size_t i); // Pre: (locked() && ! removed(i))
57 void update(size_t i, const T & Elem); // Pre: (locked() && ! removed(i))
58
59 protected:
60
61 heap_array(const heap_array &);
62 heap_array & operator = (const heap_array &);
63
64 class linker
65 {
66 public:
linker(const T & Elem,size_t i)67 linker(const T & Elem, size_t i)
68 : m_Elem(Elem), m_Index(i) { }
69
70 T m_Elem;
71 size_t m_Index;
72 };
73
74 typedef std::vector<linker> linked_heap;
75 typedef std::vector<size_t> finder;
76
77 void Adjust(size_t i);
78 void Swap(size_t a, size_t b);
79 bool Less(const linker & a, const linker & b) const;
80
81 linked_heap m_Heap;
82 finder m_Finder;
83 CmpT m_Compare;
84 bool m_Locked;
85 };
86
87
88
89
90
91 //////////////////////////////////////////////////////////////////////////
92 // heap_indexed inline functions
93 //////////////////////////////////////////////////////////////////////////
94
95 template <class T, class CmpT>
clear()96 inline void heap_array<T, CmpT>::clear()
97 {
98 m_Heap.clear();
99 m_Finder.clear();
100 m_Locked = false;
101 }
102
103
104 template <class T, class CmpT>
empty()105 inline bool heap_array<T, CmpT>::empty() const
106 {
107 return m_Heap.empty();
108 }
109
110
111 template <class T, class CmpT>
locked()112 inline bool heap_array<T, CmpT>::locked() const
113 {
114 return m_Locked;
115 }
116
117
118 template <class T, class CmpT>
reserve(const size_t Size)119 inline void heap_array<T, CmpT>::reserve(const size_t Size)
120 {
121 m_Heap.reserve(Size);
122 m_Finder.reserve(Size);
123 }
124
125
126 template <class T, class CmpT>
size()127 inline size_t heap_array<T, CmpT>::size() const
128 {
129 return m_Heap.size();
130 }
131
132
133 template <class T, class CmpT>
top()134 inline const T & heap_array<T, CmpT>::top() const
135 {
136 assert(! empty());
137
138 return m_Heap.front().m_Elem;
139 }
140
141
142 template <class T, class CmpT>
peek(const size_t i)143 inline const T & heap_array<T, CmpT>::peek(const size_t i) const
144 {
145 assert(! removed(i));
146
147 return (m_Heap[m_Finder[i]].m_Elem);
148 }
149
150
151 template <class T, class CmpT>
152 inline const T & heap_array<T, CmpT>::operator [] (const size_t i) const
153 {
154 return peek(i);
155 }
156
157
158 template <class T, class CmpT>
pop()159 inline void heap_array<T, CmpT>::pop()
160 {
161 assert(locked());
162 assert(! empty());
163
164 Swap(0, size() - 1);
165 m_Heap.pop_back();
166
167 if (! empty())
168 Adjust(0);
169 }
170
171
172 template <class T, class CmpT>
lock()173 inline void heap_array<T, CmpT>::lock()
174 {
175 assert(! locked());
176
177 m_Locked =true;
178 }
179
180
181 template <class T, class CmpT>
push(const T & Elem)182 inline size_t heap_array<T, CmpT>::push(const T & Elem)
183 {
184 assert(! locked());
185
186 const size_t Id = size();
187 m_Finder.push_back(Id);
188 m_Heap.push_back(linker(Elem, Id));
189 Adjust(Id);
190
191 return Id;
192 }
193
194
195 template <class T, class CmpT>
erase(const size_t i)196 inline void heap_array<T, CmpT>::erase(const size_t i)
197 {
198 assert(locked());
199 assert(! removed(i));
200
201 const size_t j = m_Finder[i];
202 Swap(j, size() - 1);
203 m_Heap.pop_back();
204
205 if (j != size())
206 Adjust(j);
207 }
208
209
210 template <class T, class CmpT>
removed(const size_t i)211 inline bool heap_array<T, CmpT>::removed(const size_t i) const
212 {
213 assert(valid(i));
214
215 return (m_Finder[i] >= m_Heap.size());
216 }
217
218
219 template <class T, class CmpT>
valid(const size_t i)220 inline bool heap_array<T, CmpT>::valid(const size_t i) const
221 {
222 return (i < m_Finder.size());
223 }
224
225
226 template <class T, class CmpT>
position(const size_t i)227 inline size_t heap_array<T, CmpT>::position(const size_t i) const
228 {
229 assert(valid(i));
230
231 return (m_Heap[i].m_Index);
232 }
233
234
235 template <class T, class CmpT>
update(const size_t i,const T & Elem)236 inline void heap_array<T, CmpT>::update(const size_t i, const T & Elem)
237 {
238 assert(locked());
239 assert(! removed(i));
240
241 const size_t j = m_Finder[i];
242 m_Heap[j].m_Elem = Elem;
243 Adjust(j);
244 }
245
246
247 template <class T, class CmpT>
Adjust(size_t i)248 inline void heap_array<T, CmpT>::Adjust(size_t i)
249 {
250 assert(i < m_Heap.size());
251
252 size_t j;
253
254 // Check the upper part of the heap
255 for (j = i; (j > 0) && (Less(m_Heap[(j - 1) / 2], m_Heap[j])); j = ((j - 1) / 2))
256 Swap(j, (j - 1) / 2);
257
258 // Check the lower part of the heap
259 for (i = j; (j = 2 * i + 1) < size(); i = j) {
260 if ((j + 1 < size()) && (Less(m_Heap[j], m_Heap[j + 1])))
261 ++j;
262
263 if (Less(m_Heap[j], m_Heap[i]))
264 return;
265
266 Swap(i, j);
267 }
268 }
269
270
271 template <class T, class CmpT>
Swap(const size_t a,const size_t b)272 inline void heap_array<T, CmpT>::Swap(const size_t a, const size_t b)
273 {
274 std::swap(m_Heap[a], m_Heap[b]);
275
276 m_Finder[(m_Heap[a].m_Index)] = a;
277 m_Finder[(m_Heap[b].m_Index)] = b;
278 }
279
280
281 template <class T, class CmpT>
Less(const linker & a,const linker & b)282 inline bool heap_array<T, CmpT>::Less(const linker & a, const linker & b) const
283 {
284 return m_Compare(a.m_Elem, b.m_Elem);
285 }
286
287
288
289
290 } // namespace detail
291
292 } // namespace triangle_stripper
293
294
295
296
297 #endif // TRI_STRIPPER_HEADER_GUARD_HEAP_ARRAY_H
298