Scippy

SCIP

Solving Constraint Integer Programs

sorttpl.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file sorttpl.c
26  * @ingroup OTHER_CFILES
27  * @brief template functions for sorting
28  * @author Michael Winkler
29  * @author Tobias Achterberg
30  * @author Gregor Hendel
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 /* template parameters that have to be passed in as #define's:
36  * #define SORTTPL_NAMEEXT <ext> extension to be used for SCIP method names, for example DownIntRealPtr
37  * #define SORTTPL_KEYTYPE <type> data type of the key array
38  * #define SORTTPL_FIELD1TYPE <type> data type of first additional array which should be sorted in the same way (optional)
39  * #define SORTTPL_FIELD2TYPE <type> data type of second additional array which should be sorted in the same way (optional)
40  * #define SORTTPL_FIELD3TYPE <type> data type of third additional array which should be sorted in the same way (optional)
41  * #define SORTTPL_FIELD4TYPE <type> data type of fourth additional array which should be sorted in the same way (optional)
42  * #define SORTTPL_FIELD5TYPE <type> data type of fifth additional array which should be sorted in the same way (optional)
43  * #define SORTTPL_FIELD6TYPE <type> data type of fifth additional array which should be sorted in the same way (optional)
44  * #define SORTTPL_PTRCOMP ptrcomp method should be used for comparisons (optional)
45  * #define SORTTPL_INDCOMP indcomp method should be used for comparisons (optional)
46  * #define SORTTPL_BACKWARDS should the array be sorted other way around
47  */
48 #include "scip/def.h"
49 #include "scip/dbldblarith.h"
50 #define SORTTPL_SHELLSORTMAX 25 /* maximal size for shell sort */
51 #define SORTTPL_MINSIZENINTHER 729 /* minimum input size to use ninther (median of nine) for pivot selection */
52 
53 #ifndef SORTTPL_NAMEEXT
54 #error You need to define SORTTPL_NAMEEXT.
55 #endif
56 #ifndef SORTTPL_KEYTYPE
57 #error You need to define SORTTPL_KEYTYPE.
58 #endif
59 
60 #ifdef SORTTPL_EXPANDNAME
61 #undef SORTTPL_EXPANDNAME
62 #endif
63 #ifdef SORTTPL_NAME
64 #undef SORTTPL_NAME
65 #endif
66 
67 /* enabling and disabling additional lines in the code */
68 #ifdef SORTTPL_FIELD1TYPE
69 #define SORTTPL_HASFIELD1(x) x
70 #define SORTTPL_HASFIELD1PAR(x) x,
71 #else
72 #define SORTTPL_HASFIELD1(x) /**/
73 #define SORTTPL_HASFIELD1PAR(x) /**/
74 #endif
75 #ifdef SORTTPL_FIELD2TYPE
76 #define SORTTPL_HASFIELD2(x) x
77 #define SORTTPL_HASFIELD2PAR(x) x,
78 #else
79 #define SORTTPL_HASFIELD2(x) /**/
80 #define SORTTPL_HASFIELD2PAR(x) /**/
81 #endif
82 #ifdef SORTTPL_FIELD3TYPE
83 #define SORTTPL_HASFIELD3(x) x
84 #define SORTTPL_HASFIELD3PAR(x) x,
85 #else
86 #define SORTTPL_HASFIELD3(x) /**/
87 #define SORTTPL_HASFIELD3PAR(x) /**/
88 #endif
89 #ifdef SORTTPL_FIELD4TYPE
90 #define SORTTPL_HASFIELD4(x) x
91 #define SORTTPL_HASFIELD4PAR(x) x,
92 #else
93 #define SORTTPL_HASFIELD4(x) /**/
94 #define SORTTPL_HASFIELD4PAR(x) /**/
95 #endif
96 #ifdef SORTTPL_FIELD5TYPE
97 #define SORTTPL_HASFIELD5(x) x
98 #define SORTTPL_HASFIELD5PAR(x) x,
99 #else
100 #define SORTTPL_HASFIELD5(x) /**/
101 #define SORTTPL_HASFIELD5PAR(x) /**/
102 #endif
103 #ifdef SORTTPL_FIELD6TYPE
104 #define SORTTPL_HASFIELD6(x) x
105 #define SORTTPL_HASFIELD6PAR(x) x,
106 #else
107 #define SORTTPL_HASFIELD6(x) /**/
108 #define SORTTPL_HASFIELD6PAR(x) /**/
109 #endif
110 #ifdef SORTTPL_PTRCOMP
111 #define SORTTPL_HASPTRCOMP(x) x
112 #define SORTTPL_HASPTRCOMPPAR(x) x,
113 #else
114 #define SORTTPL_HASPTRCOMP(x) /**/
115 #define SORTTPL_HASPTRCOMPPAR(x) /**/
116 #endif
117 #ifdef SORTTPL_INDCOMP
118 #define SORTTPL_HASINDCOMP(x) x
119 #define SORTTPL_HASINDCOMPPAR(x) x,
120 #else
121 #define SORTTPL_HASINDCOMP(x) /**/
122 #define SORTTPL_HASINDCOMPPAR(x) /**/
123 #endif
124 
125 
126 /* the two-step macro definition is needed, such that macro arguments
127  * get expanded by prescan of the C preprocessor (see "info cpp",
128  * chapter 3.10.6: Argument Prescan)
129  */
130 #define SORTTPL_EXPANDNAME(method, methodname) \
131  method ## methodname
132 #define SORTTPL_NAME(method, methodname) \
133  SORTTPL_EXPANDNAME(method, methodname)
134 
135 /* comparator method */
136 #ifdef SORTTPL_PTRCOMP
137 #ifdef SORTTPL_BACKWARDS
138 #define SORTTPL_CMP(x,y) (-ptrcomp((x), (y)))
139 #else
140 #define SORTTPL_CMP(x,y) (ptrcomp((x), (y)))
141 #endif
142 #else
143 #ifdef SORTTPL_INDCOMP
144 #ifdef SORTTPL_BACKWARDS
145 #define SORTTPL_CMP(x,y) (-indcomp(dataptr, (x), (y)))
146 #else
147 #define SORTTPL_CMP(x,y) (indcomp(dataptr, (x), (y)))
148 #endif
149 #else
150 #ifdef SORTTPL_BACKWARDS
151 #define SORTTPL_CMP(x,y) ((y) - (x))
152 #else
153 #define SORTTPL_CMP(x,y) ((x) - (y))
154 #endif
155 #endif
156 #endif
157 
158 #define SORTTPL_ISBETTER(x,y) (SORTTPL_CMP(x,y) < 0)
159 #define SORTTPL_ISWORSE(x,y) (SORTTPL_CMP(x,y) > 0)
160 
161 /* swapping two variables */
162 #define SORTTPL_SWAP(T,x,y) \
163  { \
164  T temp = x; \
165  x = y; \
166  y = temp; \
167  }
168 
169 
170 /** shell-sort an array of data elements; use it only for arrays smaller than 25 entries */
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
SORTTPL_KEYTYPE
#define SORTTPL_KEYTYPE
Definition: misc.c:6627
SORTTPL_CMP
#define SORTTPL_CMP(x, y)
Definition: sorttpl.c:153
SORTTPL_HASFIELD4PAR
#define SORTTPL_HASFIELD4PAR(x)
Definition: sorttpl.c:94
NULL
#define NULL
Definition: def.h:267
SORTTPL_NAME
#define SORTTPL_NAME(method, methodname)
Definition: sorttpl.c:132
SCIPquadprecSumQD
#define SCIPquadprecSumQD(r, a, b)
Definition: dbldblarith.h:62
SORTTPL_HASFIELD4
#define SORTTPL_HASFIELD4(x)
Definition: sorttpl.c:93
SORTTPL_FIELD5TYPE
#define SORTTPL_FIELD5TYPE
Definition: misc.c:6632
FALSE
#define FALSE
Definition: def.h:94
SORTTPL_SHELLSORTMAX
#define SORTTPL_SHELLSORTMAX
Definition: sorttpl.c:50
TRUE
#define TRUE
Definition: def.h:93
QUAD_ASSIGN
#define QUAD_ASSIGN(a, constant)
Definition: dbldblarith.h:51
dbldblarith.h
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
QUAD_TO_DBL
#define QUAD_TO_DBL(x)
Definition: dbldblarith.h:49
SCIP_DEFAULT_EPSILON
#define SCIP_DEFAULT_EPSILON
Definition: def.h:179
SORTTPL_HASFIELD6PAR
#define SORTTPL_HASFIELD6PAR(x)
Definition: sorttpl.c:108
SORTTPL_MINSIZENINTHER
#define SORTTPL_MINSIZENINTHER
Definition: sorttpl.c:51
SORTTPL_SWAP
#define SORTTPL_SWAP(T, x, y)
Definition: sorttpl.c:162
SORTTPL_HASINDCOMPPAR
#define SORTTPL_HASINDCOMPPAR(x)
Definition: sorttpl.c:122
QUAD
#define QUAD(x)
Definition: dbldblarith.h:47
SORTTPL_FIELD3TYPE
#define SORTTPL_FIELD3TYPE
Definition: misc.c:6630
SORTTPL_ISWORSE
#define SORTTPL_ISWORSE(x, y)
Definition: sorttpl.c:159
h
SCIP_VAR * h
Definition: circlepacking.c:68
SORTTPL_FIELD4TYPE
#define SORTTPL_FIELD4TYPE
Definition: misc.c:6631
SORTTPL_NAMEEXT
#define SORTTPL_NAMEEXT
Definition: misc.c:6626
SORTTPL_HASFIELD3PAR
#define SORTTPL_HASFIELD3PAR(x)
Definition: sorttpl.c:87
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
SORTTPL_HASFIELD5PAR
#define SORTTPL_HASFIELD5PAR(x)
Definition: sorttpl.c:101
EXCH
#define EXCH(x, y)
Definition: sorttpl.c:788
SORTTPL_HASFIELD2
#define SORTTPL_HASFIELD2(x)
Definition: sorttpl.c:79
SORTTPL_HASFIELD1PAR
#define SORTTPL_HASFIELD1PAR(x)
Definition: sorttpl.c:73
SORTTPL_HASFIELD6
#define SORTTPL_HASFIELD6(x)
Definition: sorttpl.c:107
SCIP_DECL_SORTINDCOMP
#define SCIP_DECL_SORTINDCOMP(x)
Definition: type_misc.h:180
b
SCIP_VAR ** b
Definition: circlepacking.c:65
MAX
#define MAX(x, y)
Definition: def.h:239
SCIPsort
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5538
SCIP_DECL_SORTPTRCOMP
#define SCIP_DECL_SORTPTRCOMP(x)
Definition: type_misc.h:188
SORTTPL_HASPTRCOMPPAR
#define SORTTPL_HASPTRCOMPPAR(x)
Definition: sorttpl.c:115
SORTTPL_FIELD1TYPE
#define SORTTPL_FIELD1TYPE
Definition: misc.c:6628
a
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_Real
#define SCIP_Real
Definition: def.h:173
SORTTPL_HASFIELD5
#define SORTTPL_HASFIELD5(x)
Definition: sorttpl.c:100
SORTTPL_HASFIELD1
#define SORTTPL_HASFIELD1(x)
Definition: sorttpl.c:72
SORTTPL_FIELD2TYPE
#define SORTTPL_FIELD2TYPE
Definition: misc.c:6629
def.h
common defines and data types used in all packages of SCIP
SORTTPL_HASFIELD3
#define SORTTPL_HASFIELD3(x)
Definition: sorttpl.c:86
SORTTPL_ISBETTER
#define SORTTPL_ISBETTER(x, y)
Definition: sorttpl.c:158
SORTTPL_HASFIELD2PAR
#define SORTTPL_HASFIELD2PAR(x)
Definition: sorttpl.c:80