5 #ifndef SORTLIST_TYPE_H |
5 #ifndef SORTLIST_TYPE_H |
6 #define SORTLIST_TYPE_H |
6 #define SORTLIST_TYPE_H |
7 |
7 |
8 #include "core/enum_type.hpp" |
8 #include "core/enum_type.hpp" |
9 #include "core/bitmath_func.hpp" |
9 #include "core/bitmath_func.hpp" |
|
10 #include "core/mem_func.hpp" |
|
11 #include "core/sort_func.hpp" |
10 #include "misc/smallvec.h" |
12 #include "misc/smallvec.h" |
11 #include "date_type.h" |
13 #include "date_type.h" |
12 |
14 |
13 enum SortListFlags { |
15 enum SortListFlags { |
14 VL_NONE = 0, ///< no sort |
16 VL_NONE = 0, ///< no sort |
172 /** |
159 /** |
173 * Toogle the sort order |
160 * Toogle the sort order |
174 * Since that is the worst condition for the sort function |
161 * Since that is the worst condition for the sort function |
175 * reverse the list here. |
162 * reverse the list here. |
176 */ |
163 */ |
177 FORCEINLINE void ToggleSortOrder() |
164 void ToggleSortOrder() |
178 { |
165 { |
179 this->flags ^= VL_DESC; |
166 this->flags ^= VL_DESC; |
180 |
167 |
181 if (this->IsSortable()) this->Reverse(); |
168 if (this->IsSortable()) MemReverseT(this->data, this->items); |
182 } |
169 } |
183 |
170 |
184 /** |
171 /** |
185 * GnomeSort algorithm |
172 * Sort the list. |
186 * This sorting uses a slightly modifyied Gnome search. |
173 * For the first sorting we use qsort since it is |
187 * The basic Gnome search trys to sort already sorted |
174 * faster for irregular sorted data. After that we |
188 * list parts. The modification skips these. For the first |
175 * use gsort. |
189 * sorting we use qsort since it is faster for irregular |
|
190 * sorted data. |
|
191 * |
176 * |
192 * @param compare The function to compare two list items |
177 * @param compare The function to compare two list items |
193 * @return true if the list sequence has been altered |
178 * @return true if the list sequence has been altered |
194 * */ |
179 * */ |
195 FORCEINLINE bool Sort(SortFunction *compare) |
180 bool Sort(SortFunction *compare) |
196 { |
181 { |
197 /* Do not sort if the resort bit is not set */ |
182 /* Do not sort if the resort bit is not set */ |
198 if (!HASBITS(this->flags, VL_RESORT)) return false; |
183 if (!HASBITS(this->flags, VL_RESORT)) return false; |
199 |
184 |
200 CLRBITS(this->flags, VL_RESORT); |
185 CLRBITS(this->flags, VL_RESORT); |
206 |
191 |
207 const bool desc = HASBITS(this->flags, VL_DESC); |
192 const bool desc = HASBITS(this->flags, VL_DESC); |
208 |
193 |
209 if (HASBITS(this->flags, VL_FIRST_SORT)) { |
194 if (HASBITS(this->flags, VL_FIRST_SORT)) { |
210 CLRBITS(this->flags, VL_FIRST_SORT); |
195 CLRBITS(this->flags, VL_FIRST_SORT); |
211 qsort(this->data, this->items, sizeof(T), (int (CDECL *)(const void *, const void *))compare); |
196 |
212 |
197 QSortT(this->data, this->items, compare, desc); |
213 if (desc) this->Reverse(); |
|
214 return true; |
198 return true; |
215 } |
199 } |
216 |
200 |
217 T *a = this->data; |
201 GSortT(this->data, this->items, compare, desc); |
218 T *b = a + 1; |
|
219 |
|
220 uint length = this->items; |
|
221 uint offset = 0; // Jump variable |
|
222 |
|
223 while (length > 1) { |
|
224 const int diff = compare(a, b); |
|
225 if ((!desc && diff <= 0) || (desc && diff >= 0)) { |
|
226 if (offset != 0) { |
|
227 /* Jump back to the last direction switch point */ |
|
228 a += offset; |
|
229 b += offset; |
|
230 offset = 0; |
|
231 continue; |
|
232 } |
|
233 a++; |
|
234 b++; |
|
235 length--; |
|
236 } else { |
|
237 Swap(*a, *b); |
|
238 if (a != this->data) { |
|
239 offset++; |
|
240 a--; |
|
241 b--; |
|
242 } |
|
243 } |
|
244 } |
|
245 return true; |
202 return true; |
246 } |
203 } |
247 |
204 |
248 /** |
205 /** |
249 * Hand the array of sort function pointers to the sort list |
206 * Hand the array of sort function pointers to the sort list |