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-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
    SORTTPL_FIELD1TYPE
    #define SORTTPL_FIELD1TYPE
    Definition: misc.c:6705
    SORTTPL_NAMEEXT
    #define SORTTPL_NAMEEXT
    Definition: misc.c:6703
    SORTTPL_FIELD3TYPE
    #define SORTTPL_FIELD3TYPE
    Definition: misc.c:6707
    SORTTPL_FIELD5TYPE
    #define SORTTPL_FIELD5TYPE
    Definition: misc.c:6709
    SORTTPL_FIELD4TYPE
    #define SORTTPL_FIELD4TYPE
    Definition: misc.c:6708
    SORTTPL_FIELD2TYPE
    #define SORTTPL_FIELD2TYPE
    Definition: misc.c:6706
    SORTTPL_KEYTYPE
    #define SORTTPL_KEYTYPE
    Definition: misc.c:6704
    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