21 template <
class S,
class T>
39 template <
class S,
class T>
50 template <
class S,
class T>
61 template <
class S,
class T>
76 template <
class S,
class T>
93 template <
class S,
class T,
class V>
111 template <
class S,
class T,
class V>
134 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
135 template <
class Iter_S,
class Iter_T,
class CoinCompare2>
void
136 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst,
const CoinCompare2& pc)
138 typedef typename std::iterator_traits<Iter_S>::value_type S;
139 typedef typename std::iterator_traits<Iter_T>::value_type T;
145 ST_pair* x =
static_cast<ST_pair*
>(::operator
new(len *
sizeof(ST_pair)));
147 memset(x,0,(len*
sizeof(ST_pair))) ;
151 Iter_S scurrent = sfirst;
152 Iter_T tcurrent = tfirst;
153 while (scurrent != slast) {
154 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
157 std::sort(x.begin(), x.end(), pc);
161 for (i = 0; i < len; ++i) {
162 *scurrent++ = x[i].first;
163 *tcurrent++ = x[i].second;
166 ::operator
delete(x);
169 template <
class Iter_S,
class Iter_T>
void
170 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
172 typedef typename std::iterator_traits<Iter_S>::value_type S;
173 typedef typename std::iterator_traits<Iter_T>::value_type T;
177 #else //=======================================================================
179 template <
class S,
class T,
class CoinCompare2>
void
180 CoinSort_2(S* sfirst, S* slast, T* tfirst,
const CoinCompare2& pc)
187 ST_pair* x =
static_cast<ST_pair*
>(::operator
new(len *
sizeof(ST_pair)));
191 memset(x,0,(len*
sizeof(ST_pair))) ;
195 S* scurrent = sfirst;
196 T* tcurrent = tfirst;
197 while (scurrent != slast) {
198 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
201 std::sort(x, x + len, pc);
205 for (i = 0; i < len; ++i) {
206 *scurrent++ = x[i].first;
207 *tcurrent++ = x[i].second;
210 ::operator
delete(x);
212 template <
class S,
class T>
void
218 #ifndef COIN_USE_EKK_SORT
220 template <
class S,
class T>
void
227 extern int boundary_sort;
228 extern int boundary_sort2;
229 extern int boundary_sort3;
231 template <
class S,
class T>
void
237 }
else if (number>10000) {
242 if (number==boundary_sort3) {
243 printf(
"before sort %d entries\n",number);
244 for (
int j=0;j<number;j++) {
245 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
247 std::cout<<std::endl;
255 S * ls[32] , * rs[32];
271 sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
274 if ( rs[sp] - ls[sp] > minsize )
276 l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
279 t = *l ; *l = *m ; *m = t ;
280 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
284 t = *m ; *m = *r ; *r = t ;
285 it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
288 t = *l ; *l = *m ; *m = t ;
289 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
295 while ( *(++l) < c ) ;
296 while ( *(--r) > c ) ;
297 t = *l ; *l = *r ; *r = t ;
298 it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
302 { ls[sp+1] = ls[sp] ;
315 for ( l = v , m = v + (n-1) ; l < m ; l++ )
319 it = array2[(l-v)+1] ;
320 for ( r = l ; r >= v && *r > c ; r-- )
323 array2[(r-v)+1] = array2[(r-v)] ;
326 array2[(r-v)+1] = it ;
330 if (number==boundary_sort3) {
331 printf(
"after sort %d entries\n",number);
332 for (
int j=0;j<number;j++) {
333 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
335 std::cout<<std::endl;
336 CoinSort_2Many(key, lastKey, array2);
337 printf(
"after2 sort %d entries\n",number);
338 for (
int j=0;j<number;j++) {
339 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
341 std::cout<<std::endl;
351 template <
class S,
class T,
class U>
370 template <
class S,
class T,
class U >
381 template <
class S,
class T,
class U >
392 template <
class S,
class T,
class U >
401 return t1Abs < t2Abs;
407 template <
class S,
class T,
class U >
416 return t1Abs > t2Abs;
425 template <
class S,
class T,
class U,
class V>
443 template <
class S,
class T,
class U,
class V>
479 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
480 template <
class Iter_S,
class Iter_T,
class Iter_U,
class CoinCompare3>
void
481 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
482 const CoinCompare3& tc)
484 typedef typename std::iterator_traits<Iter_S>::value_type S;
485 typedef typename std::iterator_traits<Iter_T>::value_type T;
486 typedef typename std::iterator_traits<Iter_U>::value_type U;
493 static_cast<STU_triple*
>(::operator
new(len *
sizeof(STU_triple)));
496 Iter_S scurrent = sfirst;
497 Iter_T tcurrent = tfirst;
498 Iter_U ucurrent = ufirst;
499 while (scurrent != slast) {
500 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
503 std::sort(x, x+len, tc);
508 for (i = 0; i < len; ++i) {
509 *scurrent++ = x[i].first;
510 *tcurrent++ = x[i].second;
511 *ucurrent++ = x[i].third;
514 ::operator
delete(x);
517 template <
class Iter_S,
class Iter_T,
class Iter_U>
void
518 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
520 typedef typename std::iterator_traits<Iter_S>::value_type S;
521 typedef typename std::iterator_traits<Iter_T>::value_type T;
522 typedef typename std::iterator_traits<Iter_U>::value_type U;
526 #else //=======================================================================
528 template <
class S,
class T,
class U,
class CoinCompare3>
void
529 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst,
const CoinCompare3& tc)
537 static_cast<STU_triple*
>(::operator
new(len *
sizeof(STU_triple)));
540 S* scurrent = sfirst;
541 T* tcurrent = tfirst;
542 U* ucurrent = ufirst;
543 while (scurrent != slast) {
544 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
547 std::sort(x, x+len, tc);
552 for (i = 0; i < len; ++i) {
553 *scurrent++ = x[i].first;
554 *tcurrent++ = x[i].second;
555 *ucurrent++ = x[i].third;
558 ::operator
delete(x);
561 template <
class S,
class T,
class U>
void
CoinExternalVectorFirstGreater_2(const V *v)
CoinExternalVectorFirstLess_2()
CoinExternalVectorFirstLess_3(const V *v)
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
U third
Third member of triple.
S first
First member of pair.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
CoinExternalVectorFirstGreater_2()
T second
Second member of triple.
T second
Second member of pair.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
void coinDistance(ForwardIterator first, ForwardIterator last, Distance &n)
CoinDistance.
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
S first
First member of triple.
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
CoinExternalVectorFirstLess_2(const V *v)
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
CoinPair(const S &s, const T &t)
Construct from ordered pair.
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
Compare function.
CoinExternalVectorFirstGreater_3(const V *v)
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
CoinExternalVectorFirstLess_3()
CoinExternalVectorFirstGreater_3()
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.