50#define SORTTPL_SHELLSORTMAX 25
51#define SORTTPL_MINSIZENINTHER 729
53#ifndef SORTTPL_NAMEEXT
54#error You need to define SORTTPL_NAMEEXT.
56#ifndef SORTTPL_KEYTYPE
57#error You need to define SORTTPL_KEYTYPE.
60#ifdef SORTTPL_EXPANDNAME
61#undef SORTTPL_EXPANDNAME
68#ifdef SORTTPL_FIELD1TYPE
69#define SORTTPL_HASFIELD1(x) x
70#define SORTTPL_HASFIELD1PAR(x) x,
72#define SORTTPL_HASFIELD1(x)
73#define SORTTPL_HASFIELD1PAR(x)
75#ifdef SORTTPL_FIELD2TYPE
76#define SORTTPL_HASFIELD2(x) x
77#define SORTTPL_HASFIELD2PAR(x) x,
79#define SORTTPL_HASFIELD2(x)
80#define SORTTPL_HASFIELD2PAR(x)
82#ifdef SORTTPL_FIELD3TYPE
83#define SORTTPL_HASFIELD3(x) x
84#define SORTTPL_HASFIELD3PAR(x) x,
86#define SORTTPL_HASFIELD3(x)
87#define SORTTPL_HASFIELD3PAR(x)
89#ifdef SORTTPL_FIELD4TYPE
90#define SORTTPL_HASFIELD4(x) x
91#define SORTTPL_HASFIELD4PAR(x) x,
93#define SORTTPL_HASFIELD4(x)
94#define SORTTPL_HASFIELD4PAR(x)
96#ifdef SORTTPL_FIELD5TYPE
97#define SORTTPL_HASFIELD5(x) x
98#define SORTTPL_HASFIELD5PAR(x) x,
100#define SORTTPL_HASFIELD5(x)
101#define SORTTPL_HASFIELD5PAR(x)
103#ifdef SORTTPL_FIELD6TYPE
104#define SORTTPL_HASFIELD6(x) x
105#define SORTTPL_HASFIELD6PAR(x) x,
107#define SORTTPL_HASFIELD6(x)
108#define SORTTPL_HASFIELD6PAR(x)
110#ifdef SORTTPL_PTRCOMP
111#define SORTTPL_HASPTRCOMP(x) x
112#define SORTTPL_HASPTRCOMPPAR(x) x,
114#define SORTTPL_HASPTRCOMP(x)
115#define SORTTPL_HASPTRCOMPPAR(x)
117#ifdef SORTTPL_INDCOMP
118#define SORTTPL_HASINDCOMP(x) x
119#define SORTTPL_HASINDCOMPPAR(x) x,
121#define SORTTPL_HASINDCOMP(x)
122#define SORTTPL_HASINDCOMPPAR(x)
130#define SORTTPL_EXPANDNAME(method, methodname) \
132#define SORTTPL_NAME(method, methodname) \
133 SORTTPL_EXPANDNAME(method, methodname)
136#ifdef SORTTPL_PTRCOMP
137#ifdef SORTTPL_BACKWARDS
138#define SORTTPL_CMP(x,y) (-ptrcomp((x), (y)))
140#define SORTTPL_CMP(x,y) (ptrcomp((x), (y)))
143#ifdef SORTTPL_INDCOMP
144#ifdef SORTTPL_BACKWARDS
145#define SORTTPL_CMP(x,y) (-indcomp(dataptr, (x), (y)))
147#define SORTTPL_CMP(x,y) (indcomp(dataptr, (x), (y)))
150#ifdef SORTTPL_BACKWARDS
151#define SORTTPL_CMP(x,y) ((y) - (x))
153#define SORTTPL_CMP(x,y) ((x) - (y))
158#define SORTTPL_ISBETTER(x,y) (SORTTPL_CMP(x,y) < 0)
159#define SORTTPL_ISWORSE(x,y) (SORTTPL_CMP(x,y) > 0)
162#define SORTTPL_SWAP(T,x,y) \
189 static const int incs[3] = {1, 5, 19};
194 for( k = 2; k >= 0; --k )
197 int first =
h + start;
200 for(
i = first;
i <= end; ++
i )
219 if( weights !=
NULL )
220 weights[j] = weights[j -
h];
233 if( weights !=
NULL )
234 weights[j] = tmpweight;
315 pivotindex = (start + end) / 2;
319 int mid = (start + end) / 2;
330 int gap = (end - start + 1) / 9;
336 assert(start + 8 * gap <= end);
344 start, start + gap, start + 2 * gap);
351 start + 3 * gap, start + 4 * gap, start + 5 * gap);
357 start + 6 * gap, start + 7 * gap, start + 8 * gap);
365 median1, median2, median3);
444 assert((hi == lo-1) || (type && hi == start) || (!type && lo == end));
491 if( hi - start <= end - lo )
539 if( end - start >= 1 )
570 for(
i = 0;
i < len-1;
i++ )
713 assert(0 <= pos && pos < *len);
717 for( j = pos; j < *len; j++ )
733#ifndef SORTTPL_FIELD1TYPE
760 while( left <= right )
764 middle = (left+right)/2;
765 assert(0 <= middle && middle < len);
791 SORTTPL_SWAP(SORTTPL_KEYTYPE, key[x], key[y]); \
793 if( weights != NULL ) \
794 SORTTPL_SWAP(SCIP_Real, weights[x], weights[y]); \
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]); ) \
824 for(
i = 0;
i < len;
i++ )
826 if ( weights !=
NULL )
840 else if(
i < medianpos )
881 int localmedianpos = -1;
887 residualcapacity = capacity;
890 if( weights !=
NULL )
892 for( j = 0; j < len; ++j )
893 totalweightsum += weights[j];
896 totalweightsum = len;
898 if( totalweightsum <= capacity )
900 localmedianpos = len;
924 pivot = key[pivotindex];
927 if( pivotindex != lo )
929 EXCH(lo, pivotindex);
968 if( weights !=
NULL )
971 betterweightsum = 0.0;
972 for(
i = lo;
i < bt; ++
i )
975 betterweightsum += weights[
i];
981 betterweightsum = bt - lo;
985 if( betterweightsum > residualcapacity )
994 for( p = bt; p <= wt; ++p )
997 pivotweight = weights !=
NULL ? weights[p] : 1.0;
998 weightsum += pivotweight;
1001 if( weightsum > residualcapacity )
1005 goto CHECKANDRETURN;
1010 residualcapacity -= weightsum;
1018 if( hi - lo + 1 > 1 )
1041 for( j = lo; j <=
MAX(lo, hi); ++j )
1046 if( weight > residualcapacity )
1053 residualcapacity -= weight;
1071 if( medianpos !=
NULL )
1072 *medianpos = localmedianpos;
1098 if( k < 0 || k >= len )
1118 NULL, capacity, len, &pos);
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
1156#undef SORTTPL_SHELLSORTMAX
1157#undef SORTTPL_MINSIZENINTHER
1158#undef SORTTPL_BACKWARDS
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
#define SCIPquadprecSumQD(r, a, b)
#define QUAD_ASSIGN(a, constant)
common defines and data types used in all packages of SCIP
#define SCIP_DEFAULT_EPSILON
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
assert(minobj< SCIPgetCutoffbound(scip))
#define SORTTPL_FIELD1TYPE
#define SORTTPL_FIELD3TYPE
#define SORTTPL_FIELD5TYPE
#define SORTTPL_FIELD4TYPE
#define SORTTPL_FIELD2TYPE
#define SORTTPL_HASFIELD1PAR(x)
#define SORTTPL_HASPTRCOMPPAR(x)
#define SORTTPL_SHELLSORTMAX
#define SORTTPL_HASFIELD6(x)
#define SORTTPL_HASFIELD3PAR(x)
#define SORTTPL_MINSIZENINTHER
#define SORTTPL_HASFIELD5PAR(x)
#define SORTTPL_HASFIELD2(x)
#define SORTTPL_HASINDCOMPPAR(x)
#define SORTTPL_ISBETTER(x, y)
#define SORTTPL_HASFIELD6PAR(x)
#define SORTTPL_NAME(method, methodname)
#define SORTTPL_CMP(x, y)
#define SORTTPL_HASFIELD3(x)
#define SORTTPL_HASFIELD2PAR(x)
#define SORTTPL_ISWORSE(x, y)
#define SORTTPL_HASFIELD5(x)
#define SORTTPL_HASFIELD4PAR(x)
#define SORTTPL_HASFIELD4(x)
#define SORTTPL_HASFIELD1(x)
#define SORTTPL_SWAP(T, x, y)
#define SCIP_DECL_SORTPTRCOMP(x)
#define SCIP_DECL_SORTINDCOMP(x)