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

- File List
- File Members

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

Go to the documentation of this file.

    00001 // Copyright (C) 2000, International Business Machines
    00002 // Corporation and others.  All Rights Reserved.
    00003 #ifndef CoinSort_H
    00004 #define CoinSort_H
    00005
    00006 #include <functional>
    00007 #include <new>
    00008 #include "CoinDistance.hpp"
    00009 #include "CoinFinite.hpp"
    00010
    00011 // Uncomment the next three lines to get thorough initialisation of memory.
    00012 // #ifndef ZEROFAULT
    00013 // #define ZEROFAULT
    00014 // #endif
    00015
    00016 //#############################################################################
    00017
    00020 template <class S, class T>
    00021 struct CoinPair {
    00022 public:
    00024   S first;
    00026   T second;
    00027 public:
    00029   CoinPair(const S& s, const T& t) : first(s), second(t) {}
    00030 };
    00031
    00032 //#############################################################################
    00033
    00038 template < class S, class T>
    00039 class CoinFirstLess_2 {
    00040 public:
    00042   inline bool operator()(const CoinPair<S,T>& t1,
    00043                          const CoinPair<S,T>& t2) const
    00044   { return t1.first < t2.first; }
    00045 };
    00046 //-----------------------------------------------------------------------------
    00049 template < class S, class T>
    00050 class CoinFirstGreater_2 {
    00051 public:
    00053   inline bool operator()(const CoinPair<S,T>& t1,
    00054                          const CoinPair<S,T>& t2) const
    00055   { return t1.first > t2.first; }
    00056 };
    00057 //-----------------------------------------------------------------------------
    00060 template < class S, class T>
    00061 class CoinFirstAbsLess_2 {
    00062 public:
    00064   inline bool operator()(const CoinPair<S,T>& t1,
    00065                          const CoinPair<S,T>& t2) const
    00066   {
    00067     const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
    00068     const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
    00069     return t1Abs < t2Abs;
    00070   }
    00071 };
    00072 //-----------------------------------------------------------------------------
    00075 template < class S, class T>
    00076 class CoinFirstAbsGreater_2 {
    00077 public:
    00079   inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
    00080   {
    00081     const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
    00082     const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
    00083     return t1Abs > t2Abs;
    00084   }
    00085 };
    00086 //-----------------------------------------------------------------------------
    00092 template < class S, class T, class V>
    00093 class CoinExternalVectorFirstLess_2 {
    00094 private:
    00095   CoinExternalVectorFirstLess_2();
    00096 private:
    00097   const V* vec_;
    00098 public:
    00099   inline bool operator()(const CoinPair<S,T>& t1,
    00100                          const CoinPair<S,T>& t2) const
    00101   { return vec_[t1.first] < vec_[t2.first]; }
    00102   CoinExternalVectorFirstLess_2(const V* v) : vec_(v) {}
    00103 };
    00104 //-----------------------------------------------------------------------------
    00110 template < class S, class T, class V>
    00111 class CoinExternalVectorFirstGreater_2 {
    00112 private:
    00113   CoinExternalVectorFirstGreater_2();
    00114 private:
    00115   const V* vec_;
    00116 public:
    00117   inline bool operator()(const CoinPair<S,T>& t1,
    00118                          const CoinPair<S,T>& t2) const
    00119   { return vec_[t1.first] > vec_[t2.first]; }
    00120   CoinExternalVectorFirstGreater_2(const V* v) : vec_(v) {}
    00121 };
    00123
    00124 //#############################################################################
    00125
    00133 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
    00134 template <class Iter_S, class Iter_T, class CoinCompare2> void
    00135 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst, const CoinCompare2& pc)
    00136 {
    00137   typedef typename std::iterator_traits<Iter_S>::value_type S;
    00138   typedef typename std::iterator_traits<Iter_T>::value_type T;
    00139   const int len = coinDistance(sfirst, slast);
    00140   if (len <= 1)
    00141     return;
    00142
    00143   typedef CoinPair<S,T> ST_pair;
    00144   ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
    00145 # ifdef ZEROFAULT
    00146   memset(x,0,(len*sizeof(ST_pair))) ;
    00147 # endif
    00148
    00149   int i = 0;
    00150   Iter_S scurrent = sfirst;
    00151   Iter_T tcurrent = tfirst;
    00152   while (scurrent != slast) {
    00153     new (x+i++) ST_pair(*scurrent++, *tcurrent++);
    00154   }
    00155
    00156   std::sort(x.begin(), x.end(), pc);
    00157
    00158   scurrent = sfirst;
    00159   tcurrent = tfirst;
    00160   for (i = 0; i < len; ++i) {
    00161     *scurrent++ = x[i].first;
    00162     *tcurrent++ = x[i].second;
    00163   }
    00164
    00165   ::operator delete(x);
    00166 }
    00167 //-----------------------------------------------------------------------------
    00168 template <class Iter_S, class Iter_T> void
    00169 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
    00170 {
    00171   typedef typename std::iterator_traits<Iter_S>::value_type S;
    00172   typedef typename std::iterator_traits<Iter_T>::value_type T;
    00173   CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
    00174 }
    00175
    00176 #else //=======================================================================
    00177
    00178 template <class S, class T, class CoinCompare2> void
    00179 CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
    00180 {
    00181   const int len = coinDistance(sfirst, slast);
    00182   if (len <= 1)
    00183     return;
    00184
    00185   typedef CoinPair<S,T> ST_pair;
    00186   ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
    00187 # ifdef ZEROFAULT
    00188   // Can show RUI errors on some systems due to copy of ST_pair with gaps.
    00189   // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro.
    00190   memset(x,0,(len*sizeof(ST_pair))) ;
    00191 # endif
    00192
    00193   int i = 0;
    00194   S* scurrent = sfirst;
    00195   T* tcurrent = tfirst;
    00196   while (scurrent != slast) {
    00197     new (x+i++) ST_pair(*scurrent++, *tcurrent++);
    00198   }
    00199
    00200   std::sort(x, x + len, pc);
    00201
    00202   scurrent = sfirst;
    00203   tcurrent = tfirst;
    00204   for (i = 0; i < len; ++i) {
    00205     *scurrent++ = x[i].first;
    00206     *tcurrent++ = x[i].second;
    00207   }
    00208
    00209   ::operator delete(x);
    00210 }
    00211 template <class S, class T> void
    00212 // This Always uses std::sort
    00213 CoinSort_2Std(S* sfirst, S* slast, T* tfirst)
    00214 {
    00215   CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
    00216 }
    00217 #ifndef COIN_USE_EKK_SORT
    00218 //-----------------------------------------------------------------------------
    00219 template <class S, class T> void
    00220 CoinSort_2(S* sfirst, S* slast, T* tfirst)
    00221 {
    00222   CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
    00223 }
    00224 #else
    00225 //-----------------------------------------------------------------------------
    00226 extern int boundary_sort;
    00227 extern int boundary_sort2;
    00228 extern int boundary_sort3;
    00230 template <class S, class T> void
    00231 CoinSort_2(S* key, S* lastKey, T* array2)
    00232 {
    00233   const int number = coinDistance(key, lastKey);
    00234   if (number <= 1) {
    00235     return;
    00236   } else if (number>10000) {
    00237     CoinSort_2Std(key, lastKey, array2);
    00238     return;
    00239   }
    00240 #if 0
    00241   if (number==boundary_sort3) {
    00242     printf("before sort %d entries\n",number);
    00243     for (int j=0;j<number;j++) {
    00244       std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
    00245     }
    00246     std::cout<<std::endl;
    00247   }
    00248 #endif
    00249   int minsize=10;
    00250   int n = number;
    00251   int sp;
    00252   S *v = key;
    00253   S *m, t;
    00254   S * ls[32] , * rs[32];
    00255   S *l , *r , c;
    00256   T it;
    00257   int j;
    00258   /*check already sorted  */
    00259   S last=key[0];
    00260   for (j=1;j<number;j++) {
    00261     if (key[j]>=last) {
    00262       last=key[j];
    00263     } else {
    00264       break;
    00265     } /* endif */
    00266   } /* endfor */
    00267   if (j==number) {
    00268     return;
    00269   } /* endif */
    00270   sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
    00271   while( sp >= 0 )
    00272   {
    00273      if ( rs[sp] - ls[sp] > minsize )
    00274      {
    00275         l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
    00276         if ( *l > *m )
    00277         {
    00278            t = *l ; *l = *m ; *m = t ;
    00279            it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
    00280         }
    00281         if ( *m > *r )
    00282         {
    00283            t = *m ; *m = *r ; *r = t ;
    00284            it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
    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         }
    00291         c = *m ;
    00292         while ( r - l > 1 )
    00293         {
    00294            while ( *(++l) < c ) ;
    00295            while ( *(--r) > c ) ;
    00296            t = *l ; *l = *r ; *r = t ;
    00297            it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
    00298         }
    00299         l = r - 1 ;
    00300         if ( l < m )
    00301         {  ls[sp+1] = ls[sp] ;
    00302            rs[sp+1] = l      ;
    00303            ls[sp  ] = r      ;
    00304         }
    00305         else
    00306         {  ls[sp+1] = r      ;
    00307            rs[sp+1] = rs[sp] ;
    00308            rs[sp  ] = l      ;
    00309         }
    00310         sp++ ;
    00311      }
    00312      else sp-- ;
    00313   }
    00314   for ( l = v , m = v + (n-1) ; l < m ; l++ )
    00315   {  if ( *l > *(l+1) )
    00316      {
    00317         c = *(l+1) ;
    00318         it = array2[(l-v)+1] ;
    00319         for ( r = l ; r >= v && *r > c ; r-- )
    00320         {
    00321             *(r+1) = *r ;
    00322             array2[(r-v)+1] = array2[(r-v)] ;
    00323         }
    00324         *(r+1) = c ;
    00325         array2[(r-v)+1] = it ;
    00326      }
    00327   }
    00328 #if 0
    00329   if (number==boundary_sort3) {
    00330     printf("after sort %d entries\n",number);
    00331     for (int j=0;j<number;j++) {
    00332       std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
    00333     }
    00334     std::cout<<std::endl;
    00335     CoinSort_2Many(key, lastKey, array2);
    00336     printf("after2 sort %d entries\n",number);
    00337     for (int j=0;j<number;j++) {
    00338       std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
    00339     }
    00340     std::cout<<std::endl;
    00341   }
    00342 #endif
    00343 }
    00344 #endif
    00345 #endif
    00346 //#############################################################################
    00347 //#############################################################################
    00348
    00350 template <class S, class T, class U>
    00351 class CoinTriple {
    00352 public:
    00354   S first;
    00356   T second;
    00358   U third;
    00359 public:
    00361   CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
    00362 };
    00363
    00364 //#############################################################################
    00369 template < class S, class T, class U >
    00370 class CoinFirstLess_3 {
    00371 public:
    00373   inline bool operator()(const CoinTriple<S,T,U>& t1,
    00374                          const CoinTriple<S,T,U>& t2) const
    00375   { return t1.first < t2.first; }
    00376 };
    00377 //-----------------------------------------------------------------------------
    00380 template < class S, class T, class U >
    00381 class CoinFirstGreater_3 {
    00382 public:
    00384   inline bool operator()(const CoinTriple<S,T,U>& t1,
    00385                          const CoinTriple<S,T,U>& t2) const
    00386   { return t1.first>t2.first; }
    00387 };
    00388 //-----------------------------------------------------------------------------
    00391 template < class S, class T, class U >
    00392 class CoinFirstAbsLess_3 {
    00393 public:
    00395   inline bool operator()(const CoinTriple<S,T,U>& t1,
    00396                          const CoinTriple<S,T,U>& t2) const
    00397   {
    00398     const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
    00399     const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
    00400     return t1Abs < t2Abs;
    00401   }
    00402 };
    00403 //-----------------------------------------------------------------------------
    00406 template < class S, class T, class U >
    00407 class CoinFirstAbsGreater_3 {
    00408 public:
    00410   inline bool operator()(const CoinTriple<S,T,U>& t1,
    00411                          const CoinTriple<S,T,U>& t2) const
    00412   {
    00413     const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
    00414     const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
    00415     return t1Abs > t2Abs;
    00416   }
    00417 };
    00418 //-----------------------------------------------------------------------------
    00424 template < class S, class T, class U, class V>
    00425 class CoinExternalVectorFirstLess_3 {
    00426 private:
    00427   CoinExternalVectorFirstLess_3();
    00428 private:
    00429   const V* vec_;
    00430 public:
    00431   inline bool operator()(const CoinTriple<S,T,U>& t1,
    00432                          const CoinTriple<S,T,U>& t2) const
    00433   { return vec_[t1.first] < vec_[t2.first]; }
    00434   CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
    00435 };
    00436 //-----------------------------------------------------------------------------
    00442 template < class S, class T, class U, class V>
    00443 class CoinExternalVectorFirstGreater_3 {
    00444 private:
    00445   CoinExternalVectorFirstGreater_3();
    00446 private:
    00447   const V* vec_;
    00448 public:
    00449   inline bool operator()(const CoinTriple<S,T,U>& t1,
    00450                          const CoinTriple<S,T,U>& t2) const
    00451   { return vec_[t1.first] > vec_[t2.first]; }
    00452   CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
    00453 };
    00455
    00456 //#############################################################################
    00457
    00461
    00462 typedef CoinExternalVectorFirstLess_3<int, int, double, double>
    00463 CoinIncrSolutionOrdered;
    00465 typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
    00466 CoinDecrSolutionOrdered;
    00468
    00469 //#############################################################################
    00470
    00478 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
    00479 template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
    00480 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
    00481           const CoinCompare3& tc)
    00482 {
    00483   typedef typename std::iterator_traits<Iter_S>::value_type S;
    00484   typedef typename std::iterator_traits<Iter_T>::value_type T;
    00485   typedef typename std::iterator_traits<Iter_U>::value_type U;
    00486   const int len = coinDistance(sfirst, slast);
    00487   if (len <= 1)
    00488     return;
    00489
    00490   typedef CoinTriple<S,T,U> STU_triple;
    00491   STU_triple* x =
    00492     static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
    00493
    00494   int i = 0;
    00495   Iter_S scurrent = sfirst;
    00496   Iter_T tcurrent = tfirst;
    00497   Iter_U ucurrent = ufirst;
    00498   while (scurrent != slast) {
    00499     new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
    00500   }
    00501
    00502   std::sort(x, x+len, tc);
    00503
    00504   scurrent = sfirst;
    00505   tcurrent = tfirst;
    00506   ucurrent = ufirst;
    00507   for (i = 0; i < len; ++i) {
    00508     *scurrent++ = x[i].first;
    00509     *tcurrent++ = x[i].second;
    00510     *ucurrent++ = x[i].third;
    00511   }
    00512
    00513   ::operator delete(x);
    00514 }
    00515 //-----------------------------------------------------------------------------
    00516 template <class Iter_S, class Iter_T, class Iter_U> void
    00517 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
    00518 {
    00519   typedef typename std::iterator_traits<Iter_S>::value_type S;
    00520   typedef typename std::iterator_traits<Iter_T>::value_type T;
    00521   typedef typename std::iterator_traits<Iter_U>::value_type U;
    00522   CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
    00523 }
    00524
    00525 #else //=======================================================================
    00526
    00527 template <class S, class T, class U, class CoinCompare3> void
    00528 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
    00529 {
    00530   const size_t len = coinDistance(sfirst,slast);
    00531   if (len <= 1)
    00532     return;
    00533
    00534   typedef CoinTriple<S,T,U> STU_triple;
    00535   STU_triple* x =
    00536     static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
    00537
    00538   size_t i = 0;
    00539   S* scurrent = sfirst;
    00540   T* tcurrent = tfirst;
    00541   U* ucurrent = ufirst;
    00542   while (scurrent != slast) {
    00543     new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
    00544   }
    00545
    00546   std::sort(x, x+len, tc);
    00547
    00548   scurrent = sfirst;
    00549   tcurrent = tfirst;
    00550   ucurrent = ufirst;
    00551   for (i = 0; i < len; ++i) {
    00552     *scurrent++ = x[i].first;
    00553     *tcurrent++ = x[i].second;
    00554     *ucurrent++ = x[i].third;
    00555   }
    00556
    00557   ::operator delete(x);
    00558 }
    00559 //-----------------------------------------------------------------------------
    00560 template <class S, class T, class U> void
    00561 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
    00562 {
    00563   CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
    00564 }
    00565
    00566 #endif
    00567
    00568 //#############################################################################
    00569
    00570 #endif