SCIP-SDP  4.0.0
sorttpllex.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of SCIPSDP - a solving framework for mixed-integer */
4 /* semidefinite programs based on SCIP. */
5 /* */
6 /* Copyright (C) 2011-2013 Discrete Optimization, TU Darmstadt */
7 /* EDOM, FAU Erlangen-Nürnberg */
8 /* 2014-2021 Discrete Optimization, TU Darmstadt */
9 /* */
10 /* */
11 /* This program is free software; you can redistribute it and/or */
12 /* modify it under the terms of the GNU Lesser General Public License */
13 /* as published by the Free Software Foundation; either version 3 */
14 /* of the License, or (at your option) any later version. */
15 /* */
16 /* This program is distributed in the hope that it will be useful, */
17 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
18 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
19 /* GNU Lesser General Public License for more details. */
20 /* */
21 /* You should have received a copy of the GNU Lesser General Public License */
22 /* along with this program; if not, write to the Free Software */
23 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
24 /* */
25 /* */
26 /* Based on SCIP - Solving Constraint Integer Programs */
27 /* Copyright (C) 2002-2021 Zuse Institute Berlin */
28 /* SCIP is distributed under the terms of the SCIP Academic Licence, */
29 /* see file COPYING in the SCIP distribution. */
30 /* */
31 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
32 
39 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40 
41 #include "scip/def.h"
42 
43 #define SORTTPL_SHELLSORTMAX 25 /* maximal size for shell sort */
44 #define SORTTPL_MINSIZENINTHER 729 /* minimum input size to use ninther (median of nine) for pivot selection */
45 
46 #ifndef SORTTPL_NAMEEXT
47 #error You need to define SORTTPL_NAMEEXT.
48 #endif
49 #ifndef SORTTPL_KEYTYPE
50 #error You need to define SORTTPL_KEYTYPE.
51 #endif
52 
53 #ifdef SORTTPL_EXPANDNAME
54 #undef SORTTPL_EXPANDNAME
55 #endif
56 #ifdef SORTTPL_NAME
57 #undef SORTTPL_NAME
58 #endif
59 
60 /* enabling and disabling additional lines in the code */
61 #ifdef SORTTPL_FIELD1TYPE
62 #define SORTTPL_HASFIELD1(x) x
63 #define SORTTPL_HASFIELD1PAR(x) x,
64 #else
65 #define SORTTPL_HASFIELD1(x)
66 #define SORTTPL_HASFIELD1PAR(x)
67 #endif
68 #ifdef SORTTPL_FIELD2TYPE
69 #define SORTTPL_HASFIELD2(x) x
70 #define SORTTPL_HASFIELD2PAR(x) x,
71 #else
72 #define SORTTPL_HASFIELD2(x)
73 #define SORTTPL_HASFIELD2PAR(x)
74 #endif
75 #ifdef SORTTPL_FIELD3TYPE
76 #define SORTTPL_HASFIELD3(x) x
77 #define SORTTPL_HASFIELD3PAR(x) x,
78 #else
79 #define SORTTPL_HASFIELD3(x)
80 #define SORTTPL_HASFIELD3PAR(x)
81 #endif
82 #ifdef SORTTPL_FIELD4TYPE
83 #define SORTTPL_HASFIELD4(x) x
84 #define SORTTPL_HASFIELD4PAR(x) x,
85 #else
86 #define SORTTPL_HASFIELD4(x)
87 #define SORTTPL_HASFIELD4PAR(x)
88 #endif
89 #ifdef SORTTPL_FIELD5TYPE
90 #define SORTTPL_HASFIELD5(x) x
91 #define SORTTPL_HASFIELD5PAR(x) x,
92 #else
93 #define SORTTPL_HASFIELD5(x)
94 #define SORTTPL_HASFIELD5PAR(x)
95 #endif
96 #ifdef SORTTPL_FIELD6TYPE
97 #define SORTTPL_HASFIELD6(x) x
98 #define SORTTPL_HASFIELD6PAR(x) x,
99 #else
100 #define SORTTPL_HASFIELD6(x)
101 #define SORTTPL_HASFIELD6PAR(x)
102 #endif
103 
104 /* the two-step macro definition is needed, such that macro arguments
105  * get expanded by prescan of the C preprocessor (see "info cpp",
106  * chapter 3.10.6: Argument Prescan)
107  */
108 #define SORTTPL_EXPANDNAME(method, methodname) \
109  method ## methodname
110 #define SORTTPL_NAME(method, methodname) \
111  SORTTPL_EXPANDNAME(method, methodname)
112 
114 static
115 int SORTTPL_CMP(
116  SORTTPL_KEYTYPE x1,
117  SORTTPL_KEYTYPE x2,
118  SORTTPL_KEYTYPE y1,
119  SORTTPL_KEYTYPE y2
120  )
121 {
122  if ( x1 < y1 )
123  return -1;
124 
125  if ( x1 > y1 )
126  return 1;
127  assert( x1 == y1 );
128 
129  if ( x2 < y2 )
130  return -1;
131 
132  if ( x2 > y2 )
133  return 1;
134 
135  return 0;
136 }
137 
138 
139 #ifdef SORTTPL_BACKWARDS
140 #define SORTTPL_ISLEXBETTER(x1,x2,y1,y2) (SORTTPL_CMP(x1,x2,y1,y2) > 0)
141 #define SORTTPL_ISLEXWORSE(x1,x2,y1,y2) (SORTTPL_CMP(x1,x2,y1,y2) < 0)
142 #else
143 #define SORTTPL_ISLEXBETTER(x1,x2,y1,y2) (SORTTPL_CMP(x1,x2,y1,y2) < 0)
144 #define SORTTPL_ISLEXWORSE(x1,x2,y1,y2) (SORTTPL_CMP(x1,x2,y1,y2) > 0)
145 #endif
146 
147 /* swapping two variables */
148 #define SORTTPL_SWAP(T,x,y) \
149  { \
150  T temp = x; \
151  x = y; \
152  y = temp; \
153  }
154 
155 
157 static
158 void SORTTPL_NAME(sorttpl_lexShellSort, SORTTPL_NAMEEXT)
159 (
160  SORTTPL_KEYTYPE* key1,
161  SORTTPL_KEYTYPE* key2,
162  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /*lint !e665*/
163  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /*lint !e665*/
164  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /*lint !e665*/
165  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /*lint !e665*/
166  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /*lint !e665*/
167  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /*lint !e665*/
168  int start,
169  int end
170  )
171 {
172  static const int incs[3] = {1, 5, 19}; /* sequence of increments */
173  int k;
174 
175  assert( key1 != NULL );
176  assert( key2 != NULL );
177  assert( start <= end );
178 
179  for (k = 2; k >= 0; --k)
180  {
181  int h = incs[k];
182  int first = h + start;
183  int i;
184 
185  for (i = first; i <= end; ++i)
186  {
187  int j;
188  SORTTPL_KEYTYPE tempkey1 = key1[i];
189  SORTTPL_KEYTYPE tempkey2 = key2[i];
190 
191  SORTTPL_HASFIELD1( SORTTPL_FIELD1TYPE tempfield1 = field1[i]; )
192  SORTTPL_HASFIELD2( SORTTPL_FIELD2TYPE tempfield2 = field2[i]; )
193  SORTTPL_HASFIELD3( SORTTPL_FIELD3TYPE tempfield3 = field3[i]; )
194  SORTTPL_HASFIELD4( SORTTPL_FIELD4TYPE tempfield4 = field4[i]; )
195  SORTTPL_HASFIELD5( SORTTPL_FIELD5TYPE tempfield5 = field5[i]; )
196  SORTTPL_HASFIELD6( SORTTPL_FIELD6TYPE tempfield6 = field6[i]; )
197 
198  j = i;
199  while (j >= first && SORTTPL_ISLEXBETTER(tempkey1, tempkey2, key1[j-h], key2[j-h]))
200  {
201  key1[j] = key1[j-h];
202  key2[j] = key2[j-h];
203 
204  SORTTPL_HASFIELD1( field1[j] = field1[j-h]; )
205  SORTTPL_HASFIELD2( field2[j] = field2[j-h]; )
206  SORTTPL_HASFIELD3( field3[j] = field3[j-h]; )
207  SORTTPL_HASFIELD4( field4[j] = field4[j-h]; )
208  SORTTPL_HASFIELD5( field5[j] = field5[j-h]; )
209  SORTTPL_HASFIELD6( field6[j] = field6[j-h]; )
210  j -= h;
211  }
212 
213  key1[j] = tempkey1;
214  key2[j] = tempkey2;
215 
216  SORTTPL_HASFIELD1( field1[j] = tempfield1; )
217  SORTTPL_HASFIELD2( field2[j] = tempfield2; )
218  SORTTPL_HASFIELD3( field3[j] = tempfield3; )
219  SORTTPL_HASFIELD4( field4[j] = tempfield4; )
220  SORTTPL_HASFIELD5( field5[j] = tempfield5; )
221  SORTTPL_HASFIELD6( field6[j] = tempfield6; )
222  }
223  }
224 }
225 
227 static
228 int SORTTPL_NAME(sorttpl_lexMedianThree, SORTTPL_NAMEEXT)
229 (
230  SORTTPL_KEYTYPE* key1,
231  SORTTPL_KEYTYPE* key2,
232  int a,
233  int b,
234  int c
235  )
236 {
237  assert( a >= 0 );
238  assert( b >= 0 );
239  assert( c >= 0 );
240  assert( a != b );
241  assert( b != c );
242  assert( c != a );
243 
244  /* let the elements in the unsorted order be a, b, c at positions start, mid, and end */
245  if ( SORTTPL_ISLEXBETTER(key1[a], key2[a], key1[b], key2[b]) ) /* a <= b */
246  {
247  if ( SORTTPL_ISLEXBETTER(key1[b], key2[b], key1[c], key2[c]) ) /* b <= c */
248  /* resulting permutation: a b c */
249  return b;
250  else /* b > c */
251  {
252  if ( SORTTPL_ISLEXBETTER(key1[a], key2[a], key1[c], key2[c]) ) /* a <= c */
253  /* resulting permutation: a c b */
254  return c;
255  else
256  /* resulting permutation: c a b */
257  return a;
258  }
259  }
260  else /* a > b */
261  {
262  if ( SORTTPL_ISLEXBETTER(key1[b], key2[b], key1[c], key2[c]) )
263  {
264  if ( SORTTPL_ISLEXBETTER(key1[a], key2[a], key1[c], key2[c]) )
265  /* resulting permutation: b a c */
266  return a;
267  else
268  /* resulting permutation: b c a */
269  return c;
270  }
271  else
272  /* resulting permutation: c b a */
273  return b;
274  }
275 }
276 
278 static
279 int SORTTPL_NAME(sorttpl_lexSelectPivotIndex, SORTTPL_NAMEEXT)
280 (
281  SORTTPL_KEYTYPE* key1,
282  SORTTPL_KEYTYPE* key2,
283  int start,
284  int end
285  )
286 {
287  int pivotindex;
288 
289  /* use the middle index on small arrays */
290  if ( end - start + 1 <= SORTTPL_SHELLSORTMAX )
291  pivotindex = (start + end) / 2;
292  else if ( end - start + 1 < SORTTPL_MINSIZENINTHER )
293  {
294  /* select the median of the first, last, and middle element as pivot element */
295  int mid = (start + end) / 2;
296  pivotindex = SORTTPL_NAME(sorttpl_lexMedianThree, SORTTPL_NAMEEXT)(key1, key2, start, mid, end);
297  }
298  else
299  {
300  /* use the median of medians of nine evenly distributed elements of the key array */
301  int gap = (end - start + 1) / 9;
302  int median1;
303  int median2;
304  int median3;
305 
306  /* this should always hold */
307  assert( start + 8 * gap <= end );
308 
309  /* collect 3 medians evenly distributed over the array */
310  median1 = SORTTPL_NAME(sorttpl_lexMedianThree, SORTTPL_NAMEEXT)(key1, key2, start, start + gap, start + 2 * gap);
311 
312  median2 = SORTTPL_NAME(sorttpl_lexMedianThree, SORTTPL_NAMEEXT)(key1, key2, start + 3 * gap, start + 4 * gap, start + 5 * gap);
313  median3 = SORTTPL_NAME(sorttpl_lexMedianThree, SORTTPL_NAMEEXT)(key1, key2, start + 6 * gap, start + 7 * gap, start + 8 * gap);
314 
315  /* compute and return the median of the medians */
316  pivotindex = SORTTPL_NAME(sorttpl_lexMedianThree, SORTTPL_NAMEEXT)(key1, key2, median1, median2, median3);
317  }
318 
319  return pivotindex;
320 }
321 
323 static
324 void SORTTPL_NAME(sorttpl_lexQSort, SORTTPL_NAMEEXT)
325 (
326  SORTTPL_KEYTYPE* key1,
327  SORTTPL_KEYTYPE* key2,
328  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /*lint !e665*/
329  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /*lint !e665*/
330  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /*lint !e665*/
331  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /*lint !e665*/
332  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /*lint !e665*/
333  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /*lint !e665*/
334  int start,
335  int end,
336  SCIP_Bool type
337  )
338 {
339  assert( start <= end );
340 
341  /* use quick-sort for long lists */
342  while ( end - start >= SORTTPL_SHELLSORTMAX )
343  {
344  SORTTPL_KEYTYPE pivotkey1;
345  SORTTPL_KEYTYPE pivotkey2;
346  int lo;
347  int hi;
348  int mid;
349 
350  /* select pivot element */
351  mid = SORTTPL_NAME(sorttpl_lexSelectPivotIndex, SORTTPL_NAMEEXT)(key1, key2, start, end);
352  pivotkey1 = key1[mid];
353  pivotkey2 = key2[mid];
354 
355  /* partition the array into elements < pivot [start,hi] and elements >= pivot [lo,end] */
356  lo = start;
357  hi = end;
358  for ( ;; )
359  {
360  if ( type )
361  {
362  while ( lo < end && SORTTPL_ISLEXBETTER(key1[lo], key2[lo], pivotkey1, pivotkey2) )
363  lo++;
364  while ( hi > start && ! SORTTPL_ISLEXBETTER(key1[hi], key2[hi], pivotkey1, pivotkey2) )
365  hi--;
366  }
367  else
368  {
369  while ( lo < end && ! SORTTPL_ISLEXWORSE(key1[lo], key2[lo], pivotkey1, pivotkey2) )
370  lo++;
371  while ( hi > start && SORTTPL_ISLEXWORSE(key1[hi], key2[hi], pivotkey1, pivotkey2) )
372  hi--;
373  }
374 
375  if ( lo >= hi )
376  break;
377 
378  SORTTPL_SWAP(SORTTPL_KEYTYPE, key1[lo], key1[hi]);
379  SORTTPL_SWAP(SORTTPL_KEYTYPE, key2[lo], key2[hi]);
380  SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[lo], field1[hi]); )
381  SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[lo], field2[hi]); )
382  SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[lo], field3[hi]); )
383  SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[lo], field4[hi]); )
384  SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[lo], field5[hi]); )
385  SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[lo], field6[hi]); )
386 
387  lo++;
388  hi--;
389  }
390  assert( (hi == lo-1) || (type && hi == start) || (!type && lo == end) );
391 
392  /* skip entries which are equal to the pivot element (three partitions, <, =, > than pivot)*/
393  if ( type )
394  {
395  while ( lo < end && ! SORTTPL_ISLEXBETTER(pivotkey1, pivotkey2, key1[lo], key2[lo]) )
396  lo++;
397 
398  /* make sure that we have at least one element in the smaller partition */
399  if ( lo == start )
400  {
401  /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
402  assert( ! SORTTPL_ISLEXBETTER(key1[mid], key2[mid], pivotkey1, pivotkey2) ); /* the pivot element did not change its position */
403  assert( ! SORTTPL_ISLEXBETTER(pivotkey1, pivotkey2, key1[mid], key2[mid]) );
404  SORTTPL_SWAP(SORTTPL_KEYTYPE, key1[lo], key1[mid]);
405  SORTTPL_SWAP(SORTTPL_KEYTYPE, key2[lo], key2[mid]);
406  SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[lo], field1[mid]); )
407  SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[lo], field2[mid]); )
408  SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[lo], field3[mid]); )
409  SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[lo], field4[mid]); )
410  SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[lo], field5[mid]); )
411  SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[lo], field6[mid]); )
412  lo++;
413  }
414  }
415  else
416  {
417  while ( hi > start && ! SORTTPL_ISLEXWORSE(pivotkey1, pivotkey2, key1[hi], key2[hi]) )
418  hi--;
419 
420  /* make sure that we have at least one element in the smaller partition */
421  if ( hi == end )
422  {
423  /* everything is greater or equal than the pivot element: move pivot to the left (degenerate case) */
424  assert( ! SORTTPL_ISLEXBETTER(key1[mid], key2[mid], pivotkey1, pivotkey2) ); /* the pivot element did not change its position */
425  assert( ! SORTTPL_ISLEXBETTER(pivotkey1, pivotkey2, key1[mid], key2[mid]) );
426  SORTTPL_SWAP(SORTTPL_KEYTYPE, key1[hi], key1[mid]);
427  SORTTPL_SWAP(SORTTPL_KEYTYPE, key2[hi], key2[mid]);
428  SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[hi], field1[mid]); )
429  SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[hi], field2[mid]); )
430  SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[hi], field3[mid]); )
431  SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[hi], field4[mid]); )
432  SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[hi], field5[mid]); )
433  SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[hi], field6[mid]); )
434  hi--;
435  }
436  }
437 
438  /* sort the smaller partition by a recursive call, sort the larger part without recursion */
439  if ( hi - start <= end - lo )
440  {
441  /* sort [start,hi] with a recursive call */
442  if ( start < hi )
443  {
444  SORTTPL_NAME(sorttpl_lexQSort, SORTTPL_NAMEEXT)
445  (key1, key2,
446  SORTTPL_HASFIELD1PAR(field1)
447  SORTTPL_HASFIELD2PAR(field2)
448  SORTTPL_HASFIELD3PAR(field3)
449  SORTTPL_HASFIELD4PAR(field4)
450  SORTTPL_HASFIELD5PAR(field5)
451  SORTTPL_HASFIELD6PAR(field6)
452  start, hi, !type);
453  }
454 
455  /* now focus on the larger part [lo,end] */
456  start = lo;
457  }
458  else
459  {
460  if( lo < end )
461  {
462  /* sort [lo,end] with a recursive call */
463  SORTTPL_NAME(sorttpl_lexQSort, SORTTPL_NAMEEXT)
464  (key1, key2,
465  SORTTPL_HASFIELD1PAR(field1)
466  SORTTPL_HASFIELD2PAR(field2)
467  SORTTPL_HASFIELD3PAR(field3)
468  SORTTPL_HASFIELD4PAR(field4)
469  SORTTPL_HASFIELD5PAR(field5)
470  SORTTPL_HASFIELD6PAR(field6)
471  lo, end, !type);
472  }
473 
474  /* now focus on the larger part [start,hi] */
475  end = hi;
476  }
477  type = !type;
478  }
479 
480  /* use shell sort on the remaining small list */
481  if ( end - start >= 1 )
482  {
483  SORTTPL_NAME(sorttpl_lexShellSort, SORTTPL_NAMEEXT)
484  (key1, key2,
485  SORTTPL_HASFIELD1PAR(field1)
486  SORTTPL_HASFIELD2PAR(field2)
487  SORTTPL_HASFIELD3PAR(field3)
488  SORTTPL_HASFIELD4PAR(field4)
489  SORTTPL_HASFIELD5PAR(field5)
490  SORTTPL_HASFIELD6PAR(field6)
491  start, end);
492  }
493 }
494 
495 #ifndef NDEBUG
496 
497 static
498 void SORTTPL_NAME(sorttpl_lexCheckSort, SORTTPL_NAMEEXT)
499 (
500  SORTTPL_KEYTYPE* key1,
501  SORTTPL_KEYTYPE* key2,
502  int len
503  )
504 {
505  int i;
506 
507  for ( i = 0; i < len-1; i++ )
508  {
509  assert( ! SORTTPL_ISLEXBETTER(key1[i+1], key2[i+1], key1[i], key2[i]) );
510  }
511 }
512 #endif
513 
515 static
516 void SORTTPL_NAME(SCIPlexSort, SORTTPL_NAMEEXT)
517 (
518  SORTTPL_KEYTYPE* key1,
519  SORTTPL_KEYTYPE* key2,
520  SORTTPL_HASFIELD1PAR( SORTTPL_FIELD1TYPE* field1 ) /*lint !e665*/
521  SORTTPL_HASFIELD2PAR( SORTTPL_FIELD2TYPE* field2 ) /*lint !e665*/
522  SORTTPL_HASFIELD3PAR( SORTTPL_FIELD3TYPE* field3 ) /*lint !e665*/
523  SORTTPL_HASFIELD4PAR( SORTTPL_FIELD4TYPE* field4 ) /*lint !e665*/
524  SORTTPL_HASFIELD5PAR( SORTTPL_FIELD5TYPE* field5 ) /*lint !e665*/
525  SORTTPL_HASFIELD6PAR( SORTTPL_FIELD6TYPE* field6 ) /*lint !e665*/
526  int len
527  )
528 {
529  /* ignore the trivial cases */
530  if ( len <= 1 )
531  return;
532 
533  /* use shell sort on the remaining small list */
534  if ( len <= SORTTPL_SHELLSORTMAX )
535  {
536  SORTTPL_NAME(sorttpl_lexShellSort, SORTTPL_NAMEEXT)
537  (key1, key2,
538  SORTTPL_HASFIELD1PAR(field1)
539  SORTTPL_HASFIELD2PAR(field2)
540  SORTTPL_HASFIELD3PAR(field3)
541  SORTTPL_HASFIELD4PAR(field4)
542  SORTTPL_HASFIELD5PAR(field5)
543  SORTTPL_HASFIELD6PAR(field6)
544  0, len-1);
545  }
546  else
547  {
548  SORTTPL_NAME(sorttpl_lexQSort, SORTTPL_NAMEEXT)
549  (key1, key2,
550  SORTTPL_HASFIELD1PAR(field1)
551  SORTTPL_HASFIELD2PAR(field2)
552  SORTTPL_HASFIELD3PAR(field3)
553  SORTTPL_HASFIELD4PAR(field4)
554  SORTTPL_HASFIELD5PAR(field5)
555  SORTTPL_HASFIELD6PAR(field6)
556  0, len-1, TRUE);
557  }
558 #ifndef NDEBUG
559  SORTTPL_NAME(sorttpl_lexCheckSort, SORTTPL_NAMEEXT)(key1, key2, len);
560 #endif
561 }
562 
563 /* undefine template parameters and local defines */
564 #undef SORTTPL_NAMEEXT
565 #undef SORTTPL_KEYTYPE
566 #undef SORTTPL_FIELD1TYPE
567 #undef SORTTPL_FIELD2TYPE
568 #undef SORTTPL_FIELD3TYPE
569 #undef SORTTPL_FIELD4TYPE
570 #undef SORTTPL_FIELD5TYPE
571 #undef SORTTPL_FIELD6TYPE
572 #undef SORTTPL_HASFIELD1
573 #undef SORTTPL_HASFIELD2
574 #undef SORTTPL_HASFIELD3
575 #undef SORTTPL_HASFIELD4
576 #undef SORTTPL_HASFIELD5
577 #undef SORTTPL_HASFIELD6
578 #undef SORTTPL_HASFIELD1PAR
579 #undef SORTTPL_HASFIELD2PAR
580 #undef SORTTPL_HASFIELD3PAR
581 #undef SORTTPL_HASFIELD4PAR
582 #undef SORTTPL_HASFIELD5PAR
583 #undef SORTTPL_HASFIELD6PAR
584 #undef SORTTPL_ISLEXBETTER
585 #undef SORTTPL_ISLEXWORSE
586 #undef SORTTPL_CMP
587 #undef SORTTPL_SWAP
588 #undef SORTTPL_SHELLSORTMAX
589 #undef SORTTPL_MINSIZENINTHER
SORTTPL_HASFIELD3
#define SORTTPL_HASFIELD3(x)
Definition: sorttpllex.c:79
SORTTPL_CMP
static int SORTTPL_CMP(SORTTPL_KEYTYPE x1, SORTTPL_KEYTYPE x2, SORTTPL_KEYTYPE y1, SORTTPL_KEYTYPE y2)
Definition: sorttpllex.c:115
SORTTPL_HASFIELD4
#define SORTTPL_HASFIELD4(x)
Definition: sorttpllex.c:86
SORTTPL_HASFIELD3PAR
#define SORTTPL_HASFIELD3PAR(x)
Definition: sorttpllex.c:80
SORTTPL_SHELLSORTMAX
#define SORTTPL_SHELLSORTMAX
Definition: sorttpllex.c:43
SORTTPL_HASFIELD6PAR
#define SORTTPL_HASFIELD6PAR(x)
Definition: sorttpllex.c:101
SORTTPL_HASFIELD5
#define SORTTPL_HASFIELD5(x)
Definition: sorttpllex.c:93
SORTTPL_HASFIELD2PAR
#define SORTTPL_HASFIELD2PAR(x)
Definition: sorttpllex.c:73
SORTTPL_HASFIELD4PAR
#define SORTTPL_HASFIELD4PAR(x)
Definition: sorttpllex.c:87
SORTTPL_HASFIELD5PAR
#define SORTTPL_HASFIELD5PAR(x)
Definition: sorttpllex.c:94
SORTTPL_ISLEXBETTER
#define SORTTPL_ISLEXBETTER(x1, x2, y1, y2)
Definition: sorttpllex.c:143
SORTTPL_HASFIELD1PAR
#define SORTTPL_HASFIELD1PAR(x)
Definition: sorttpllex.c:66
SORTTPL_NAME
#define SORTTPL_NAME(method, methodname)
Definition: sorttpllex.c:110
SORTTPL_HASFIELD6
#define SORTTPL_HASFIELD6(x)
Definition: sorttpllex.c:100
SORTTPL_HASFIELD2
#define SORTTPL_HASFIELD2(x)
Definition: sorttpllex.c:72
SORTTPL_ISLEXWORSE
#define SORTTPL_ISLEXWORSE(x1, x2, y1, y2)
Definition: sorttpllex.c:144
SORTTPL_HASFIELD1
#define SORTTPL_HASFIELD1(x)
Definition: sorttpllex.c:65
SORTTPL_SWAP
#define SORTTPL_SWAP(T, x, y)
Definition: sorttpllex.c:148
SORTTPL_KEYTYPE
#define SORTTPL_KEYTYPE
Definition: SdpVarfixer.c:49
SORTTPL_MINSIZENINTHER
#define SORTTPL_MINSIZENINTHER
Definition: sorttpllex.c:44
SORTTPL_FIELD1TYPE
#define SORTTPL_FIELD1TYPE
Definition: SdpVarfixer.c:50
SORTTPL_NAMEEXT
#define SORTTPL_NAMEEXT
Definition: SdpVarfixer.c:48
Generated by   doxygen 1.8.11