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