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

- File List
- File Members

# /home/coin/SVN-release/Clp-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(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