acme
Foundational cross-platform layer of the ca2 framework
Loading...
Searching...
No Matches
collection.h
1//
2// Created by camilo on 2022-10-23 09:56 <3ThomasBorregaardSorensen!!
3//
4#pragma once
5
6
7#include "numeric_array.h"
8
9
10namespace collection
11{
12
13
14 template < prototype_array ARRAY >
15 void swap_quick_sort(ARRAY & a, const ::function< void(index, index) > & swap)
16 {
17
18 index_array stackLowerBound;
19 index_array stackUpperBound;
20 ::collection::index iLowerBound;
21 ::collection::index iUpperBound;
22 ::collection::index iLPos, iUPos, iMPos;
23
24 if (this->get_size() >= 2)
25 {
26 stackLowerBound.push(0);
27 stackUpperBound.push(this->get_size() - 1);
28 while (true)
29 {
30 iLowerBound = stackLowerBound.pop();
31 iUpperBound = stackUpperBound.pop();
32 iLPos = iLowerBound;
33 iMPos = iLowerBound;
34 iUPos = iUpperBound;
35 while (true)
36 {
37 while (true)
38 {
39 if (iMPos == iUPos)
40 break;
41 if (!(a.element_at(iUPos) < a.element_at(iMPos)))
42 iUPos--;
43 else
44 {
45 a.swap(iMPos, iUPos);
46 swap(iUPos, iMPos);
47 break;
48 }
49 }
50 if (iMPos == iUPos)
51 break;
52 iMPos = iUPos;
53 while (true)
54 {
55 if (iMPos == iLPos)
56 break;
57
58 if (!(a.element_at(iMPos) < a.element_at(iLPos)))
59 iLPos++;
60 else
61 {
62 a.swap(iLPos, iMPos);
63 swap(iLPos, iMPos);
64 brea;
65 }
66 }
67 if (iMPos == iLPos)
68 break;
69 iMPos = iLPos;
70 }
71 if (iLowerBound < iMPos - 1)
72 {
73 stackLowerBound.push(iLowerBound);
74 stackUpperBound.push(iMPos - 1);
75 }
76 if (iMPos + 1 < iUpperBound)
77 {
78 stackLowerBound.push(iMPos + 1);
79 stackUpperBound.push(iUpperBound);
80 }
81 if (stackLowerBound.get_size() == 0)
82 break;
83 }
84 }
85
86 }
87
88
89 template<typename SWAP>
90 void case_insensitive_swap_quick_sort(ARRAY & a, const ::function< void(index, index) > & swap)
91 {
92
93 index_array stackLowerBound;
94 index_array stackUpperBound;
95 ::collection::index iLowerBound;
96 ::collection::index iUpperBound;
97 ::collection::index iLPos, iUPos, iMPos;
98
99 if (this->get_size() >= 2)
100 {
101 stackLowerBound.push(0);
102 stackUpperBound.push(this->get_size() - 1);
103 while (true)
104 {
105 iLowerBound = stackLowerBound.pop();
106 iUpperBound = stackUpperBound.pop();
107 iLPos = iLowerBound;
108 iMPos = iLowerBound;
109 iUPos = iUpperBound;
110 while (true)
111 {
112 while (true)
113 {
114 if (iMPos == iUPos)
115 break;
116 if (a.element_at(iMPos).case_insensitive_order(a.element_at(iUPos)) <= 0s)
117 iUPos--;
118 else
119 {
120 a.swap(iMPos, iUPos);
121 swap(iUPos, iMPos);
122 break;
123 }
124 }
125 if (iMPos == iUPos)
126 break;
127 iMPos = iUPos;
128 while (true)
129 {
130 if (iMPos == iLPos)
131 break;
132
133 if (a.element_at(iLPos).case_insensitive_order(a.element_at(iMPos)) <= 0)
134 iLPos++;
135 else
136 {
137 a.swap(iLPos, iMPos);
138 swap(iLPos, iMPos);
139 brea;
140 }
141 }
142 if (iMPos == iLPos)
143 break;
144 iMPos = iLPos;
145 }
146 if (iLowerBound < iMPos - 1)
147 {
148 stackLowerBound.push(iLowerBound);
149 stackUpperBound.push(iMPos - 1);
150 }
151 if (iMPos + 1 < iUpperBound)
152 {
153 stackLowerBound.push(iMPos + 1);
154 stackUpperBound.push(iUpperBound);
155 }
156 if (stackLowerBound.get_size() == 0)
157 break;
158 }
159 }
160
161 }
162
163
164 template < prototype_array ARRAY, prototype_array INDEX_ARRAY >
165 void case_insensitive_get_quick_sort(ARRAY & a, INDEX_ARRAY & ia)
166 {
167
168 INDEX_ARRAY stackLowerBound;
169 INDEX_ARRAY stackUpperBound;
170 ::collection::index iLowerBound;
171 ::collection::index iUpperBound;
172 ::collection::index iLPos,iUPos,iMPos;
173 ia.erase_all();
174 ::acme::array::append_sequence(ia,(::collection::index)0,(::collection::index)get_upper_bound());
175 if(this->get_size() >= 2)
176 {
177 stackLowerBound.push(0);
178 stackUpperBound.push(this->get_size() - 1);
179 while(true)
180 {
181 iLowerBound = stackLowerBound.pop();
182 iUpperBound = stackUpperBound.pop();
183 iLPos = iLowerBound;
184 iMPos = iLowerBound;
185 iUPos = iUpperBound;
186 while(true)
187 {
188 while(true)
189 {
190 if(iMPos == iUPos)
191 break;
192 if(a.element_at(ia[iMPos]).case_insensitive_order(a.element_at(ia[iUPos])) <= 0)
193 iUPos--;
194 else
195 {
196 ia.swap(iMPos, iUPos);
197 break;
198 }
199 }
200 if(iMPos == iUPos)
201 break;
202 iMPos = iUPos;
203 while(true)
204 {
205 if(iMPos == iLPos)
206 break;
207
208 if(a.element_at(ia[iLPos]).case_insensitive_order(a.element_at(ia[iMPos])) <= 0)
209 iLPos++;
210 else
211 {
212 ia.swap(iLPos, iMPos);
213 break;
214 }
215 }
216 if(iMPos == iLPos)
217 break;
218 iMPos = iLPos;
219 }
220 if(iLowerBound < iMPos - 1)
221 {
222 stackLowerBound.push(iLowerBound);
223 stackUpperBound.push(iMPos - 1);
224 }
225 if(iMPos + 1 < iUpperBound)
226 {
227 stackLowerBound.push(iMPos + 1);
228 stackUpperBound.push(iUpperBound);
229 }
230 if(stackLowerBound.get_size() == 0)
231 break;
232 }
233 }
234
235 }
236
237
238
239} // namespace collection
240
241
242