CoinSort.hpp

Go to the documentation of this file.
00001 /* $Id: CoinSort.hpp 1594 2013-04-19 14:33:00Z forrest $ */
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 = 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   /*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
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   /*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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

Generated on 28 Aug 2016 for CoinUtils by  doxygen 1.6.1