00001
00002
00003 #ifndef CoinSort_H
00004 #define CoinSort_H
00005
00006 #include <functional>
00007 #include <new>
00008 #include <CoinDistance.hpp>
00009
00010
00011
00014 template <class S, class T>
00015 struct CoinPair {
00016 public:
00018 S first;
00020 T second;
00021 public:
00023 CoinPair(const S& s, const T& t) : first(s), second(t) {}
00024 };
00025
00026
00027
00032 template < class S, class T>
00033 class CoinFirstLess_2 {
00034 public:
00036 inline bool operator()(const CoinPair<S,T>& t1,
00037 const CoinPair<S,T>& t2) const
00038 { return t1.first < t2.first; }
00039 };
00040
00043 template < class S, class T>
00044 class CoinFirstGreater_2 {
00045 public:
00047 inline bool operator()(const CoinPair<S,T>& t1,
00048 const CoinPair<S,T>& t2) const
00049 { return t1.first > t2.first; }
00050 };
00051
00054 template < class S, class T>
00055 class CoinFirstAbsLess_2 {
00056 public:
00058 inline bool operator()(const CoinPair<S,T>& t1,
00059 const CoinPair<S,T>& t2) const
00060 {
00061 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00062 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00063 return t1Abs < t2Abs;
00064 }
00065 };
00066
00069 template < class S, class T>
00070 class CoinFirstAbsGreater_2 {
00071 public:
00073 inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
00074 {
00075 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00076 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00077 return t1Abs > t2Abs;
00078 }
00079 };
00080
00086 template < class S, class T, class V>
00087 class CoinExternalVectorFirstLess_2 {
00088 private:
00089 CoinExternalVectorFirstLess_2();
00090 private:
00091 const V* vec_;
00092 public:
00093 inline bool operator()(const CoinPair<S,T>& t1,
00094 const CoinPair<S,T>& t2) const
00095 { return vec_[t1.first] < vec_[t2.first]; }
00096 CoinExternalVectorFirstLess_2(const V* v) : vec_(v) {}
00097 };
00098
00104 template < class S, class T, class V>
00105 class CoinExternalVectorFirstGreater_2 {
00106 private:
00107 CoinExternalVectorFirstGreater_2();
00108 private:
00109 const V* vec_;
00110 public:
00111 inline bool operator()(const CoinPair<S,T>& t1,
00112 const CoinPair<S,T>& t2) const
00113 { return vec_[t1.first] > vec_[t2.first]; }
00114 CoinExternalVectorFirstGreater_2(const V* v) : vec_(v) {}
00115 };
00117
00118
00119
00127 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00128 template <class Iter_S, class Iter_T, class CoinCompare2> void
00129 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst, const CoinCompare2& pc)
00130 {
00131 typedef typename std::iterator_traits<Iter_S>::value_type S;
00132 typedef typename std::iterator_traits<Iter_T>::value_type T;
00133 const int len = coinDistance(sfirst, slast);
00134 if (len <= 1)
00135 return;
00136
00137 typedef CoinPair<S,T> ST_pair;
00138 ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
00139
00140 int i = 0;
00141 Iter_S scurrent = sfirst;
00142 Iter_T tcurrent = tfirst;
00143 while (scurrent != slast) {
00144 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
00145 }
00146
00147 std::sort(x.begin(), x.end(), pc);
00148
00149 scurrent = sfirst;
00150 tcurrent = tfirst;
00151 for (i = 0; i < len; ++i) {
00152 *scurrent++ = x[i].first;
00153 *tcurrent++ = x[i].second;
00154 }
00155
00156 ::operator delete(x);
00157 }
00158
00159 template <class Iter_S, class Iter_T> void
00160 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
00161 {
00162 typedef typename std::iterator_traits<Iter_S>::value_type S;
00163 typedef typename std::iterator_traits<Iter_T>::value_type T;
00164 CoinSort_2(sfirts, slast, tfirst, CoinFirstLess_2<S,T>());
00165 }
00166
00167 #else //=======================================================================
00168
00169 template <class S, class T, class CoinCompare2> void
00170 CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
00171 {
00172 const int len = coinDistance(sfirst, slast);
00173 if (len <= 1)
00174 return;
00175
00176 typedef CoinPair<S,T> ST_pair;
00177 ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
00178
00179 int i = 0;
00180 S* scurrent = sfirst;
00181 T* tcurrent = tfirst;
00182 while (scurrent != slast) {
00183 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
00184 }
00185
00186
00187
00188
00189 std::sort(x, x + len, pc);
00190
00191 scurrent = sfirst;
00192 tcurrent = tfirst;
00193 for (i = 0; i < len; ++i) {
00194 *scurrent++ = x[i].first;
00195 *tcurrent++ = x[i].second;
00196 }
00197
00198 ::operator delete(x);
00199 }
00200
00201 template <class S, class T> void
00202 CoinSort_2(S* sfirst, S* slast, T* tfirst)
00203 {
00204 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
00205 }
00206
00207 #endif
00208
00209
00210
00211
00213 template <class S, class T, class U>
00214 class CoinTriple {
00215 public:
00217 S first;
00219 T second;
00221 U third;
00222 public:
00224 CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
00225 };
00226
00227
00232 template < class S, class T, class U >
00233 class CoinFirstLess_3 {
00234 public:
00236 inline bool operator()(const CoinTriple<S,T,U>& t1,
00237 const CoinTriple<S,T,U>& t2) const
00238 { return t1.first < t2.first; }
00239 };
00240
00243 template < class S, class T, class U >
00244 class CoinFirstGreater_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 CoinFirstAbsLess_3 {
00256 public:
00258 inline bool operator()(const CoinTriple<S,T,U>& t1,
00259 const CoinTriple<S,T,U>& t2) const
00260 {
00261 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00262 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00263 return t1Abs < t2Abs;
00264 }
00265 };
00266
00269 template < class S, class T, class U >
00270 class CoinFirstAbsGreater_3 {
00271 public:
00273 inline bool operator()(const CoinTriple<S,T,U>& t1,
00274 const CoinTriple<S,T,U>& t2) const
00275 {
00276 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
00277 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
00278 return t1Abs > t2Abs;
00279 }
00280 };
00281
00287 template < class S, class T, class U, class V>
00288 class CoinExternalVectorFirstLess_3 {
00289 private:
00290 CoinExternalVectorFirstLess_3();
00291 private:
00292 const V* vec_;
00293 public:
00294 inline bool operator()(const CoinTriple<S,T,U>& t1,
00295 const CoinTriple<S,T,U>& t2) const
00296 { return vec_[t1.first] < vec_[t2.first]; }
00297 CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
00298 };
00299
00305 template < class S, class T, class U, class V>
00306 class CoinExternalVectorFirstGreater_3 {
00307 private:
00308 CoinExternalVectorFirstGreater_3();
00309 private:
00310 const V* vec_;
00311 public:
00312 inline bool operator()(const CoinTriple<S,T,U>& t1,
00313 const CoinTriple<S,T,U>& t2) const
00314 { return vec_[t1.first] > vec_[t2.first]; }
00315 CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
00316 };
00318
00319
00320
00324
00325 typedef CoinExternalVectorFirstLess_3<int, int, double, double>
00326 CoinIncrSolutionOrdered;
00328 typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
00329 CoinDecrSolutionOrdered;
00331
00332
00333
00341 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
00342 template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
00343 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
00344 const CoinCompare3& tc)
00345 {
00346 typedef typename std::iterator_traits<Iter_S>::value_type S;
00347 typedef typename std::iterator_traits<Iter_T>::value_type T;
00348 typedef typename std::iterator_traits<Iter_U>::value_type U;
00349 const int len = coinDistance(sfirst, slast);
00350 if (len <= 1)
00351 return;
00352
00353 typedef CoinTriple<S,T,U> STU_triple;
00354 STU_triple* x =
00355 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00356
00357 int i = 0;
00358 Iter_S scurrent = sfirst;
00359 Iter_T tcurrent = tfirst;
00360 Iter_U ucurrent = ufirst;
00361 while (scurrent != slast) {
00362 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00363 }
00364
00365 std::sort(x, x+len, tc);
00366
00367 scurrent = sfirst;
00368 tcurrent = tfirst;
00369 ucurrent = ufirst;
00370 for (i = 0; i < len; ++i) {
00371 *scurrent++ = x[i].first;
00372 *tcurrent++ = x[i].second;
00373 *ucurrent++ = x[i].third;
00374 }
00375
00376 ::operator delete(x);
00377 }
00378
00379 template <class Iter_S, class Iter_T, class Iter_U> void
00380 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
00381 {
00382 typedef typename std::iterator_traits<Iter_S>::value_type S;
00383 typedef typename std::iterator_traits<Iter_T>::value_type T;
00384 typedef typename std::iterator_traits<Iter_U>::value_type U;
00385 CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00386 }
00387
00388 #else //=======================================================================
00389
00390 template <class S, class T, class U, class CoinCompare3> void
00391 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
00392 {
00393 const int len = coinDistance(sfirst,slast);
00394 if (len <= 1)
00395 return;
00396
00397 typedef CoinTriple<S,T,U> STU_triple;
00398 STU_triple* x =
00399 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
00400
00401 int i = 0;
00402 S* scurrent = sfirst;
00403 T* tcurrent = tfirst;
00404 U* ucurrent = ufirst;
00405 while (scurrent != slast) {
00406 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
00407 }
00408
00409 std::sort(x, x+len, tc);
00410
00411 scurrent = sfirst;
00412 tcurrent = tfirst;
00413 ucurrent = ufirst;
00414 for (i = 0; i < len; ++i) {
00415 *scurrent++ = x[i].first;
00416 *tcurrent++ = x[i].second;
00417 *ucurrent++ = x[i].third;
00418 }
00419
00420 ::operator delete(x);
00421 }
00422
00423 template <class S, class T, class U> void
00424 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
00425 {
00426 CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
00427 }
00428
00429 #endif
00430
00431
00432
00433 #endif