38 #define SORTTPL_SHELLSORTMAX 25 39 #define SORTTPL_MINSIZENINTHER 729 41 #ifndef SORTTPL_NAMEEXT 42 #error You need to define SORTTPL_NAMEEXT. 44 #ifndef SORTTPL_KEYTYPE 45 #error You need to define SORTTPL_KEYTYPE. 48 #ifdef SORTTPL_EXPANDNAME 49 #undef SORTTPL_EXPANDNAME 56 #ifdef SORTTPL_FIELD1TYPE 57 #define SORTTPL_HASFIELD1(x) x 58 #define SORTTPL_HASFIELD1PAR(x) x, 60 #define SORTTPL_HASFIELD1(x) 61 #define SORTTPL_HASFIELD1PAR(x) 63 #ifdef SORTTPL_FIELD2TYPE 64 #define SORTTPL_HASFIELD2(x) x 65 #define SORTTPL_HASFIELD2PAR(x) x, 67 #define SORTTPL_HASFIELD2(x) 68 #define SORTTPL_HASFIELD2PAR(x) 70 #ifdef SORTTPL_FIELD3TYPE 71 #define SORTTPL_HASFIELD3(x) x 72 #define SORTTPL_HASFIELD3PAR(x) x, 74 #define SORTTPL_HASFIELD3(x) 75 #define SORTTPL_HASFIELD3PAR(x) 77 #ifdef SORTTPL_FIELD4TYPE 78 #define SORTTPL_HASFIELD4(x) x 79 #define SORTTPL_HASFIELD4PAR(x) x, 81 #define SORTTPL_HASFIELD4(x) 82 #define SORTTPL_HASFIELD4PAR(x) 84 #ifdef SORTTPL_FIELD5TYPE 85 #define SORTTPL_HASFIELD5(x) x 86 #define SORTTPL_HASFIELD5PAR(x) x, 88 #define SORTTPL_HASFIELD5(x) 89 #define SORTTPL_HASFIELD5PAR(x) 91 #ifdef SORTTPL_FIELD6TYPE 92 #define SORTTPL_HASFIELD6(x) x 93 #define SORTTPL_HASFIELD6PAR(x) x, 95 #define SORTTPL_HASFIELD6(x) 96 #define SORTTPL_HASFIELD6PAR(x) 98 #ifdef SORTTPL_PTRCOMP 99 #define SORTTPL_HASPTRCOMP(x) x 100 #define SORTTPL_HASPTRCOMPPAR(x) x, 102 #define SORTTPL_HASPTRCOMP(x) 103 #define SORTTPL_HASPTRCOMPPAR(x) 105 #ifdef SORTTPL_INDCOMP 106 #define SORTTPL_HASINDCOMP(x) x 107 #define SORTTPL_HASINDCOMPPAR(x) x, 109 #define SORTTPL_HASINDCOMP(x) 110 #define SORTTPL_HASINDCOMPPAR(x) 118 #define SORTTPL_EXPANDNAME(method, methodname) \ 120 #define SORTTPL_NAME(method, methodname) \ 121 SORTTPL_EXPANDNAME(method, methodname) 124 #ifdef SORTTPL_PTRCOMP 125 #ifdef SORTTPL_BACKWARDS 126 #define SORTTPL_CMP(x,y) (-ptrcomp((x), (y))) 128 #define SORTTPL_CMP(x,y) (ptrcomp((x), (y))) 131 #ifdef SORTTPL_INDCOMP 132 #ifdef SORTTPL_BACKWARDS 133 #define SORTTPL_CMP(x,y) (-indcomp(dataptr, (x), (y))) 135 #define SORTTPL_CMP(x,y) (indcomp(dataptr, (x), (y))) 138 #ifdef SORTTPL_BACKWARDS 139 #define SORTTPL_CMP(x,y) ((y) - (x)) 141 #define SORTTPL_CMP(x,y) ((x) - (y)) 146 #define SORTTPL_ISBETTER(x,y) (SORTTPL_CMP(x,y) < 0) 147 #define SORTTPL_ISWORSE(x,y) (SORTTPL_CMP(x,y) > 0) 150 #define SORTTPL_SWAP(T,x,y) \ 177 static const int incs[3] = {1, 5, 19};
180 assert(start <= end);
182 for( k = 2; k >= 0; --k )
185 int first = h + start;
188 for( i = first; i <= end; ++i )
193 SCIP_Real tmpweight = weights != NULL ? weights[i] : 1;
207 if( weights != NULL )
208 weights[j] = weights[j - h];
221 if( weights != NULL )
222 weights[j] = tmpweight;
301 pivotindex = (start + end) / 2;
305 int mid = (start + end) / 2;
316 int gap = (end - start + 1) / 9;
322 assert(start + 8 * gap <= end);
330 start, start + gap, start + 2 * gap);
337 start + 3 * gap, start + 4 * gap, start + 5 * gap);
343 start + 6 * gap, start + 7 * gap, start + 8 * gap);
351 median1, median2, median3);
377 assert(start <= end);
430 assert((hi == lo-1) || (type && hi == start) || (!type && lo == end));
477 if( hi - start <= end - lo )
525 if( end - start >= 1 )
556 for( i = 0; i < len-1; i++ )
698 assert(0 <= pos && pos < *len);
702 for( j = pos; j < *len; j++ )
745 while( left <= right )
749 middle = (left+right)/2;
750 assert(0 <= middle && middle < len);
762 assert(left == right+1);
776 SORTTPL_SWAP(SORTTPL_KEYTYPE, key[x], key[y]); \ 778 if( weights != NULL ) \ 779 SORTTPL_SWAP(SCIP_Real, weights[x], weights[y]); \ 781 SORTTPL_HASFIELD1( SORTTPL_SWAP(SORTTPL_FIELD1TYPE, field1[x], field1[y]); ) \ 782 SORTTPL_HASFIELD2( SORTTPL_SWAP(SORTTPL_FIELD2TYPE, field2[x], field2[y]); ) \ 783 SORTTPL_HASFIELD3( SORTTPL_SWAP(SORTTPL_FIELD3TYPE, field3[x], field3[y]); ) \ 784 SORTTPL_HASFIELD4( SORTTPL_SWAP(SORTTPL_FIELD4TYPE, field4[x], field4[y]); ) \ 785 SORTTPL_HASFIELD5( SORTTPL_SWAP(SORTTPL_FIELD5TYPE, field5[x], field5[y]); ) \ 786 SORTTPL_HASFIELD6( SORTTPL_SWAP(SORTTPL_FIELD6TYPE, field6[x], field6[y]); ) \ 821 residualcapacity = capacity;
845 pivot = key[pivotindex];
848 if( pivotindex != lo )
850 EXCH(lo, pivotindex);
889 if( weights != NULL )
891 betterweightsum = 0.0;
893 for( i = lo; i < bt; ++i )
896 betterweightsum += weights[i];
902 betterweightsum = bt - lo;
906 if( betterweightsum >= residualcapacity )
914 for( p = bt; p <= wt; ++p )
917 pivotweight = weights != NULL ? weights[p] : 1;
918 weightsum += pivotweight;
921 if( weightsum >= residualcapacity )
923 if( medianpos != NULL )
931 residualcapacity -= weightsum;
939 if( hi - lo + 1 > 1 )
955 for( j = lo; j <=
MAX(lo, hi); ++j )
957 SCIP_Real weight = (weights != NULL ? weights[j] : 1);
959 if( weight >= residualcapacity )
961 if( medianpos != NULL )
967 residualcapacity -= weight;
971 if( j == len && medianpos != NULL )
973 assert(residualcapacity > 0);
999 if( k < 0 || k >= len )
1019 NULL, capacity, len, &pos);
1026 #undef SORTTPL_NAMEEXT 1027 #undef SORTTPL_KEYTYPE 1028 #undef SORTTPL_FIELD1TYPE 1029 #undef SORTTPL_FIELD2TYPE 1030 #undef SORTTPL_FIELD3TYPE 1031 #undef SORTTPL_FIELD4TYPE 1032 #undef SORTTPL_FIELD5TYPE 1033 #undef SORTTPL_FIELD6TYPE 1034 #undef SORTTPL_PTRCOMP 1035 #undef SORTTPL_INDCOMP 1036 #undef SORTTPL_HASFIELD1 1037 #undef SORTTPL_HASFIELD2 1038 #undef SORTTPL_HASFIELD3 1039 #undef SORTTPL_HASFIELD4 1040 #undef SORTTPL_HASFIELD5 1041 #undef SORTTPL_HASFIELD6 1042 #undef SORTTPL_HASPTRCOMP 1043 #undef SORTTPL_HASINDCOMP 1044 #undef SORTTPL_HASFIELD1PAR 1045 #undef SORTTPL_HASFIELD2PAR 1046 #undef SORTTPL_HASFIELD3PAR 1047 #undef SORTTPL_HASFIELD4PAR 1048 #undef SORTTPL_HASFIELD5PAR 1049 #undef SORTTPL_HASFIELD6PAR 1050 #undef SORTTPL_HASPTRCOMPPAR 1051 #undef SORTTPL_HASINDCOMPPAR 1052 #undef SORTTPL_ISBETTER 1053 #undef SORTTPL_ISWORSE 1057 #undef SORTTPL_SHELLSORTMAX 1058 #undef SORTTPL_MINSIZENINTHER 1059 #undef SORTTPL_BACKWARDS
#define SORTTPL_CMP(x, y)
#define SORTTPL_HASFIELD4PAR(x)
#define SORTTPL_NAME(method, methodname)
#define SORTTPL_HASFIELD4(x)
#define SORTTPL_FIELD5TYPE
#define SORTTPL_SHELLSORTMAX
#define SORTTPL_HASFIELD6PAR(x)
#define SORTTPL_MINSIZENINTHER
#define SORTTPL_SWAP(T, x, y)
#define SORTTPL_HASINDCOMPPAR(x)
#define SORTTPL_FIELD3TYPE
#define SORTTPL_ISWORSE(x, y)
#define SORTTPL_FIELD4TYPE
#define SORTTPL_HASFIELD3PAR(x)
#define SORTTPL_HASFIELD5PAR(x)
#define SORTTPL_HASFIELD2(x)
#define SORTTPL_HASFIELD1PAR(x)
#define SORTTPL_HASFIELD6(x)
#define SCIP_DECL_SORTINDCOMP(x)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
#define SCIP_DECL_SORTPTRCOMP(x)
#define SORTTPL_HASPTRCOMPPAR(x)
#define SORTTPL_FIELD1TYPE
#define SORTTPL_HASFIELD5(x)
#define SORTTPL_HASFIELD1(x)
#define SORTTPL_FIELD2TYPE
common defines and data types used in all packages of SCIP
#define SORTTPL_HASFIELD3(x)
#define SORTTPL_ISBETTER(x, y)
#define SORTTPL_HASFIELD2PAR(x)