CoinUtils trunk
CoinSort.hpp
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines