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