Scippy

GCG

Branch-and-Price & Column Generation for Everyone

gcgsorttpl.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file gcgsorttpl.c
29  * @brief template functions for sorting
30  * @author Michael Winkler
31  * @author Tobias Achterberg
32  * @author Tobias Oelschlaegel
33  */
34 
35 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36 
37 /* template parameters that have to be passed in as #define's:
38  * #define GCGSORTTPL_NAMEEXT <ext> extension to be used for SCIP method names, for example DownIntRealPtr
39  * #define GCGSORTTPL_KEYTYPE <type> data type of the key array
40  * #define GCGSORTTPL_FIELD1TYPE <type> data type of first additional array which should be sorted in the same way (optional)
41  * #define GCGSORTTPL_FIELD2TYPE <type> data type of second additional array which should be sorted in the same way (optional)
42  * #define GCGSORTTPL_FIELD3TYPE <type> data type of third additional array which should be sorted in the same way (optional)
43  * #define GCGSORTTPL_FIELD4TYPE <type> data type of fourth additional array which should be sorted in the same way (optional)
44  * #define GCGSORTTPL_FIELD5TYPE <type> data type of fifth additional array which should be sorted in the same way (optional)
45  * #define GCGSORTTPL_FIELD6TYPE <type> data type of fifth additional array which should be sorted in the same way (optional)
46  * #define GCGSORTTPL_PTRCOMP ptrcomp method should be used for comparisons (optional)
47  * #define GCGSORTTPL_INDCOMP indcomp method should be used for comparisons (optional)
48  * #define GCGSORTTPL_BACKWARDS should the array be sorted other way around
49  */
50 
51 /** compares two element indices
52  ** result:
53  ** < 0: ind1 comes before (is better than) ind2
54  ** = 0: both indices have the same value
55  ** > 0: ind2 comes after (is worse than) ind2
56  **/
57 #define GCG_DECL_SORTINDCOMP(x) int x (void* userdata, void* dataptr, int ind1, int ind2)
58 
59 /** compares two data element pointers
60  ** result:
61  ** < 0: elem1 comes before (is better than) elem2
62  ** = 0: both elements have the same value
63  ** > 0: elem2 comes after (is worse than) elem2
64  **/
65 #define GCG_DECL_SORTPTRCOMP(x) int x (void* userdata, void* elem1, void* elem2)
66 
67 
68 #define GCGSORTTPL_SHELLSORTMAX 25
69 
70 #ifndef GCGSORTTPL_NAMEEXT
71 #error You need to define GCGSORTTPL_NAMEEXT.
72 #endif
73 #ifndef GCGSORTTPL_KEYTYPE
74 #error You need to define GCGSORTTPL_KEYTYPE.
75 #endif
76 
77 #ifdef GCGSORTTPL_EXPANDNAME
78 #undef GCGSORTTPL_EXPANDNAME
79 #endif
80 #ifdef GCGSORTTPL_NAME
81 #undef GCGSORTTPL_NAME
82 #endif
83 
84 /* enabling and disabling additional lines in the code */
85 #ifdef GCGSORTTPL_FIELD1TYPE
86 #define GCGSORTTPL_HASFIELD1(x) x
87 #define GCGSORTTPL_HASFIELD1PAR(x) x,
88 #else
89 #define GCGSORTTPL_HASFIELD1(x) /**/
90 #define GCGSORTTPL_HASFIELD1PAR(x) /**/
91 #endif
92 #ifdef GCGSORTTPL_FIELD2TYPE
93 #define GCGSORTTPL_HASFIELD2(x) x
94 #define GCGSORTTPL_HASFIELD2PAR(x) x,
95 #else
96 #define GCGSORTTPL_HASFIELD2(x) /**/
97 #define GCGSORTTPL_HASFIELD2PAR(x) /**/
98 #endif
99 #ifdef GCGSORTTPL_FIELD3TYPE
100 #define GCGSORTTPL_HASFIELD3(x) x
101 #define GCGSORTTPL_HASFIELD3PAR(x) x,
102 #else
103 #define GCGSORTTPL_HASFIELD3(x) /**/
104 #define GCGSORTTPL_HASFIELD3PAR(x) /**/
105 #endif
106 #ifdef GCGSORTTPL_FIELD4TYPE
107 #define GCGSORTTPL_HASFIELD4(x) x
108 #define GCGSORTTPL_HASFIELD4PAR(x) x,
109 #else
110 #define GCGSORTTPL_HASFIELD4(x) /**/
111 #define GCGSORTTPL_HASFIELD4PAR(x) /**/
112 #endif
113 #ifdef GCGSORTTPL_FIELD5TYPE
114 #define GCGSORTTPL_HASFIELD5(x) x
115 #define GCGSORTTPL_HASFIELD5PAR(x) x,
116 #else
117 #define GCGSORTTPL_HASFIELD5(x) /**/
118 #define GCGSORTTPL_HASFIELD5PAR(x) /**/
119 #endif
120 #ifdef GCGSORTTPL_FIELD6TYPE
121 #define GCGSORTTPL_HASFIELD6(x) x
122 #define GCGSORTTPL_HASFIELD6PAR(x) x,
123 #else
124 #define GCGSORTTPL_HASFIELD6(x) /**/
125 #define GCGSORTTPL_HASFIELD6PAR(x) /**/
126 #endif
127 #ifdef GCGSORTTPL_PTRCOMP
128 #define GCGSORTTPL_HASPTRCOMP(x) x
129 #define GCGSORTTPL_HASPTRCOMPPAR(x) x,
130 #else
131 #define GCGSORTTPL_HASPTRCOMP(x) /**/
132 #define GCGSORTTPL_HASPTRCOMPPAR(x) /**/
133 #endif
134 #ifdef GCGSORTTPL_INDCOMP
135 #define GCGSORTTPL_HASINDCOMP(x) x
136 #define GCGSORTTPL_HASINDCOMPPAR(x) x,
137 #else
138 #define GCGSORTTPL_HASINDCOMP(x) /**/
139 #define GCGSORTTPL_HASINDCOMPPAR(x) /**/
140 #endif
141 
142 
143 /* the two-step macro definition is needed, such that macro arguments
144  * get expanded by prescan of the C preprocessor (see "info cpp",
145  * chapter 3.10.6: Argument Prescan)
146  */
147 #define GCGSORTTPL_EXPANDNAME(method, methodname) \
148  method ## methodname
149 #define GCGSORTTPL_NAME(method, methodname) \
150  GCGSORTTPL_EXPANDNAME(method, methodname)
151 
152 /* comparator method */
153 #ifdef GCGSORTTPL_PTRCOMP
154 #ifdef GCGSORTTPL_BACKWARDS
155 #define GCGSORTTPL_ISBETTER(x,y) (ptrcomp(userdata, (x), (y)) > 0)
156 #define GCGSORTTPL_ISWORSE(x,y) (ptrcomp(userdata, (x), (y)) < 0)
157 #else
158 #define GCGSORTTPL_ISBETTER(x,y) (ptrcomp(userdata, (x), (y)) < 0)
159 #define GCGSORTTPL_ISWORSE(x,y) (ptrcomp(userdata, (x), (y)) > 0)
160 #endif
161 #else
162 #ifdef GCGSORTTPL_INDCOMP
163 #ifdef GCGSORTTPL_BACKWARDS
164 #define GCGSORTTPL_ISBETTER(x,y) (indcomp(userdata, dataptr, (x), (y)) > 0)
165 #define GCGSORTTPL_ISWORSE(x,y) (indcomp(userdata, dataptr, (x), (y)) < 0)
166 #else
167 #define GCGSORTTPL_ISBETTER(x,y) (indcomp(userdata, dataptr, (x), (y)) < 0)
168 #define GCGSORTTPL_ISWORSE(x,y) (indcomp(userdata, dataptr, (x), (y)) > 0)
169 #endif
170 #else
171 #ifdef GCGSORTTPL_BACKWARDS
172 #define GCGSORTTPL_ISBETTER(x,y) ((x) > (y))
173 #define GCGSORTTPL_ISWORSE(x,y) ((x) < (y))
174 #else
175 #define GCGSORTTPL_ISBETTER(x,y) ((x) < (y))
176 #define GCGSORTTPL_ISWORSE(x,y) ((x) > (y))
177 #endif
178 #endif
179 #endif
180 
181 /* swapping two variables */
182 #define GCGSORTTPL_SWAP(T,x,y) \
183  { \
184  T temp = x; \
185  x = y; \
186  y = temp; \
187  }
188 
189 
190 /** shell-sort an array of data elements; use it only for arrays smaller than 25 entries */
191 static
192 void GCGSORTTPL_NAME(gcgsorttpl_shellSort, GCGSORTTPL_NAMEEXT)
193 (
194  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
195  GCGSORTTPL_HASFIELD1PAR( GCGSORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
196  GCGSORTTPL_HASFIELD2PAR( GCGSORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
197  GCGSORTTPL_HASFIELD3PAR( GCGSORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
198  GCGSORTTPL_HASFIELD4PAR( GCGSORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
199  GCGSORTTPL_HASFIELD5PAR( GCGSORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
200  GCGSORTTPL_HASFIELD6PAR( GCGSORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
201  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
202  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
203  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
204  void* userdata, /**< userdata that is supplied to the comparator function */
205  int start, /**< starting index */
206  int end /**< ending index */
207  )
208 {
209  static const int incs[3] = {1, 5, 19}; /* sequence of increments */
210  int k;
211 
212  assert(start <= end);
213 
214  for( k = 2; k >= 0; --k )
215  {
216  int h = incs[k];
217  int first = h + start;
218  int i;
219 
220  for( i = first; i <= end; ++i )
221  {
222  int j;
223  GCGSORTTPL_KEYTYPE tempkey = key[i];
224 
225  GCGSORTTPL_HASFIELD1( GCGSORTTPL_FIELD1TYPE tempfield1 = field1[i]; )
226  GCGSORTTPL_HASFIELD2( GCGSORTTPL_FIELD2TYPE tempfield2 = field2[i]; )
227  GCGSORTTPL_HASFIELD3( GCGSORTTPL_FIELD3TYPE tempfield3 = field3[i]; )
228  GCGSORTTPL_HASFIELD4( GCGSORTTPL_FIELD4TYPE tempfield4 = field4[i]; )
229  GCGSORTTPL_HASFIELD5( GCGSORTTPL_FIELD5TYPE tempfield5 = field5[i]; )
230  GCGSORTTPL_HASFIELD6( GCGSORTTPL_FIELD6TYPE tempfield6 = field6[i]; )
231 
232  j = i;
233  while( j >= first && GCGSORTTPL_ISBETTER(tempkey, key[j-h]) )
234  {
235  key[j] = key[j-h];
236  GCGSORTTPL_HASFIELD1( field1[j] = field1[j-h]; )
237  GCGSORTTPL_HASFIELD2( field2[j] = field2[j-h]; )
238  GCGSORTTPL_HASFIELD3( field3[j] = field3[j-h]; )
239  GCGSORTTPL_HASFIELD4( field4[j] = field4[j-h]; )
240  GCGSORTTPL_HASFIELD5( field5[j] = field5[j-h]; )
241  GCGSORTTPL_HASFIELD6( field6[j] = field6[j-h]; )
242  j -= h;
243  }
244 
245  key[j] = tempkey;
246  GCGSORTTPL_HASFIELD1( field1[j] = tempfield1; )
247  GCGSORTTPL_HASFIELD2( field2[j] = tempfield2; )
248  GCGSORTTPL_HASFIELD3( field3[j] = tempfield3; )
249  GCGSORTTPL_HASFIELD4( field4[j] = tempfield4; )
250  GCGSORTTPL_HASFIELD5( field5[j] = tempfield5; )
251  GCGSORTTPL_HASFIELD6( field6[j] = tempfield6; )
252  }
253  }
254 }
255 
256 
257 /** quick-sort an array of pointers; pivot is the medial element */
258 static
259 void GCGSORTTPL_NAME(gcgsorttpl_qSort, GCGSORTTPL_NAMEEXT)
260 (
261  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
262  GCGSORTTPL_HASFIELD1PAR( GCGSORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
263  GCGSORTTPL_HASFIELD2PAR( GCGSORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
264  GCGSORTTPL_HASFIELD3PAR( GCGSORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
265  GCGSORTTPL_HASFIELD4PAR( GCGSORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
266  GCGSORTTPL_HASFIELD5PAR( GCGSORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
267  GCGSORTTPL_HASFIELD6PAR( GCGSORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
268  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
269  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
270  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
271  void* userdata, /**< userdata that is supplied to the comparator function */
272  int start, /**< starting index */
273  int end, /**< ending index */
274  SCIP_Bool type /**< TRUE, if quick-sort should start with with key[lo] < pivot <= key[hi], key[lo] <= pivot < key[hi] otherwise */
275  )
276 {
277  assert(start <= end);
278 
279  /* use quick-sort for long lists */
280  while( end - start >= GCGSORTTPL_SHELLSORTMAX )
281  {
282  GCGSORTTPL_KEYTYPE pivotkey;
283  int lo;
284  int hi;
285  int mid;
286 
287  /* select pivot element */
288  mid = (start+end)/2;
289  pivotkey = key[mid];
290 
291  /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */
292  lo = start;
293  hi = end;
294  for( ;; )
295  {
296  if( type )
297  {
298  while( lo < end && GCGSORTTPL_ISBETTER(key[lo], pivotkey) )
299  lo++;
300  while( hi > start && !GCGSORTTPL_ISBETTER(key[hi], pivotkey) )
301  hi--;
302  }
303  else
304  {
305  while( lo < end && !GCGSORTTPL_ISWORSE(key[lo], pivotkey) )
306  lo++;
307  while( hi > start && GCGSORTTPL_ISWORSE(key[hi], pivotkey) )
308  hi--;
309  }
310 
311  if( lo >= hi )
312  break;
313 
314  GCGSORTTPL_SWAP(GCGSORTTPL_KEYTYPE, key[lo], key[hi]);
315  GCGSORTTPL_HASFIELD1( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD1TYPE, field1[lo], field1[hi]); )
316  GCGSORTTPL_HASFIELD2( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD2TYPE, field2[lo], field2[hi]); )
317  GCGSORTTPL_HASFIELD3( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD3TYPE, field3[lo], field3[hi]); )
318  GCGSORTTPL_HASFIELD4( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD4TYPE, field4[lo], field4[hi]); )
319  GCGSORTTPL_HASFIELD5( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD5TYPE, field5[lo], field5[hi]); )
320  GCGSORTTPL_HASFIELD6( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD6TYPE, field6[lo], field6[hi]); )
321 
322  lo++;
323  hi--;
324  }
325  assert((hi == lo-1) || (type && hi == start) || (!type && lo == end));
326 
327  /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/
328  if( type )
329  {
330  while( lo < end && !GCGSORTTPL_ISBETTER(pivotkey, key[lo]) )
331  lo++;
332 
333  /* make sure that we have at least one element in the smaller partition */
334  if( lo == start )
335  {
336  /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
337  assert(!GCGSORTTPL_ISBETTER(key[mid], pivotkey)); /* the pivot element did not change its position */
338  assert(!GCGSORTTPL_ISBETTER(pivotkey, key[mid]));
339  GCGSORTTPL_SWAP(GCGSORTTPL_KEYTYPE, key[lo], key[mid]);
340  GCGSORTTPL_HASFIELD1( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD1TYPE, field1[lo], field1[mid]); )
341  GCGSORTTPL_HASFIELD2( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD2TYPE, field2[lo], field2[mid]); )
342  GCGSORTTPL_HASFIELD3( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD3TYPE, field3[lo], field3[mid]); )
343  GCGSORTTPL_HASFIELD4( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD4TYPE, field4[lo], field4[mid]); )
344  GCGSORTTPL_HASFIELD5( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD5TYPE, field5[lo], field5[mid]); )
345  GCGSORTTPL_HASFIELD6( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD6TYPE, field6[lo], field6[mid]); )
346  lo++;
347  }
348  }
349  else
350  {
351  while( hi > start && !GCGSORTTPL_ISWORSE(pivotkey, key[hi]) )
352  hi--;
353 
354  /* make sure that we have at least one element in the smaller partition */
355  if( hi == end )
356  {
357  /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
358  assert(!GCGSORTTPL_ISBETTER(key[mid], pivotkey)); /* the pivot element did not change its position */
359  assert(!GCGSORTTPL_ISBETTER(pivotkey, key[mid]));
360  GCGSORTTPL_SWAP(GCGSORTTPL_KEYTYPE, key[hi], key[mid]);
361  GCGSORTTPL_HASFIELD1( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD1TYPE, field1[hi], field1[mid]); )
362  GCGSORTTPL_HASFIELD2( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD2TYPE, field2[hi], field2[mid]); )
363  GCGSORTTPL_HASFIELD3( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD3TYPE, field3[hi], field3[mid]); )
364  GCGSORTTPL_HASFIELD4( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD4TYPE, field4[hi], field4[mid]); )
365  GCGSORTTPL_HASFIELD5( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD5TYPE, field5[hi], field5[mid]); )
366  GCGSORTTPL_HASFIELD6( GCGSORTTPL_SWAP(GCGSORTTPL_FIELD6TYPE, field6[hi], field6[mid]); )
367  hi--;
368  }
369  }
370 
371  /* sort the smaller partition by a recursive call, sort the larger part without recursion */
372  if( hi - start <= end - lo )
373  {
374  /* sort [start,hi] with a recursive call */
375  if( start < hi )
376  {
377  GCGSORTTPL_NAME(gcgsorttpl_qSort, GCGSORTTPL_NAMEEXT)
378  (key,
379  GCGSORTTPL_HASFIELD1PAR(field1)
380  GCGSORTTPL_HASFIELD2PAR(field2)
381  GCGSORTTPL_HASFIELD3PAR(field3)
382  GCGSORTTPL_HASFIELD4PAR(field4)
383  GCGSORTTPL_HASFIELD5PAR(field5)
384  GCGSORTTPL_HASFIELD6PAR(field6)
385  GCGSORTTPL_HASPTRCOMPPAR(ptrcomp)
386  GCGSORTTPL_HASINDCOMPPAR(indcomp)
387  GCGSORTTPL_HASINDCOMPPAR(dataptr)
388  userdata, start, hi, !type);
389  }
390 
391  /* now focus on the larger part [lo,end] */
392  start = lo;
393  }
394  else
395  {
396  if( lo < end )
397  {
398  /* sort [lo,end] with a recursive call */
399  GCGSORTTPL_NAME(gcgsorttpl_qSort, GCGSORTTPL_NAMEEXT)
400  (key,
401  GCGSORTTPL_HASFIELD1PAR(field1)
402  GCGSORTTPL_HASFIELD2PAR(field2)
403  GCGSORTTPL_HASFIELD3PAR(field3)
404  GCGSORTTPL_HASFIELD4PAR(field4)
405  GCGSORTTPL_HASFIELD5PAR(field5)
406  GCGSORTTPL_HASFIELD6PAR(field6)
407  GCGSORTTPL_HASPTRCOMPPAR(ptrcomp)
408  GCGSORTTPL_HASINDCOMPPAR(indcomp)
409  GCGSORTTPL_HASINDCOMPPAR(dataptr)
410  userdata, lo, end, !type);
411  }
412 
413  /* now focus on the larger part [start,hi] */
414  end = hi;
415  }
416  type = !type;
417  }
418 
419  /* use shell sort on the remaining small list */
420  if( end - start >= 1 )
421  {
422  GCGSORTTPL_NAME(gcgsorttpl_shellSort, GCGSORTTPL_NAMEEXT)
423  (key,
424  GCGSORTTPL_HASFIELD1PAR(field1)
425  GCGSORTTPL_HASFIELD2PAR(field2)
426  GCGSORTTPL_HASFIELD3PAR(field3)
427  GCGSORTTPL_HASFIELD4PAR(field4)
428  GCGSORTTPL_HASFIELD5PAR(field5)
429  GCGSORTTPL_HASFIELD6PAR(field6)
430  GCGSORTTPL_HASPTRCOMPPAR(ptrcomp)
431  GCGSORTTPL_HASINDCOMPPAR(indcomp)
432  GCGSORTTPL_HASINDCOMPPAR(dataptr)
433  userdata, start, end);
434  }
435 }
436 
437 #ifndef NDEBUG
438 /** verifies that an array is indeed sorted */
439 static
440 void GCGSORTTPL_NAME(gcgsorttpl_checkSort, GCGSORTTPL_NAMEEXT)
441 (
442  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
443  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
444  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
445  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
446  void* userdata, /**< userdata that is supplied to the comparator function */
447  int len /**< length of the array */
448  )
449 {
450  int i;
451 
452  for( i = 0; i < len-1; i++ )
453  {
454  assert(!GCGSORTTPL_ISBETTER(key[i+1], key[i]));
455  }
456 }
457 #endif
458 
459 /** SCIPsort...(): sorts array 'key' and performs the same permutations on the additional 'field' arrays */
460 void GCGSORTTPL_NAME(GCGsort, GCGSORTTPL_NAMEEXT)
461 (
462  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
463  GCGSORTTPL_HASFIELD1PAR( GCGSORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
464  GCGSORTTPL_HASFIELD2PAR( GCGSORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
465  GCGSORTTPL_HASFIELD3PAR( GCGSORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
466  GCGSORTTPL_HASFIELD4PAR( GCGSORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
467  GCGSORTTPL_HASFIELD5PAR( GCGSORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
468  GCGSORTTPL_HASFIELD6PAR( GCGSORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
469  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
470  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
471  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
472  void* userdata, /** userdata that is supplied to the comparator function */
473  int len /**< length of arrays */
474  )
475 {
476  /* ignore the trivial cases */
477  if( len <= 1 )
478  return;
479 
480  /* use shell sort on the remaining small list */
481  if( len <= GCGSORTTPL_SHELLSORTMAX )
482  {
483  GCGSORTTPL_NAME(gcgsorttpl_shellSort, GCGSORTTPL_NAMEEXT)
484  (key,
485  GCGSORTTPL_HASFIELD1PAR(field1)
486  GCGSORTTPL_HASFIELD2PAR(field2)
487  GCGSORTTPL_HASFIELD3PAR(field3)
488  GCGSORTTPL_HASFIELD4PAR(field4)
489  GCGSORTTPL_HASFIELD5PAR(field5)
490  GCGSORTTPL_HASFIELD6PAR(field6)
491  GCGSORTTPL_HASPTRCOMPPAR(ptrcomp)
492  GCGSORTTPL_HASINDCOMPPAR(indcomp)
493  GCGSORTTPL_HASINDCOMPPAR(dataptr)
494  userdata, 0, len-1);
495  }
496  else
497  {
498  GCGSORTTPL_NAME(gcgsorttpl_qSort, GCGSORTTPL_NAMEEXT)
499  (key,
500  GCGSORTTPL_HASFIELD1PAR(field1)
501  GCGSORTTPL_HASFIELD2PAR(field2)
502  GCGSORTTPL_HASFIELD3PAR(field3)
503  GCGSORTTPL_HASFIELD4PAR(field4)
504  GCGSORTTPL_HASFIELD5PAR(field5)
505  GCGSORTTPL_HASFIELD6PAR(field6)
506  GCGSORTTPL_HASPTRCOMPPAR(ptrcomp)
507  GCGSORTTPL_HASINDCOMPPAR(indcomp)
508  GCGSORTTPL_HASINDCOMPPAR(dataptr)
509  userdata, 0, len-1, TRUE);
510  }
511 #ifndef NDEBUG
512  GCGSORTTPL_NAME(gcgsorttpl_checkSort, GCGSORTTPL_NAMEEXT)
513  (key,
514  GCGSORTTPL_HASPTRCOMPPAR(ptrcomp)
515  GCGSORTTPL_HASINDCOMPPAR(indcomp)
516  GCGSORTTPL_HASINDCOMPPAR(dataptr)
517  userdata,
518  len);
519 #endif
520 }
521 
522 #ifdef GCGSORTTPL_SORTED_VEC
523 /** SCIPsortedvecInsert...(): adds an element to a sorted multi-vector;
524  * This method does not do any memory allocation! It assumes that the arrays are large enough
525  * to store the additional values.
526  */
527 void GCGSORTTPL_NAME(GCGsortedvecInsert, GCGSORTTPL_NAMEEXT)
528 (
529  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
530  GCGSORTTPL_HASFIELD1PAR( GCGSORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
531  GCGSORTTPL_HASFIELD2PAR( GCGSORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
532  GCGSORTTPL_HASFIELD3PAR( GCGSORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
533  GCGSORTTPL_HASFIELD4PAR( GCGSORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
534  GCGSORTTPL_HASFIELD5PAR( GCGSORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
535  GCGSORTTPL_HASFIELD6PAR( GCGSORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
536  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
537  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
538  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
539  GCGSORTTPL_KEYTYPE keyval, /**< key value of new element */
540  GCGSORTTPL_HASFIELD1PAR( GCGSORTTPL_FIELD1TYPE field1val ) /**< field1 value of new element */
541  GCGSORTTPL_HASFIELD2PAR( GCGSORTTPL_FIELD2TYPE field2val ) /**< field1 value of new element */
542  GCGSORTTPL_HASFIELD3PAR( GCGSORTTPL_FIELD3TYPE field3val ) /**< field1 value of new element */
543  GCGSORTTPL_HASFIELD4PAR( GCGSORTTPL_FIELD4TYPE field4val ) /**< field1 value of new element */
544  GCGSORTTPL_HASFIELD5PAR( GCGSORTTPL_FIELD5TYPE field5val ) /**< field1 value of new element */
545  GCGSORTTPL_HASFIELD6PAR( GCGSORTTPL_FIELD6TYPE field6val ) /**< field1 value of new element */
546  void* userdata, /**< userdata that is supplied to the comparator function */
547  int* len, /**< pointer to length of arrays (will be increased by 1) */
548  int* pos /**< pointer to store the insert position, or NULL */
549  )
550 {
551  int j;
552 
553  for( j = *len; j > 0 && GCGSORTTPL_ISBETTER(keyval, key[j-1]); j-- )
554  {
555  key[j] = key[j-1];
556  GCGSORTTPL_HASFIELD1( field1[j] = field1[j-1]; )
557  GCGSORTTPL_HASFIELD2( field2[j] = field2[j-1]; )
558  GCGSORTTPL_HASFIELD3( field3[j] = field3[j-1]; )
559  GCGSORTTPL_HASFIELD4( field4[j] = field4[j-1]; )
560  GCGSORTTPL_HASFIELD5( field5[j] = field5[j-1]; )
561  GCGSORTTPL_HASFIELD6( field6[j] = field6[j-1]; )
562  }
563 
564  key[j] = keyval;
565  GCGSORTTPL_HASFIELD1( field1[j] = field1val; )
566  GCGSORTTPL_HASFIELD2( field2[j] = field2val; )
567  GCGSORTTPL_HASFIELD3( field3[j] = field3val; )
568  GCGSORTTPL_HASFIELD4( field4[j] = field4val; )
569  GCGSORTTPL_HASFIELD5( field5[j] = field5val; )
570  GCGSORTTPL_HASFIELD6( field6[j] = field6val; )
571 
572  (*len)++;
573 
574  if( pos != NULL )
575  (*pos) = j;
576 }
577 
578 /** SCIPsortedvecDelPos...(): deletes an element at a given position from a sorted multi-vector */
579 void GCGSORTTPL_NAME(GCGsortedvecDelPos, GCGSORTTPL_NAMEEXT)
580 (
581  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
582  GCGSORTTPL_HASFIELD1PAR( GCGSORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
583  GCGSORTTPL_HASFIELD2PAR( GCGSORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
584  GCGSORTTPL_HASFIELD3PAR( GCGSORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
585  GCGSORTTPL_HASFIELD4PAR( GCGSORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
586  GCGSORTTPL_HASFIELD5PAR( GCGSORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
587  GCGSORTTPL_HASFIELD6PAR( GCGSORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
588  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
589  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
590  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
591  void* userdata, /**< userdata that is supplied to the comparator function */
592  int pos, /**< array position of element to be deleted */
593  int* len /**< pointer to length of arrays (will be decreased by 1) */
594  )
595 {
596  int j;
597 
598  assert(0 <= pos && pos < *len);
599 
600  (*len)--;
601 
602  for( j = pos; j < *len; j++ )
603  {
604  key[j] = key[j+1];
605  GCGSORTTPL_HASFIELD1( field1[j] = field1[j+1]; )
606  GCGSORTTPL_HASFIELD2( field2[j] = field2[j+1]; )
607  GCGSORTTPL_HASFIELD3( field3[j] = field3[j+1]; )
608  GCGSORTTPL_HASFIELD4( field4[j] = field4[j+1]; )
609  GCGSORTTPL_HASFIELD5( field5[j] = field5[j+1]; )
610  GCGSORTTPL_HASFIELD6( field6[j] = field6[j+1]; )
611  }
612 }
613 
614 
615 /* The SCIPsortedvecFind...() method only has needs the key array but not the other field arrays. In order to
616  * avoid defining the same method multiple times, only include this method if we do not have any additional fields.
617  */
618 #ifndef GCGSORTTPL_FIELD1TYPE
619 
620 /** SCIPsortedvecFind...(): Finds the position at which 'val' is located in the sorted vector by binary search.
621  * If the element exists, the method returns TRUE and stores the position of the element in '*pos'.
622  * If the element does not exist, the method returns FALSE and stores the position of the element that follows
623  * 'val' in the ordering in '*pos', i.e., '*pos' is the position at which 'val' would be inserted.
624  * Note that if the element is not found, '*pos' may be equal to len if all existing elements are smaller than 'val'.
625  */
626 SCIP_Bool GCGSORTTPL_NAME(GCGsortedvecFind, GCGSORTTPL_NAMEEXT)
627 (
628  GCGSORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
629  GCGSORTTPL_HASPTRCOMPPAR( GCG_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
630  GCGSORTTPL_HASINDCOMPPAR( GCG_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
631  GCGSORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
632  GCGSORTTPL_KEYTYPE val, /**< data field to find position for */
633  void* userdata, /**< userdata that is supplied to the comparator function */
634  int len, /**< length of array */
635  int* pos /**< pointer to store the insert position */
636  )
637 {
638  int left;
639  int right;
640 
641  assert(key != NULL);
642  assert(pos != NULL);
643 
644  left = 0;
645  right = len-1;
646  while( left <= right )
647  {
648  int middle;
649 
650  middle = (left+right)/2;
651  assert(0 <= middle && middle < len);
652 
653  if( GCGSORTTPL_ISBETTER(val, key[middle]) )
654  right = middle-1;
655  else if( GCGSORTTPL_ISBETTER(key[middle], val) )
656  left = middle+1;
657  else
658  {
659  *pos = middle;
660  return TRUE;
661  }
662  }
663  assert(left == right+1);
664 
665  *pos = left;
666  return FALSE;
667 }
668 
669 #endif
670 #endif /* GCGSORTTPL_SORTED_VEC */
671 
672 /* undefine template parameters and local defines */
673 #undef GCGSORTTPL_NAMEEXT
674 #undef GCGSORTTPL_KEYTYPE
675 #undef GCGSORTTPL_FIELD1TYPE
676 #undef GCGSORTTPL_FIELD2TYPE
677 #undef GCGSORTTPL_FIELD3TYPE
678 #undef GCGSORTTPL_FIELD4TYPE
679 #undef GCGSORTTPL_FIELD5TYPE
680 #undef GCGSORTTPL_FIELD6TYPE
681 #undef GCGSORTTPL_PTRCOMP
682 #undef GCGSORTTPL_INDCOMP
683 #undef GCGSORTTPL_HASFIELD1
684 #undef GCGSORTTPL_HASFIELD2
685 #undef GCGSORTTPL_HASFIELD3
686 #undef GCGSORTTPL_HASFIELD4
687 #undef GCGSORTTPL_HASFIELD5
688 #undef GCGSORTTPL_HASFIELD6
689 #undef GCGSORTTPL_HASPTRCOMP
690 #undef GCGSORTTPL_HASINDCOMP
691 #undef GCGSORTTPL_HASFIELD1PAR
692 #undef GCGSORTTPL_HASFIELD2PAR
693 #undef GCGSORTTPL_HASFIELD3PAR
694 #undef GCGSORTTPL_HASFIELD4PAR
695 #undef GCGSORTTPL_HASFIELD5PAR
696 #undef GCGSORTTPL_HASFIELD6PAR
697 #undef GCGSORTTPL_HASPTRCOMPPAR
698 #undef GCGSORTTPL_HASINDCOMPPAR
699 #undef GCGSORTTPL_ISBETTER
700 #undef GCGSORTTPL_ISWORSE
701 #undef GCGSORTTPL_SWAP
702 #undef GCGSORTTPL_SHELLSORTMAX
703 #undef GCGSORTTPL_BACKWARDS
704 #undef GCGSORTTPL_SORTED_VEC
GCGSORTTPL_NAME
#define GCGSORTTPL_NAME(method, methodname)
Definition: gcgsorttpl.c:149
GCGSORTTPL_HASFIELD4
#define GCGSORTTPL_HASFIELD4(x)
Definition: gcgsorttpl.c:110
GCGSORTTPL_SHELLSORTMAX
#define GCGSORTTPL_SHELLSORTMAX
Definition: gcgsorttpl.c:68
GCGSORTTPL_HASFIELD6
#define GCGSORTTPL_HASFIELD6(x)
Definition: gcgsorttpl.c:124
GCG_DECL_SORTPTRCOMP
#define GCG_DECL_SORTPTRCOMP(x)
Definition: gcgsorttpl.c:65
GCGSORTTPL_HASFIELD1PAR
#define GCGSORTTPL_HASFIELD1PAR(x)
Definition: gcgsorttpl.c:90
GCGSORTTPL_NAMEEXT
#define GCGSORTTPL_NAMEEXT
Definition: gcgsort.c:41
GCGSORTTPL_ISBETTER
#define GCGSORTTPL_ISBETTER(x, y)
Definition: gcgsorttpl.c:175
GCGSORTTPL_HASPTRCOMPPAR
#define GCGSORTTPL_HASPTRCOMPPAR(x)
Definition: gcgsorttpl.c:132
GCGSORTTPL_HASFIELD3
#define GCGSORTTPL_HASFIELD3(x)
Definition: gcgsorttpl.c:103
GCGSORTTPL_FIELD1TYPE
#define GCGSORTTPL_FIELD1TYPE
Definition: gcgsort.c:43
GCGSORTTPL_SWAP
#define GCGSORTTPL_SWAP(T, x, y)
Definition: gcgsorttpl.c:182
GCGSORTTPL_HASFIELD6PAR
#define GCGSORTTPL_HASFIELD6PAR(x)
Definition: gcgsorttpl.c:125
GCGSORTTPL_HASFIELD4PAR
#define GCGSORTTPL_HASFIELD4PAR(x)
Definition: gcgsorttpl.c:111
GCGSORTTPL_HASINDCOMPPAR
#define GCGSORTTPL_HASINDCOMPPAR(x)
Definition: gcgsorttpl.c:139
GCGSORTTPL_HASFIELD5PAR
#define GCGSORTTPL_HASFIELD5PAR(x)
Definition: gcgsorttpl.c:118
GCGSORTTPL_HASFIELD3PAR
#define GCGSORTTPL_HASFIELD3PAR(x)
Definition: gcgsorttpl.c:104
GCGSORTTPL_HASFIELD2
#define GCGSORTTPL_HASFIELD2(x)
Definition: gcgsorttpl.c:96
GCGSORTTPL_KEYTYPE
#define GCGSORTTPL_KEYTYPE
Definition: gcgsort.c:42
GCGSORTTPL_ISWORSE
#define GCGSORTTPL_ISWORSE(x, y)
Definition: gcgsorttpl.c:176
GCG_DECL_SORTINDCOMP
#define GCG_DECL_SORTINDCOMP(x)
Definition: gcgsorttpl.c:57
GCGSORTTPL_HASFIELD5
#define GCGSORTTPL_HASFIELD5(x)
Definition: gcgsorttpl.c:117
GCGSORTTPL_HASFIELD2PAR
#define GCGSORTTPL_HASFIELD2PAR(x)
Definition: gcgsorttpl.c:97
GCGSORTTPL_HASFIELD1
#define GCGSORTTPL_HASFIELD1(x)
Definition: gcgsorttpl.c:89