- Main Page
- Namespaces
- Classes
- Files
- Directories

- Search for |

- File List
- File Members

# CoinSort.hpp

Go to the documentation of this file.

    00001 /* $Id: CoinSort.hpp 1448 2011-06-19 15:34:41Z stefan $ */
    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