acme
Foundational cross-platform layer of the ca2 framework
Loading...
Searching...
No Matches
_range.h
1// Created by camilo on 2023-01-20 22:08 <3ThomasBorregaardSorensen!!
2// 2023-01-20 22:08 - Mummi, Lucinho, Bilbo, Blue, Carol e Zibia contribution through ca2 HQ!!
3// 2023-01-20 22:08 - lowluds, shegotmad, mrsteinbergplease and octaelliptical contribution through Twitch.TV!!
4#pragma once
5
6
7namespace generic
8{
9
10
11 namespace range
12 {
13
14
15 template < prototype_range RANGE, typename COMPARE_INTERFACE >
16 void quick_sort(
17 RANGE & range,
18 COMPARE_INTERFACE * pinterface,
19 ::std::strong_ordering(COMPARE_INTERFACE:: * fCompare)(typename RANGE::ARG_ITEM a, typename RANGE::ARG_ITEM b))
20 {
21
22 comparable_array < typename RANGE::const_iterator > stackLowerBound;
23
24 comparable_array < typename RANGE::const_iterator > stackUpperBound;
25
26 typename RANGE::const_iterator pLowerBound;
27
28 typename RANGE::const_iterator pUpperBound;
29
30 typename RANGE::const_iterator pLPos, pUPos, pMPos;
31
32 if (range.size() >= 2)
33 {
34
35 stackLowerBound.add(range.begin());
36
37 stackUpperBound.add(range.end() - 1);
38
39 while (true)
40 {
41
42 pLowerBound = stackLowerBound.pop();
43
44 pUpperBound = stackUpperBound.pop();
45
46 pLPos = pLowerBound;
47
48 pMPos = pLowerBound;
49
50 pUPos = pUpperBound;
51
52 while (true)
53 {
54
55 while (true)
56 {
57
58 if (pMPos == pUPos)
59 {
60
61 break;
62
63 }
64
65 if ((pinterface->*fCompare)(*pMPos, *pUPos) <= 0)
66 {
67
68 pUPos--;
69
70 }
71 else
72 {
73
74 range.__swap(pMPos, pUPos);
75
76 break;
77
78 }
79
80 }
81
82 if (pMPos == pUPos)
83 {
84
85 break;
86
87 }
88
89 pMPos = pUPos;
90
91 while (true)
92 {
93
94 if (pMPos == pLPos)
95 {
96
97 break;
98
99 }
100
101 if ((pinterface->*fCompare)(*pLPos, *pMPos) <= 0)
102 {
103
104 pLPos++;
105
106 }
107 else
108 {
109
110 range.__swap(pLPos, pMPos);
111
112 break;
113
114 }
115
116 }
117
118 if (pMPos == pLPos)
119 {
120
121 break;
122
123 }
124
125 pMPos = pLPos;
126
127 }
128
129 if (pLowerBound < pMPos - 1)
130 {
131
132 stackLowerBound.push(pLowerBound);
133
134 stackUpperBound.push(pMPos - 1);
135
136 }
137
138 if (pMPos + 1 < pUpperBound)
139 {
140
141 stackLowerBound.push(pMPos + 1);
142
143 stackUpperBound.push(pUpperBound);
144
145 }
146
147 if (stackLowerBound.get_size() == 0)
148 {
149
150 break;
151
152 }
153
154 }
155
156 }
157
158 }
159
160
161 } // namespace range
162
163
164} // namespace generic
165
166