20#ifndef COIN_USE_EKK_SORT
21#define COIN_USE_EKK_SORT
29template <
class S,
class T >
52template <
class S,
class T >
65template <
class S,
class T >
78template <
class S,
class T >
93template <
class S,
class T >
101 return t1Abs > t2Abs;
110template <
class S,
class T,
class V >
135template <
class S,
class T,
class V >
165#ifdef COIN_SORT_ARBITRARY_CONTAINERS
166template <
class Iter_S,
class Iter_T,
class CoinCompare2 >
167void 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);
200template <
class Iter_S,
class Iter_T >
201void 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;
210template <
class S,
class T,
class CoinCompare2 >
211void 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);
243template <
class S,
class T >
250#ifndef COIN_USE_EKK_SORT
252template <
class S,
class T >
259extern int boundary_sort;
260extern int boundary_sort2;
261extern int boundary_sort3;
263template <
class S,
class T >
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;
393template <
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;
508template <
class S,
class T,
class U >
533template <
class S,
class T,
class U >
546template <
class S,
class T,
class U >
559template <
class S,
class T,
class U >
568 return t1Abs < t2Abs;
574template <
class S,
class T,
class U >
583 return t1Abs > t2Abs;
592template <
class S,
class T,
class U,
class V >
617template <
class S,
class T,
class U,
class V >
660#ifdef COIN_SORT_ARBITRARY_CONTAINERS
661template <
class Iter_S,
class Iter_T,
class Iter_U,
class CoinCompare3 >
662void 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);
697template <
class Iter_S,
class Iter_T,
class Iter_U >
698void 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;
708template <
class S,
class T,
class U,
class CoinCompare3 >
709void 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);
740template <
class S,
class T,
class U >
void coinDistance(ForwardIterator first, ForwardIterator last, Distance &n)
CoinDistance.
void CoinShortSort_2(S *key, S *lastKey, T *array2)
Sort without new and delete.
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
CoinExternalVectorFirstGreater_2(const V *v)
CoinExternalVectorFirstGreater_2()
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
CoinExternalVectorFirstGreater_3(const V *v)
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
CoinExternalVectorFirstGreater_3()
CoinExternalVectorFirstLess_2()
CoinExternalVectorFirstLess_2(const V *v)
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
CoinExternalVectorFirstLess_3()
CoinExternalVectorFirstLess_3(const V *v)
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
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
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
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
Compare function.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
T second
Second member of triple.
S first
First member of triple.
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
U third
Third member of triple.
S first
First member of pair.
CoinPair(const S &s, const T &t)
Construct from ordered pair.
T second
Second member of pair.