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