?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
remove \r
[extl.git] / extl / algorithm / detail / sort_impl.h
blobe2f6d1bf2ac901d61caddb870845e1056e3bda04
1 /* ///////////////////////////////////////////////////////////////////////
2 * File: sort_impl.h
3 *
4 * Created: 08.11.09
5 * Updated: 08.11.09
6 *
7 * Brief: The sort_impl algorithm
8 *
9 * [<Home>]
10 * Copyright (c) 2008-2020, Waruqi All rights reserved.
11 * //////////////////////////////////////////////////////////////////// */
12
13 #ifndef EXTL_ALGORITHM_SORT_IMPL_H
14 #define EXTL_ALGORITHM_SORT_IMPL_H
15
16 /*!\file sort_impl.h
17 * \brief The sort_impl algorithm
18 */
19 #ifndef __cplusplus
20 # error sort_impl.h need be supported by c++.
21 #endif
22
23 /* ///////////////////////////////////////////////////////////////////////
24 * Includes
25 */
26 #include "../prefix.h"
27
28 /* ///////////////////////////////////////////////////////////////////////
29 * ::extl namespace
30 */
31 EXTL_BEGIN_NAMESPACE
32 EXTL_DETAIL_BEGIN_NAMESPACE
33
34 // swap_impl
35 template<typename_param_k T>
36 EXTL_INLINE void swap_impl(T& lhs, T& rhs)
37 {
38 T temp = rhs;
39 rhs = lhs;
40 lhs = temp;
41 }
42
43 /* ///////////////////////////////////////////////////////////////////////
44 * bubble_sort
45 * time: O(n^2)
46 */
47
48 // bubble_sort_impl - using operator < for ascending
49 template<typename_param_k InIt>
50 EXTL_INLINE void bubble_sort_impl(InIt first, InIt last)
51 {
52 EXTL_ITERATOR_MUST_BE_INPUT(InIt);
53 EXTL_ASSERT(std_distance(first, last) >= 0);
54
55 InIt p2;
56 for (InIt p1 = first; p1 != last; ++p1)
57 for (p2 = p1, ++p2; p2 != last; ++p2)
58 if (*p2 < *p1) swap_impl(*p1, *p2);
59 }
60 // bubble_sort_impl - using pred
61 template< typename_param_k InIt
62 , typename_param_k Pr
63 >
64 EXTL_INLINE void bubble_sort_impl(InIt first, InIt last, Pr pred)
65 {
66 EXTL_ITERATOR_MUST_BE_INPUT(InIt);
67 EXTL_ASSERT(std_distance(first, last) >= 0);
68
69 InIt p2;
70 for (InIt p1 = first; p1 != last; ++p1)
71 for (p2 = p1, ++p2; p2 != last; ++p2)
72 if (pred(*p2, *p1)) swap_impl(*p1, *p2);
73 }
74
75 /* ///////////////////////////////////////////////////////////////////////
76 * insertion_sort
77 * time: O(n^2)
78 */
79
80 /* insertion_sort_impl - using operator< for ascending
81 *
82 * old: 5 2 6 2 8 6 1
83 *
84 * (hole)
85 * step1: ((5)) 2 6 2 8 6 1
86 * (next)
87 *
88 * (hole)
89 * step2: ((2)) (5) 6 2 8 6 1
90 * (next)
91 *
92 * (hole)
93 * step3: 2 5 ((6)) 2 8 6 1
94 * (next)
95 *
96 * (hole)
97 * step4: 2 ((2)) (5) (6) 8 6 1
98 * (next)
99 *
100 * (hole)
101 * step5: 2 2 5 6 ((8)) 6 1
102 * (next)
103 *
104 * (hole)
105 * step6: 2 2 5 6 ((6)) (8) 1
106 * (next)
107 *
108 * (hole)
109 * step7: ((1)) (2) (2) (5) (6) (6) (8)
110 * (next)
111 */
112 template<typename_param_k BidIt>
113 EXTL_INLINE void insertion_sort_impl(BidIt first, BidIt last)
114 {
115 EXTL_ITERATOR_MUST_BE_BIDIRECTIONAL(BidIt);
116 EXTL_ASSERT(std_distance(first, last) >= 0);
117 typedef typename_type_k xtl_iterator_traits<BidIt>::value_type value_type;
118
119 if (first != last)
120 {
121 for (BidIt next = first; ++next != last; )
122 {
123 value_type val = *next;
124
125 // look for hole and move elements[hole, next - 1] => [hole + 1, next]
126 for (BidIt last2 = next; last2 != first && val < *--last2; next = last2)
127 *next = *last2;
128
129 *next = val; // val => hole
130 }
131 }
132 }
133
134 // insertion_sort_impl - using pred
135 template< typename_param_k BidIt
136 , typename_param_k Pr
137 >
138 EXTL_INLINE void insertion_sort_impl(BidIt first, BidIt last, Pr pred)
139 {
140 EXTL_ITERATOR_MUST_BE_BIDIRECTIONAL(BidIt);
141 EXTL_ASSERT(std_distance(first, last) >= 0);
142 typedef typename_type_k xtl_iterator_traits<BidIt>::value_type value_type;
143
144 if (first != last)
145 {
146 for (BidIt next = first; ++next != last; )
147 {
148 value_type val = *next;
149
150 // look for hole and move elements[hole, next - 1] => [hole + 1, next]
151 for (BidIt last2 = next; last2 != first && pred(val, *--last2); next = last2)
152 *next = *last2;
153
154 *next = val; // val => hole
155 }
156 }
157 }
158
159 /* ///////////////////////////////////////////////////////////////////////
160 * heap_sort(max-heap)
161 * time: O(nlg(n))
162 */
163
164 // returns \true if the given range is a valid heap - using operator < for ascending
165 template<typename_param_k RanIt>
166 EXTL_INLINE e_bool_t is_valid_heap(RanIt first, RanIt last)
167 {
168 if (first != last)
169 {
170 for (RanIt root = first; ++first != last; ++root)
171 {
172 if (*root < *first) // *root < left child
173 return e_false_v;
174 else if (++first == last)
175 break;
176 else if (*root < *first) // *root < right child
177 return e_false_v;
178 }
179 }
180 return e_true_v;
181 }
182
183 // returns \true if the given range is a valid heap - using pred
184 template< typename_param_k RanIt
185 , typename_param_k Pr
186 >
187 EXTL_INLINE e_bool_t is_valid_heap(RanIt first, RanIt last, Pr pred)
188 {
189 if (first != last)
190 {
191 for (RanIt root = first; ++first != last; ++root)
192 {
193 if (pred(*root, *first))
194 return e_false_v;
195 else if (++first == last)
196 break;
197 else if (pred(*root, *first))
198 return e_false_v;
199 }
200 }
201 return e_true_v;
202 }
203 /* push_heap_impl - using operator < for ascending
204 *
205 * hole: bottom => top
206 * init:
207 * 16(top)
208 * -------------------------
209 * | |
210 * 14 10
211 * -------------- -------------
212 * | | | |
213 * 8(parent) 7 9 3
214 * ---------
215 * | |
216 * 2 (hole) <= 11(val)
217 * after:
218 * 16(top)
219 * -------------------------
220 * | |
221 * 14(parent) 10
222 * -------------- -------------
223 * | | | |
224 * 11(hole) 7 9 3
225 * ---------
226 * | |
227 * 2 8
228 */
229 template< typename_param_k RanIt
230 , typename_param_k Diff
231 , typename_param_k Val
232 >
233 EXTL_INLINE void push_heap_impl(RanIt first, Diff hole, Diff top, Val val)
234 {
235 // (hole - 1) / 2: the parent node of the hole
236 // finds the final hole
237 for (Diff i = (hole - 1) / 2; hole > top && *(first + i) < val; i = (hole - 1) / 2)
238 {
239 // copy value: parent => hole
240 *(first + hole) = *(first + i);
241
242 // move node: hole => parent
243 hole = i;
244 }
245
246 // set value
247 *(first + hole) = val;
248 }
249
250 // push_heap_impl - using pred
251 template< typename_param_k RanIt
252 , typename_param_k Diff
253 , typename_param_k Val
254 , typename_param_k Pr
255 >
256 EXTL_INLINE void push_heap_impl(RanIt first, Diff hole, Diff top, Val val, Pr pred)
257 {
258 // (hole - 1) / 2: the parent node of the hole
259 // finds the final hole
260 for (Diff i = (hole - 1) / 2; hole > top && pred(*(first + i), val); i = (hole - 1) / 2)
261 {
262 // copy value: parent => hole
263 *(first + hole) = *(first + i);
264
265 // move node: hole => parent
266 hole = i;
267 }
268
269 // set value
270 *(first + hole) = val;
271 }
272
273 /* adjust_heap_impl - using operator < for ascending
274 *
275 * hole: top => bottom
276 * init:
277 * 16(first)
278 * -------------------------
279 * | |
280 * (hole) 10
281 * -------------- -------------
282 * | | | |
283 * 8(larger) 7 9 3
284 * --------- ----
285 * | | |
286 * 2 4 1(bottom - 1)
287 *
288 * after:
289 * 16(first)
290 * -------------------------
291 * | |
292 * 8 10
293 * -------------- -------------
294 * | | | |
295 * (hole) 7 9 3
296 * --------- ----
297 * | | |
298 * 2 (larger)4 1(bottom - 1)
299 *
300 * after:
301 * 16(first)
302 * -------------------------
303 * | |
304 * 8 10
305 * -------------- -------------
306 * | | | |
307 * 4 7 9 3
308 * --------- ----
309 * | | |
310 * 2 (hole) 1(bottom - 1)
311 */
312 template< typename_param_k RanIt
313 , typename_param_k Diff
314 , typename_param_k Val
315 >
316 EXTL_INLINE void adjust_heap_impl(RanIt first, Diff hole, Diff bottom, Val val)
317 {
318 // save top position
319 Diff top = hole;
320
321 // 2 * hole + 2: the right child node of hole
322 Diff i = 2 * hole + 2;
323
324 for (; i < bottom; i = 2 * i + 2)
325 {
326 // gets the larger child node
327 if (*(first + i) < *(first + (i - 1))) --i;
328
329 // larger child => hole
330 *(first + hole) = *(first + i);
331
332 // move the hole down to it's larger child node
333 hole = i;
334 }
335
336 if (i == bottom)
337 {
338 // bottom child => hole
339 *(first + hole) = *(first + (bottom - 1));
340
341 // move hole down to bottom
342 hole = bottom - 1;
343 }
344
345 // push val into the hole
346 push_heap_impl(first, hole, top, val);
347 }
348
349 // adjust_heap_impl - using pred
350 template< typename_param_k RanIt
351 , typename_param_k Diff
352 , typename_param_k Val
353 , typename_param_k Pr
354 >
355 EXTL_INLINE void adjust_heap_impl(RanIt first, Diff hole, Diff bottom, Val val, Pr pred)
356 {
357 // save top position
358 Diff top = hole;
359
360 // 2 * hole + 2: the right child node of hole
361 Diff i = 2 * hole + 2;
362
363 for (; i < bottom; i = 2 * i + 2)
364 {
365 // gets the larger child node
366 if (pred(*(first + i), *(first + (i - 1)))) --i;
367
368 // larger child => hole
369 *(first + hole) = *(first + i);
370
371 // move the hole down to it's larger child node
372 hole = i;
373 }
374
375 if (i == bottom)
376 {
377 // bottom child => hole
378 *(first + hole) = *(first + (bottom - 1));
379
380 // move hole down to bottom
381 hole = bottom - 1;
382 }
383
384 // push val into the hole
385 push_heap_impl(first, hole, top, val, pred);
386 }
387
388 // error: there are no arguments to `invariance_error' that depend on a template parameter, so a declaration of `invariance_error' must be available
389 /*#ifdef EXTL_COMPILER_IS_GCC
390 class invariance_error;
391 #endif*/
392 /* pop_heap_impl - using operator < for ascending
393 *
394 * pop *first to *dest and reheap
395 * 16
396 * -------------------------
397 * | |
398 * 14(first)---- 10
399 * -------------- | -------------
400 * | | | | |
401 * 8 7 | 9 3
402 * --------- ---- |
403 * | | | |
404 * 2 4 1(dest)<-
405 *
406 */
407 template< typename_param_k RanIt
408 , typename_param_k Val
409 >
410 EXTL_INLINE void pop_heap_impl(RanIt first, RanIt last, RanIt dest, Val val)
411 {
412 EXTL_MESSAGE_ASSERT(is_valid_heap(first, last), "invalid heap");
413 //EXTL_ASSERT_THROW(is_valid_heap(first, last), invariance_error("invalid heap"));
414
415 typedef typename_type_k xtl_iterator_traits<RanIt>::difference_type difference_type;
416 *dest = *first;
417 adjust_heap_impl(first, difference_type(0), difference_type(last - first), val);
418
419 EXTL_MESSAGE_ASSERT(is_valid_heap(first, last), "invalid heap");
420 //EXTL_ASSERT_THROW(is_valid_heap(first, last), invariance_error("invalid heap"));
421 }
422
423 // pop_heap_impl - using pred
424 template< typename_param_k RanIt
425 , typename_param_k Val
426 , typename_param_k Pr
427 >
428 EXTL_INLINE void pop_heap_impl(RanIt first, RanIt last, RanIt dest, Val val, Pr pred)
429 {
430 EXTL_MESSAGE_ASSERT(is_valid_heap(first, last, pred), "invalid heap");
431 //EXTL_ASSERT_THROW(is_valid_heap(first, last, pred), invariance_error("invalid heap"));
432
433 typedef typename_type_k xtl_iterator_traits<RanIt>::difference_type difference_type;
434 *dest = *first;
435 adjust_heap_impl(first, difference_type(0), difference_type(last - first), val, pred);
436
437 EXTL_MESSAGE_ASSERT(is_valid_heap(first, last, pred), "invalid heap");
438 //EXTL_ASSERT_THROW(is_valid_heap(first, last, pred), invariance_error("invalid heap"));
439 }
440 /* pop_heap_0_impl - using operator < for ascending
441 *
442 * pop the top of heap to *(last - 1) and reheap
443 * 16(first)
444 * ----------------|--------
445 * | | |
446 * 14 | 10
447 * -------------- | -------------
448 * | | | | |
449 * 8 7 | 9 3
450 * --------- ---- |
451 * | | | |
452 * 2 4 1(last - 1)<-
453 * (hole)
454 */
455 template<typename_param_k RanIt>
456 EXTL_INLINE void pop_heap_0_impl(RanIt first, RanIt last)
457 {
458 typedef typename_type_k xtl_iterator_traits<RanIt>::value_type value_type;
459
460 if (last - first > 1)
461 pop_heap_impl(first, last - 1, last - 1, value_type(*(last - 1)));
462 }
463
464 // pop_heap_0_impl - using pred
465 template< typename_param_k RanIt
466 , typename_param_k Pr
467 >
468 EXTL_INLINE void pop_heap_0_impl(RanIt first, RanIt last, Pr pred)
469 {
470 typedef typename_type_k xtl_iterator_traits<RanIt>::value_type value_type;
471
472 if (last - first > 1)
473 pop_heap_impl(first, last - 1, last - 1, value_type(*(last - 1)), pred);
474 }
475
476 /* make_heap_impl: - using operator < for ascending
477 * heap: 16 14 10 8 7 9 3 2 4 1
478 *
479 * 16(first)
480 * -------------------------
481 * | |
482 * 14 10
483 * -------------- -------------
484 * | | | |
485 * 8 (bottom / 2 - 1)7 9 3
486 * --------- ----
487 * | | |
488 * 2 4 1(bottom - 1)
489 */
490 template<typename_param_k RanIt>
491 EXTL_INLINE void make_heap_impl(RanIt first, RanIt last)
492 {
493 typedef typename_type_k xtl_iterator_traits<RanIt>::difference_type difference_type;
494 typedef typename_type_k xtl_iterator_traits<RanIt>::value_type value_type;
495
496 // adjust heap[0, bottom / 2 - 1]
497 // hole = (bottom / 2 - 1) ... 0
498 difference_type bottom = last - first;
499 for (difference_type hole = bottom / 2; hole > 0; )
500 {
501 // reheap top half, bottom to top
502 --hole;
503 adjust_heap_impl(first, hole, bottom, value_type(*(first + hole)));
504 }
505
506 EXTL_MESSAGE_ASSERT(is_valid_heap(first, last), "invalid heap");
507 //EXTL_ASSERT_THROW(is_valid_heap(first, last), invariance_error("invalid heap"));
508 }
509 // make_heap_impl: - using pred
510 template< typename_param_k RanIt
511 , typename_param_k Pr
512 >
513 EXTL_INLINE void make_heap_impl(RanIt first, RanIt last, Pr pred)
514 {
515 typedef typename_type_k xtl_iterator_traits<RanIt>::difference_type difference_type;
516 typedef typename_type_k xtl_iterator_traits<RanIt>::value_type value_type;
517
518 // adjust heap[0, bottom / 2 - 1]
519 // hole = (bottom / 2 - 1) ... 0
520 difference_type bottom = last - first;
521 for (difference_type hole = bottom / 2; hole > 0; )
522 {
523 // reheap top half, bottom to top
524 --hole;
525 adjust_heap_impl(first, hole, bottom, value_type(*(first + hole)), pred);
526 }
527
528 EXTL_MESSAGE_ASSERT(is_valid_heap(first, last, pred), "invalid heap");
529 //EXTL_ASSERT_THROW(is_valid_heap(first, last, pred), invariance_error("invalid heap"));
530 }
531 /* heap_sort_impl(max-heap) - using operator < for ascending
532 *
533 * init:
534 *
535 * 16(first)
536 * -------------------------
537 * | |
538 * 4 10
539 * -------------- -------------
540 * | | | |
541 * 14 7 9 3
542 * --------- ----
543 * | | |
544 * 2 8 1(last - 1)
545 *
546 * make_heap:
547 *
548 * 16(first)
549 * -------------------------
550 * | |
551 * 14 10
552 * -------------- -------------
553 * | | | |
554 * 8 7 9 3
555 * --------- ----
556 * | | |
557 * 2 4 1(last - 1)
558 * pop_heap:
559 *
560 * 16(first)--------------------------
561 * ------------------------- |
562 * | | |
563 * 4 10 |
564 * -------------- ------------- |
565 * | | | | |
566 * 14 7 9 3 |
567 * --------- ---- |
568 * | | | |
569 * 2 8 1(last - 1) <------------------------------
570 *
571 * (hole)(first)
572 * -------------------------
573 * | |
574 * 4 10
575 * -------------- -------------
576 * | | | | (val = 1)
577 * 14 7 9 3
578 * --------- ----
579 * | | |
580 * 2 8 16(last - 1)
581 *
582 * adjust_heap:
583 * 14(first)
584 * -------------------------
585 * | |
586 * 8 10
587 * -------------- -------------
588 * | | | | (val = 1)
589 * 4 7 9 3
590 * ---------
591 * | |
592 * 2 (hole)(last - 1) 16
593 *
594 *
595 * push_heap:
596 * 14(first)
597 * -------------------------
598 * | |
599 * 8 10
600 * -------------- -------------
601 * | | | | (val = 1)
602 * 4 7 9 3 |
603 * --------- |
604 * | | /-----------------------------------------------
605 * 2 (hole)(last - 1) 16
606 *
607 * 14(first)
608 * -------------------------
609 * | |
610 * 8 10
611 * -------------- -------------
612 * | | | | (val = 1)
613 * 4 7 9 3
614 * ---------
615 * | |
616 * 2 1(last - 1) 16
617 *
618 * pop_heap adjust_heap push_heap ...
619 *
620 * final_heap:
621 * 1(first)
622 *
623 *
624 * 2 3
625 *
626 *
627 * 4 7 8 9
628 *
629 *
630 * 10 14 16
631 *
632 * result: 1 2 3 4 7 8 9 10 14 16
633 */
634 template<typename_param_k RanIt>
635 EXTL_INLINE void heap_sort_impl(RanIt first, RanIt last)
636 {
637 EXTL_ITERATOR_MUST_BE_RANDOM_ACCESS(RanIt);
638 EXTL_ASSERT(std_distance(first, last) >= 0);
639
640 make_heap_impl(first, last);
641
642 for (; 1 < last - first; --last)
643 pop_heap_0_impl(first, last);
644 }
645 // heap_sort_impl(max-heap) - using pred
646 template< typename_param_k RanIt
647 , typename_param_k Pr
648 >
649 EXTL_INLINE void heap_sort_impl(RanIt first, RanIt last, Pr pred)
650 {
651 EXTL_ITERATOR_MUST_BE_RANDOM_ACCESS(RanIt);
652 EXTL_ASSERT(std_distance(first, last) >= 0);
653
654 make_heap_impl(first, last, pred);
655
656 for (; 1 < last - first; --last)
657 pop_heap_0_impl(first, last, pred);
658 }
659 // heap_sort_top_n - using operator < for descending
660 template< typename_param_k RanIt
661 , typename_param_k Diff
662 >
663 EXTL_INLINE void heap_sort_top_n_impl(RanIt first, RanIt last, Diff n)
664 {
665 EXTL_ITERATOR_MUST_BE_RANDOM_ACCESS(RanIt);
666 EXTL_ASSERT(std_distance(first, last) >= 0);
667 EXTL_ASSERT(n >= 0);
668
669 typedef typename_type_k xtl_iterator_traits<RanIt>::value_type value_type;
670 typedef reverse_iterator_base<RanIt> reverse_iterator_type;
671 reverse_iterator_type rfirst(last);
672 reverse_iterator_type rlast(first);
673
674 make_heap_impl(rfirst, rlast);
675
676 for (; 1 < rlast - rfirst && n--; --rlast)
677 pop_heap_0_impl(rfirst, rlast);
678 }
679
680 // heap_sort_top_n - using pred
681 template< typename_param_k RanIt
682 , typename_param_k Diff
683 , typename_param_k Pr
684 >
685 EXTL_INLINE void heap_sort_top_n_impl(RanIt first, RanIt last, Diff n, Pr pred)
686 {
687 EXTL_ITERATOR_MUST_BE_RANDOM_ACCESS(RanIt);
688 EXTL_ASSERT(std_distance(first, last) >= 0);
689 EXTL_ASSERT(n >= 0);
690
691 typedef typename_type_k xtl_iterator_traits<RanIt>::value_type value_type;
692 typedef reverse_iterator_base<RanIt> reverse_iterator_type;
693 reverse_iterator_type rfirst(last);
694 reverse_iterator_type rlast(first);
695
696 make_heap_impl(rfirst, rlast, pred);
697
698 for (; 1 < rlast - rfirst && n--; --rlast)
699 pop_heap_0_impl(rfirst, rlast, pred);
700 }
701
702 /* ///////////////////////////////////////////////////////////////////////
703 * ::extl namespace
704 */
705 EXTL_DETAIL_END_NAMESPACE
706 EXTL_END_NAMESPACE
707
708 /* //////////////////////////////////////////////////////////////////// */
709 #endif /* EXTL_ALGORITHM_SORT_IMPL_H */
710 /* //////////////////////////////////////////////////////////////////// */
a c++ generic library