00001
00002
00003 #ifndef CoinSort_H
00004 #define CoinSort_H
00005
00006 #include <functional>
00007 #include <new>
00008 #include "CoinDistance.hpp"
00009 #include "CoinFinite.hpp"
00010
00011
00012
00013
00014
00015
00016
00017
00020 template <class S, class T>
00021 struct CoinPair {
00022 public:
00024 S first;
00026 T second;
00027 public:
00029 CoinPair(const S& s, const T& t) : first(s), second(t) {}
00030 };
00031
00032
00033
00038 template < class S, class T>
00039 class CoinFirstLess_2 {
00040 public:
00042 inline bool operator()(const CoinPair<S,T>& t1,
00043 const CoinPair<S,T>& t2) const
00044 { return t1.first < t2.first; }
00045 };
00046
00049 template < class S, class T>
00050 class CoinFirstGreater_2 {
00051 public:
00053 inline bool operator()(const CoinPair<S,T>& t1,
00054 const CoinPair<S,T>& t2) const
00055 { return t1.first > t2.first; }
00056 };
00057
00060 template < class S, class T>
00061 class CoinFirstAbsLess_2 {
00062 public:
00064 inline bool operator()(const CoinPair<S,T>& t1,
00065 const CoinPair<S,T>& t2) const
00066 {
00067 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00068 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00069 return t1Abs < t2Abs;
00070 }
00071 };
00072
00075 template < class S, class T>
00076 class CoinFirstAbsGreater_2 {
00077 public:
00079 inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
00080 {
00081 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00082 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00083 return t1Abs > t2Abs;
00084 }
00085 };
00086
00092 template < class S, class T, class V>
00093 class CoinExternalVectorFirstLess_2 {
00094 private:
00095 CoinExternalVectorFirstLess_2();
00096 private:
00097 const V* vec_;
00098 public:
00099 inline bool operator()(const CoinPair<S,T>& t1,
00100 const CoinPair<S,T>& t2) const
00101 { return vec_[t1.first] < vec_[t2.first]; }
00102 CoinExternalVectorFirstLess_2(const V* v) : vec_(v) {}
00103 };
00104
00110 template < class S, class T, class V>
00111 class CoinExternalVectorFirstGreater_2 {
00112 private:
00113 CoinExternalVectorFirstGreater_2();
00114 private:
00115 const V* vec_;
00116 public:
00117 inline bool operator()(const CoinPair<S,T>& t1,
00118 const CoinPair<S,T>& t2) const
00119 { return vec_[t1.first] > vec_[t2.first]; }
00120 CoinExternalVectorFirstGreater_2(const V* v) : vec_(v) {}
00121 };
00123
00124
00125
00133 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00134 template <class Iter_S, class Iter_T, class CoinCompare2> void
00135 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst, const CoinCompare2& pc)
00136 {
00137 typedef typename std::iterator_traits<Iter_S>::value_type S;
00138 typedef typename std::iterator_traits<Iter_T>::value_type T;
00139 const int len = coinDistance(sfirst, slast);
00140 if (len <= 1)
00141 return;
00142
00143 typedef CoinPair<S,T> ST_pair;
00144 ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
00145 # ifdef ZEROFAULT
00146 memset(x,0,(len*sizeof(ST_pair))) ;
00147 # endif
00148
00149 int i = 0;
00150 Iter_S scurrent = sfirst;
00151 Iter_T tcurrent = tfirst;
00152 while (scurrent != slast) {
00153 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
00154 }
00155
00156 std::sort(x.begin(), x.end(), pc);
00157
00158 scurrent = sfirst;
00159 tcurrent = tfirst;
00160 for (i = 0; i < len; ++i) {
00161 *scurrent++ = x[i].first;
00162 *tcurrent++ = x[i].second;
00163 }
00164
00165 ::operator delete(x);
00166 }
00167
00168 template <class Iter_S, class Iter_T> void
00169 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
00170 {
00171 typedef typename std::iterator_traits<Iter_S>::value_type S;
00172 typedef typename std::iterator_traits<Iter_T>::value_type T;
00173 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00174 }
00175
00176 #else //=======================================================================
00177
00178 template <class S, class T, class CoinCompare2> void
00179 CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
00180 {
00181 const int len = coinDistance(sfirst, slast);
00182 if (len <= 1)
00183 return;
00184
00185 typedef CoinPair<S,T> ST_pair;
00186 ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
00187 # ifdef ZEROFAULT
00188
00189
00190 memset(x,0,(len*sizeof(ST_pair))) ;
00191 # endif
00192
00193 int i = 0;
00194 S* scurrent = sfirst;
00195 T* tcurrent = tfirst;
00196 while (scurrent != slast) {
00197 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
00198 }
00199
00200 std::sort(x, x + len, pc);
00201
00202 scurrent = sfirst;
00203 tcurrent = tfirst;
00204 for (i = 0; i < len; ++i) {
00205 *scurrent++ = x[i].first;
00206 *tcurrent++ = x[i].second;
00207 }
00208
00209 ::operator delete(x);
00210 }
00211 template <class S, class T> void
00212
00213 CoinSort_2Std(S* sfirst, S* slast, T* tfirst)
00214 {
00215 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00216 }
00217 #ifndef COIN_USE_EKK_SORT
00218
00219 template <class S, class T> void
00220 CoinSort_2(S* sfirst, S* slast, T* tfirst)
00221 {
00222 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00223 }
00224 #else
00225
00226 extern int boundary_sort;
00227 extern int boundary_sort2;
00228 extern int boundary_sort3;
00230 template <class S, class T> void
00231 CoinSort_2(S* key, S* lastKey, T* array2)
00232 {
00233 const int number = coinDistance(key, lastKey);
00234 if (number <= 1) {
00235 return;
00236 } else if (number>10000) {
00237 CoinSort_2Std(key, lastKey, array2);
00238 return;
00239 }
00240 #if 0
00241 if (number==boundary_sort3) {
00242 printf("before sort %d entries\n",number);
00243 for (int j=0;j<number;j++) {
00244 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
00245 }
00246 std::cout<<std::endl;
00247 }
00248 #endif
00249 int minsize=10;
00250 int n = number;
00251 int sp;
00252 S *v = key;
00253 S *m, t;
00254 S * ls[32] , * rs[32];
00255 S *l , *r , c;
00256 T it;
00257 int j;
00258
00259 S last=key[0];
00260 for (j=1;j<number;j++) {
00261 if (key[j]>=last) {
00262 last=key[j];
00263 } else {
00264 break;
00265 }
00266 }
00267 if (j==number) {
00268 return;
00269 }
00270 sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
00271 while( sp >= 0 )
00272 {
00273 if ( rs[sp] - ls[sp] > minsize )
00274 {
00275 l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
00276 if ( *l > *m )
00277 {
00278 t = *l ; *l = *m ; *m = t ;
00279 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
00280 }
00281 if ( *m > *r )
00282 {
00283 t = *m ; *m = *r ; *r = t ;
00284 it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
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 }
00291 c = *m ;
00292 while ( r - l > 1 )
00293 {
00294 while ( *(++l) < c ) ;
00295 while ( *(--r) > c ) ;
00296 t = *l ; *l = *r ; *r = t ;
00297 it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
00298 }
00299 l = r - 1 ;
00300 if ( l < m )
00301 { ls[sp+1] = ls[sp] ;
00302 rs[sp+1] = l ;
00303 ls[sp ] = r ;
00304 }
00305 else
00306 { ls[sp+1] = r ;
00307 rs[sp+1] = rs[sp] ;
00308 rs[sp ] = l ;
00309 }
00310 sp++ ;
00311 }
00312 else sp-- ;
00313 }
00314 for ( l = v , m = v + (n-1) ; l < m ; l++ )
00315 { if ( *l > *(l+1) )
00316 {
00317 c = *(l+1) ;
00318 it = array2[(l-v)+1] ;
00319 for ( r = l ; r >= v && *r > c ; r-- )
00320 {
00321 *(r+1) = *r ;
00322 array2[(r-v)+1] = array2[(r-v)] ;
00323 }
00324 *(r+1) = c ;
00325 array2[(r-v)+1] = it ;
00326 }
00327 }
00328 #if 0
00329 if (number==boundary_sort3) {
00330 printf("after sort %d entries\n",number);
00331 for (int j=0;j<number;j++) {
00332 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
00333 }
00334 std::cout<<std::endl;
00335 CoinSort_2Many(key, lastKey, array2);
00336 printf("after2 sort %d entries\n",number);
00337 for (int j=0;j<number;j++) {
00338 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
00339 }
00340 std::cout<<std::endl;
00341 }
00342 #endif
00343 }
00344 #endif
00345 #endif
00346
00347
00348
00350 template <class S, class T, class U>
00351 class CoinTriple {
00352 public:
00354 S first;
00356 T second;
00358 U third;
00359 public:
00361 CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
00362 };
00363
00364
00369 template < class S, class T, class U >
00370 class CoinFirstLess_3 {
00371 public:
00373 inline bool operator()(const CoinTriple<S,T,U>& t1,
00374 const CoinTriple<S,T,U>& t2) const
00375 { return t1.first < t2.first; }
00376 };
00377
00380 template < class S, class T, class U >
00381 class CoinFirstGreater_3 {
00382 public:
00384 inline bool operator()(const CoinTriple<S,T,U>& t1,
00385 const CoinTriple<S,T,U>& t2) const
00386 { return t1.first>t2.first; }
00387 };
00388
00391 template < class S, class T, class U >
00392 class CoinFirstAbsLess_3 {
00393 public:
00395 inline bool operator()(const CoinTriple<S,T,U>& t1,
00396 const CoinTriple<S,T,U>& t2) const
00397 {
00398 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00399 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00400 return t1Abs < t2Abs;
00401 }
00402 };
00403
00406 template < class S, class T, class U >
00407 class CoinFirstAbsGreater_3 {
00408 public:
00410 inline bool operator()(const CoinTriple<S,T,U>& t1,
00411 const CoinTriple<S,T,U>& t2) const
00412 {
00413 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00414 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00415 return t1Abs > t2Abs;
00416 }
00417 };
00418
00424 template < class S, class T, class U, class V>
00425 class CoinExternalVectorFirstLess_3 {
00426 private:
00427 CoinExternalVectorFirstLess_3();
00428 private:
00429 const V* vec_;
00430 public:
00431 inline bool operator()(const CoinTriple<S,T,U>& t1,
00432 const CoinTriple<S,T,U>& t2) const
00433 { return vec_[t1.first] < vec_[t2.first]; }
00434 CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
00435 };
00436
00442 template < class S, class T, class U, class V>
00443 class CoinExternalVectorFirstGreater_3 {
00444 private:
00445 CoinExternalVectorFirstGreater_3();
00446 private:
00447 const V* vec_;
00448 public:
00449 inline bool operator()(const CoinTriple<S,T,U>& t1,
00450 const CoinTriple<S,T,U>& t2) const
00451 { return vec_[t1.first] > vec_[t2.first]; }
00452 CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
00453 };
00455
00456
00457
00461
00462 typedef CoinExternalVectorFirstLess_3<int, int, double, double>
00463 CoinIncrSolutionOrdered;
00465 typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
00466 CoinDecrSolutionOrdered;
00468
00469
00470
00478 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00479 template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
00480 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
00481 const CoinCompare3& tc)
00482 {
00483 typedef typename std::iterator_traits<Iter_S>::value_type S;
00484 typedef typename std::iterator_traits<Iter_T>::value_type T;
00485 typedef typename std::iterator_traits<Iter_U>::value_type U;
00486 const int len = coinDistance(sfirst, slast);
00487 if (len <= 1)
00488 return;
00489
00490 typedef CoinTriple<S,T,U> STU_triple;
00491 STU_triple* x =
00492 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00493
00494 int i = 0;
00495 Iter_S scurrent = sfirst;
00496 Iter_T tcurrent = tfirst;
00497 Iter_U ucurrent = ufirst;
00498 while (scurrent != slast) {
00499 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00500 }
00501
00502 std::sort(x, x+len, tc);
00503
00504 scurrent = sfirst;
00505 tcurrent = tfirst;
00506 ucurrent = ufirst;
00507 for (i = 0; i < len; ++i) {
00508 *scurrent++ = x[i].first;
00509 *tcurrent++ = x[i].second;
00510 *ucurrent++ = x[i].third;
00511 }
00512
00513 ::operator delete(x);
00514 }
00515
00516 template <class Iter_S, class Iter_T, class Iter_U> void
00517 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
00518 {
00519 typedef typename std::iterator_traits<Iter_S>::value_type S;
00520 typedef typename std::iterator_traits<Iter_T>::value_type T;
00521 typedef typename std::iterator_traits<Iter_U>::value_type U;
00522 CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00523 }
00524
00525 #else //=======================================================================
00526
00527 template <class S, class T, class U, class CoinCompare3> void
00528 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
00529 {
00530 const size_t len = coinDistance(sfirst,slast);
00531 if (len <= 1)
00532 return;
00533
00534 typedef CoinTriple<S,T,U> STU_triple;
00535 STU_triple* x =
00536 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00537
00538 size_t i = 0;
00539 S* scurrent = sfirst;
00540 T* tcurrent = tfirst;
00541 U* ucurrent = ufirst;
00542 while (scurrent != slast) {
00543 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00544 }
00545
00546 std::sort(x, x+len, tc);
00547
00548 scurrent = sfirst;
00549 tcurrent = tfirst;
00550 ucurrent = ufirst;
00551 for (i = 0; i < len; ++i) {
00552 *scurrent++ = x[i].first;
00553 *tcurrent++ = x[i].second;
00554 *ucurrent++ = x[i].third;
00555 }
00556
00557 ::operator delete(x);
00558 }
00559
00560 template <class S, class T, class U> void
00561 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
00562 {
00563 CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00564 }
00565
00566 #endif
00567
00568
00569
00570 #endif