acme
Foundational cross-platform layer of the ca2 framework
Loading...
Searching...
No Matches
_sort.h
1#pragma once
2
3
4#include "numeric_array.h"
5#include "acme/prototype/comparison/less.h"
6
7
8namespace sort
9{
10
11
12 template<typename A, typename B>
13 constexpr bool sort(A & a, B & b)
14 {
15
16 if (b < a)
17 {
18
19 swap(a, b);
20
21 return true;
22
23 }
24
25 return false;
26
27 }
28
29 template<class TYPE>
30 static iptr NumericCompare(const TYPE * pointA, const TYPE * pointB);
31
32 // static iptr DWordCompare(const iptr dwA, const iptr dwB);
33
34 // static void BubbleSort(LPINT pInt, iptr i32_size);
35
36
37 // static void quick_sort(
38 // array<::u32, ::u32> & a,
39 // iptr (*fCompare)(const iptr, const iptr),
40 //void (*__swap)(void * pVoidSwapArg, iptr iA, iptr iB),
41
42 //void * pVoidSwapArg);
43
44
45 template<class A>
46 static iptr CompareTkPosition(const A a1, const A a2);
47
48 template<class TYPE>
49 iptr NumericCompare(const TYPE * p1, const TYPE * p2)
50 {
51 if (*p1 > *p2)
52 return 1;
53 else if (*p1 < *p2)
54 return -1;
55 else
56 return 0;
57 }
58
59
60 template<class A>
61 static iptr CompareTkPosition(const A a1, const A a2)
62 {
63 if (a1.m_tkPosition > a2.m_tkPosition)
64 return 1;
65 else if (a1.m_tkPosition > a2.m_tkPosition)
66 return -1;
67 else
68 return 0;
69 }
70
71 // template <class TYPE, class ARG_TYPE>
72 // void SwapArray(
73 // array<TYPE, ARG_TYPE> & a,
74 // iptr iA,
75 // iptr iB)
76 // {
77 // TYPE t;
78 // t = a.get_at(iA);
79 // a.set_at(iA, a.get_at(iB));
80 // a.set_at(iB, t);
81 // };
82 /*template <class TYPE, class ARG_TYPE>
83 void quick_sort(
84 array<TYPE, ARG_TYPE> & array,
85 ::std::strong_ordering (* fCompare)(const TYPE *, const TYPE *),
86 void (* fSwap)(TYPE *, TYPE *));*/
87
88 /*template <class TYPE, class ARG_TYPE>
89 void __swap(
90 CarrayInterface<TYPE, ARG_TYPE> * parray,
91 iptr iA,
92 iptr iB)
93 {
94 TYPE t;
95 t = parray->element_at(iA);
96 parray->set_at(iA, parray->element_at(iB));
97 parray->set_at(iB, t);
98 };*/
99
100
101 template<class TYPE>
102 iptr CompareAscending(
103 TYPE * pA,
104 TYPE * pB)
105 {
106 return *pA - *pB;
107 };
108
109 template<class TYPE, class ARG_TYPE, class FIRST>
110 void quick_sort(array<TYPE, ARG_TYPE> & a)
111 {
112 TYPE t;
113 index_array stackLowerBound;
114 index_array stackUpperBound;
115 iptr iLowerBound;
116 iptr iUpperBound;
117 iptr iLPos, iUPos, iMPos;
118 // ::u32 t;
119
120 if (a.get_size() >= 2)
121 {
122 stackLowerBound.push(0);
123 stackUpperBound.push(a.get_size() - 1);
124 while (true)
125 {
126 iLowerBound = stackLowerBound.pop();
127 iUpperBound = stackUpperBound.pop();
128 iLPos = iLowerBound;
129 iMPos = iLowerBound;
130 iUPos = iUpperBound;
131 while (true)
132 {
133 while (true)
134 {
135 if (iMPos == iUPos)
136 break;
137 if (FIRST::Compare(&a.element_at(iMPos), &a.element_at(iUPos)) <= 0)
138 iUPos--;
139 else
140 {
141 t = a.element_at(iMPos);
142 a.element_at(iMPos) = a.element_at(iUPos);
143 a.element_at(iUPos) = t;
144 break;
145 }
146 }
147 if (iMPos == iUPos)
148 break;
149 iMPos = iUPos;
150 while (true)
151 {
152 if (iMPos == iLPos)
153 break;
154 if (FIRST::Compare(&a.element_at(iLPos), &a.element_at(iMPos)) <= 0)
155 iLPos++;
156 else
157 {
158 t = a.element_at(iMPos);
159 a.element_at(iMPos) = a.element_at(iLPos);
160 a.element_at(iLPos) = t;
161 break;
162 }
163 }
164 if (iMPos == iLPos)
165 break;
166 iMPos = iLPos;
167 }
168 if (iLowerBound < iMPos - 1)
169 {
170 stackLowerBound.push(iLowerBound);
171 stackUpperBound.push(iMPos - 1);
172 }
173 if (iMPos + 1 < iUpperBound)
174 {
175 stackLowerBound.push(iMPos + 1);
176 stackUpperBound.push(iUpperBound);
177 }
178 if (stackLowerBound.get_size() == 0)
179 break;
180 }
181 }
182
183 };
184
185
186 template<class TYPE, class ARG_TYPE, typename SWAP>
187 void quick_sort(
188 array<TYPE, ARG_TYPE> & a,
189 SWAP __swap)
190 {
191 index_array stackLowerBound;
192 index_array stackUpperBound;
193 iptr iLowerBound;
194 iptr iUpperBound;
195 iptr iLPos, iUPos, iMPos;
196
197 if (a.get_size() >= 2)
198 {
199 stackLowerBound.push(0);
200 stackUpperBound.push(a.get_size() - 1);
201 while (true)
202 {
203 iLowerBound = stackLowerBound.pop();
204 iUpperBound = stackUpperBound.pop();
205 iLPos = iLowerBound;
206 iMPos = iLowerBound;
207 iUPos = iUpperBound;
208 while (true)
209 {
210 while (true)
211 {
212 if (iMPos == iUPos)
213 break;
214 if (a.get_at(iMPos) <= a.get_at(iUPos))
215 iUPos--;
216 else
217 {
218 a.__swap(iMPos, iUPos);
219 __swap(iUPos, iMPos);
220 break;
221 }
222 }
223 if (iMPos == iUPos)
224 break;
225 iMPos = iUPos;
226 while (true)
227 {
228 if (iMPos == iLPos)
229 break;
230 if (a.get_at(iLPos) <= a.get_at(iMPos))
231 iLPos++;
232 else
233 {
234 a.__swap(iMPos, iLPos);
235 __swap(iLPos, iMPos);
236 break;
237 }
238 }
239 if (iMPos == iLPos)
240 break;
241 iMPos = iLPos;
242 }
243 if (iLowerBound < iMPos - 1)
244 {
245 stackLowerBound.push(iLowerBound);
246 stackUpperBound.push(iMPos - 1);
247 }
248 if (iMPos + 1 < iUpperBound)
249 {
250 stackLowerBound.push(iMPos + 1);
251 stackUpperBound.push(iUpperBound);
252 }
253 if (stackLowerBound.get_size() == 0)
254 break;
255 }
256 }
257
258 }
259
260
261 template<class TYPE, class ARG_TYPE>
262 void quick_sort(
263 array<TYPE, ARG_TYPE> & a,
264 ::std::strong_ordering fCompare(const ARG_TYPE, const ARG_TYPE),
265 void __swap(void * pVoidSwapArg, iptr iA, iptr iB),
266
267 void * pVoidSwapArg)
268 {
269 index_array stackLowerBound;
270 index_array stackUpperBound;
271 iptr iLowerBound;
272 iptr iUpperBound;
273 iptr iLPos, iUPos, iMPos;
274
275 if (a.get_size() >= 2)
276 {
277 stackLowerBound.push(0);
278 stackUpperBound.push(a.get_size() - 1);
279 while (true)
280 {
281 iLowerBound = stackLowerBound.pop();
282 iUpperBound = stackUpperBound.pop();
283 iLPos = iLowerBound;
284 iMPos = iLowerBound;
285 iUPos = iUpperBound;
286 while (true)
287 {
288 while (true)
289 {
290 if (iMPos == iUPos)
291 break;
292 if (fCompare(a.get_at(iMPos), a.get_at(iUPos)) <= 0)
293 iUPos--;
294 else
295 {
296 a.__swap(iMPos, iUPos);
297 __swap(pVoidSwapArg, iUPos, iMPos);
298
299 break;
300 }
301 }
302 if (iMPos == iUPos)
303 break;
304 iMPos = iUPos;
305 while (true)
306 {
307 if (iMPos == iLPos)
308 break;
309 if (fCompare(a.get_at(iLPos), a.get_at(iMPos)) <= 0)
310 iLPos++;
311 else
312 {
313 a.__swap(iMPos, iLPos);
314 __swap(pVoidSwapArg, iLPos, iMPos);
315
316 break;
317 }
318 }
319 if (iMPos == iLPos)
320 break;
321 iMPos = iLPos;
322 }
323 if (iLowerBound < iMPos - 1)
324 {
325 stackLowerBound.push(iLowerBound);
326 stackUpperBound.push(iMPos - 1);
327 }
328 if (iMPos + 1 < iUpperBound)
329 {
330 stackLowerBound.push(iMPos + 1);
331 stackUpperBound.push(iUpperBound);
332 }
333 if (stackLowerBound.get_size() == 0)
334 break;
335 }
336 }
337
338 }
339
340
341 template<class iterator, class COMPARE = ::comparison::less<typename iterator::BASE_TYPE, typename iterator::BASE_ARG_TYPE> >
342 void quick_sort(const iterator & a, const iterator & b);
343
344
345
346
347
348 //template <class TYPE, class ARG_TYPE>
349 //void quick_sort(
350 // array<TYPE, ARG_TYPE> & a,
351 // ::i32 (* fCompare)(const ARG_TYPE, const ARG_TYPE))
352 //{
353 // index_array stackLowerBound;
354 // index_array stackUpperBound;
355 // iptr iLowerBound;
356 // iptr iUpperBound;
357 // iptr iLPos, iUPos, iMPos;
358 // TYPE t;
359
360 // if(a.get_size() >= 2)
361 // {
362 // stackLowerBound.push(0);
363 // stackUpperBound.push(a.get_size() - 1);
364 // while(true)
365 // {
366 // iLowerBound = stackLowerBound.pop();
367 // iUpperBound = stackUpperBound.pop();
368 // iLPos = iLowerBound;
369 // iMPos = iLowerBound;
370 // iUPos = iUpperBound;
371 // while(true)
372 // {
373 // while(true)
374 // {
375 // if(iMPos == iUPos)
376 // break;
377 // if(fCompare(a.element_at(iMPos), a.element_at(iUPos)) <= 0)
378 // iUPos--;
379 // else
380 // {
381 // // t = a.get_at(iMPos);
382 // // a.set_at(iMPos, a.get_at(iUPos));
383 // //a.set_at(iUPos, t);
384 // a.__swap(iMPos, iUPos);
385 // break;
386 // }
387 // }
388 // if(iMPos == iUPos)
389 // break;
390 // iMPos = iUPos;
391 // while(true)
392 // {
393 // if(iMPos == iLPos)
394 // break;
395 // if(fCompare(a.element_at(iLPos), a.element_at(iMPos)) <= 0)
396 // iLPos++;
397 // else
398 // {
399 // // t = a.get_at(iMPos);
400 // // a.set_at(iMPos, a.get_at(iLPos));
401 // // a.set_at(iLPos, t);
402 // a.__swap(iLPos, iMPos);
403 // break;
404 // }
405 // }
406 // if(iMPos == iLPos)
407 // break;
408 // iMPos = iLPos;
409 // }
410 // if(iLowerBound < iMPos - 1)
411 // {
412 // stackLowerBound.push(iLowerBound);
413 // stackUpperBound.push(iMPos - 1);
414 // }
415 // if(iMPos + 1 < iUpperBound)
416 // {
417 // stackLowerBound.push(iMPos + 1);
418 // stackUpperBound.push(iUpperBound);
419 // }
420 // if(stackLowerBound.get_size() == 0)
421 // break;
422 // }
423 // }
424 //}
425
426 template<typename PRED_LE, typename ARRAY>
427 void predicate_array_quick_sort(ARRAY & a, PRED_LE predicate_le)
428 {
429 index_array stackLowerBound;
430 index_array stackUpperBound;
431 iptr iLowerBound;
432 iptr iUpperBound;
433 iptr iLPos, iUPos, iMPos;
434
435 if (a.get_size() >= 2)
436 {
437 stackLowerBound.push(0);
438 stackUpperBound.push(a.get_size() - 1);
439 while (true)
440 {
441 iLowerBound = stackLowerBound.pop();
442 iUpperBound = stackUpperBound.pop();
443 iLPos = iLowerBound;
444 iMPos = iLowerBound;
445 iUPos = iUpperBound;
446 while (true)
447 {
448 while (true)
449 {
450 if (iMPos == iUPos)
451 break;
452 if (predicate_le(a.element_at(iMPos), a.element_at(iUPos)))
453 iUPos--;
454 else
455 {
456 // t = a.get_at(iMPos);
457 // a.set_at(iMPos, a.get_at(iUPos));
458 //a.set_at(iUPos, t);
459 a.__swap(iMPos, iUPos);
460 break;
461 }
462 }
463 if (iMPos == iUPos)
464 break;
465 iMPos = iUPos;
466 while (true)
467 {
468 if (iMPos == iLPos)
469 break;
470 if (predicate_le(a.element_at(iLPos), a.element_at(iMPos)))
471 iLPos++;
472 else
473 {
474 // t = a.get_at(iMPos);
475 // a.set_at(iMPos, a.get_at(iLPos));
476 // a.set_at(iLPos, t);
477 a.__swap(iLPos, iMPos);
478 break;
479 }
480 }
481 if (iMPos == iLPos)
482 break;
483 iMPos = iLPos;
484 }
485 if (iLowerBound < iMPos - 1)
486 {
487 stackLowerBound.push(iLowerBound);
488 stackUpperBound.push(iMPos - 1);
489 }
490 if (iMPos + 1 < iUpperBound)
491 {
492 stackLowerBound.push(iMPos + 1);
493 stackUpperBound.push(iUpperBound);
494 }
495
496 if (stackLowerBound.get_size() == 0)
497 break;
498
499 }
500
501 }
502
503 }
504
505
506 template<class TYPE, class ARG_TYPE, class ARRAY_TYPE>
507 void QuickSortAsc(comparable_array<TYPE, ARG_TYPE, ARRAY_TYPE> & a)
508 {
509 index_array stackLowerBound;
510 index_array stackUpperBound;
511 iptr iLowerBound;
512 iptr iUpperBound;
513 iptr iLPos, iUPos, iMPos;
514
515 if (a.get_size() >= 2)
516 {
517 stackLowerBound.push(0);
518 stackUpperBound.push(a.get_upper_bound());
519 while (true)
520 {
521 iLowerBound = stackLowerBound.pop();
522 iUpperBound = stackUpperBound.pop();
523 iLPos = iLowerBound;
524 iMPos = iLowerBound;
525 iUPos = iUpperBound;
526 while (true)
527 {
528 while (true)
529 {
530 if (iMPos == iUPos)
531 break;
532 if (a.element_at(iMPos) <= a.element_at(iUPos))
533 iUPos--;
534 else
535 {
536 a.__swap(iMPos, iUPos);
537 break;
538 }
539 }
540 if (iMPos == iUPos)
541 break;
542 iMPos = iUPos;
543 while (true)
544 {
545 if (iMPos == iLPos)
546 break;
547 if (a.element_at(iLPos) <= a.element_at(iMPos))
548 iLPos++;
549 else
550 {
551 a.__swap(iLPos, iMPos);
552 break;
553 }
554 }
555 if (iMPos == iLPos)
556 break;
557 iMPos = iLPos;
558 }
559 if (iLowerBound < iMPos - 1)
560 {
561 stackLowerBound.push(iLowerBound);
562 stackUpperBound.push(iMPos - 1);
563 }
564 if (iMPos + 1 < iUpperBound)
565 {
566 stackLowerBound.push(iMPos + 1);
567 stackUpperBound.push(iUpperBound);
568 }
569 if (stackLowerBound.get_size() == 0)
570 break;
571 }
572 }
573 }
574
575 template<class TYPE, class ARG_TYPE, class ARRAY_TYPE>
576 void QuickSortDesc(comparable_array<TYPE, ARG_TYPE, ARRAY_TYPE> & a)
577 {
578 index_array stackLowerBound;
579 index_array stackUpperBound;
580 iptr iLowerBound;
581 iptr iUpperBound;
582 iptr iLPos, iUPos, iMPos;
583
584 if (a.get_size() >= 2)
585 {
586 stackLowerBound.push(0);
587 stackUpperBound.push(a.get_upper_bound());
588 while (true)
589 {
590 iLowerBound = stackLowerBound.pop();
591 iUpperBound = stackUpperBound.pop();
592 iLPos = iLowerBound;
593 iMPos = iLowerBound;
594 iUPos = iUpperBound;
595 while (true)
596 {
597 while (true)
598 {
599 if (iMPos == iUPos)
600 break;
601 if (a.element_at(iUPos) <= a.element_at(iMPos))
602 iUPos--;
603 else
604 {
605 a.__swap(iMPos, iUPos);
606 break;
607 }
608 }
609 if (iMPos == iUPos)
610 break;
611 iMPos = iUPos;
612 while (true)
613 {
614 if (iMPos == iLPos)
615 break;
616 if (a.element_at(iMPos) <= a.element_at(iLPos))
617 iLPos++;
618 else
619 {
620 a.__swap(iLPos, iMPos);
621 break;
622 }
623 }
624 if (iMPos == iLPos)
625 break;
626 iMPos = iLPos;
627 }
628 if (iLowerBound < iMPos - 1)
629 {
630 stackLowerBound.push(iLowerBound);
631 stackUpperBound.push(iMPos - 1);
632 }
633 if (iMPos + 1 < iUpperBound)
634 {
635 stackLowerBound.push(iMPos + 1);
636 stackUpperBound.push(iUpperBound);
637 }
638 if (stackLowerBound.get_size() == 0)
639 break;
640 }
641 }
642 }
643
644
645 template<prototype_range RANGE>
646 void QuickSortAsc(RANGE & range)
647 {
648
649 if (range.size() < 2)
650 {
651
652 return;
653
654 }
655
656 ::array < typename RANGE::iterator > stackLowerBound;
657 ::array < typename RANGE::iterator > stackUpperBound;
658 typename RANGE::iterator iLowerBound;
659 typename RANGE::iterator iUpperBound;
660 typename RANGE::iterator iLPos, iUPos, iMPos;
661
662 stackLowerBound.push(range.begin());
663 stackUpperBound.push(range.back());
664 while (true)
665 {
666 iLowerBound = stackLowerBound.pop();
667 iUpperBound = stackUpperBound.pop();
668 iLPos = iLowerBound;
669 iMPos = iLowerBound;
670 iUPos = iUpperBound;
671 while (true)
672 {
673 while (true)
674 {
675 if (iMPos == iUPos)
676 break;
677 if (*iMPos <= *iUPos)
678 iUPos--;
679 else
680 {
681 ::swap(*iMPos, *iUPos);
682 break;
683 }
684 }
685 if (iMPos == iUPos)
686 break;
687 iMPos = iUPos;
688 while (true)
689 {
690 if (iMPos == iLPos)
691 break;
692 if (*iLPos <= *iMPos)
693 iLPos++;
694 else
695 {
696 ::swap(*iLPos, *iMPos);
697 break;
698 }
699 }
700 if (iMPos == iLPos)
701 break;
702 iMPos = iLPos;
703 }
704 if (iLowerBound < iMPos - 1)
705 {
706 stackLowerBound.push(iLowerBound);
707 stackUpperBound.push(iMPos - 1);
708 }
709 if (iMPos + 1 < iUpperBound)
710 {
711 stackLowerBound.push(iMPos + 1);
712 stackUpperBound.push(iUpperBound);
713 }
714 if (stackLowerBound.get_size() == 0)
715 break;
716 }
717
718 }
719
720
721 template<prototype_range RANGE>
722 void QuickSortDesc(RANGE & range)
723 {
724
725 if (range.size() < 2)
726 {
727
728 return;
729
730 }
731
732 ::array < typename RANGE::iterator > stackLowerBound;
733 ::array < typename RANGE::iterator > stackUpperBound;
734 typename RANGE::iterator iLowerBound;
735 typename RANGE::iterator iUpperBound;
736 typename RANGE::iterator iLPos, iUPos, iMPos;
737
738 stackLowerBound.push(range.begin());
739 stackUpperBound.push(range.end());
740 while (true)
741 {
742 iLowerBound = stackLowerBound.pop();
743 iUpperBound = stackUpperBound.pop();
744 iLPos = iLowerBound;
745 iMPos = iLowerBound;
746 iUPos = iUpperBound;
747 while (true)
748 {
749 while (true)
750 {
751 if (iMPos == iUPos)
752 break;
753 if (*iUPos <= *iMPos)
754 iUPos--;
755 else
756 {
757 ::swap(*iMPos, *iUPos);
758 break;
759 }
760 }
761 if (iMPos == iUPos)
762 break;
763 iMPos = iUPos;
764 while (true)
765 {
766 if (iMPos == iLPos)
767 break;
768 if (*iMPos <= *iLPos)
769 iLPos++;
770 else
771 {
772 ::swap(*iLPos, *iMPos);
773 break;
774 }
775 }
776 if (iMPos == iLPos)
777 break;
778 iMPos = iLPos;
779 }
780 if (iLowerBound < iMPos - 1)
781 {
782 stackLowerBound.push(iLowerBound);
783 stackUpperBound.push(iMPos - 1);
784 }
785 if (iMPos + 1 < iUpperBound)
786 {
787 stackLowerBound.push(iMPos + 1);
788 stackUpperBound.push(iUpperBound);
789 }
790 if (stackLowerBound.get_size() == 0)
791 break;
792 }
793
794 }
795
796
797 template<class KEY, class TYPE, class ARG_TYPE>
798 void QuickSortByKey(
799 array<TYPE, ARG_TYPE> & a,
800 KEY(TYPE:: * fKey)())
801 {
802 index_array stackLowerBound;
803 index_array stackUpperBound;
804 iptr iLowerBound;
805 iptr iUpperBound;
806 iptr iLPos, iUPos, iMPos;
807 TYPE t;
808
809 if (a.get_size() >= 2)
810 {
811 stackLowerBound.push(0);
812 stackUpperBound.push(a.get_size() - 1);
813 while (true)
814 {
815 iLowerBound = stackLowerBound.pop();
816 iUpperBound = stackUpperBound.pop();
817 iLPos = iLowerBound;
818 iMPos = iLowerBound;
819 iUPos = iUpperBound;
820 while (true)
821 {
822 while (true)
823 {
824 if (iMPos == iUPos)
825 break;
826 if ((a.element_at(iMPos).*fKey)() < (a.element_at(iUPos).*fKey)())
827 iUPos--;
828 else
829 {
830 // t = a.get_at(iMPos);
831 // a.set_at(iMPos, a.get_at(iUPos));
832 //a.set_at(iUPos, t);
833 a.__swap(iMPos, iUPos);
834 break;
835 }
836 }
837 if (iMPos == iUPos)
838 break;
839 iMPos = iUPos;
840 while (true)
841 {
842 if (iMPos == iLPos)
843 break;
844 if ((a.element_at(iLPos).*fKey)() < (a.element_at(iMPos).*fKey)())
845 iLPos++;
846 else
847 {
848 // t = a.get_at(iMPos);
849 // a.set_at(iMPos, a.get_at(iLPos));
850 // a.set_at(iLPos, t);
851 a.__swap(iLPos, iMPos);
852 break;
853 }
854 }
855 if (iMPos == iLPos)
856 break;
857 iMPos = iLPos;
858 }
859 if (iLowerBound < iMPos - 1)
860 {
861 stackLowerBound.push(iLowerBound);
862 stackUpperBound.push(iMPos - 1);
863 }
864 if (iMPos + 1 < iUpperBound)
865 {
866 stackLowerBound.push(iMPos + 1);
867 stackUpperBound.push(iUpperBound);
868 }
869 if (stackLowerBound.get_size() == 0)
870 break;
871 }
872 }
873 }
874
875 template<class ARG_TYPE>
876 inline iptr SortCompare(ARG_TYPE t1, ARG_TYPE t2)
877 {
878 return t1 - t2;
879 }
880
881
882 template<class TYPE, class ARG_TYPE>
883 bool SortFind(array<TYPE, ARG_TYPE> & a, ARG_TYPE t, iptr & iIndex, iptr iStart, iptr iEnd)
884 {
885 if (a.get_size() == 0)
886 {
887 return false;
888 }
889 iptr iLowerBound = iStart;
890 iptr iMaxBound = iEnd;
891 iptr iUpperBound = iMaxBound;
892 iptr iCompare;
893
894 while (true)
895 {
896 iIndex = (iUpperBound + iLowerBound) / 2;
897 iCompare = SortCompare((ARG_TYPE)a.element_at(iIndex), (ARG_TYPE)t);
898 if (iCompare == 0)
899 {
900 return true;
901 }
902 else if (iCompare > 0)
903 {
904 iUpperBound = iIndex - 1;
905 if (iUpperBound < 0)
906 break;
907 }
908 else
909 {
910 iLowerBound = iIndex + 1;
911 if (iLowerBound > iMaxBound)
912 {
913 iIndex = iLowerBound;
914 break;
915 }
916 }
917 if (iUpperBound < iLowerBound)
918 break;
919
920 }
921 return false;
922
923 }
924
925 template<class TYPE, class ARG_TYPE>
926 bool SortFind(array<TYPE, ARG_TYPE> & a, ARG_TYPE t, iptr & iIndex)
927 {
928 return SortFind(a, t, iIndex, 0, a.get_size() - 1);
929 }
930
931 template<class TYPE, class ARG_TYPE>
932 void BubbleSortByLPGetSize(array<TYPE, ARG_TYPE> & a, bool bAsc = true);
933
934 //template<class TYPE, class ARG_TYPE>
935 //void BubbleSortByGetSize(array<TYPE, ARG_TYPE> & a, bool bAsc = true);
936
937 template<typename TYPE>
938 void BubbleSortByPtrAtGetSize(
939 pointer_array<TYPE> & a,
940 bool bAsc = true);
941
942 template<class TYPE, class ARG_TYPE = const TYPE &, class DEFCONSTRUCTOR>
943 void quick_sort(
944 array<TYPE, ARG_TYPE, DEFCONSTRUCTOR> & a,
945 ::std::strong_ordering(*pfnCompare)(ARG_TYPE, ARG_TYPE));
946
947
948 template<class TYPE, class ARG_TYPE>
949 void BubbleSortByLPGetSize(
950 array<TYPE, ARG_TYPE> & a,
951 bool bAsc)
952 {
953 TYPE * t;
954 if (bAsc)
955 {
956 for (iptr i = 0; i < a.get_size(); i++)
957 for (iptr j = i + 1; j < a.get_size(); j++)
958 {
959 if (a.element_at(i)->get_size() > a.element_at(j)->get_size())
960 {
961 t = a.element_at(i);
962 set_at(i, a.element_at(j));
963 set_at(j, t);
964 }
965
966 }
967 }
968 else
969 {
970 for (iptr i = 0; i < a.get_size(); i++)
971 for (iptr j = i + 1; j < a.get_size(); j++)
972 {
973 if (a.element_at(i)->get_size() < a.element_at(j)->get_size())
974 {
975 t = a.element_at(i);
976 set_at(i, a.element_at(j));
977 set_at(j, t);
978 }
979
980 }
981 }
982
983 return;
984 }
985
986
987 template<prototype_array ARRAY>
988 void BubbleSortByGetSize(ARRAY & a, bool bAsc)
989 {
990
991 if (bAsc)
992 {
993
994 for (iptr i = 0; i < a.get_size(); i++)
995 {
996
997 for (iptr j = i + 1; j < a.get_size(); j++)
998 {
999
1000 if (a[i].get_size() > a[j].get_size())
1001 {
1002
1003 a.__swap(i, j);
1004
1005 }
1006
1007 }
1008
1009 }
1010
1011 }
1012 else
1013 {
1014
1015 for (iptr i = 0; i < a.get_size(); i++)
1016 {
1017
1018 for (iptr j = i + 1; j < a.get_size(); j++)
1019 {
1020
1021 if (a[i].get_size() < a[j].get_size())
1022 {
1023
1024 a.__swap(i, j);
1025
1026 }
1027
1028 }
1029
1030 }
1031
1032 }
1033
1034 }
1035
1036 //template<class ARRAY>
1037 //void BubbleSortByGetSize(
1038 // ARRAY & a,
1039 // bool bAsc)
1040 //{
1041 // typename ARRAY::BASE_TYPE t;
1042 // if (bAsc)
1043 // {
1044 // for (iptr i = 0; i < a.get_size(); i++)
1045 // for (iptr j = i + 1; j < a.get_size(); j++)
1046 // {
1047 // if (a.element_at(i).get_size() > a.element_at(j).get_size())
1048 // {
1049 // a.__swap(i, j);
1050 // }
1051 // }
1052 // }
1053 // else
1054 // {
1055 // for (iptr i = 0; i < a.get_size(); i++)
1056 // for (iptr j = i + 1; j < a.get_size(); j++)
1057 // {
1058 // if (a.element_at(i).get_size() < a.element_at(j).get_size())
1059 // {
1060 // a.__swap(i, j);
1061 // }
1062
1063 // }
1064 // }
1065
1066 // return;
1067 //}
1068
1069
1070 template<typename TYPE>
1071 void BubbleSortByPtrAtGetSize(
1072 pointer_array<TYPE> & a,
1073 bool bAsc)
1074 {
1075 TYPE t;
1076 if (bAsc)
1077 {
1078 for (iptr i = 0; i < a.get_size(); i++)
1079 for (iptr j = i + 1; j < a.get_size(); j++)
1080 {
1081 if (a.element_at(i)->get_size() > a.element_at(j)->get_size())
1082 {
1083 a.__swap(i, j);
1084 }
1085 }
1086 }
1087 else
1088 {
1089 for (iptr i = 0; i < a.get_size(); i++)
1090 for (iptr j = i + 1; j < a.get_size(); j++)
1091 {
1092 if (a.element_at(i)->get_size() < a.element_at(j)->get_size())
1093 {
1094 a.__swap(i, j);
1095 }
1096
1097 }
1098 }
1099
1100 return;
1101 }
1102
1103
1104
1105 namespace array
1106 {
1107
1108 template < typename ARRAY_TYPE >
1109 void quick_sort(
1110 ARRAY_TYPE & a,
1111 ::std::strong_ordering(*pfnCompare)(typename ARRAY_TYPE::BASE_ARG_TYPE, typename ARRAY_TYPE::BASE_ARG_TYPE))
1112 {
1113
1114 index_array stackLowerBound;
1115
1116 index_array stackUpperBound;
1117
1118 iptr iLowerBound;
1119
1120 iptr iUpperBound;
1121
1122 iptr iLPos, iUPos, iMPos;
1123
1124 if (a.get_size() >= 2)
1125 {
1126
1127 stackLowerBound.push(0);
1128
1129 stackUpperBound.push(a.get_upper_bound());
1130
1131 while (true)
1132 {
1133
1134 iLowerBound = stackLowerBound.pop();
1135
1136 iUpperBound = stackUpperBound.pop();
1137
1138 iLPos = iLowerBound;
1139
1140 iMPos = iLowerBound;
1141
1142 iUPos = iUpperBound;
1143
1144 while (true)
1145 {
1146
1147 while (true)
1148 {
1149
1150 if (iMPos == iUPos)
1151 {
1152
1153 break;
1154
1155 }
1156
1157 if (pfnCompare((typename ARRAY_TYPE::BASE_ARG_TYPE)a.element_at(iMPos), (typename ARRAY_TYPE::BASE_ARG_TYPE)a.element_at(iUPos)) <= 0)
1158 {
1159
1160 iUPos--;
1161
1162 }
1163 else
1164 {
1165
1166 a.__swap(iMPos, iUPos);
1167
1168 break;
1169
1170 }
1171
1172 }
1173
1174 if (iMPos == iUPos)
1175 {
1176
1177 break;
1178
1179 }
1180
1181 iMPos = iUPos;
1182
1183 while (true)
1184 {
1185
1186 if (iMPos == iLPos)
1187 {
1188
1189 break;
1190
1191 }
1192
1193 if (pfnCompare((typename ARRAY_TYPE::BASE_ARG_TYPE)a.element_at(iLPos), (typename ARRAY_TYPE::BASE_ARG_TYPE)a.element_at(iMPos)) <= 0)
1194 {
1195
1196 iLPos++;
1197
1198 }
1199 else
1200 {
1201
1202 a.__swap(iLPos, iMPos);
1203
1204 break;
1205
1206 }
1207
1208 }
1209
1210 if (iMPos == iLPos)
1211 {
1212
1213 break;
1214
1215 }
1216
1217 iMPos = iLPos;
1218
1219 }
1220
1221 if (iLowerBound < iMPos - 1)
1222 {
1223
1224 stackLowerBound.push(iLowerBound);
1225
1226 stackUpperBound.push(iMPos - 1);
1227
1228 }
1229
1230 if (iMPos + 1 < iUpperBound)
1231 {
1232
1233 stackLowerBound.push(iMPos + 1);
1234
1235 stackUpperBound.push(iUpperBound);
1236
1237 }
1238
1239 if (stackLowerBound.get_size() == 0)
1240 {
1241
1242 break;
1243
1244 }
1245
1246 }
1247
1248 }
1249
1250 }
1251
1252
1253 template < typename ARRAY_TYPE >
1254 void quick_sort(ARRAY_TYPE & a, less_predicate_base < typename ARRAY_TYPE::BASE_ARG_TYPE > * pless, index_array & ia)
1255 {
1256
1257 if (ia.get_size() != a.get_size())
1258 {
1259
1260 throw_exception(error_bad_argument);
1261
1262 }
1263
1264 index_array stackLowerBound;
1265
1266 index_array stackUpperBound;
1267
1268 iptr iLowerBound;
1269
1270 iptr iUpperBound;
1271
1272 iptr iLPos, iUPos, iMPos;
1273
1274 if (a.get_size() >= 2)
1275 {
1276
1277 stackLowerBound.push(0);
1278
1279 stackUpperBound.push(a.get_upper_bound());
1280
1281 while (true)
1282 {
1283
1284 iLowerBound = stackLowerBound.pop();
1285
1286 iUpperBound = stackUpperBound.pop();
1287
1288 iLPos = iLowerBound;
1289
1290 iMPos = iLowerBound;
1291
1292 iUPos = iUpperBound;
1293
1294 while (true)
1295 {
1296
1297 while (true)
1298 {
1299
1300 if (iMPos == iUPos)
1301 {
1302
1303 break;
1304
1305 }
1306
1307 if (pless->less(a.element_at(ia[iMPos]), a.element_at(ia[iUPos])) <= 0)
1308 {
1309
1310 iUPos--;
1311
1312 }
1313 else
1314 {
1315
1316 ia.__swap(iMPos, iUPos);
1317
1318 break;
1319
1320 }
1321
1322 }
1323
1324 if (iMPos == iUPos)
1325 {
1326
1327 break;
1328
1329 }
1330
1331 iMPos = iUPos;
1332
1333 while (true)
1334 {
1335
1336 if (iMPos == iLPos)
1337 {
1338
1339 break;
1340
1341 }
1342
1343 if (pless->less(a.element_at(ia[iLPos]), a.element_at(ia[iMPos])) <= 0)
1344 {
1345
1346 iLPos++;
1347
1348 }
1349 else
1350 {
1351
1352 ia.__swap(iLPos, iMPos);
1353
1354 break;
1355
1356 }
1357
1358 }
1359
1360 if (iMPos == iLPos)
1361 {
1362
1363 break;
1364
1365 }
1366
1367 iMPos = iLPos;
1368
1369 }
1370
1371 if (iLowerBound < iMPos - 1)
1372 {
1373
1374 stackLowerBound.push(iLowerBound);
1375
1376 stackUpperBound.push(iMPos - 1);
1377
1378 }
1379
1380 if (iMPos + 1 < iUpperBound)
1381 {
1382
1383 stackLowerBound.push(iMPos + 1);
1384
1385 stackUpperBound.push(iUpperBound);
1386
1387 }
1388
1389 if (stackLowerBound.is_empty())
1390 {
1391
1392 break;
1393
1394 }
1395
1396 }
1397
1398 }
1399
1400 }
1401
1402
1403
1404 } // namespace array
1405
1406
1407
1408 // Sort "array" according to "fCompare" function
1409 // of "pCompare" interface
1410
1411
1412
1413
1414 template < typename LIST, typename PRED>
1415 void predicate_quick_sort_list(LIST & list_base, PRED pred)
1416 {
1417
1418 if (list_base.get_size() < 2)
1419 {
1420
1421 return;
1422
1423 }
1424
1425 typedef typename LIST::node node;
1426
1427 ::raw_array_base < node * > stackLowerBound;
1428
1429 ::raw_array_base < node * > stackUpperBound;
1430
1431 node * iLowerBound;
1432
1433 node * iUpperBound;
1434 node * iLPos, * iUPos, * iMPos;
1435
1436 stackLowerBound.push(list_base.m_phead);
1437 stackUpperBound.push(list_base.m_ptail);
1438 while (true)
1439 {
1440 iLowerBound = stackLowerBound.pop();
1441 iUpperBound = stackUpperBound.pop();
1442 iLPos = iLowerBound;
1443 iMPos = iLowerBound;
1444 iUPos = iUpperBound;
1445 while (true)
1446 {
1447 while (true)
1448 {
1449 if (iMPos == iUPos)
1450 goto break_mid_loop;
1451 if (pred(iUPos->m_value, iMPos->m_value))
1452 {
1453 list_base.__swap(iMPos, iUPos);
1454 break;
1455 }
1456 iUPos = iUPos->m_pprevious;
1457 }
1458 iMPos = iUPos;
1459 while (true)
1460 {
1461 if (iMPos == iLPos)
1462 goto break_mid_loop;
1463 if (pred(iMPos->m_value, iLPos->m_value))
1464 {
1465 list_base.__swap(iLPos, iMPos);
1466 break;
1467 }
1468 iLPos = iLPos->m_pnext;
1469 }
1470 iMPos = iLPos;
1471 }
1472 break_mid_loop:
1473 if (iLowerBound != iMPos->m_pprevious)
1474 {
1475 stackLowerBound.push(iLowerBound);
1476 stackUpperBound.push(iMPos->m_pprevious);
1477 }
1478 if (iMPos->m_pnext != iUpperBound)
1479 {
1480 stackLowerBound.push(iMPos->m_pnext);
1481 stackUpperBound.push(iUpperBound);
1482 }
1483 if (stackLowerBound.get_size() == 0)
1484 break;
1485 }
1486
1487 }
1488
1489
1490 template < typename LIST, typename PRED >
1491 void predicate_quick_sort_list_descending(LIST & list_base, PRED pred)
1492 {
1493
1494 predicate_quick_sort_list(list_base, [&](auto & a, auto & b) { return pred(b, a); });
1495
1496 }
1497
1498
1499 template < typename LIST >
1500 void quick_sort_list(LIST & list_base, bool bAscendent = true)
1501 {
1502
1503 if (bAscendent)
1504 {
1505
1506 predicate_quick_sort_list(list_base, [](auto & a, auto & b) { return a < b; });
1507
1508 }
1509 else
1510 {
1511
1512 predicate_quick_sort_list(list_base, [](auto & a, auto & b) { return b < a; });
1513
1514 }
1515
1516 }
1517
1518
1519 template < class ARRAY >
1520 inline bool sort_find(ARRAY & a, typename ARRAY::BASE_ARG_TYPE arg, iptr & iIndex, iptr iStart, iptr iEnd)
1521 {
1522 if (a.get_size() == 0)
1523 {
1524 return false;
1525 }
1526 iptr iLowerBound = iStart;
1527 iptr iMaxBound = iEnd;
1528 iptr iUpperBound = iMaxBound;
1529 memsize iCompare;
1530 // do binary search
1531 iIndex = (iUpperBound + iLowerBound) / 2;
1532 while (iUpperBound - iLowerBound >= 8)
1533 {
1534 iCompare = CompareElements(a.element_at(iIndex), arg);
1535 if (iCompare == 0)
1536 {
1537 return true;
1538 }
1539 else if (iCompare > 0)
1540 {
1541 iUpperBound = iIndex - 1;
1542 if (iUpperBound < 0)
1543 {
1544 iIndex = 0;
1545 break;
1546 }
1547 }
1548 else
1549 {
1550 iLowerBound = iIndex + 1;
1551 if (iLowerBound > iMaxBound)
1552 {
1553 iIndex = iMaxBound + 1;
1554 break;
1555 }
1556 }
1557 iIndex = (iUpperBound + iLowerBound) / 2;
1558 }
1559 // do sequential search
1560 while (iIndex < a.get_count())
1561 {
1562 iCompare = CompareElements(a.element_at(iIndex), arg);
1563 if (iCompare == 0)
1564 return true;
1565 else if (iCompare < 0)
1566 iIndex++;
1567 else
1568 break;
1569 }
1570 if (iIndex >= a.get_count())
1571 return false;
1572 while (iIndex >= 0)
1573 {
1574 iCompare = CompareElements(a.element_at(iIndex), arg);
1575 if (iCompare == 0)
1576 return true;
1577 else if (iCompare > 0)
1578 iIndex--;
1579 else
1580 break;
1581 }
1582 iIndex++;
1583 return false;
1584
1585 }
1586
1587 template < class ARRAY >
1588 void quick_sort(ARRAY & a, bool bAsc)
1589 {
1590 if (bAsc)
1591 {
1592 sort::QuickSortAsc(a);
1593 }
1594 else
1595 {
1596 sort::QuickSortDesc(a);
1597 }
1598 }
1599
1600
1601 template < typename ITERATOR>
1602 void quick_sort_iter(ITERATOR first, ITERATOR last)
1603 {
1604
1605 //auto & iterable = first.iterable();
1606
1607 //ASSERT(&iterable == &last.iterable());
1608
1609 //if (&iterable != &last.iterable())
1610 //{
1611
1612 // return;
1613
1614 //}
1615
1616 if (last - first < 2)
1617 {
1618
1619 return;
1620
1621 }
1622
1623 ::array < ITERATOR > stackLowerBound;
1624 ::array < ITERATOR > stackUpperBound;
1625 ITERATOR iLowerBound;
1626 ITERATOR iUpperBound;
1627 ITERATOR iLPos, iUPos, iMPos;
1628
1629 stackLowerBound.push(first);
1630 stackUpperBound.push(last);
1631
1632 while (true)
1633 {
1634
1635 iLowerBound = stackLowerBound.pop();
1636 iUpperBound = stackUpperBound.pop();
1637
1638 iLPos = iLowerBound;
1639 iMPos = iLowerBound;
1640 iUPos = iUpperBound;
1641
1642 while (true)
1643 {
1644 while (true)
1645 {
1646 if (iMPos == iUPos)
1647 goto break_mid_loop;
1648 __sort(*iMPos, *iUPos);
1649 iUPos--;
1650
1651 }
1652 if (iMPos == iUPos)
1653 break;
1654 iMPos = iUPos;
1655 while (true)
1656 {
1657 if (iMPos == iLPos)
1658 goto break_mid_loop;
1659 __sort(*iLPos, *iMPos);
1660 iLPos++;
1661 }
1662 if (iMPos == iLPos)
1663 break;
1664 iMPos = iLPos;
1665 }
1666 break_mid_loop:
1667 if (iLowerBound < iMPos - 1)
1668 {
1669 stackLowerBound.push(iLowerBound);
1670 stackUpperBound.push(iMPos - 1);
1671 }
1672 if (iMPos + 1 < iUpperBound)
1673 {
1674 stackLowerBound.push(iMPos + 1);
1675 stackUpperBound.push(iUpperBound);
1676 }
1677 if (stackLowerBound.get_size() == 0)
1678 break;
1679 }
1680
1681 }
1682
1683
1684 //https://stackoverflow.com/questions/32937902/sorting-iptr-of-array-using-merge-sort
1685
1686 template < typename ARRAY, typename PRED >
1687 void predicate_index_merge(ARRAY & a, PRED leq, index_array & temp, index_array & perm, ::i32 lo, ::i32 mid, ::i32 hi)
1688 {
1689
1690 ::i32 i = lo, j = mid + 1;
1691
1692 for (::i32 k = lo; k <= hi; k++)
1693 {
1694
1695 temp[k] = perm[k];
1696
1697 }
1698
1699 for (::i32 k = lo; k <= hi; k++)
1700 {
1701
1702 if (i > mid)
1703 {
1704
1705 perm[k] = temp[j++];
1706
1707 }
1708 else if (j > hi)
1709 {
1710
1711 perm[k] = temp[i++];
1712
1713 }
1714 else if (leq(a[temp[i]], a[temp[j]]))
1715 {
1716
1717 perm[k] = temp[i++];
1718
1719 }
1720 else
1721 {
1722
1723 perm[k] = temp[j++];
1724
1725 }
1726
1727 }
1728
1729 }
1730
1731 template < typename ARRAY, typename PRED >
1732 void predicate_index_merge_sort(ARRAY & a, PRED leq, index_array & temp, index_array & perm, ::i32 lo, ::i32 hi)
1733 {
1734
1735 if (hi <= lo)
1736 return;
1737
1738 ::i32 mid = (hi + lo) / 2;
1739
1740 predicate_merge_sort(a, leq, temp, perm, lo, mid);
1741
1742 predicate_merge_sort(a, leq, temp, perm, mid + 1, hi);
1743
1744 predicate_merge(a, leq, temp, perm, lo, mid, hi);
1745
1746 }
1747
1748 template < typename ARRAY, typename PRED >
1749 void predicate_stable_index_sort(ARRAY & a, index_array & perm, PRED leq)
1750 {
1751
1752 index_array temp;
1753
1754 temp.set_size(a.get_size());
1755
1756 predicate_index_merge_sort(a, leq, temp, perm, 0, a.get_upper_bound());
1757
1758 }
1759
1760
1761
1762 // Merges two subarrays of arr[].
1763 // First subarray is arr[l..m]
1764 // Second subarray is arr[m+1..r]
1765 template < typename ARRAY, typename PRED >
1766 void predicate_merge(ARRAY & a, PRED leq, ::i32 l, ::i32 m, ::i32 r)
1767 {
1768
1769 ::i32 i, j, k;
1770 ::i32 n1 = m - l + 1;
1771 ::i32 n2 = r - m;
1772
1773 /* create temp arrays */
1774 ARRAY L;
1775 L.set_size(n1);
1776 ARRAY R;
1777 R.set_size(n2);
1778
1779 /* Copy data to temp arrays L[] and R[] */
1780 for (i = 0; i < n1; i++)
1781 L[i] = a[l + i];
1782 for (j = 0; j < n2; j++)
1783 R[j] = a[m + 1 + j];
1784
1785 /* Merge the temp arrays back into arr[l..r]*/
1786 i = 0; // Initial iptr of first subarray
1787 j = 0; // Initial iptr of second subarray
1788 k = l; // Initial iptr of merged subarray
1789 while (i < n1 && j < n2)
1790 {
1791 if (leq(L[i], R[j]))
1792 {
1793 a[k] = L[i];
1794 i++;
1795 }
1796 else
1797 {
1798 a[k] = R[j];
1799 j++;
1800 }
1801 k++;
1802 }
1803
1804 /* Copy the remaining elements of L[], if there
1805 are any */
1806 while (i < n1)
1807 {
1808 a[k] = L[i];
1809 i++;
1810 k++;
1811 }
1812
1813 /* Copy the remaining elements of R[], if there
1814 are any */
1815 while (j < n2)
1816 {
1817 a[k] = R[j];
1818 j++;
1819 k++;
1820 }
1821 }
1822
1823 /* l is for left iptr and r is right iptr of the
1824 sub-array of arr to be sorted */
1825 template < typename ARRAY, typename PRED >
1826 void predicate_merge_sort(ARRAY & a, PRED leq, ::i32 l, ::i32 r)
1827 {
1828
1829 if (l < r)
1830 {
1831
1832 // Same as (l+r)/2, but avoids overflow for large l and h
1833
1834 ::i32 m = l + (r - l) / 2;
1835
1836 // Sort first and second halves
1837
1838 predicate_merge_sort(a, leq, l, m);
1839
1840 predicate_merge_sort(a, leq, m + 1, r);
1841
1842 predicate_merge(a, leq, l, m, r);
1843
1844 }
1845
1846 }
1847
1848 template < typename ARRAY, typename PRED >
1849 void predicate_stable_sort(ARRAY & a, PRED leq)
1850 {
1851
1852 predicate_merge_sort(a, leq, 0, a.get_upper_bound());
1853
1854 }
1855
1856} // namespace sort
1857
1858
1859
1860
1861//#include "collection_sort_array.h"
1862// #include "collection_key_sort_array.h"
1863
1864
1865//template < class TYPE, class ARG_TYPE, class ARRAY_TYPE>
1866//void comparable_array< TYPE, ARG_TYPE, ARRAY_TYPE >::quick_sort(bool bAsc)
1867//{
1868// if(bAsc)
1869// {
1870// sort::QuickSortAsc(*this);
1871// }
1872// else
1873// {
1874// sort::QuickSortDesc(*this);
1875// }
1876//}
1877
1878
1879
1880
1881
1882
1883
1884//template < class TYPE, class ARG_TYPE, class ARRAY_TYPE>
1885//void comparable_list_base< TYPE, ARG_TYPE, ARRAY_TYPE>::
1886//quick_sort(bool bAscendent)
1887//{
1888//
1889// sort::quick_sort(*this, bAscendent);
1890//
1891//}
1892
1893//template < class KEY, class TYPE, class ARG_TYPE , class ARRAY >
1894//void key_sort_array < KEY, TYPE, ARG_TYPE, ARRAY >::
1895//SetKeyProperty(KEY (TYPE::* pfnKeyProperty)())
1896
1897//{
1898// m_lpfnKeyProperty= pfnKeyProperty;
1899
1900// sort::QuickSortByKey < KEY, TYPE, ARG_TYPE >(
1901// m_array,
1902// m_lpfnKeyProperty);
1903//}
1904//
1905//
1906
1907
1908
1909