20 #ifndef COIN_USE_EKK_SORT
21 #define COIN_USE_EKK_SORT
29 template <
class S,
class T>
47 template <
class S,
class T>
58 template <
class S,
class T>
69 template <
class S,
class T>
84 template <
class S,
class T>
101 template <
class S,
class T,
class V>
119 template <
class S,
class T,
class V>
142 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
143 template <
class Iter_S,
class Iter_T,
class CoinCompare2>
void
144 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst,
const CoinCompare2& pc)
146 typedef typename std::iterator_traits<Iter_S>::value_type S;
147 typedef typename std::iterator_traits<Iter_T>::value_type T;
153 ST_pair* x =
static_cast<ST_pair*
>(::operator
new(len *
sizeof(ST_pair)));
155 memset(x,0,(len*
sizeof(ST_pair))) ;
159 Iter_S scurrent = sfirst;
160 Iter_T tcurrent = tfirst;
161 while (scurrent != slast) {
162 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
165 std::sort(x.begin(), x.end(), pc);
169 for (i = 0; i < len; ++i) {
170 *scurrent++ = x[i].first;
171 *tcurrent++ = x[i].second;
174 ::operator
delete(x);
177 template <
class Iter_S,
class Iter_T>
void
178 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
180 typedef typename std::iterator_traits<Iter_S>::value_type S;
181 typedef typename std::iterator_traits<Iter_T>::value_type T;
185 #else //=======================================================================
187 template <
class S,
class T,
class CoinCompare2>
void
188 CoinSort_2(S* sfirst, S* slast, T* tfirst,
const CoinCompare2& pc)
195 ST_pair* x =
static_cast<ST_pair*
>(::operator
new(len *
sizeof(ST_pair)));
199 memset(x,0,(len*
sizeof(ST_pair))) ;
203 S* scurrent = sfirst;
204 T* tcurrent = tfirst;
205 while (scurrent != slast) {
206 new (x+i++) ST_pair(*scurrent++, *tcurrent++);
209 std::sort(x, x + len, pc);
213 for (i = 0; i < len; ++i) {
214 *scurrent++ = x[i].first;
215 *tcurrent++ = x[i].second;
218 ::operator
delete(x);
220 template <
class S,
class T>
void
226 #ifndef COIN_USE_EKK_SORT
228 template <
class S,
class T>
void
235 extern int boundary_sort;
236 extern int boundary_sort2;
237 extern int boundary_sort3;
239 template <
class S,
class T>
void
245 }
else if (number>10000) {
250 if (number==boundary_sort3) {
251 printf(
"before sort %d entries\n",number);
252 for (
int j=0;j<number;j++) {
253 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
255 std::cout<<std::endl;
259 int n =
static_cast<int>(number);
263 S * ls[32] , * rs[32];
279 sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
282 if ( rs[sp] - ls[sp] > minsize )
284 l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
287 t = *l ; *l = *m ; *m = t ;
288 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
292 t = *m ; *m = *r ; *r = t ;
293 it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
296 t = *l ; *l = *m ; *m = t ;
297 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
303 while ( *(++l) < c ) ;
304 while ( *(--r) > c ) ;
305 t = *l ; *l = *r ; *r = t ;
306 it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
310 { ls[sp+1] = ls[sp] ;
323 for ( l = v , m = v + (n-1) ; l < m ; l++ )
327 it = array2[(l-v)+1] ;
328 for ( r = l ; r >= v && *r > c ; r-- )
331 array2[(r-v)+1] = array2[(r-v)] ;
334 array2[(r-v)+1] = it ;
338 if (number==boundary_sort3) {
339 printf(
"after sort %d entries\n",number);
340 for (
int j=0;j<number;j++) {
341 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
343 std::cout<<std::endl;
344 CoinSort_2Many(key, lastKey, array2);
345 printf(
"after2 sort %d entries\n",number);
346 for (
int j=0;j<number;j++) {
347 std::cout<<
" ( "<<key[j]<<
","<<array2[j]<<
")";
349 std::cout<<std::endl;
355 template <
class S,
class T>
void
361 if (number == 2 && key[0] > key[1]) {
365 array2[0] = array2[1];
370 }
else if (number>10000) {
379 S * ls[32] , * rs[32];
395 sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
398 if ( rs[sp] - ls[sp] > minsize )
400 l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
403 t = *l ; *l = *m ; *m = t ;
404 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
408 t = *m ; *m = *r ; *r = t ;
409 it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
412 t = *l ; *l = *m ; *m = t ;
413 it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
419 while ( *(++l) < c ) ;
420 while ( *(--r) > c ) ;
421 t = *l ; *l = *r ; *r = t ;
422 it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
426 { ls[sp+1] = ls[sp] ;
439 for ( l = v , m = v + (n-1) ; l < m ; l++ )
443 it = array2[(l-v)+1] ;
444 for ( r = l ; r >= v && *r > c ; r-- )
447 array2[(r-v)+1] = array2[(r-v)] ;
450 array2[(r-v)+1] = it ;
458 template <
class S,
class T,
class U>
477 template <
class S,
class T,
class U >
488 template <
class S,
class T,
class U >
499 template <
class S,
class T,
class U >
508 return t1Abs < t2Abs;
514 template <
class S,
class T,
class U >
523 return t1Abs > t2Abs;
532 template <
class S,
class T,
class U,
class V>
550 template <
class S,
class T,
class U,
class V>
586 #ifdef COIN_SORT_ARBITRARY_CONTAINERS
587 template <
class Iter_S,
class Iter_T,
class Iter_U,
class CoinCompare3>
void
588 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
589 const CoinCompare3& tc)
591 typedef typename std::iterator_traits<Iter_S>::value_type S;
592 typedef typename std::iterator_traits<Iter_T>::value_type T;
593 typedef typename std::iterator_traits<Iter_U>::value_type U;
600 static_cast<STU_triple*
>(::operator
new(len *
sizeof(STU_triple)));
603 Iter_S scurrent = sfirst;
604 Iter_T tcurrent = tfirst;
605 Iter_U ucurrent = ufirst;
606 while (scurrent != slast) {
607 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
610 std::sort(x, x+len, tc);
615 for (i = 0; i < len; ++i) {
616 *scurrent++ = x[i].first;
617 *tcurrent++ = x[i].second;
618 *ucurrent++ = x[i].third;
621 ::operator
delete(x);
624 template <
class Iter_S,
class Iter_T,
class Iter_U>
void
625 CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
627 typedef typename std::iterator_traits<Iter_S>::value_type S;
628 typedef typename std::iterator_traits<Iter_T>::value_type T;
629 typedef typename std::iterator_traits<Iter_U>::value_type U;
633 #else //=======================================================================
635 template <
class S,
class T,
class U,
class CoinCompare3>
void
636 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst,
const CoinCompare3& tc)
644 static_cast<STU_triple*
>(::operator
new(len *
sizeof(STU_triple)));
647 S* scurrent = sfirst;
648 T* tcurrent = tfirst;
649 U* ucurrent = ufirst;
650 while (scurrent != slast) {
651 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
654 std::sort(x, x+len, tc);
659 for (i = 0; i < len; ++i) {
660 *scurrent++ = x[i].first;
661 *tcurrent++ = x[i].second;
662 *ucurrent++ = x[i].third;
665 ::operator
delete(x);
668 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 CoinShortSort_2(S *key, S *lastKey, T *array2)
Sort without new and delete.
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.