1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 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 */ 171 static 172 void 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] */ 247 static 248 int 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 */ 300 static 301 int 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 */ 373 static 374 void 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 */ 558 static 559 void 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 */ 578 void 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 */ 644 void 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 */ 695 void 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 */ 741 SCIP_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 */ 807 static 808 void 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 */ 860 void 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 1056 CHECKANDRETURN: 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 */ 1078 void 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 1159