- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# /home/coin/SVN-release/CoinUtils-2.6.1/CoinUtils/src/CoinSort.hpp

Go to the documentation of this file.

    00001 /* $Id: CoinSort.hpp 1239 2009-12-10 16:16:11Z ladanyi $ */
    00002 // Copyright (C) 2000, International Business Machines
    00003 // Corporation and others.  All Rights Reserved.
    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 // Uncomment the next three lines to get thorough initialisation of memory.
    00013 // #ifndef ZEROFAULT
    00014 // #define ZEROFAULT
    00015 // #endif
    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   // Can show RUI errors on some systems due to copy of ST_pair with gaps.
    00190   // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro.
    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 // This Always uses std::sort
    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   /*check already sorted  */
    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     } /* endif */
    00267   } /* endfor */
    00268   if (j==n) {
    00269     return;
    00270   } /* endif */
    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