• Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List
  • File Members

/build/buildd/coinutils-2.6.4/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

Generated on Fri Oct 15 2010 18:21:02 by  doxygen 1.7.1