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