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