SCIP Doxygen Documentation
Loading...
Searching...
No Matches
sorttpl.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file sorttpl.c
26 * @ingroup OTHER_CFILES
27 * @brief template functions for sorting
28 * @author Michael Winkler
29 * @author Tobias Achterberg
30 * @author Gregor Hendel
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35/* template parameters that have to be passed in as #define's:
36 * #define SORTTPL_NAMEEXT <ext> extension to be used for SCIP method names, for example DownIntRealPtr
37 * #define SORTTPL_KEYTYPE <type> data type of the key array
38 * #define SORTTPL_FIELD1TYPE <type> data type of first additional array which should be sorted in the same way (optional)
39 * #define SORTTPL_FIELD2TYPE <type> data type of second additional array which should be sorted in the same way (optional)
40 * #define SORTTPL_FIELD3TYPE <type> data type of third additional array which should be sorted in the same way (optional)
41 * #define SORTTPL_FIELD4TYPE <type> data type of fourth additional array which should be sorted in the same way (optional)
42 * #define SORTTPL_FIELD5TYPE <type> data type of fifth additional array which should be sorted in the same way (optional)
43 * #define SORTTPL_FIELD6TYPE <type> data type of fifth additional array which should be sorted in the same way (optional)
44 * #define SORTTPL_PTRCOMP ptrcomp method should be used for comparisons (optional)
45 * #define SORTTPL_INDCOMP indcomp method should be used for comparisons (optional)
46 * #define SORTTPL_BACKWARDS should the array be sorted other way around
47 */
48#include "scip/def.h"
49#define SORTTPL_SHELLSORTMAX 25 /* maximal size for shell sort */
50#define SORTTPL_MINSIZENINTHER 729 /* minimum input size to use ninther (median of nine) for pivot selection */
51
52#ifndef SORTTPL_NAMEEXT
53#error You need to define SORTTPL_NAMEEXT.
54#endif
55#ifndef SORTTPL_KEYTYPE
56#error You need to define SORTTPL_KEYTYPE.
57#endif
58
59#ifdef SORTTPL_EXPANDNAME
60#undef SORTTPL_EXPANDNAME
61#endif
62#ifdef SORTTPL_NAME
63#undef SORTTPL_NAME
64#endif
65
66/* enabling and disabling additional lines in the code */
67#ifdef SORTTPL_FIELD1TYPE
68#define SORTTPL_HASFIELD1(x) x
69#define SORTTPL_HASFIELD1PAR(x) x,
70#else
71#define SORTTPL_HASFIELD1(x) /**/
72#define SORTTPL_HASFIELD1PAR(x) /**/
73#endif
74#ifdef SORTTPL_FIELD2TYPE
75#define SORTTPL_HASFIELD2(x) x
76#define SORTTPL_HASFIELD2PAR(x) x,
77#else
78#define SORTTPL_HASFIELD2(x) /**/
79#define SORTTPL_HASFIELD2PAR(x) /**/
80#endif
81#ifdef SORTTPL_FIELD3TYPE
82#define SORTTPL_HASFIELD3(x) x
83#define SORTTPL_HASFIELD3PAR(x) x,
84#else
85#define SORTTPL_HASFIELD3(x) /**/
86#define SORTTPL_HASFIELD3PAR(x) /**/
87#endif
88#ifdef SORTTPL_FIELD4TYPE
89#define SORTTPL_HASFIELD4(x) x
90#define SORTTPL_HASFIELD4PAR(x) x,
91#else
92#define SORTTPL_HASFIELD4(x) /**/
93#define SORTTPL_HASFIELD4PAR(x) /**/
94#endif
95#ifdef SORTTPL_FIELD5TYPE
96#define SORTTPL_HASFIELD5(x) x
97#define SORTTPL_HASFIELD5PAR(x) x,
98#else
99#define SORTTPL_HASFIELD5(x) /**/
100#define SORTTPL_HASFIELD5PAR(x) /**/
101#endif
102#ifdef SORTTPL_FIELD6TYPE
103#define SORTTPL_HASFIELD6(x) x
104#define SORTTPL_HASFIELD6PAR(x) x,
105#else
106#define SORTTPL_HASFIELD6(x) /**/
107#define SORTTPL_HASFIELD6PAR(x) /**/
108#endif
109#ifdef SORTTPL_PTRCOMP
110#define SORTTPL_HASPTRCOMP(x) x
111#define SORTTPL_HASPTRCOMPPAR(x) x,
112#else
113#define SORTTPL_HASPTRCOMP(x) /**/
114#define SORTTPL_HASPTRCOMPPAR(x) /**/
115#endif
116#ifdef SORTTPL_INDCOMP
117#define SORTTPL_HASINDCOMP(x) x
118#define SORTTPL_HASINDCOMPPAR(x) x,
119#else
120#define SORTTPL_HASINDCOMP(x) /**/
121#define SORTTPL_HASINDCOMPPAR(x) /**/
122#endif
123
124
125/* the two-step macro definition is needed, such that macro arguments
126 * get expanded by prescan of the C preprocessor (see "info cpp",
127 * chapter 3.10.6: Argument Prescan)
128 */
129#define SORTTPL_EXPANDNAME(method, methodname) \
130 method ## methodname
131#define SORTTPL_NAME(method, methodname) \
132 SORTTPL_EXPANDNAME(method, methodname)
133
134/* comparator method */
135#ifdef SORTTPL_PTRCOMP
136#ifdef SORTTPL_BACKWARDS
137#define SORTTPL_CMP(x,y) (-ptrcomp((x), (y)))
138#else
139#define SORTTPL_CMP(x,y) (ptrcomp((x), (y)))
140#endif
141#else
142#ifdef SORTTPL_INDCOMP
143#ifdef SORTTPL_BACKWARDS
144#define SORTTPL_CMP(x,y) (-indcomp(dataptr, (x), (y)))
145#else
146#define SORTTPL_CMP(x,y) (indcomp(dataptr, (x), (y)))
147#endif
148#else
149#ifdef SORTTPL_BACKWARDS
150#define SORTTPL_CMP(x,y) ((y) - (x))
151#else
152#define SORTTPL_CMP(x,y) ((x) - (y))
153#endif
154#endif
155#endif
156
157#define SORTTPL_ISBETTER(x,y) (SORTTPL_CMP(x,y) < 0)
158#define SORTTPL_ISWORSE(x,y) (SORTTPL_CMP(x,y) > 0)
159
160/* swapping two variables */
161#define SORTTPL_SWAP(T,x,y) \
162 { \
163 T temp = x; \
164 x = y; \
165 y = temp; \
166 }
167
168
169/** shell-sort an array of data elements; use it only for arrays smaller than 25 entries */
170static
171void SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
172(
173 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
174 SCIP_Real* weights, /**< real, nonnegative weights that should be permuted like key, or NULL */
175 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
176 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
177 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
178 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
179 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
180 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
181 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
182 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
183 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
184 int start, /**< starting index */
185 int end /**< ending index */
186 )
187{
188 static const int incs[3] = {1, 5, 19}; /* sequence of increments */
189 int k;
190
191 assert(start <= end);
192
193 for( k = 2; k >= 0; --k )
194 {
195 int h = incs[k];
196 int first = h + start;
197 int i;
198
199 for( i = first; i <= end; ++i )
200 {
201 int j;
202 SORTTPL_KEYTYPE tempkey = key[i];
203
204 SCIP_Real tmpweight = weights != NULL ? weights[i] : 1;
205
206 SORTTPL_HASFIELD1( SORTTPL_FIELD1TYPE tempfield1 = field1[i]; )
207 SORTTPL_HASFIELD2( SORTTPL_FIELD2TYPE tempfield2 = field2[i]; )
208 SORTTPL_HASFIELD3( SORTTPL_FIELD3TYPE tempfield3 = field3[i]; )
209 SORTTPL_HASFIELD4( SORTTPL_FIELD4TYPE tempfield4 = field4[i]; )
210 SORTTPL_HASFIELD5( SORTTPL_FIELD5TYPE tempfield5 = field5[i]; )
211 SORTTPL_HASFIELD6( SORTTPL_FIELD6TYPE tempfield6 = field6[i]; )
212
213 j = i;
214 while( j >= first && SORTTPL_ISBETTER(tempkey, key[j-h]) )
215 {
216 key[j] = key[j-h];
217
218 if( weights != NULL )
219 weights[j] = weights[j - h];
220
221 SORTTPL_HASFIELD1( field1[j] = field1[j-h]; )
222 SORTTPL_HASFIELD2( field2[j] = field2[j-h]; )
223 SORTTPL_HASFIELD3( field3[j] = field3[j-h]; )
224 SORTTPL_HASFIELD4( field4[j] = field4[j-h]; )
225 SORTTPL_HASFIELD5( field5[j] = field5[j-h]; )
226 SORTTPL_HASFIELD6( field6[j] = field6[j-h]; )
227 j -= h;
228 }
229
230 key[j] = tempkey;
231
232 if( weights != NULL )
233 weights[j] = tmpweight;
234
235 SORTTPL_HASFIELD1( field1[j] = tempfield1; )
236 SORTTPL_HASFIELD2( field2[j] = tempfield2; )
237 SORTTPL_HASFIELD3( field3[j] = tempfield3; )
238 SORTTPL_HASFIELD4( field4[j] = tempfield4; )
239 SORTTPL_HASFIELD5( field5[j] = tempfield5; )
240 SORTTPL_HASFIELD6( field6[j] = tempfield6; )
241 }
242 }
243}
244
245/** returns the index a, b, or c of the median element among key[a], key[b], and key[c] */
246static
247int SORTTPL_NAME(sorttpl_medianThree, SORTTPL_NAMEEXT)
248(
249 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
250 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
251 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
252 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
253 int a, /**< first index of the key array to consider */
254 int b, /**< second index of the key array to consider */
255 int c /**< third index of the array to consider */
256 )
257{
258 assert(a >= 0);
259 assert(b >= 0);
260 assert(c >= 0);
261 assert(a != b);
262 assert(b != c);
263 assert(c != a);
264
265 /* let the elements in the unsorted order be a, b, c at positions start, mid, and end */
266 if( SORTTPL_ISBETTER( key[a], key[b]) ) /* a <= b */
267 {
268 if( SORTTPL_ISBETTER( key[b], key[c]) ) /* b <= c */
269 /* resulting permutation: a b c */
270 return b;
271 else /* b > c */
272 {
273 if( SORTTPL_ISBETTER( key[a], key[c]) ) /* a <= c */
274 /* resulting permutation: a c b */
275 return c;
276 else
277 /* resulting permutation: c a b */
278 return a;
279 }
280 }
281 else /* a > b */
282 {
283 if( SORTTPL_ISBETTER( key[b], key[c] ) )
284 {
285 if( SORTTPL_ISBETTER( key[a], key[c]) )
286 /* resulting permutation: b a c */
287 return a;
288 else
289 /* resulting permutation: b c a */
290 return c;
291 }
292 else
293 /* resulting permutation: c b a */
294 return b;
295 }
296}
297
298/** guess a median for the key array [start, ..., end] by using the median of the first, last, and middle element */
299static
300int SORTTPL_NAME(sorttpl_selectPivotIndex, SORTTPL_NAMEEXT)
301(
302 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
303 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
304 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
305 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
306 int start, /**< first index of the key array to consider */
307 int end /**< last index of the key array to consider */
308 )
309{
310 int pivotindex;
311
312 /* use the middle index on small arrays */
313 if( end - start + 1 <= SORTTPL_SHELLSORTMAX )
314 pivotindex = (start + end) / 2;
315 else if( end - start + 1 < SORTTPL_MINSIZENINTHER )
316 {
317 /* select the median of the first, last, and middle element as pivot element */
318 int mid = (start + end) / 2;
319 pivotindex = SORTTPL_NAME(sorttpl_medianThree, SORTTPL_NAMEEXT)
320 (key,
321 SORTTPL_HASPTRCOMPPAR(ptrcomp)
322 SORTTPL_HASINDCOMPPAR(indcomp)
323 SORTTPL_HASINDCOMPPAR(dataptr)
324 start, mid, end);
325 }
326 else
327 {
328 /* use the median of medians of nine evenly distributed elements of the key array */
329 int gap = (end - start + 1) / 9;
330 int median1;
331 int median2;
332 int median3;
333
334 /* this should always hold */
335 assert(start + 8 * gap <= end);
336
337 /* collect 3 medians evenly distributed over the array */
338 median1 = SORTTPL_NAME(sorttpl_medianThree, SORTTPL_NAMEEXT)
339 (key,
340 SORTTPL_HASPTRCOMPPAR(ptrcomp)
341 SORTTPL_HASINDCOMPPAR(indcomp)
342 SORTTPL_HASINDCOMPPAR(dataptr)
343 start, start + gap, start + 2 * gap);
344
345 median2 = SORTTPL_NAME(sorttpl_medianThree, SORTTPL_NAMEEXT)
346 (key,
347 SORTTPL_HASPTRCOMPPAR(ptrcomp)
348 SORTTPL_HASINDCOMPPAR(indcomp)
349 SORTTPL_HASINDCOMPPAR(dataptr)
350 start + 3 * gap, start + 4 * gap, start + 5 * gap);
351 median3 = SORTTPL_NAME(sorttpl_medianThree, SORTTPL_NAMEEXT)
352 (key,
353 SORTTPL_HASPTRCOMPPAR(ptrcomp)
354 SORTTPL_HASINDCOMPPAR(indcomp)
355 SORTTPL_HASINDCOMPPAR(dataptr)
356 start + 6 * gap, start + 7 * gap, start + 8 * gap);
357
358 /* compute and return the median of the medians */
359 pivotindex = SORTTPL_NAME(sorttpl_medianThree, SORTTPL_NAMEEXT)
360 (key,
361 SORTTPL_HASPTRCOMPPAR(ptrcomp)
362 SORTTPL_HASINDCOMPPAR(indcomp)
363 SORTTPL_HASINDCOMPPAR(dataptr)
364 median1, median2, median3);
365 }
366
367 return pivotindex;
368}
369
370
371/** quick-sort an array of pointers; pivot is the medial element */
372static
373void SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
374(
375 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
376 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
377 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
378 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
379 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
380 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
381 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
382 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
383 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
384 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
385 int start, /**< starting index */
386 int end, /**< ending index */
387 SCIP_Bool type /**< TRUE, if quick-sort should start with with key[lo] < pivot <= key[hi], key[lo] <= pivot < key[hi] otherwise */
388 )
389{
390 assert(start <= end);
391
392 /* use quick-sort for long lists */
393 while( end - start >= SORTTPL_SHELLSORTMAX )
394 {
395 SORTTPL_KEYTYPE pivotkey;
396 int lo;
397 int hi;
398 int mid;
399
400 /* select pivot element */
401 mid = SORTTPL_NAME(sorttpl_selectPivotIndex, SORTTPL_NAMEEXT)
402 (key,
403 SORTTPL_HASPTRCOMPPAR(ptrcomp)
404 SORTTPL_HASINDCOMPPAR(indcomp)
405 SORTTPL_HASINDCOMPPAR(dataptr)
406 start, end);
407 pivotkey = key[mid];
408
409 /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */
410 lo = start;
411 hi = end;
412 for( ;; )
413 {
414 if( type )
415 {
416 while( lo < end && SORTTPL_ISBETTER(key[lo], pivotkey) )
417 lo++;
418 while( hi > start && !SORTTPL_ISBETTER(key[hi], pivotkey) )
419 hi--;
420 }
421 else
422 {
423 while( lo < end && !SORTTPL_ISWORSE(key[lo], pivotkey) )
424 lo++;
425 while( hi > start && SORTTPL_ISWORSE(key[hi], pivotkey) )
426 hi--;
427 }
428
429 if( lo >= hi )
430 break;
431
432 SORTTPL_SWAP(SORTTPL_KEYTYPE, key[lo], key[hi]);
433 SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[lo], field1[hi]); )
434 SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[lo], field2[hi]); )
435 SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[lo], field3[hi]); )
436 SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[lo], field4[hi]); )
437 SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[lo], field5[hi]); )
438 SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[lo], field6[hi]); )
439
440 lo++;
441 hi--;
442 }
443 assert((hi == lo-1) || (type && hi == start) || (!type && lo == end));
444
445 /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/
446 if( type )
447 {
448 while( lo < end && !SORTTPL_ISBETTER(pivotkey, key[lo]) )
449 lo++;
450
451 /* make sure that we have at least one element in the smaller partition */
452 if( lo == start )
453 {
454 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
455 assert(!SORTTPL_ISBETTER(key[mid], pivotkey)); /* the pivot element did not change its position */
456 assert(!SORTTPL_ISBETTER(pivotkey, key[mid]));
457 SORTTPL_SWAP(SORTTPL_KEYTYPE, key[lo], key[mid]);
458 SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[lo], field1[mid]); )
459 SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[lo], field2[mid]); )
460 SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[lo], field3[mid]); )
461 SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[lo], field4[mid]); )
462 SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[lo], field5[mid]); )
463 SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[lo], field6[mid]); )
464 lo++;
465 }
466 }
467 else
468 {
469 while( hi > start && !SORTTPL_ISWORSE(pivotkey, key[hi]) )
470 hi--;
471
472 /* make sure that we have at least one element in the smaller partition */
473 if( hi == end )
474 {
475 /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
476 assert(!SORTTPL_ISBETTER(key[mid], pivotkey)); /* the pivot element did not change its position */
477 assert(!SORTTPL_ISBETTER(pivotkey, key[mid]));
478 SORTTPL_SWAP(SORTTPL_KEYTYPE, key[hi], key[mid]);
479 SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[hi], field1[mid]); )
480 SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[hi], field2[mid]); )
481 SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[hi], field3[mid]); )
482 SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[hi], field4[mid]); )
483 SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[hi], field5[mid]); )
484 SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[hi], field6[mid]); )
485 hi--;
486 }
487 }
488
489 /* sort the smaller partition by a recursive call, sort the larger part without recursion */
490 if( hi - start <= end - lo )
491 {
492 /* sort [start,hi] with a recursive call */
493 if( start < hi )
494 {
495 SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
496 (key,
497 SORTTPL_HASFIELD1PAR(field1)
498 SORTTPL_HASFIELD2PAR(field2)
499 SORTTPL_HASFIELD3PAR(field3)
500 SORTTPL_HASFIELD4PAR(field4)
501 SORTTPL_HASFIELD5PAR(field5)
502 SORTTPL_HASFIELD6PAR(field6)
503 SORTTPL_HASPTRCOMPPAR(ptrcomp)
504 SORTTPL_HASINDCOMPPAR(indcomp)
505 SORTTPL_HASINDCOMPPAR(dataptr)
506 start, hi, !type);
507 }
508
509 /* now focus on the larger part [lo,end] */
510 start = lo;
511 }
512 else
513 {
514 if( lo < end )
515 {
516 /* sort [lo,end] with a recursive call */
517 SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
518 (key,
519 SORTTPL_HASFIELD1PAR(field1)
520 SORTTPL_HASFIELD2PAR(field2)
521 SORTTPL_HASFIELD3PAR(field3)
522 SORTTPL_HASFIELD4PAR(field4)
523 SORTTPL_HASFIELD5PAR(field5)
524 SORTTPL_HASFIELD6PAR(field6)
525 SORTTPL_HASPTRCOMPPAR(ptrcomp)
526 SORTTPL_HASINDCOMPPAR(indcomp)
527 SORTTPL_HASINDCOMPPAR(dataptr)
528 lo, end, !type);
529 }
530
531 /* now focus on the larger part [start,hi] */
532 end = hi;
533 }
534 type = !type;
535 }
536
537 /* use shell sort on the remaining small list */
538 if( end - start >= 1 )
539 {
540 SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
541 (key, NULL,
542 SORTTPL_HASFIELD1PAR(field1)
543 SORTTPL_HASFIELD2PAR(field2)
544 SORTTPL_HASFIELD3PAR(field3)
545 SORTTPL_HASFIELD4PAR(field4)
546 SORTTPL_HASFIELD5PAR(field5)
547 SORTTPL_HASFIELD6PAR(field6)
548 SORTTPL_HASPTRCOMPPAR(ptrcomp)
549 SORTTPL_HASINDCOMPPAR(indcomp)
550 SORTTPL_HASINDCOMPPAR(dataptr)
551 start, end);
552 }
553}
554
555#ifndef NDEBUG
556/** verifies that an array is indeed sorted */
557static
558void SORTTPL_NAME(sorttpl_checkSort, SORTTPL_NAMEEXT)
559(
560 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
561 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
562 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
563 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
564 int len /**< length of the array */
565 )
566{
567 int i;
568
569 for( i = 0; i < len-1; i++ )
570 {
571 assert(!SORTTPL_ISBETTER(key[i+1], key[i]));
572 }
573}
574#endif
575
576/** SCIPsort...(): sorts array 'key' and performs the same permutations on the additional 'field' arrays */
577void SORTTPL_NAME(SCIPsort, SORTTPL_NAMEEXT)
578(
579 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
580 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
581 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
582 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
583 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
584 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
585 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
586 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
587 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
588 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
589 int len /**< length of arrays */
590 )
591{
592 /* ignore the trivial cases */
593 if( len <= 1 )
594 return;
595
596 /* use shell sort on the remaining small list */
597 if( len <= SORTTPL_SHELLSORTMAX )
598 {
599 SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
600 (key, NULL,
601 SORTTPL_HASFIELD1PAR(field1)
602 SORTTPL_HASFIELD2PAR(field2)
603 SORTTPL_HASFIELD3PAR(field3)
604 SORTTPL_HASFIELD4PAR(field4)
605 SORTTPL_HASFIELD5PAR(field5)
606 SORTTPL_HASFIELD6PAR(field6)
607 SORTTPL_HASPTRCOMPPAR(ptrcomp)
608 SORTTPL_HASINDCOMPPAR(indcomp)
609 SORTTPL_HASINDCOMPPAR(dataptr)
610 0, len-1);
611 }
612 else
613 {
614 SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
615 (key,
616 SORTTPL_HASFIELD1PAR(field1)
617 SORTTPL_HASFIELD2PAR(field2)
618 SORTTPL_HASFIELD3PAR(field3)
619 SORTTPL_HASFIELD4PAR(field4)
620 SORTTPL_HASFIELD5PAR(field5)
621 SORTTPL_HASFIELD6PAR(field6)
622 SORTTPL_HASPTRCOMPPAR(ptrcomp)
623 SORTTPL_HASINDCOMPPAR(indcomp)
624 SORTTPL_HASINDCOMPPAR(dataptr)
625 0, len-1, TRUE);
626 }
627#ifndef NDEBUG
628 SORTTPL_NAME(sorttpl_checkSort, SORTTPL_NAMEEXT)
629 (key,
630 SORTTPL_HASPTRCOMPPAR(ptrcomp)
631 SORTTPL_HASINDCOMPPAR(indcomp)
632 SORTTPL_HASINDCOMPPAR(dataptr)
633 len);
634#endif
635}
636
637
638/** SCIPsortedvecInsert...(): adds an element to a sorted multi-vector
639 *
640 * This method does not do any memory allocation! It assumes that the arrays are large enough
641 * to store the additional values.
642 */
643void SORTTPL_NAME(SCIPsortedvecInsert, SORTTPL_NAMEEXT)
644(
645 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
646 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
647 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
648 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
649 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
650 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
651 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
652 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
653 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
654 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
655 SORTTPL_KEYTYPE keyval, /**< key value of new element */
656 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE field1val ) /**< field1 value of new element */
657 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE field2val ) /**< field1 value of new element */
658 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE field3val ) /**< field1 value of new element */
659 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE field4val ) /**< field1 value of new element */
660 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE field5val ) /**< field1 value of new element */
661 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE field6val ) /**< field1 value of new element */
662 int* len, /**< pointer to length of arrays (will be increased by 1) */
663 int* pos /**< pointer to store the insert position, or NULL */
664 )
665{
666 int j;
667
668 for( j = *len; j > 0 && SORTTPL_ISBETTER(keyval, key[j-1]); j-- )
669 {
670 key[j] = key[j-1];
671 SORTTPL_HASFIELD1( field1[j] = field1[j-1]; )
672 SORTTPL_HASFIELD2( field2[j] = field2[j-1]; )
673 SORTTPL_HASFIELD3( field3[j] = field3[j-1]; )
674 SORTTPL_HASFIELD4( field4[j] = field4[j-1]; )
675 SORTTPL_HASFIELD5( field5[j] = field5[j-1]; )
676 SORTTPL_HASFIELD6( field6[j] = field6[j-1]; )
677 }
678
679 key[j] = keyval;
680 SORTTPL_HASFIELD1( field1[j] = field1val; )
681 SORTTPL_HASFIELD2( field2[j] = field2val; )
682 SORTTPL_HASFIELD3( field3[j] = field3val; )
683 SORTTPL_HASFIELD4( field4[j] = field4val; )
684 SORTTPL_HASFIELD5( field5[j] = field5val; )
685 SORTTPL_HASFIELD6( field6[j] = field6val; )
686
687 (*len)++;
688
689 if( pos != NULL )
690 (*pos) = j;
691}
692
693/** SCIPsortedvecDelPos...(): deletes an element at a given position from a sorted multi-vector */
694void SORTTPL_NAME(SCIPsortedvecDelPos, SORTTPL_NAMEEXT)
695(
696 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
697 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
698 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
699 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
700 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
701 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
702 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
703 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
704 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
705 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
706 int pos, /**< array position of element to be deleted */
707 int* len /**< pointer to length of arrays (will be decreased by 1) */
708 )
709{
710 int j;
711
712 assert(0 <= pos && pos < *len);
713
714 (*len)--;
715
716 for( j = pos; j < *len; j++ )
717 {
718 key[j] = key[j+1];
719 SORTTPL_HASFIELD1( field1[j] = field1[j+1]; )
720 SORTTPL_HASFIELD2( field2[j] = field2[j+1]; )
721 SORTTPL_HASFIELD3( field3[j] = field3[j+1]; )
722 SORTTPL_HASFIELD4( field4[j] = field4[j+1]; )
723 SORTTPL_HASFIELD5( field5[j] = field5[j+1]; )
724 SORTTPL_HASFIELD6( field6[j] = field6[j+1]; )
725 }
726}
727
728
729/* The SCIPsortedvecFind...() method only has needs the key array but not the other field arrays. In order to
730 * avoid defining the same method multiple times, only include this method if we do not have any additional fields.
731 */
732#ifndef SORTTPL_FIELD1TYPE
733
734/** SCIPsortedvecFind...(): Finds the position at which 'val' is located in the sorted vector by binary search.
735 * If the element exists, the method returns TRUE and stores the position of the element in '*pos'.
736 * If the element does not exist, the method returns FALSE and stores the position of the element that follows
737 * 'val' in the ordering in '*pos', i.e., '*pos' is the position at which 'val' would be inserted.
738 * Note that if the element is not found, '*pos' may be equal to len if all existing elements are smaller than 'val'.
739 */
740SCIP_Bool SORTTPL_NAME(SCIPsortedvecFind, SORTTPL_NAMEEXT)
741(
742 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
743 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
744 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
745 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
746 SORTTPL_KEYTYPE val, /**< data field to find position for */
747 int len, /**< length of array */
748 int* pos /**< pointer to store the insert position */
749 )
750{
751 int left;
752 int right;
753
754 assert(key != NULL);
755 assert(pos != NULL);
756
757 left = 0;
758 right = len-1;
759 while( left <= right )
760 {
761 int middle;
762
763 middle = (left+right)/2;
764 assert(0 <= middle && middle < len);
765
766 if( SORTTPL_ISBETTER(val, key[middle]) )
767 right = middle-1;
768 else if( SORTTPL_ISBETTER(key[middle], val) )
769 left = middle+1;
770 else
771 {
772 *pos = middle;
773 return TRUE;
774 }
775 }
776 assert(left == right+1);
777
778 *pos = left;
779 return FALSE;
780}
781
782#endif
783
784
785
786/** macro that performs an exchange in the weighted selection algorithm, including weights */
787#define EXCH(x,y) \
788 do \
789 { \
790 SORTTPL_SWAP(SORTTPL_KEYTYPE, key[x], key[y]); \
791 \
792 if( weights != NULL ) \
793 SORTTPL_SWAP(SCIP_Real, weights[x], weights[y]); \
794 \
795 SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[x], field1[y]); ) \
796 SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[x], field2[y]); ) \
797 SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[x], field3[y]); ) \
798 SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[x], field4[y]); ) \
799 SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[x], field5[y]); ) \
800 SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[x], field6[y]); ) \
801 } \
802 while( FALSE )
803
804#ifndef NDEBUG
805/** verifies that the partial sorting and especially the critical item satisfy all properties */
806static
807void SORTTPL_NAME(sorttpl_checkWeightedSelection, SORTTPL_NAMEEXT)
808(
809 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
810 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
811 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
812 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
813 SCIP_Real* weights, /**< (optional), nonnegative weights array for the critical item, or NULL (all weights are equal to one) */
814 SCIP_Real capacity, /**< the maximum capacity that is exceeded by the critical item */
815 int len, /**< length of arrays */
816 int medianpos /**< the index of the critical item */
817 )
818{
819 SCIP_Real weightsum = 0.0;
820 int i;
821
822 assert(medianpos >= 0);
823 assert(medianpos <= len);
824
825 for( i = 0; i < len; i++ )
826 {
827 weightsum += weights != NULL ? weights[i] : 1.0;
828
829 /* check that the weight sum exceeds the capacity at the critical item
830 * and that the partial sorting is correct
831 */
832 assert(i < medianpos || (weightsum > capacity + SCIP_DEFAULT_EPSILON
833 && !SORTTPL_ISBETTER(key[i], key[medianpos])));
834 assert(i >= medianpos || (weightsum <= capacity + SCIP_DEFAULT_EPSILON
835 && (medianpos == len || !SORTTPL_ISBETTER(key[medianpos], key[i]))));
836 }
837}
838#endif
839
840/** partially sorts a given keys array around the critical item w.r.t. the \p capacity and permutes the
841 * additional 'field' arrays in the same way
842 *
843 * The critical item is the first element whose cumulative weight strictly exceeds the capacity.
844 *
845 * If no weights-array is passed, the algorithm assumes weights equal to one.
846 */
847void SORTTPL_NAME(SCIPselectWeighted, SORTTPL_NAMEEXT)
848(
849 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
850 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
851 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
852 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
853 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
854 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
855 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
856 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
857 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
858 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
859 SCIP_Real* weights, /**< (optional), nonnegative weights array for the critical item, or NULL (all weights are equal to one) */
860 SCIP_Real capacity, /**< the maximum capacity that is exceeded by the critical item */
861 int len, /**< length of arrays */
862 int* medianpos /**< pointer to store the index of the critical item, or NULL, if not needed */
863 )
864{
865 int hi;
866 int lo;
867 int j;
868 int localmedianpos = -1;
869 SCIP_Real totalweightsum;
870 SCIP_Real partialweightsum;
871
872 lo = 0;
873 hi = len - 1;
874
875 /* compute the total weight and stop if the full set does not exceed the capacity */
876 if( weights != NULL )
877 {
878 totalweightsum = 0.0;
879 for( j = 0; j < len; ++j )
880 totalweightsum += weights[j];
881 }
882 else
883 totalweightsum = len;
884
885 if( totalweightsum <= capacity + SCIP_DEFAULT_EPSILON )
886 {
887 localmedianpos = len;
888
889 goto CHECKANDRETURN;
890 }
891
892 partialweightsum = 0.0;
893
894SELECT:
895 while( hi - lo + 1 > SORTTPL_SHELLSORTMAX )
896 {
897 int i;
898 int bt;
899 int wt;
900 int p;
901 int pivotindex;
902 SCIP_Real weightsum;
903 SCIP_Real pivotweight;
904 SORTTPL_KEYTYPE pivot;
905
906 /* guess a critical item as pivot */
907 pivotindex = SORTTPL_NAME(sorttpl_selectPivotIndex, SORTTPL_NAMEEXT)
908 (key,
909 SORTTPL_HASPTRCOMPPAR(ptrcomp)
910 SORTTPL_HASINDCOMPPAR(indcomp)
911 SORTTPL_HASINDCOMPPAR(dataptr)
912 lo, hi);
913
914 pivot = key[pivotindex];
915
916 /* swap pivot element to the end of the array */
917 if( pivotindex != lo )
918 {
919 EXCH(lo, pivotindex);
920 }
921
922 /* initialize array indices for the current element, the better elements, and the worse elements */
923 i = lo;
924 bt = lo;
925 wt = hi;
926
927 /* iterate through elements once to establish three partition into better elements, equal elements, and worse elements
928 *
929 * at every iteration, i denotes the current, previously unseen element, starting from the position lo
930 * all elements [lo,...bt - 1] are better than the pivot
931 * all elements [wt + 1,... hi] are worse than the pivot
932 *
933 * at termination, all elements [bt,...wt] are equal to the pivot element
934 * */
935 while( i <= wt )
936 {
937 /* element i is better than pivot; exchange elements i and bt, increase both */
938 if( SORTTPL_ISBETTER(key[i], pivot) )
939 {
940 EXCH(i, bt);
941 i++;
942 bt++;
943 }
944 /* element i is worse than pivot: exchange it with the element at position wt; no increment of i
945 * because an unseen element is waiting at index i after the swap
946 */
947 else if( SORTTPL_ISWORSE(key[i], pivot) )
948 {
949 EXCH(i, wt);
950 wt--;
951 }
952 else
953 i++;
954 }
955
956 assert(wt >= bt);
957
958 if( weights != NULL )
959 {
960 /* collect weights of elements larger than the pivot */
961 weightsum = partialweightsum;
962 for( i = lo; i < bt; ++i )
963 {
964 assert(SORTTPL_ISBETTER(key[i], pivot));
965 weightsum += weights[i];
966 }
967 }
968 else
969 {
970 /* if all weights are equal to one, we directly know the larger and the equal weight sum */
971 weightsum = bt;
972 }
973
974 /* the weight in the better half of the array exceeds the capacity. Continue the search there */
975 if( weightsum > capacity + SCIP_DEFAULT_EPSILON )
976 hi = bt - 1;
977 else
978 {
979 /* loop through duplicates of pivot element and check if one is the critical item */
980 for( p = bt; p <= wt; ++p )
981 {
982 assert(SORTTPL_CMP(key[p], pivot) == 0);
983 pivotweight = weights != NULL ? weights[p] : 1.0;
984 weightsum += pivotweight;
985
986 /* the element at index p is the critical item */
987 if( weightsum > capacity + SCIP_DEFAULT_EPSILON )
988 {
989 localmedianpos = p;
990
991 goto CHECKANDRETURN;
992 }
993 }
994
995 /* continue loop by searching the remaining elements [wt+1,...,hi] */
996 partialweightsum = weightsum;
997 lo = wt + 1;
998 }
999 }
1000
1001 assert(hi - lo + 1 <= SORTTPL_SHELLSORTMAX);
1002
1003 /* use shell sort to solve the remaining elements completely */
1004 if( hi - lo + 1 > 1 )
1005 {
1006 SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
1007 (key, weights,
1008 SORTTPL_HASFIELD1PAR(field1)
1009 SORTTPL_HASFIELD2PAR(field2)
1010 SORTTPL_HASFIELD3PAR(field3)
1011 SORTTPL_HASFIELD4PAR(field4)
1012 SORTTPL_HASFIELD5PAR(field5)
1013 SORTTPL_HASFIELD6PAR(field6)
1014 SORTTPL_HASPTRCOMPPAR(ptrcomp)
1015 SORTTPL_HASINDCOMPPAR(indcomp)
1016 SORTTPL_HASINDCOMPPAR(dataptr)
1017 lo, hi);
1018 }
1019
1020 /* after sorting it is possible for lo to reach the end of the array */
1021 assert(lo <= len);
1022 assert(hi < len);
1023 hi = MIN(hi + 1, len - 1);
1024
1025 /* determine the critical item position among the remaining elements */
1026 for( j = lo; j <= hi; ++j )
1027 {
1028 partialweightsum += weights != NULL ? weights[j] : 1.0;
1029
1030 /* we finally found the critical item */
1031 if( partialweightsum > capacity + SCIP_DEFAULT_EPSILON )
1032 {
1033 localmedianpos = j;
1034
1035 goto CHECKANDRETURN;
1036 }
1037 }
1038
1039 /* continue selection after candidate range if sorting introduced substantial numerical deviation */
1040 if( j < len )
1041 {
1042 lo = j;
1043 hi = len - 1;
1044
1045 goto SELECT;
1046 }
1047
1048 localmedianpos = len;
1049
1050CHECKANDRETURN:
1051
1052/* perform a thorough debug check of the selection result */
1053#ifndef NDEBUG
1054 SORTTPL_NAME(sorttpl_checkWeightedSelection, SORTTPL_NAMEEXT)
1055 (key,
1056 SORTTPL_HASPTRCOMPPAR(ptrcomp)
1057 SORTTPL_HASINDCOMPPAR(indcomp)
1058 SORTTPL_HASINDCOMPPAR(dataptr)
1059 weights,
1060 capacity,
1061 len,
1062 localmedianpos);
1063#endif
1064
1065 if( medianpos != NULL )
1066 *medianpos = localmedianpos;
1067
1068 return;
1069}
1070
1071/** partially sorts a given keys array around the given index \p k and permutes the additional 'field' arrays are in the same way */
1072void SORTTPL_NAME(SCIPselect, SORTTPL_NAMEEXT)
1073(
1074 SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
1075 SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
1076 SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
1077 SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
1078 SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
1079 SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
1080 SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
1081 SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
1082 SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
1083 SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
1084 int k, /**< the index of the desired element, must be between 0 (search for maximum/minimum) and len - 1 */
1085 int len /**< length of arrays */
1086 )
1087{
1088 SCIP_Real capacity;
1089 int pos;
1090
1091 /* return directly in cases that make no sense at all */
1092 if( k < 0 || k >= len )
1093 return;
1094
1095 /* The summand 0.5 is necessary because the elements are zero-indexed. */
1096 capacity = k + 0.5;
1097
1098 pos = -1;
1099
1100 /* call the general algorithm for the critical item with weights equal to one (by passing NULL) */
1101 SORTTPL_NAME(SCIPselectWeighted, SORTTPL_NAMEEXT)
1102 (key,
1103 SORTTPL_HASFIELD1PAR(field1)
1104 SORTTPL_HASFIELD2PAR(field2)
1105 SORTTPL_HASFIELD3PAR(field3)
1106 SORTTPL_HASFIELD4PAR(field4)
1107 SORTTPL_HASFIELD5PAR(field5)
1108 SORTTPL_HASFIELD6PAR(field6)
1109 SORTTPL_HASPTRCOMPPAR(ptrcomp)
1110 SORTTPL_HASINDCOMPPAR(indcomp)
1111 SORTTPL_HASINDCOMPPAR(dataptr)
1112 NULL, capacity, len, &pos);
1113
1114 /* the critical item position should be exactly at position k */
1115 assert(pos == k);
1116}
1117
1118/* undefine template parameters and local defines */
1119#undef SORTTPL_NAMEEXT
1120#undef SORTTPL_KEYTYPE
1121#undef SORTTPL_FIELD1TYPE
1122#undef SORTTPL_FIELD2TYPE
1123#undef SORTTPL_FIELD3TYPE
1124#undef SORTTPL_FIELD4TYPE
1125#undef SORTTPL_FIELD5TYPE
1126#undef SORTTPL_FIELD6TYPE
1127#undef SORTTPL_PTRCOMP
1128#undef SORTTPL_INDCOMP
1129#undef SORTTPL_HASFIELD1
1130#undef SORTTPL_HASFIELD2
1131#undef SORTTPL_HASFIELD3
1132#undef SORTTPL_HASFIELD4
1133#undef SORTTPL_HASFIELD5
1134#undef SORTTPL_HASFIELD6
1135#undef SORTTPL_HASPTRCOMP
1136#undef SORTTPL_HASINDCOMP
1137#undef SORTTPL_HASFIELD1PAR
1138#undef SORTTPL_HASFIELD2PAR
1139#undef SORTTPL_HASFIELD3PAR
1140#undef SORTTPL_HASFIELD4PAR
1141#undef SORTTPL_HASFIELD5PAR
1142#undef SORTTPL_HASFIELD6PAR
1143#undef SORTTPL_HASPTRCOMPPAR
1144#undef SORTTPL_HASINDCOMPPAR
1145#undef SORTTPL_ISBETTER
1146#undef SORTTPL_ISWORSE
1147#undef SORTTPL_CMP
1148#undef EXCH
1149#undef SORTTPL_SWAP
1150#undef SORTTPL_SHELLSORTMAX
1151#undef SORTTPL_MINSIZENINTHER
1152#undef SORTTPL_BACKWARDS
h
SCIP_VAR * h
Definition circlepacking.c:68
a
SCIP_VAR * a
Definition circlepacking.c:66
b
SCIP_VAR ** b
Definition circlepacking.c:65
def.h
common defines and data types used in all packages of SCIP
NULL
#define NULL
Definition def.h:257
SCIP_Bool
#define SCIP_Bool
Definition def.h:100
SCIP_DEFAULT_EPSILON
#define SCIP_DEFAULT_EPSILON
Definition def.h:173
MIN
#define MIN(x, y)
Definition def.h:233
SCIP_Real
#define SCIP_Real
Definition def.h:165
TRUE
#define TRUE
Definition def.h:102
FALSE
#define FALSE
Definition def.h:103
SCIPsort
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition misc.c:5581
c
int c
Definition heur_intdiving.c:223
assert
assert(minobj< SCIPgetCutoffbound(scip))
i
int i
Definition heur_rootsoldiving.c:216
SORTTPL_FIELD1TYPE
#define SORTTPL_FIELD1TYPE
Definition misc.c:5617
SORTTPL_NAMEEXT
#define SORTTPL_NAMEEXT
Definition misc.c:5601
SORTTPL_FIELD3TYPE
#define SORTTPL_FIELD3TYPE
Definition misc.c:5668
SORTTPL_FIELD5TYPE
#define SORTTPL_FIELD5TYPE
Definition misc.c:5919
SORTTPL_FIELD4TYPE
#define SORTTPL_FIELD4TYPE
Definition misc.c:5678
SORTTPL_FIELD2TYPE
#define SORTTPL_FIELD2TYPE
Definition misc.c:5650
SORTTPL_KEYTYPE
#define SORTTPL_KEYTYPE
Definition misc.c:5602
SORTTPL_HASFIELD1PAR
#define SORTTPL_HASFIELD1PAR(x)
Definition sorttpl.c:72
SORTTPL_HASPTRCOMPPAR
#define SORTTPL_HASPTRCOMPPAR(x)
Definition sorttpl.c:114
SORTTPL_SHELLSORTMAX
#define SORTTPL_SHELLSORTMAX
Definition sorttpl.c:49
EXCH
#define EXCH(x, y)
Definition sorttpl.c:787
SORTTPL_HASFIELD6
#define SORTTPL_HASFIELD6(x)
Definition sorttpl.c:106
SORTTPL_HASFIELD3PAR
#define SORTTPL_HASFIELD3PAR(x)
Definition sorttpl.c:86
SORTTPL_MINSIZENINTHER
#define SORTTPL_MINSIZENINTHER
Definition sorttpl.c:50
SORTTPL_HASFIELD5PAR
#define SORTTPL_HASFIELD5PAR(x)
Definition sorttpl.c:100
SORTTPL_HASFIELD2
#define SORTTPL_HASFIELD2(x)
Definition sorttpl.c:78
SORTTPL_HASINDCOMPPAR
#define SORTTPL_HASINDCOMPPAR(x)
Definition sorttpl.c:121
SORTTPL_ISBETTER
#define SORTTPL_ISBETTER(x, y)
Definition sorttpl.c:157
SORTTPL_HASFIELD6PAR
#define SORTTPL_HASFIELD6PAR(x)
Definition sorttpl.c:107
SORTTPL_NAME
#define SORTTPL_NAME(method, methodname)
Definition sorttpl.c:131
SORTTPL_CMP
#define SORTTPL_CMP(x, y)
Definition sorttpl.c:152
SORTTPL_HASFIELD3
#define SORTTPL_HASFIELD3(x)
Definition sorttpl.c:85
SORTTPL_HASFIELD2PAR
#define SORTTPL_HASFIELD2PAR(x)
Definition sorttpl.c:79
SORTTPL_ISWORSE
#define SORTTPL_ISWORSE(x, y)
Definition sorttpl.c:158
SORTTPL_HASFIELD5
#define SORTTPL_HASFIELD5(x)
Definition sorttpl.c:99
SORTTPL_HASFIELD4PAR
#define SORTTPL_HASFIELD4PAR(x)
Definition sorttpl.c:93
SORTTPL_HASFIELD4
#define SORTTPL_HASFIELD4(x)
Definition sorttpl.c:92
SORTTPL_HASFIELD1
#define SORTTPL_HASFIELD1(x)
Definition sorttpl.c:71
SORTTPL_SWAP
#define SORTTPL_SWAP(T, x, y)
Definition sorttpl.c:161
SCIP_DECL_SORTPTRCOMP
#define SCIP_DECL_SORTPTRCOMP(x)
Definition type_misc.h:189
SCIP_DECL_SORTINDCOMP
#define SCIP_DECL_SORTINDCOMP(x)
Definition type_misc.h:181