Scippy

SCIP

Solving Constraint Integer Programs

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