00001
00002
00003
00004
00005
00006 #ifndef CoinSort_H
00007 #define CoinSort_H
00008
00009 #include <functional>
00010 #include <new>
00011 #include <algorithm>
00012 #include "CoinDistance.hpp"
00013
00014
00015
00016
00017
00018
00019 #ifdef COIN_FAST_CODE
00020 #ifndef COIN_USE_EKK_SORT
00021 #define COIN_USE_EKK_SORT
00022 #endif
00023 #endif
00024
00025
00026
00029 template <class S, class T>
00030 struct CoinPair {
00031 public:
00033 S first;
00035 T second;
00036 public:
00038 CoinPair(const S& s, const T& t) : first(s), second(t) {}
00039 };
00040
00041
00042
00047 template < class S, class T>
00048 class CoinFirstLess_2 {
00049 public:
00051 inline bool operator()(const CoinPair<S,T>& t1,
00052 const CoinPair<S,T>& t2) const
00053 { return t1.first < t2.first; }
00054 };
00055
00058 template < class S, class T>
00059 class CoinFirstGreater_2 {
00060 public:
00062 inline bool operator()(const CoinPair<S,T>& t1,
00063 const CoinPair<S,T>& t2) const
00064 { return t1.first > t2.first; }
00065 };
00066
00069 template < class S, class T>
00070 class CoinFirstAbsLess_2 {
00071 public:
00073 inline bool operator()(const CoinPair<S,T>& t1,
00074 const CoinPair<S,T>& t2) const
00075 {
00076 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00077 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00078 return t1Abs < t2Abs;
00079 }
00080 };
00081
00084 template < class S, class T>
00085 class CoinFirstAbsGreater_2 {
00086 public:
00088 inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
00089 {
00090 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00091 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00092 return t1Abs > t2Abs;
00093 }
00094 };
00095
00101 template < class S, class T, class V>
00102 class CoinExternalVectorFirstLess_2 {
00103 private:
00104 CoinExternalVectorFirstLess_2();
00105 private:
00106 const V* vec_;
00107 public:
00108 inline bool operator()(const CoinPair<S,T>& t1,
00109 const CoinPair<S,T>& t2) const
00110 { return vec_[t1.first] < vec_[t2.first]; }
00111 CoinExternalVectorFirstLess_2(const V* v) : vec_(v) {}
00112 };
00113
00119 template < class S, class T, class V>
00120 class CoinExternalVectorFirstGreater_2 {
00121 private:
00122 CoinExternalVectorFirstGreater_2();
00123 private:
00124 const V* vec_;
00125 public:
00126 inline bool operator()(const CoinPair<S,T>& t1,
00127 const CoinPair<S,T>& t2) const
00128 { return vec_[t1.first] > vec_[t2.first]; }
00129 CoinExternalVectorFirstGreater_2(const V* v) : vec_(v) {}
00130 };
00132
00133
00134
00142 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00143 template <class Iter_S, class Iter_T, class CoinCompare2> void
00144 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst, const CoinCompare2& pc)
00145 {
00146 typedef typename std::iterator_traits<Iter_S>::value_type S;
00147 typedef typename std::iterator_traits<Iter_T>::value_type T;
00148 const size_t len = coinDistance(sfirst, slast);
00149 if (len <= 1)
00150 return;
00151
00152 typedef CoinPair<S,T> ST_pair;
00153 ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
00154 # ifdef ZEROFAULT
00155 memset(x,0,(len*sizeof(ST_pair))) ;
00156 # endif
00157
00158 int i = 0;
00159 Iter_S scurrent = sfirst;
00160 Iter_T tcurrent = tfirst;
00161 while (scurrent != slast) {
00162 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
00163 }
00164
00165 std::sort(x.begin(), x.end(), pc);
00166
00167 scurrent = sfirst;
00168 tcurrent = tfirst;
00169 for (i = 0; i < len; ++i) {
00170 *scurrent++ = x[i].first;
00171 *tcurrent++ = x[i].second;
00172 }
00173
00174 ::operator delete(x);
00175 }
00176
00177 template <class Iter_S, class Iter_T> void
00178 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
00179 {
00180 typedef typename std::iterator_traits<Iter_S>::value_type S;
00181 typedef typename std::iterator_traits<Iter_T>::value_type T;
00182 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00183 }
00184
00185 #else //=======================================================================
00186
00187 template <class S, class T, class CoinCompare2> void
00188 CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
00189 {
00190 const size_t len = coinDistance(sfirst, slast);
00191 if (len <= 1)
00192 return;
00193
00194 typedef CoinPair<S,T> ST_pair;
00195 ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
00196 # ifdef ZEROFAULT
00197
00198
00199 memset(x,0,(len*sizeof(ST_pair))) ;
00200 # endif
00201
00202 size_t i = 0;
00203 S* scurrent = sfirst;
00204 T* tcurrent = tfirst;
00205 while (scurrent != slast) {
00206 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
00207 }
00208
00209 std::sort(x, x + len, pc);
00210
00211 scurrent = sfirst;
00212 tcurrent = tfirst;
00213 for (i = 0; i < len; ++i) {
00214 *scurrent++ = x[i].first;
00215 *tcurrent++ = x[i].second;
00216 }
00217
00218 ::operator delete(x);
00219 }
00220 template <class S, class T> void
00221
00222 CoinSort_2Std(S* sfirst, S* slast, T* tfirst)
00223 {
00224 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00225 }
00226 #ifndef COIN_USE_EKK_SORT
00227
00228 template <class S, class T> void
00229 CoinSort_2(S* sfirst, S* slast, T* tfirst)
00230 {
00231 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00232 }
00233 #else
00234
00235 extern int boundary_sort;
00236 extern int boundary_sort2;
00237 extern int boundary_sort3;
00239 template <class S, class T> void
00240 CoinSort_2(S* key, S* lastKey, T* array2)
00241 {
00242 const size_t number = coinDistance(key, lastKey);
00243 if (number <= 1) {
00244 return;
00245 } else if (number>10000) {
00246 CoinSort_2Std(key, lastKey, array2);
00247 return;
00248 }
00249 #if 0
00250 if (number==boundary_sort3) {
00251 printf("before sort %d entries\n",number);
00252 for (int j=0;j<number;j++) {
00253 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
00254 }
00255 std::cout<<std::endl;
00256 }
00257 #endif
00258 int minsize=10;
00259 int n = static_cast<int>(number);
00260 int sp;
00261 S *v = key;
00262 S *m, t;
00263 S * ls[32] , * rs[32];
00264 S *l , *r , c;
00265 T it;
00266 int j;
00267
00268 S last=key[0];
00269 for (j=1;j<n;j++) {
00270 if (key[j]>=last) {
00271 last=key[j];
00272 } else {
00273 break;
00274 }
00275 }
00276 if (j==n) {
00277 return;
00278 }
00279 sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
00280 while( sp >= 0 )
00281 {
00282 if ( rs[sp] - ls[sp] > minsize )
00283 {
00284 l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
00285 if ( *l > *m )
00286 {
00287 t = *l ; *l = *m ; *m = t ;
00288 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
00289 }
00290 if ( *m > *r )
00291 {
00292 t = *m ; *m = *r ; *r = t ;
00293 it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
00294 if ( *l > *m )
00295 {
00296 t = *l ; *l = *m ; *m = t ;
00297 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
00298 }
00299 }
00300 c = *m ;
00301 while ( r - l > 1 )
00302 {
00303 while ( *(++l) < c ) ;
00304 while ( *(--r) > c ) ;
00305 t = *l ; *l = *r ; *r = t ;
00306 it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
00307 }
00308 l = r - 1 ;
00309 if ( l < m )
00310 { ls[sp+1] = ls[sp] ;
00311 rs[sp+1] = l ;
00312 ls[sp ] = r ;
00313 }
00314 else
00315 { ls[sp+1] = r ;
00316 rs[sp+1] = rs[sp] ;
00317 rs[sp ] = l ;
00318 }
00319 sp++ ;
00320 }
00321 else sp-- ;
00322 }
00323 for ( l = v , m = v + (n-1) ; l < m ; l++ )
00324 { if ( *l > *(l+1) )
00325 {
00326 c = *(l+1) ;
00327 it = array2[(l-v)+1] ;
00328 for ( r = l ; r >= v && *r > c ; r-- )
00329 {
00330 *(r+1) = *r ;
00331 array2[(r-v)+1] = array2[(r-v)] ;
00332 }
00333 *(r+1) = c ;
00334 array2[(r-v)+1] = it ;
00335 }
00336 }
00337 #if 0
00338 if (number==boundary_sort3) {
00339 printf("after sort %d entries\n",number);
00340 for (int j=0;j<number;j++) {
00341 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
00342 }
00343 std::cout<<std::endl;
00344 CoinSort_2Many(key, lastKey, array2);
00345 printf("after2 sort %d entries\n",number);
00346 for (int j=0;j<number;j++) {
00347 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
00348 }
00349 std::cout<<std::endl;
00350 }
00351 #endif
00352 }
00353 #endif
00354 #endif
00356 template <class S, class T> void
00357 CoinShortSort_2(S* key, S* lastKey, T* array2)
00358 {
00359 const size_t number = coinDistance(key, lastKey);
00360 if (number <= 2) {
00361 if (number == 2 && key[0] > key[1]) {
00362 S tempS = key[0];
00363 T tempT = array2[0];
00364 key[0] = key[1];
00365 array2[0] = array2[1];
00366 key[1] = tempS;
00367 array2[1] = tempT;
00368 }
00369 return;
00370 } else if (number>10000) {
00371 CoinSort_2Std(key, lastKey, array2);
00372 return;
00373 }
00374 int minsize=10;
00375 size_t n = number;
00376 int sp;
00377 S *v = key;
00378 S *m, t;
00379 S * ls[32] , * rs[32];
00380 S *l , *r , c;
00381 T it;
00382 size_t j;
00383
00384 S last=key[0];
00385 for (j=1;j<n;j++) {
00386 if (key[j]>=last) {
00387 last=key[j];
00388 } else {
00389 break;
00390 }
00391 }
00392 if (j==n) {
00393 return;
00394 }
00395 sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
00396 while( sp >= 0 )
00397 {
00398 if ( rs[sp] - ls[sp] > minsize )
00399 {
00400 l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
00401 if ( *l > *m )
00402 {
00403 t = *l ; *l = *m ; *m = t ;
00404 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
00405 }
00406 if ( *m > *r )
00407 {
00408 t = *m ; *m = *r ; *r = t ;
00409 it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
00410 if ( *l > *m )
00411 {
00412 t = *l ; *l = *m ; *m = t ;
00413 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
00414 }
00415 }
00416 c = *m ;
00417 while ( r - l > 1 )
00418 {
00419 while ( *(++l) < c ) ;
00420 while ( *(--r) > c ) ;
00421 t = *l ; *l = *r ; *r = t ;
00422 it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
00423 }
00424 l = r - 1 ;
00425 if ( l < m )
00426 { ls[sp+1] = ls[sp] ;
00427 rs[sp+1] = l ;
00428 ls[sp ] = r ;
00429 }
00430 else
00431 { ls[sp+1] = r ;
00432 rs[sp+1] = rs[sp] ;
00433 rs[sp ] = l ;
00434 }
00435 sp++ ;
00436 }
00437 else sp-- ;
00438 }
00439 for ( l = v , m = v + (n-1) ; l < m ; l++ )
00440 { if ( *l > *(l+1) )
00441 {
00442 c = *(l+1) ;
00443 it = array2[(l-v)+1] ;
00444 for ( r = l ; r >= v && *r > c ; r-- )
00445 {
00446 *(r+1) = *r ;
00447 array2[(r-v)+1] = array2[(r-v)] ;
00448 }
00449 *(r+1) = c ;
00450 array2[(r-v)+1] = it ;
00451 }
00452 }
00453 }
00454
00455
00456
00458 template <class S, class T, class U>
00459 class CoinTriple {
00460 public:
00462 S first;
00464 T second;
00466 U third;
00467 public:
00469 CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
00470 };
00471
00472
00477 template < class S, class T, class U >
00478 class CoinFirstLess_3 {
00479 public:
00481 inline bool operator()(const CoinTriple<S,T,U>& t1,
00482 const CoinTriple<S,T,U>& t2) const
00483 { return t1.first < t2.first; }
00484 };
00485
00488 template < class S, class T, class U >
00489 class CoinFirstGreater_3 {
00490 public:
00492 inline bool operator()(const CoinTriple<S,T,U>& t1,
00493 const CoinTriple<S,T,U>& t2) const
00494 { return t1.first>t2.first; }
00495 };
00496
00499 template < class S, class T, class U >
00500 class CoinFirstAbsLess_3 {
00501 public:
00503 inline bool operator()(const CoinTriple<S,T,U>& t1,
00504 const CoinTriple<S,T,U>& t2) const
00505 {
00506 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00507 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00508 return t1Abs < t2Abs;
00509 }
00510 };
00511
00514 template < class S, class T, class U >
00515 class CoinFirstAbsGreater_3 {
00516 public:
00518 inline bool operator()(const CoinTriple<S,T,U>& t1,
00519 const CoinTriple<S,T,U>& t2) const
00520 {
00521 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00522 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00523 return t1Abs > t2Abs;
00524 }
00525 };
00526
00532 template < class S, class T, class U, class V>
00533 class CoinExternalVectorFirstLess_3 {
00534 private:
00535 CoinExternalVectorFirstLess_3();
00536 private:
00537 const V* vec_;
00538 public:
00539 inline bool operator()(const CoinTriple<S,T,U>& t1,
00540 const CoinTriple<S,T,U>& t2) const
00541 { return vec_[t1.first] < vec_[t2.first]; }
00542 CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
00543 };
00544
00550 template < class S, class T, class U, class V>
00551 class CoinExternalVectorFirstGreater_3 {
00552 private:
00553 CoinExternalVectorFirstGreater_3();
00554 private:
00555 const V* vec_;
00556 public:
00557 inline bool operator()(const CoinTriple<S,T,U>& t1,
00558 const CoinTriple<S,T,U>& t2) const
00559 { return vec_[t1.first] > vec_[t2.first]; }
00560 CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
00561 };
00563
00564
00565
00569
00570 typedef CoinExternalVectorFirstLess_3<int, int, double, double>
00571 CoinIncrSolutionOrdered;
00573 typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
00574 CoinDecrSolutionOrdered;
00576
00577
00578
00586 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00587 template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
00588 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
00589 const CoinCompare3& tc)
00590 {
00591 typedef typename std::iterator_traits<Iter_S>::value_type S;
00592 typedef typename std::iterator_traits<Iter_T>::value_type T;
00593 typedef typename std::iterator_traits<Iter_U>::value_type U;
00594 const size_t len = coinDistance(sfirst, slast);
00595 if (len <= 1)
00596 return;
00597
00598 typedef CoinTriple<S,T,U> STU_triple;
00599 STU_triple* x =
00600 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00601
00602 int i = 0;
00603 Iter_S scurrent = sfirst;
00604 Iter_T tcurrent = tfirst;
00605 Iter_U ucurrent = ufirst;
00606 while (scurrent != slast) {
00607 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00608 }
00609
00610 std::sort(x, x+len, tc);
00611
00612 scurrent = sfirst;
00613 tcurrent = tfirst;
00614 ucurrent = ufirst;
00615 for (i = 0; i < len; ++i) {
00616 *scurrent++ = x[i].first;
00617 *tcurrent++ = x[i].second;
00618 *ucurrent++ = x[i].third;
00619 }
00620
00621 ::operator delete(x);
00622 }
00623
00624 template <class Iter_S, class Iter_T, class Iter_U> void
00625 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
00626 {
00627 typedef typename std::iterator_traits<Iter_S>::value_type S;
00628 typedef typename std::iterator_traits<Iter_T>::value_type T;
00629 typedef typename std::iterator_traits<Iter_U>::value_type U;
00630 CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00631 }
00632
00633 #else //=======================================================================
00634
00635 template <class S, class T, class U, class CoinCompare3> void
00636 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
00637 {
00638 const size_t len = coinDistance(sfirst,slast);
00639 if (len <= 1)
00640 return;
00641
00642 typedef CoinTriple<S,T,U> STU_triple;
00643 STU_triple* x =
00644 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00645
00646 size_t i = 0;
00647 S* scurrent = sfirst;
00648 T* tcurrent = tfirst;
00649 U* ucurrent = ufirst;
00650 while (scurrent != slast) {
00651 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00652 }
00653
00654 std::sort(x, x+len, tc);
00655
00656 scurrent = sfirst;
00657 tcurrent = tfirst;
00658 ucurrent = ufirst;
00659 for (i = 0; i < len; ++i) {
00660 *scurrent++ = x[i].first;
00661 *tcurrent++ = x[i].second;
00662 *ucurrent++ = x[i].third;
00663 }
00664
00665 ::operator delete(x);
00666 }
00667
00668 template <class S, class T, class U> void
00669 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
00670 {
00671 CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00672 }
00673
00674 #endif
00675
00676
00677
00678 #endif