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-2025 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:248
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:91
    SCIP_DEFAULT_EPSILON
    #define SCIP_DEFAULT_EPSILON
    Definition: def.h:164
    SCIP_Real
    #define SCIP_Real
    Definition: def.h:156
    TRUE
    #define TRUE
    Definition: def.h:93
    FALSE
    #define FALSE
    Definition: def.h:94
    MAX
    #define MAX(x, y)
    Definition: def.h:220
    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: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:189
    SCIP_DECL_SORTINDCOMP
    #define SCIP_DECL_SORTINDCOMP(x)
    Definition: type_misc.h:181