CoinUtils trunk
|
00001 /* $Id$ */ 00002 // Copyright (C) 2000, International Business Machines 00003 // Corporation and others. All Rights Reserved. 00004 // This code is licensed under the terms of the Eclipse Public License (EPL). 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 // Uncomment the next three lines to get thorough initialisation of memory. 00015 // #ifndef ZEROFAULT 00016 // #define ZEROFAULT 00017 // #endif 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 // Can show RUI errors on some systems due to copy of ST_pair with gaps. 00198 // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro. 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 // This Always uses std::sort 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 = 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 /*check already sorted */ 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 } /* endif */ 00275 } /* endfor */ 00276 if (j==n) { 00277 return; 00278 } /* endif */ 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 00355 //############################################################################# 00356 //############################################################################# 00357 00359 template <class S, class T, class U> 00360 class CoinTriple { 00361 public: 00363 S first; 00365 T second; 00367 U third; 00368 public: 00370 CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {} 00371 }; 00372 00373 //############################################################################# 00378 template < class S, class T, class U > 00379 class CoinFirstLess_3 { 00380 public: 00382 inline bool operator()(const CoinTriple<S,T,U>& t1, 00383 const CoinTriple<S,T,U>& t2) const 00384 { return t1.first < t2.first; } 00385 }; 00386 //----------------------------------------------------------------------------- 00389 template < class S, class T, class U > 00390 class CoinFirstGreater_3 { 00391 public: 00393 inline bool operator()(const CoinTriple<S,T,U>& t1, 00394 const CoinTriple<S,T,U>& t2) const 00395 { return t1.first>t2.first; } 00396 }; 00397 //----------------------------------------------------------------------------- 00400 template < class S, class T, class U > 00401 class CoinFirstAbsLess_3 { 00402 public: 00404 inline bool operator()(const CoinTriple<S,T,U>& t1, 00405 const CoinTriple<S,T,U>& t2) const 00406 { 00407 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first; 00408 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first; 00409 return t1Abs < t2Abs; 00410 } 00411 }; 00412 //----------------------------------------------------------------------------- 00415 template < class S, class T, class U > 00416 class CoinFirstAbsGreater_3 { 00417 public: 00419 inline bool operator()(const CoinTriple<S,T,U>& t1, 00420 const CoinTriple<S,T,U>& t2) const 00421 { 00422 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first; 00423 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first; 00424 return t1Abs > t2Abs; 00425 } 00426 }; 00427 //----------------------------------------------------------------------------- 00433 template < class S, class T, class U, class V> 00434 class CoinExternalVectorFirstLess_3 { 00435 private: 00436 CoinExternalVectorFirstLess_3(); 00437 private: 00438 const V* vec_; 00439 public: 00440 inline bool operator()(const CoinTriple<S,T,U>& t1, 00441 const CoinTriple<S,T,U>& t2) const 00442 { return vec_[t1.first] < vec_[t2.first]; } 00443 CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {} 00444 }; 00445 //----------------------------------------------------------------------------- 00451 template < class S, class T, class U, class V> 00452 class CoinExternalVectorFirstGreater_3 { 00453 private: 00454 CoinExternalVectorFirstGreater_3(); 00455 private: 00456 const V* vec_; 00457 public: 00458 inline bool operator()(const CoinTriple<S,T,U>& t1, 00459 const CoinTriple<S,T,U>& t2) const 00460 { return vec_[t1.first] > vec_[t2.first]; } 00461 CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {} 00462 }; 00464 00465 //############################################################################# 00466 00470 00471 typedef CoinExternalVectorFirstLess_3<int, int, double, double> 00472 CoinIncrSolutionOrdered; 00474 typedef CoinExternalVectorFirstGreater_3<int, int, double, double> 00475 CoinDecrSolutionOrdered; 00477 00478 //############################################################################# 00479 00487 #ifdef COIN_SORT_ARBITRARY_CONTAINERS 00488 template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void 00489 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst, 00490 const CoinCompare3& tc) 00491 { 00492 typedef typename std::iterator_traits<Iter_S>::value_type S; 00493 typedef typename std::iterator_traits<Iter_T>::value_type T; 00494 typedef typename std::iterator_traits<Iter_U>::value_type U; 00495 const size_t len = coinDistance(sfirst, slast); 00496 if (len <= 1) 00497 return; 00498 00499 typedef CoinTriple<S,T,U> STU_triple; 00500 STU_triple* x = 00501 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple))); 00502 00503 int i = 0; 00504 Iter_S scurrent = sfirst; 00505 Iter_T tcurrent = tfirst; 00506 Iter_U ucurrent = ufirst; 00507 while (scurrent != slast) { 00508 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++); 00509 } 00510 00511 std::sort(x, x+len, tc); 00512 00513 scurrent = sfirst; 00514 tcurrent = tfirst; 00515 ucurrent = ufirst; 00516 for (i = 0; i < len; ++i) { 00517 *scurrent++ = x[i].first; 00518 *tcurrent++ = x[i].second; 00519 *ucurrent++ = x[i].third; 00520 } 00521 00522 ::operator delete(x); 00523 } 00524 //----------------------------------------------------------------------------- 00525 template <class Iter_S, class Iter_T, class Iter_U> void 00526 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst) 00527 { 00528 typedef typename std::iterator_traits<Iter_S>::value_type S; 00529 typedef typename std::iterator_traits<Iter_T>::value_type T; 00530 typedef typename std::iterator_traits<Iter_U>::value_type U; 00531 CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>()); 00532 } 00533 00534 #else //======================================================================= 00535 00536 template <class S, class T, class U, class CoinCompare3> void 00537 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc) 00538 { 00539 const size_t len = coinDistance(sfirst,slast); 00540 if (len <= 1) 00541 return; 00542 00543 typedef CoinTriple<S,T,U> STU_triple; 00544 STU_triple* x = 00545 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple))); 00546 00547 size_t i = 0; 00548 S* scurrent = sfirst; 00549 T* tcurrent = tfirst; 00550 U* ucurrent = ufirst; 00551 while (scurrent != slast) { 00552 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++); 00553 } 00554 00555 std::sort(x, x+len, tc); 00556 00557 scurrent = sfirst; 00558 tcurrent = tfirst; 00559 ucurrent = ufirst; 00560 for (i = 0; i < len; ++i) { 00561 *scurrent++ = x[i].first; 00562 *tcurrent++ = x[i].second; 00563 *ucurrent++ = x[i].third; 00564 } 00565 00566 ::operator delete(x); 00567 } 00568 //----------------------------------------------------------------------------- 00569 template <class S, class T, class U> void 00570 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst) 00571 { 00572 CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>()); 00573 } 00574 00575 #endif 00576 00577 //############################################################################# 00578 00579 #endif