/home/coin/SVN-release/Cbc-1.1.1/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(sfirts, 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 //-----------------------------------------------------------------------------
00212 template <class S, class T> void
00213 CoinSort_2(S* sfirst, S* slast, T* tfirst)
00214 {
00215   CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00216 }
00217 
00218 #endif
00219 
00220 //#############################################################################
00221 //#############################################################################
00222 
00224 template <class S, class T, class U>
00225 class CoinTriple {
00226 public:
00228   S first;
00230   T second;
00232   U third;
00233 public:  
00235   CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
00236 };
00237 
00238 //#############################################################################
00243 template < class S, class T, class U >
00244 class CoinFirstLess_3 {
00245 public:
00247   inline bool operator()(const CoinTriple<S,T,U>& t1,
00248                          const CoinTriple<S,T,U>& t2) const
00249   { return t1.first < t2.first; }
00250 };
00251 //-----------------------------------------------------------------------------
00254 template < class S, class T, class U >
00255 class CoinFirstGreater_3 {
00256 public:
00258   inline bool operator()(const CoinTriple<S,T,U>& t1,
00259                          const CoinTriple<S,T,U>& t2) const
00260   { return t1.first>t2.first; }
00261 };
00262 //-----------------------------------------------------------------------------
00265 template < class S, class T, class U >
00266 class CoinFirstAbsLess_3 {
00267 public:
00269   inline bool operator()(const CoinTriple<S,T,U>& t1,
00270                          const CoinTriple<S,T,U>& t2) const
00271   { 
00272     const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00273     const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00274     return t1Abs < t2Abs; 
00275   }
00276 };
00277 //-----------------------------------------------------------------------------
00280 template < class S, class T, class U >
00281 class CoinFirstAbsGreater_3 {
00282 public:
00284   inline bool operator()(const CoinTriple<S,T,U>& t1,
00285                          const CoinTriple<S,T,U>& t2) const
00286   { 
00287     const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00288     const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00289     return t1Abs > t2Abs; 
00290   }
00291 };
00292 //-----------------------------------------------------------------------------
00298 template < class S, class T, class U, class V>
00299 class CoinExternalVectorFirstLess_3 {
00300 private:
00301   CoinExternalVectorFirstLess_3();
00302 private:
00303   const V* vec_;
00304 public:
00305   inline bool operator()(const CoinTriple<S,T,U>& t1,
00306                          const CoinTriple<S,T,U>& t2) const
00307   { return vec_[t1.first] < vec_[t2.first]; }
00308   CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
00309 };
00310 //-----------------------------------------------------------------------------
00316 template < class S, class T, class U, class V>
00317 class CoinExternalVectorFirstGreater_3 {
00318 private:
00319   CoinExternalVectorFirstGreater_3();
00320 private:
00321   const V* vec_;
00322 public:
00323   inline bool operator()(const CoinTriple<S,T,U>& t1,
00324                          const CoinTriple<S,T,U>& t2) const
00325   { return vec_[t1.first] > vec_[t2.first]; }
00326   CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
00327 };
00329 
00330 //#############################################################################
00331 
00335 
00336 typedef CoinExternalVectorFirstLess_3<int, int, double, double>
00337 CoinIncrSolutionOrdered;
00339 typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
00340 CoinDecrSolutionOrdered;
00342 
00343 //#############################################################################
00344 
00352 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00353 template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
00354 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
00355           const CoinCompare3& tc)
00356 {
00357   typedef typename std::iterator_traits<Iter_S>::value_type S;
00358   typedef typename std::iterator_traits<Iter_T>::value_type T;
00359   typedef typename std::iterator_traits<Iter_U>::value_type U;
00360   const int len = coinDistance(sfirst, slast);
00361   if (len <= 1)
00362     return;
00363 
00364   typedef CoinTriple<S,T,U> STU_triple;
00365   STU_triple* x =
00366     static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00367 
00368   int i = 0;
00369   Iter_S scurrent = sfirst;
00370   Iter_T tcurrent = tfirst;
00371   Iter_U ucurrent = ufirst;
00372   while (scurrent != slast) {
00373     new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00374   }
00375 
00376   std::sort(x, x+len, tc);
00377 
00378   scurrent = sfirst;
00379   tcurrent = tfirst;
00380   ucurrent = ufirst;
00381   for (i = 0; i < len; ++i) {
00382     *scurrent++ = x[i].first;
00383     *tcurrent++ = x[i].second;
00384     *ucurrent++ = x[i].third;
00385   }
00386 
00387   ::operator delete(x);
00388 }
00389 //-----------------------------------------------------------------------------
00390 template <class Iter_S, class Iter_T, class Iter_U> void
00391 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
00392 {
00393   typedef typename std::iterator_traits<Iter_S>::value_type S;
00394   typedef typename std::iterator_traits<Iter_T>::value_type T;
00395   typedef typename std::iterator_traits<Iter_U>::value_type U;
00396   CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00397 }
00398 
00399 #else //=======================================================================
00400 
00401 template <class S, class T, class U, class CoinCompare3> void
00402 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
00403 {
00404   const size_t len = coinDistance(sfirst,slast);
00405   if (len <= 1)
00406     return;
00407 
00408   typedef CoinTriple<S,T,U> STU_triple;
00409   STU_triple* x =
00410     static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00411 
00412   size_t i = 0;
00413   S* scurrent = sfirst;
00414   T* tcurrent = tfirst;
00415   U* ucurrent = ufirst;
00416   while (scurrent != slast) {
00417     new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00418   }
00419 
00420   std::sort(x, x+len, tc);
00421 
00422   scurrent = sfirst;
00423   tcurrent = tfirst;
00424   ucurrent = ufirst;
00425   for (i = 0; i < len; ++i) {
00426     *scurrent++ = x[i].first;
00427     *tcurrent++ = x[i].second;
00428     *ucurrent++ = x[i].third;
00429   }
00430 
00431   ::operator delete(x);
00432 }
00433 //-----------------------------------------------------------------------------
00434 template <class S, class T, class U> void
00435 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
00436 {
00437   CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00438 }
00439 
00440 #endif
00441 
00442 //#############################################################################
00443 
00444 #endif

Generated on Thu May 15 21:59:05 2008 by  doxygen 1.4.7