acme
Foundational cross-platform layer of the ca2 framework
Loading...
Searching...
No Matches
_papaya_heap.h
1#pragma once
2
3
4namespace acme
5{
6
7 template <class RandomAccessIterator >
8 void make_heap (RandomAccessIterator first, RandomAccessIterator last)
9 {
10 raw_array < RandomAccessIterator > stackLowerBound;
11 raw_array < RandomAccessIterator > stackUpperBound;
12 RandomAccessIterator iLowerBound;
13 RandomAccessIterator iUpperBound;
14 RandomAccessIterator iLPos, iUPos, iMPos;
15 // ::u32 t;
16
17 if(last - first >= 2)
18 {
19 stackLowerBound.push(first);
20 stackUpperBound.push(last - 1);
21 while(true)
22 {
23 iLowerBound = stackLowerBound.pop();
24 iUpperBound = stackUpperBound.pop();
25 iLPos = iLowerBound;
26 iMPos = iLowerBound;
27 iUPos = iUpperBound;
28 while(true)
29 {
30 while(true)
31 {
32 if(iMPos == iUPos)
33 break;
34 if(!(*iMPos < *iUPos))
35 iUPos--;
36 else
37 {
38 auto t = *iMPos;
39 *iMPos = *iUPos;
40 *iUPos = t;
41 break;
42 }
43 }
44 if(iMPos == iUPos)
45 break;
46 iMPos = iUPos;
47 while(true)
48 {
49 if(iMPos == iLPos)
50 break;
51 if(!(*iLPos < *iMPos))
52 iLPos++;
53 else
54 {
55 auto t = *iMPos;
56 *iMPos = *iLPos;
57 *iLPos = t;
58 break;
59 }
60 }
61 if(iMPos == iLPos)
62 break;
63 iMPos = iLPos;
64 }
65 if(iLowerBound < iMPos - 1)
66 {
67 stackLowerBound.push(iLowerBound);
68 stackUpperBound.push(iMPos - 1);
69 }
70 if(iMPos + 1 < iUpperBound)
71 {
72 stackLowerBound.push(iMPos + 1);
73 stackUpperBound.push(iUpperBound);
74 }
75 if(stackLowerBound.get_size() == 0)
76 break;
77 }
78 }
79
80 }
81
82 template <class RandomAccessIterator, class Compare>
83 void make_heap (RandomAccessIterator first, RandomAccessIterator last,
84 Compare comp )
85 {
86 raw_array < RandomAccessIterator > stackLowerBound;
87 raw_array < RandomAccessIterator > stackUpperBound;
88 RandomAccessIterator iLowerBound;
89 RandomAccessIterator iUpperBound;
90 RandomAccessIterator iLPos, iUPos, iMPos;
91 // ::u32 t;
92
93 if(last - first >= 2)
94 {
95 stackLowerBound.push(first);
96 stackUpperBound.push(last - 1);
97 while(true)
98 {
99 iLowerBound = stackLowerBound.pop();
100 iUpperBound = stackUpperBound.pop();
101 iLPos = iLowerBound;
102 iMPos = iLowerBound;
103 iUPos = iUpperBound;
104 while(true)
105 {
106 while(true)
107 {
108 if(iMPos == iUPos)
109 break;
110 if(!comp(*iMPos, *iUPos))
111 iUPos--;
112 else
113 {
114 auto t = *iMPos;
115 *iMPos = *iUPos;
116 *iUPos = t;
117 break;
118 }
119 }
120 if(iMPos == iUPos)
121 break;
122 iMPos = iUPos;
123 while(true)
124 {
125 if(iMPos == iLPos)
126 break;
127 if(!comp(*iLPos, *iMPos))
128 iLPos++;
129 else
130 {
131 auto t = *iMPos;
132 *iMPos = *iLPos;
133 *iLPos = t;
134 break;
135 }
136 }
137 if(iMPos == iLPos)
138 break;
139 iMPos = iLPos;
140 }
141 if(iLowerBound < iMPos - 1)
142 {
143 stackLowerBound.push(iLowerBound);
144 stackUpperBound.push(iMPos - 1);
145 }
146 if(iMPos + 1 < iUpperBound)
147 {
148 stackLowerBound.push(iMPos + 1);
149 stackUpperBound.push(iUpperBound);
150 }
151 if(stackLowerBound.get_size() == 0)
152 break;
153 }
154 }
155 }
156
157
158 template <class RandomAccessIterator, class Compare>
159 void pop_heap (RandomAccessIterator first, RandomAccessIterator last)
160 {
161
162 make_heap(first, last);
163
164 auto t = *first;
165 *first = *last;
166 *last = t;
167
168 make_heap(first, last - 1);
169
170 }
171
172 template <class RandomAccessIterator, class Compare>
173 void pop_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
174 {
175
176 make_heap(first, last, comp);
177
178 auto t = *first;
179 *first = *last;
180 *last = t;
181
182 make_heap(first, last - 1, comp);
183
184 }
185
186 template <class RandomAccessIterator, class Compare>
187 void push_heap (RandomAccessIterator first, RandomAccessIterator last)
188 {
189
190 make_heap(first, last);
191
192 }
193
194 template <class RandomAccessIterator, class Compare>
195 void push_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
196 {
197
198 make_heap(first, last, comp);
199
200 }
201
202 template <class RandomAccessIterator>
203 void sort_heap (RandomAccessIterator first, RandomAccessIterator last)
204 {
205 raw_array < RandomAccessIterator > stackLowerBound;
206 raw_array < RandomAccessIterator > stackUpperBound;
207 RandomAccessIterator iLowerBound;
208 RandomAccessIterator iUpperBound;
209 RandomAccessIterator iLPos, iUPos, iMPos;
210 // ::u32 t;
211
212 if(last - first >= 2)
213 {
214 stackLowerBound.push(first);
215 stackUpperBound.push(last - 1);
216 while(true)
217 {
218 iLowerBound = stackLowerBound.pop();
219 iUpperBound = stackUpperBound.pop();
220 iLPos = iLowerBound;
221 iMPos = iLowerBound;
222 iUPos = iUpperBound;
223 while(true)
224 {
225 while(true)
226 {
227 if(iMPos == iUPos)
228 break;
229 if(*iMPos < *iUPos)
230 iUPos--;
231 else
232 {
233 auto t = *iMPos;
234 *iMPos = *iUPos;
235 *iUPos = t;
236 break;
237 }
238 }
239 if(iMPos == iUPos)
240 break;
241 iMPos = iUPos;
242 while(true)
243 {
244 if(iMPos == iLPos)
245 break;
246 if(*iLPos < *iMPos)
247 iLPos++;
248 else
249 {
250 auto t = *iMPos;
251 *iMPos = *iLPos;
252 *iLPos = t;
253 break;
254 }
255 }
256 if(iMPos == iLPos)
257 break;
258 iMPos = iLPos;
259 }
260 if(iLowerBound < iMPos - 1)
261 {
262 stackLowerBound.push(iLowerBound);
263 stackUpperBound.push(iMPos - 1);
264 }
265 if(iMPos + 1 < iUpperBound)
266 {
267 stackLowerBound.push(iMPos + 1);
268 stackUpperBound.push(iUpperBound);
269 }
270 if(stackLowerBound.get_size() == 0)
271 break;
272 }
273 }
274
275 }
276
277 template <class RandomAccessIterator, class Compare>
278 void sort_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp )
279 {
280 raw_array < RandomAccessIterator > stackLowerBound;
281 raw_array < RandomAccessIterator > stackUpperBound;
282 RandomAccessIterator iLowerBound;
283 RandomAccessIterator iUpperBound;
284 RandomAccessIterator iLPos, iUPos, iMPos;
285 // ::u32 t;
286
287 if(last - first >= 2)
288 {
289 stackLowerBound.push(first);
290 stackUpperBound.push(last - 1);
291 while(true)
292 {
293 iLowerBound = stackLowerBound.pop();
294 iUpperBound = stackUpperBound.pop();
295 iLPos = iLowerBound;
296 iMPos = iLowerBound;
297 iUPos = iUpperBound;
298 while(true)
299 {
300 while(true)
301 {
302 if(iMPos == iUPos)
303 break;
304 if(comp(*iMPos, *iUPos))
305 iUPos--;
306 else
307 {
308 auto t = *iMPos;
309 *iMPos = *iUPos;
310 *iUPos = t;
311 break;
312 }
313 }
314 if(iMPos == iUPos)
315 break;
316 iMPos = iUPos;
317 while(true)
318 {
319 if(iMPos == iLPos)
320 break;
321 if(comp(*iLPos, *iMPos))
322 iLPos++;
323 else
324 {
325 auto t = *iMPos;
326 *iMPos = *iLPos;
327 *iLPos = t;
328 break;
329 }
330 }
331 if(iMPos == iLPos)
332 break;
333 iMPos = iLPos;
334 }
335 if(iLowerBound < iMPos - 1)
336 {
337 stackLowerBound.push(iLowerBound);
338 stackUpperBound.push(iMPos - 1);
339 }
340 if(iMPos + 1 < iUpperBound)
341 {
342 stackLowerBound.push(iMPos + 1);
343 stackUpperBound.push(iUpperBound);
344 }
345 if(stackLowerBound.get_size() == 0)
346 break;
347 }
348 }
349 }
350
351
352
353} // namespace acme
354
355
356
357
358
359
acme
include "aura/graphics/image/context.h"
Definition aaaa__defer.h:32