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-2014 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 email to 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 
38 #define SORTTPL_SHELLSORTMAX 25
39 
40 #ifndef SORTTPL_NAMEEXT
41 #error You need to define SORTTPL_NAMEEXT.
42 #endif
43 #ifndef SORTTPL_KEYTYPE
44 #error You need to define SORTTPL_KEYTYPE.
45 #endif
46 
47 #ifdef SORTTPL_EXPANDNAME
48 #undef SORTTPL_EXPANDNAME
49 #endif
50 #ifdef SORTTPL_NAME
51 #undef SORTTPL_NAME
52 #endif
53 
54 /* enabling and disabling additional lines in the code */
55 #ifdef SORTTPL_FIELD1TYPE
56 #define SORTTPL_HASFIELD1(x) x
57 #define SORTTPL_HASFIELD1PAR(x) x,
58 #else
59 #define SORTTPL_HASFIELD1(x) /**/
60 #define SORTTPL_HASFIELD1PAR(x) /**/
61 #endif
62 #ifdef SORTTPL_FIELD2TYPE
63 #define SORTTPL_HASFIELD2(x) x
64 #define SORTTPL_HASFIELD2PAR(x) x,
65 #else
66 #define SORTTPL_HASFIELD2(x) /**/
67 #define SORTTPL_HASFIELD2PAR(x) /**/
68 #endif
69 #ifdef SORTTPL_FIELD3TYPE
70 #define SORTTPL_HASFIELD3(x) x
71 #define SORTTPL_HASFIELD3PAR(x) x,
72 #else
73 #define SORTTPL_HASFIELD3(x) /**/
74 #define SORTTPL_HASFIELD3PAR(x) /**/
75 #endif
76 #ifdef SORTTPL_FIELD4TYPE
77 #define SORTTPL_HASFIELD4(x) x
78 #define SORTTPL_HASFIELD4PAR(x) x,
79 #else
80 #define SORTTPL_HASFIELD4(x) /**/
81 #define SORTTPL_HASFIELD4PAR(x) /**/
82 #endif
83 #ifdef SORTTPL_FIELD5TYPE
84 #define SORTTPL_HASFIELD5(x) x
85 #define SORTTPL_HASFIELD5PAR(x) x,
86 #else
87 #define SORTTPL_HASFIELD5(x) /**/
88 #define SORTTPL_HASFIELD5PAR(x) /**/
89 #endif
90 #ifdef SORTTPL_FIELD6TYPE
91 #define SORTTPL_HASFIELD6(x) x
92 #define SORTTPL_HASFIELD6PAR(x) x,
93 #else
94 #define SORTTPL_HASFIELD6(x) /**/
95 #define SORTTPL_HASFIELD6PAR(x) /**/
96 #endif
97 #ifdef SORTTPL_PTRCOMP
98 #define SORTTPL_HASPTRCOMP(x) x
99 #define SORTTPL_HASPTRCOMPPAR(x) x,
100 #else
101 #define SORTTPL_HASPTRCOMP(x) /**/
102 #define SORTTPL_HASPTRCOMPPAR(x) /**/
103 #endif
104 #ifdef SORTTPL_INDCOMP
105 #define SORTTPL_HASINDCOMP(x) x
106 #define SORTTPL_HASINDCOMPPAR(x) x,
107 #else
108 #define SORTTPL_HASINDCOMP(x) /**/
109 #define SORTTPL_HASINDCOMPPAR(x) /**/
110 #endif
111 
112 
113 /* the two-step macro definition is needed, such that macro arguments
114  * get expanded by prescan of the C preprocessor (see "info cpp",
115  * chapter 3.10.6: Argument Prescan)
116  */
117 #define SORTTPL_EXPANDNAME(method, methodname) \
118  method ## methodname
119 #define SORTTPL_NAME(method, methodname) \
120  SORTTPL_EXPANDNAME(method, methodname)
121 
122 /* comparator method */
123 #ifdef SORTTPL_PTRCOMP
124 #ifdef SORTTPL_BACKWARDS
125 #define SORTTPL_ISBETTER(x,y) (ptrcomp((x), (y)) > 0)
126 #define SORTTPL_ISWORSE(x,y) (ptrcomp((x), (y)) < 0)
127 #else
128 #define SORTTPL_ISBETTER(x,y) (ptrcomp((x), (y)) < 0)
129 #define SORTTPL_ISWORSE(x,y) (ptrcomp((x), (y)) > 0)
130 #endif
131 #else
132 #ifdef SORTTPL_INDCOMP
133 #ifdef SORTTPL_BACKWARDS
134 #define SORTTPL_ISBETTER(x,y) (indcomp(dataptr, (x), (y)) > 0)
135 #define SORTTPL_ISWORSE(x,y) (indcomp(dataptr, (x), (y)) < 0)
136 #else
137 #define SORTTPL_ISBETTER(x,y) (indcomp(dataptr, (x), (y)) < 0)
138 #define SORTTPL_ISWORSE(x,y) (indcomp(dataptr, (x), (y)) > 0)
139 #endif
140 #else
141 #ifdef SORTTPL_BACKWARDS
142 #define SORTTPL_ISBETTER(x,y) ((x) > (y))
143 #define SORTTPL_ISWORSE(x,y) ((x) < (y))
144 #else
145 #define SORTTPL_ISBETTER(x,y) ((x) < (y))
146 #define SORTTPL_ISWORSE(x,y) ((x) > (y))
147 #endif
148 #endif
149 #endif
150 
151 /* swapping two variables */
152 #define SORTTPL_SWAP(T,x,y) \
153  { \
154  T temp = x; \
155  x = y; \
156  y = temp; \
157  }
158 
159 
160 /** shell-sort an array of data elements; use it only for arrays smaller than 25 entries */
161 static
162 void SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
163 (
164  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
165  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
166  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
167  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
168  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
169  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
170  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
171  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
172  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
173  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
174  int start, /**< starting index */
175  int end /**< ending index */
176  )
177 {
178  static const int incs[3] = {1, 5, 19}; /* sequence of increments */
179  int k;
180 
181  assert(start <= end);
182 
183  for( k = 2; k >= 0; --k )
184  {
185  int h = incs[k];
186  int first = h + start;
187  int i;
188 
189  for( i = first; i <= end; ++i )
190  {
191  int j;
192  SORTTPL_KEYTYPE tempkey = key[i];
193 
194  SORTTPL_HASFIELD1( SORTTPL_FIELD1TYPE tempfield1 = field1[i]; )
195  SORTTPL_HASFIELD2( SORTTPL_FIELD2TYPE tempfield2 = field2[i]; )
196  SORTTPL_HASFIELD3( SORTTPL_FIELD3TYPE tempfield3 = field3[i]; )
197  SORTTPL_HASFIELD4( SORTTPL_FIELD4TYPE tempfield4 = field4[i]; )
198  SORTTPL_HASFIELD5( SORTTPL_FIELD5TYPE tempfield5 = field5[i]; )
199  SORTTPL_HASFIELD6( SORTTPL_FIELD6TYPE tempfield6 = field6[i]; )
200 
201  j = i;
202  while( j >= first && SORTTPL_ISBETTER(tempkey, key[j-h]) )
203  {
204  key[j] = key[j-h];
205  SORTTPL_HASFIELD1( field1[j] = field1[j-h]; )
206  SORTTPL_HASFIELD2( field2[j] = field2[j-h]; )
207  SORTTPL_HASFIELD3( field3[j] = field3[j-h]; )
208  SORTTPL_HASFIELD4( field4[j] = field4[j-h]; )
209  SORTTPL_HASFIELD5( field5[j] = field5[j-h]; )
210  SORTTPL_HASFIELD6( field6[j] = field6[j-h]; )
211  j -= h;
212  }
213 
214  key[j] = tempkey;
215  SORTTPL_HASFIELD1( field1[j] = tempfield1; )
216  SORTTPL_HASFIELD2( field2[j] = tempfield2; )
217  SORTTPL_HASFIELD3( field3[j] = tempfield3; )
218  SORTTPL_HASFIELD4( field4[j] = tempfield4; )
219  SORTTPL_HASFIELD5( field5[j] = tempfield5; )
220  SORTTPL_HASFIELD6( field6[j] = tempfield6; )
221  }
222  }
223 }
224 
225 
226 /** quick-sort an array of pointers; pivot is the medial element */
227 static
228 void SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
229 (
230  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
231  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
232  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
233  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
234  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
235  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
236  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
237  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
238  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
239  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
240  int start, /**< starting index */
241  int end, /**< ending index */
242  SCIP_Bool type /**< TRUE, if quick-sort should start with with key[lo] < pivot <= key[hi], key[lo] <= pivot < key[hi] otherwise */
243  )
244 {
245  assert(start <= end);
246 
247  /* use quick-sort for long lists */
248  while( end - start >= SORTTPL_SHELLSORTMAX )
249  {
250  SORTTPL_KEYTYPE pivotkey;
251  int lo;
252  int hi;
253  int mid;
254 
255  /* select pivot element */
256  mid = (start+end)/2;
257  pivotkey = key[mid];
258 
259  /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */
260  lo = start;
261  hi = end;
262  for( ;; )
263  {
264  if( type )
265  {
266  while( lo < end && SORTTPL_ISBETTER(key[lo], pivotkey) )
267  lo++;
268  while( hi > start && !SORTTPL_ISBETTER(key[hi], pivotkey) )
269  hi--;
270  }
271  else
272  {
273  while( lo < end && !SORTTPL_ISWORSE(key[lo], pivotkey) )
274  lo++;
275  while( hi > start && SORTTPL_ISWORSE(key[hi], pivotkey) )
276  hi--;
277  }
278 
279  if( lo >= hi )
280  break;
281 
282  SORTTPL_SWAP(SORTTPL_KEYTYPE, key[lo], key[hi]);
283  SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[lo], field1[hi]); )
284  SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[lo], field2[hi]); )
285  SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[lo], field3[hi]); )
286  SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[lo], field4[hi]); )
287  SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[lo], field5[hi]); )
288  SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[lo], field6[hi]); )
289 
290  lo++;
291  hi--;
292  }
293  assert((hi == lo-1) || (type && hi == start) || (!type && lo == end));
294 
295  /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/
296  if( type )
297  {
298  while( lo < end && !SORTTPL_ISBETTER(pivotkey, key[lo]) )
299  lo++;
300 
301  /* make sure that we have at least one element in the smaller partition */
302  if( lo == start )
303  {
304  /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
305  assert(!SORTTPL_ISBETTER(key[mid], pivotkey)); /* the pivot element did not change its position */
306  assert(!SORTTPL_ISBETTER(pivotkey, key[mid]));
307  SORTTPL_SWAP(SORTTPL_KEYTYPE, key[lo], key[mid]);
308  SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[lo], field1[mid]); )
309  SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[lo], field2[mid]); )
310  SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[lo], field3[mid]); )
311  SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[lo], field4[mid]); )
312  SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[lo], field5[mid]); )
313  SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[lo], field6[mid]); )
314  lo++;
315  }
316  }
317  else
318  {
319  while( hi > start && !SORTTPL_ISWORSE(pivotkey, key[hi]) )
320  hi--;
321 
322  /* make sure that we have at least one element in the smaller partition */
323  if( hi == end )
324  {
325  /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
326  assert(!SORTTPL_ISBETTER(key[mid], pivotkey)); /* the pivot element did not change its position */
327  assert(!SORTTPL_ISBETTER(pivotkey, key[mid]));
328  SORTTPL_SWAP(SORTTPL_KEYTYPE, key[hi], key[mid]);
329  SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[hi], field1[mid]); )
330  SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[hi], field2[mid]); )
331  SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[hi], field3[mid]); )
332  SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[hi], field4[mid]); )
333  SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[hi], field5[mid]); )
334  SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[hi], field6[mid]); )
335  hi--;
336  }
337  }
338 
339  /* sort the smaller partition by a recursive call, sort the larger part without recursion */
340  if( hi - start <= end - lo )
341  {
342  /* sort [start,hi] with a recursive call */
343  if( start < hi )
344  {
345  SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
346  (key,
347  SORTTPL_HASFIELD1PAR(field1)
348  SORTTPL_HASFIELD2PAR(field2)
349  SORTTPL_HASFIELD3PAR(field3)
350  SORTTPL_HASFIELD4PAR(field4)
351  SORTTPL_HASFIELD5PAR(field5)
352  SORTTPL_HASFIELD6PAR(field6)
353  SORTTPL_HASPTRCOMPPAR(ptrcomp)
354  SORTTPL_HASINDCOMPPAR(indcomp)
355  SORTTPL_HASINDCOMPPAR(dataptr)
356  start, hi, !type);
357  }
358 
359  /* now focus on the larger part [lo,end] */
360  start = lo;
361  }
362  else
363  {
364  if( lo < end )
365  {
366  /* sort [lo,end] with a recursive call */
367  SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
368  (key,
369  SORTTPL_HASFIELD1PAR(field1)
370  SORTTPL_HASFIELD2PAR(field2)
371  SORTTPL_HASFIELD3PAR(field3)
372  SORTTPL_HASFIELD4PAR(field4)
373  SORTTPL_HASFIELD5PAR(field5)
374  SORTTPL_HASFIELD6PAR(field6)
375  SORTTPL_HASPTRCOMPPAR(ptrcomp)
376  SORTTPL_HASINDCOMPPAR(indcomp)
377  SORTTPL_HASINDCOMPPAR(dataptr)
378  lo, end, !type);
379  }
380 
381  /* now focus on the larger part [start,hi] */
382  end = hi;
383  }
384  type = !type;
385  }
386 
387  /* use shell sort on the remaining small list */
388  if( end - start >= 1 )
389  {
390  SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
391  (key,
392  SORTTPL_HASFIELD1PAR(field1)
393  SORTTPL_HASFIELD2PAR(field2)
394  SORTTPL_HASFIELD3PAR(field3)
395  SORTTPL_HASFIELD4PAR(field4)
396  SORTTPL_HASFIELD5PAR(field5)
397  SORTTPL_HASFIELD6PAR(field6)
398  SORTTPL_HASPTRCOMPPAR(ptrcomp)
399  SORTTPL_HASINDCOMPPAR(indcomp)
400  SORTTPL_HASINDCOMPPAR(dataptr)
401  start, end);
402  }
403 }
404 
405 #ifndef NDEBUG
406 /** verifies that an array is indeed sorted */
407 static
408 void SORTTPL_NAME(sorttpl_checkSort, SORTTPL_NAMEEXT)
409 (
410  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
411  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
412  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
413  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
414  int len /**< length of the array */
415  )
416 {
417  int i;
418 
419  for( i = 0; i < len-1; i++ )
420  {
421  assert(!SORTTPL_ISBETTER(key[i+1], key[i]));
422  }
423 }
424 #endif
425 
426 /** SCIPsort...(): sorts array 'key' and performs the same permutations on the additional 'field' arrays */
427 void SORTTPL_NAME(SCIPsort, SORTTPL_NAMEEXT)
428 (
429  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
430  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
431  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
432  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
433  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
434  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
435  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
436  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
437  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
438  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
439  int len /**< length of arrays */
440  )
441 {
442  /* ignore the trivial cases */
443  if( len <= 1 )
444  return;
445 
446  /* use shell sort on the remaining small list */
447  if( len <= SORTTPL_SHELLSORTMAX )
448  {
449  SORTTPL_NAME(sorttpl_shellSort, SORTTPL_NAMEEXT)
450  (key,
451  SORTTPL_HASFIELD1PAR(field1)
452  SORTTPL_HASFIELD2PAR(field2)
453  SORTTPL_HASFIELD3PAR(field3)
454  SORTTPL_HASFIELD4PAR(field4)
455  SORTTPL_HASFIELD5PAR(field5)
456  SORTTPL_HASFIELD6PAR(field6)
457  SORTTPL_HASPTRCOMPPAR(ptrcomp)
458  SORTTPL_HASINDCOMPPAR(indcomp)
459  SORTTPL_HASINDCOMPPAR(dataptr)
460  0, len-1);
461  }
462  else
463  {
464  SORTTPL_NAME(sorttpl_qSort, SORTTPL_NAMEEXT)
465  (key,
466  SORTTPL_HASFIELD1PAR(field1)
467  SORTTPL_HASFIELD2PAR(field2)
468  SORTTPL_HASFIELD3PAR(field3)
469  SORTTPL_HASFIELD4PAR(field4)
470  SORTTPL_HASFIELD5PAR(field5)
471  SORTTPL_HASFIELD6PAR(field6)
472  SORTTPL_HASPTRCOMPPAR(ptrcomp)
473  SORTTPL_HASINDCOMPPAR(indcomp)
474  SORTTPL_HASINDCOMPPAR(dataptr)
475  0, len-1, TRUE);
476  }
477 #ifndef NDEBUG
478  SORTTPL_NAME(sorttpl_checkSort, SORTTPL_NAMEEXT)
479  (key,
480  SORTTPL_HASPTRCOMPPAR(ptrcomp)
481  SORTTPL_HASINDCOMPPAR(indcomp)
482  SORTTPL_HASINDCOMPPAR(dataptr)
483  len);
484 #endif
485 }
486 
487 
488 /** SCIPsortedvecInsert...(): adds an element to a sorted multi-vector;
489  * This method does not do any memory allocation! It assumes that the arrays are large enough
490  * to store the additional values.
491  */
492 void SORTTPL_NAME(SCIPsortedvecInsert, SORTTPL_NAMEEXT)
493 (
494  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
495  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
496  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
497  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
498  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
499  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
500  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
501  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
502  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
503  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
504  SORTTPL_KEYTYPE keyval, /**< key value of new element */
505  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE field1val ) /**< field1 value of new element */
506  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE field2val ) /**< field1 value of new element */
507  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE field3val ) /**< field1 value of new element */
508  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE field4val ) /**< field1 value of new element */
509  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE field5val ) /**< field1 value of new element */
510  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE field6val ) /**< field1 value of new element */
511  int* len, /**< pointer to length of arrays (will be increased by 1) */
512  int* pos /**< pointer to store the insert position, or NULL */
513  )
514 {
515  int j;
516 
517  for( j = *len; j > 0 && SORTTPL_ISBETTER(keyval, key[j-1]); j-- )
518  {
519  key[j] = key[j-1];
520  SORTTPL_HASFIELD1( field1[j] = field1[j-1]; )
521  SORTTPL_HASFIELD2( field2[j] = field2[j-1]; )
522  SORTTPL_HASFIELD3( field3[j] = field3[j-1]; )
523  SORTTPL_HASFIELD4( field4[j] = field4[j-1]; )
524  SORTTPL_HASFIELD5( field5[j] = field5[j-1]; )
525  SORTTPL_HASFIELD6( field6[j] = field6[j-1]; )
526  }
527 
528  key[j] = keyval;
529  SORTTPL_HASFIELD1( field1[j] = field1val; )
530  SORTTPL_HASFIELD2( field2[j] = field2val; )
531  SORTTPL_HASFIELD3( field3[j] = field3val; )
532  SORTTPL_HASFIELD4( field4[j] = field4val; )
533  SORTTPL_HASFIELD5( field5[j] = field5val; )
534  SORTTPL_HASFIELD6( field6[j] = field6val; )
535 
536  (*len)++;
537 
538  if( pos != NULL )
539  (*pos) = j;
540 }
541 
542 /** SCIPsortedvecDelPos...(): deletes an element at a given position from a sorted multi-vector */
543 void SORTTPL_NAME(SCIPsortedvecDelPos, SORTTPL_NAMEEXT)
544 (
545  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
546  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /**< additional field that should be sorted in the same way */
547  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /**< additional field that should be sorted in the same way */
548  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /**< additional field that should be sorted in the same way */
549  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /**< additional field that should be sorted in the same way */
550  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /**< additional field that should be sorted in the same way */
551  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /**< additional field that should be sorted in the same way */
552  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
553  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
554  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
555  int pos, /**< array position of element to be deleted */
556  int* len /**< pointer to length of arrays (will be decreased by 1) */
557  )
558 {
559  int j;
560 
561  assert(0 <= pos && pos < *len);
562 
563  (*len)--;
564 
565  for( j = pos; j < *len; j++ )
566  {
567  key[j] = key[j+1];
568  SORTTPL_HASFIELD1( field1[j] = field1[j+1]; )
569  SORTTPL_HASFIELD2( field2[j] = field2[j+1]; )
570  SORTTPL_HASFIELD3( field3[j] = field3[j+1]; )
571  SORTTPL_HASFIELD4( field4[j] = field4[j+1]; )
572  SORTTPL_HASFIELD5( field5[j] = field5[j+1]; )
573  SORTTPL_HASFIELD6( field6[j] = field6[j+1]; )
574  }
575 }
576 
577 
578 /* The SCIPsortedvecFind...() method only has needs the key array but not the other field arrays. In order to
579  * avoid defining the same method multiple times, only include this method if we do not have any additional fields.
580  */
581 #ifndef SORTTPL_FIELD1TYPE
582 
583 /** SCIPsortedvecFind...(): Finds the position at which 'val' is located in the sorted vector by binary search.
584  * If the element exists, the method returns TRUE and stores the position of the element in '*pos'.
585  * If the element does not exist, the method returns FALSE and stores the position of the element that follows
586  * 'val' in the ordering in '*pos', i.e., '*pos' is the position at which 'val' would be inserted.
587  * Note that if the element is not found, '*pos' may be equal to len if all existing elements are smaller than 'val'.
588  */
589 SCIP_Bool SORTTPL_NAME(SCIPsortedvecFind, SORTTPL_NAMEEXT)
590 (
591  SORTTPL_KEYTYPE* key, /**< pointer to data array that defines the order */
592  SORTTPL_HASPTRCOMPPAR( SCIP_DECL_SORTPTRCOMP((*ptrcomp)) ) /**< data element comparator */
593  SORTTPL_HASINDCOMPPAR( SCIP_DECL_SORTINDCOMP((*indcomp)) ) /**< data element comparator */
594  SORTTPL_HASINDCOMPPAR( void* dataptr ) /**< pointer to data field that is given to the external compare method */
595  SORTTPL_KEYTYPE val, /**< data field to find position for */
596  int len, /**< length of array */
597  int* pos /**< pointer to store the insert position */
598  )
599 {
600  int left;
601  int right;
602 
603  assert(key != NULL);
604  assert(pos != NULL);
605 
606  left = 0;
607  right = len-1;
608  while( left <= right )
609  {
610  int middle;
611 
612  middle = (left+right)/2;
613  assert(0 <= middle && middle < len);
614 
615  if( SORTTPL_ISBETTER(val, key[middle]) )
616  right = middle-1;
617  else if( SORTTPL_ISBETTER(key[middle], val) )
618  left = middle+1;
619  else
620  {
621  *pos = middle;
622  return TRUE;
623  }
624  }
625  assert(left == right+1);
626 
627  *pos = left;
628  return FALSE;
629 }
630 
631 #endif
632 
633 
634 /* undefine template parameters and local defines */
635 #undef SORTTPL_NAMEEXT
636 #undef SORTTPL_KEYTYPE
637 #undef SORTTPL_FIELD1TYPE
638 #undef SORTTPL_FIELD2TYPE
639 #undef SORTTPL_FIELD3TYPE
640 #undef SORTTPL_FIELD4TYPE
641 #undef SORTTPL_FIELD5TYPE
642 #undef SORTTPL_FIELD6TYPE
643 #undef SORTTPL_PTRCOMP
644 #undef SORTTPL_INDCOMP
645 #undef SORTTPL_HASFIELD1
646 #undef SORTTPL_HASFIELD2
647 #undef SORTTPL_HASFIELD3
648 #undef SORTTPL_HASFIELD4
649 #undef SORTTPL_HASFIELD5
650 #undef SORTTPL_HASFIELD6
651 #undef SORTTPL_HASPTRCOMP
652 #undef SORTTPL_HASINDCOMP
653 #undef SORTTPL_HASFIELD1PAR
654 #undef SORTTPL_HASFIELD2PAR
655 #undef SORTTPL_HASFIELD3PAR
656 #undef SORTTPL_HASFIELD4PAR
657 #undef SORTTPL_HASFIELD5PAR
658 #undef SORTTPL_HASFIELD6PAR
659 #undef SORTTPL_HASPTRCOMPPAR
660 #undef SORTTPL_HASINDCOMPPAR
661 #undef SORTTPL_ISBETTER
662 #undef SORTTPL_ISWORSE
663 #undef SORTTPL_SWAP
664 #undef SORTTPL_SHELLSORTMAX
665 #undef SORTTPL_BACKWARDS
666