20 #ifndef COIN_USE_EKK_SORT
21 #define COIN_USE_EKK_SORT
29 template <
class S,
class T >
52 template <
class S,
class T >
65 template <
class S,
class T >
78 template <
class S,
class T >
93 template <
class S,
class T >
101 return t1Abs > t2Abs;
110 template <
class S,
class T,
class V >
135 template <
class S,
class T,
class V >
165 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
166 template <
class Iter_S,
class Iter_T,
class CoinCompare2 >
167 void CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst,
const CoinCompare2 &pc)
169 typedef typename std::iterator_traits< Iter_S >::value_type S;
170 typedef typename std::iterator_traits< Iter_T >::value_type T;
176 ST_pair *x =
static_cast< ST_pair *
>(::operator
new(len *
sizeof(ST_pair)));
178 memset(x, 0, (len *
sizeof(ST_pair)));
182 Iter_S scurrent = sfirst;
183 Iter_T tcurrent = tfirst;
184 while (scurrent != slast) {
185 new (x + i++) ST_pair(*scurrent++, *tcurrent++);
188 std::sort(x.begin(), x.end(), pc);
192 for (i = 0; i < len; ++i) {
193 *scurrent++ = x[i].first;
194 *tcurrent++ = x[i].second;
197 ::operator
delete(x);
200 template <
class Iter_S,
class Iter_T >
201 void CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
203 typedef typename std::iterator_traits< Iter_S >::value_type S;
204 typedef typename std::iterator_traits< Iter_T >::value_type T;
208 #else //=======================================================================
210 template <
class S,
class T,
class CoinCompare2 >
211 void CoinSort_2(S *sfirst, S *slast, T *tfirst,
const CoinCompare2 &pc)
218 ST_pair *x =
static_cast< ST_pair *
>(::operator
new(len *
sizeof(ST_pair)));
222 memset(x, 0, (len *
sizeof(ST_pair)));
226 S *scurrent = sfirst;
227 T *tcurrent = tfirst;
228 while (scurrent != slast) {
229 new (x + i++) ST_pair(*scurrent++, *tcurrent++);
232 std::sort(x, x + len, pc);
236 for (i = 0; i < len; ++i) {
237 *scurrent++ = x[i].first;
238 *tcurrent++ = x[i].second;
241 ::operator
delete(x);
243 template <
class S,
class T >
250 #ifndef COIN_USE_EKK_SORT
252 template <
class S,
class T >
259 extern int boundary_sort;
260 extern int boundary_sort2;
261 extern int boundary_sort3;
263 template <
class S,
class T >
264 void CoinSort_2(S *key, S *lastKey, T *array2)
269 }
else if (number > 10000) {
274 if (number==boundary_sort3) {
275 printf(
"before sort %d entries\n",number);
276 for (
int j=0;j<number;j++) {
277 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
279 std::cout<<std::endl;
283 int n =
static_cast< int >(number);
293 for (j = 1; j < n; j++) {
294 if (key[j] >= last) {
305 rs[sp] = v + (n - 1);
307 if (rs[sp] - ls[sp] > minsize) {
316 array2[l - v] = array2[m - v];
324 array2[m - v] = array2[r - v];
331 array2[l - v] = array2[m - v];
345 array2[l - v] = array2[r - v];
362 for (l = v, m = v + (n - 1); l < m; l++) {
365 it = array2[(l - v) + 1];
366 for (r = l; r >= v && *r > c; r--) {
368 array2[(r - v) + 1] = array2[(r - v)];
371 array2[(r - v) + 1] = it;
375 if (number==boundary_sort3) {
376 printf(
"after sort %d entries\n",number);
377 for (
int j=0;j<number;j++) {
378 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
380 std::cout<<std::endl;
381 CoinSort_2Many(key, lastKey, array2);
382 printf(
"after2 sort %d entries\n",number);
383 for (
int j=0;j<number;j++) {
384 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
386 std::cout<<std::endl;
392 template <
class S,
class T >
398 if (number == 2 && key[0] > key[1]) {
402 array2[0] = array2[1];
407 }
else if (number > 10000) {
422 for (j = 1; j < n; j++) {
423 if (key[j] >= last) {
434 rs[sp] = v + (n - 1);
436 if (rs[sp] - ls[sp] > minsize) {
445 array2[l - v] = array2[m - v];
453 array2[m - v] = array2[r - v];
460 array2[l - v] = array2[m - v];
474 array2[l - v] = array2[r - v];
491 for (l = v, m = v + (n - 1); l < m; l++) {
494 it = array2[(l - v) + 1];
495 for (r = l; r >= v && *r > c; r--) {
497 array2[(r - v) + 1] = array2[(r - v)];
500 array2[(r - v) + 1] = it;
508 template <
class S,
class T,
class U >
533 template <
class S,
class T,
class U >
546 template <
class S,
class T,
class U >
559 template <
class S,
class T,
class U >
568 return t1Abs < t2Abs;
574 template <
class S,
class T,
class U >
583 return t1Abs > t2Abs;
592 template <
class S,
class T,
class U,
class V >
617 template <
class S,
class T,
class U,
class V >
660 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
661 template <
class Iter_S,
class Iter_T,
class Iter_U,
class CoinCompare3 >
662 void CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
663 const CoinCompare3 &tc)
665 typedef typename std::iterator_traits< Iter_S >::value_type S;
666 typedef typename std::iterator_traits< Iter_T >::value_type T;
667 typedef typename std::iterator_traits< Iter_U >::value_type U;
673 STU_triple *x =
static_cast< STU_triple *
>(::operator
new(len *
sizeof(STU_triple)));
676 Iter_S scurrent = sfirst;
677 Iter_T tcurrent = tfirst;
678 Iter_U ucurrent = ufirst;
679 while (scurrent != slast) {
680 new (x + i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
683 std::sort(x, x + len, tc);
688 for (i = 0; i < len; ++i) {
689 *scurrent++ = x[i].first;
690 *tcurrent++ = x[i].second;
691 *ucurrent++ = x[i].third;
694 ::operator
delete(x);
697 template <
class Iter_S,
class Iter_T,
class Iter_U >
698 void CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
700 typedef typename std::iterator_traits< Iter_S >::value_type S;
701 typedef typename std::iterator_traits< Iter_T >::value_type T;
702 typedef typename std::iterator_traits< Iter_U >::value_type U;
706 #else //=======================================================================
708 template <
class S,
class T,
class U,
class CoinCompare3 >
709 void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst,
const CoinCompare3 &tc)
716 STU_triple *x =
static_cast< STU_triple *
>(::operator
new(len *
sizeof(STU_triple)));
719 S *scurrent = sfirst;
720 T *tcurrent = tfirst;
721 U *ucurrent = ufirst;
722 while (scurrent != slast) {
723 new (x + i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
726 std::sort(x, x + len, tc);
731 for (i = 0; i < len; ++i) {
732 *scurrent++ = x[i].first;
733 *tcurrent++ = x[i].second;
734 *ucurrent++ = x[i].third;
737 ::operator
delete(x);
740 template <
class S,
class T,
class U >
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
CoinPair(const S &s, const T &t)
Construct from ordered pair.
CoinExternalVectorFirstGreater_3(const V *v)
CoinExternalVectorFirstLess_2(const V *v)
S first
First member of pair.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
void CoinShortSort_2(S *key, S *lastKey, T *array2)
Sort without new and delete.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
void coinDistance(ForwardIterator first, ForwardIterator last, Distance &n)
CoinDistance.
T second
Second member of pair.
CoinExternalVectorFirstLess_3(const V *v)
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
CoinExternalVectorFirstLess_3()
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
CoinExternalVectorFirstLess_2()
U third
Third member of triple.
S first
First member of triple.
bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
Compare function.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
T second
Second member of triple.
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
CoinExternalVectorFirstGreater_2(const V *v)
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
CoinExternalVectorFirstGreater_2()
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
CoinExternalVectorFirstGreater_3()