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 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 int 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 int j; 00383 /*check already sorted */ 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 } /* endif */ 00391 } /* endfor */ 00392 if (j==n) { 00393 return; 00394 } /* endif */ 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