00001
00002
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
00012
00013
00014
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
00189
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