CoinUtils 2.11.10
Loading...
Searching...
No Matches
CoinSort.hpp
Go to the documentation of this file.
1/* $Id$ */
2// Copyright (C) 2000, International Business Machines
3// Corporation and others. All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6#ifndef CoinSort_H
7#define CoinSort_H
8
9#include <functional>
10#include <new>
11#include <algorithm>
12#include "CoinDistance.hpp"
13
14// Uncomment the next three lines to get thorough initialisation of memory.
15// #ifndef ZEROFAULT
16// #define ZEROFAULT
17// #endif
18
19#ifdef COIN_FAST_CODE
20#ifndef COIN_USE_EKK_SORT
21#define COIN_USE_EKK_SORT
22#endif
23#endif
24
25//#############################################################################
26
29template < class S, class T >
30struct CoinPair {
31public:
36
37public:
39 CoinPair(const S &s, const T &t)
40 : first(s)
41 , second(t)
42 {
43 }
44};
45
46//#############################################################################
47
52template < class S, class T >
54public:
56 inline bool operator()(const CoinPair< S, T > &t1,
57 const CoinPair< S, T > &t2) const
58 {
59 return t1.first < t2.first;
60 }
61};
62//-----------------------------------------------------------------------------
65template < class S, class T >
67public:
69 inline bool operator()(const CoinPair< S, T > &t1,
70 const CoinPair< S, T > &t2) const
71 {
72 return t1.first > t2.first;
73 }
74};
75//-----------------------------------------------------------------------------
78template < class S, class T >
80public:
82 inline bool operator()(const CoinPair< S, T > &t1,
83 const CoinPair< S, T > &t2) const
84 {
85 const T t1Abs = t1.first < static_cast< T >(0) ? -t1.first : t1.first;
86 const T t2Abs = t2.first < static_cast< T >(0) ? -t2.first : t2.first;
87 return t1Abs < t2Abs;
88 }
89};
90//-----------------------------------------------------------------------------
93template < class S, class T >
95public:
98 {
99 const T t1Abs = t1.first < static_cast< T >(0) ? -t1.first : t1.first;
100 const T t2Abs = t2.first < static_cast< T >(0) ? -t2.first : t2.first;
101 return t1Abs > t2Abs;
102 }
103};
104//-----------------------------------------------------------------------------
110template < class S, class T, class V >
112private:
114
115private:
116 const V *vec_;
117
118public:
119 inline bool operator()(const CoinPair< S, T > &t1,
120 const CoinPair< S, T > &t2) const
121 {
122 return vec_[t1.first] < vec_[t2.first];
123 }
125 : vec_(v)
126 {
127 }
128};
129//-----------------------------------------------------------------------------
135template < class S, class T, class V >
137private:
139
140private:
141 const V *vec_;
142
143public:
144 inline bool operator()(const CoinPair< S, T > &t1,
145 const CoinPair< S, T > &t2) const
146 {
147 return vec_[t1.first] > vec_[t2.first];
148 }
150 : vec_(v)
151 {
152 }
153};
155
156//#############################################################################
157
165#ifdef COIN_SORT_ARBITRARY_CONTAINERS
166template < class Iter_S, class Iter_T, class CoinCompare2 >
167void CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst, const CoinCompare2 &pc)
168{
169 typedef typename std::iterator_traits< Iter_S >::value_type S;
170 typedef typename std::iterator_traits< Iter_T >::value_type T;
171 const size_t len = coinDistance(sfirst, slast);
172 if (len <= 1)
173 return;
174
175 typedef CoinPair< S, T > ST_pair;
176 ST_pair *x = static_cast< ST_pair * >(::operator new(len * sizeof(ST_pair)));
177#ifdef ZEROFAULT
178 memset(x, 0, (len * sizeof(ST_pair)));
179#endif
180
181 int i = 0;
182 Iter_S scurrent = sfirst;
183 Iter_T tcurrent = tfirst;
184 while (scurrent != slast) {
185 new (x + i++) ST_pair(*scurrent++, *tcurrent++);
186 }
187
188 std::sort(x.begin(), x.end(), pc);
189
190 scurrent = sfirst;
191 tcurrent = tfirst;
192 for (i = 0; i < len; ++i) {
193 *scurrent++ = x[i].first;
194 *tcurrent++ = x[i].second;
195 }
196
197 ::operator delete(x);
198}
199//-----------------------------------------------------------------------------
200template < class Iter_S, class Iter_T >
201void CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
202{
203 typedef typename std::iterator_traits< Iter_S >::value_type S;
204 typedef typename std::iterator_traits< Iter_T >::value_type T;
205 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2< S, T >());
206}
207
208#else //=======================================================================
209
210template < class S, class T, class CoinCompare2 >
211void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
212{
213 const size_t len = coinDistance(sfirst, slast);
214 if (len <= 1)
215 return;
216
217 typedef CoinPair< S, T > ST_pair;
218 ST_pair *x = static_cast< ST_pair * >(::operator new(len * sizeof(ST_pair)));
219#ifdef ZEROFAULT
220 // Can show RUI errors on some systems due to copy of ST_pair with gaps.
221 // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro.
222 memset(x, 0, (len * sizeof(ST_pair)));
223#endif
224
225 size_t i = 0;
226 S *scurrent = sfirst;
227 T *tcurrent = tfirst;
228 while (scurrent != slast) {
229 new (x + i++) ST_pair(*scurrent++, *tcurrent++);
230 }
231
232 std::sort(x, x + len, pc);
233
234 scurrent = sfirst;
235 tcurrent = tfirst;
236 for (i = 0; i < len; ++i) {
237 *scurrent++ = x[i].first;
238 *tcurrent++ = x[i].second;
239 }
240
241 ::operator delete(x);
242}
243template < class S, class T >
244void
245// This Always uses std::sort
246CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
247{
248 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2< S, T >());
249}
250#ifndef COIN_USE_EKK_SORT
251//-----------------------------------------------------------------------------
252template < class S, class T >
253void CoinSort_2(S *sfirst, S *slast, T *tfirst)
254{
255 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2< S, T >());
256}
257#else
258//-----------------------------------------------------------------------------
259extern int boundary_sort;
260extern int boundary_sort2;
261extern int boundary_sort3;
263template < class S, class T >
264void CoinSort_2(S *key, S *lastKey, T *array2)
265{
266 const size_t number = coinDistance(key, lastKey);
267 if (number <= 1) {
268 return;
269 } else if (number > 10000) {
270 CoinSort_2Std(key, lastKey, array2);
271 return;
272 }
273#if 0
274 if (number==boundary_sort3) {
275 printf("before sort %d entries\n",number);
276 for (int j=0;j<number;j++) {
277 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
278 }
279 std::cout<<std::endl;
280 }
281#endif
282 int minsize = 10;
283 int n = static_cast< int >(number);
284 int sp;
285 S *v = key;
286 S *m, t;
287 S *ls[32], *rs[32];
288 S *l, *r, c;
289 T it;
290 int j;
291 /*check already sorted */
292 S last = key[0];
293 for (j = 1; j < n; j++) {
294 if (key[j] >= last) {
295 last = key[j];
296 } else {
297 break;
298 } /* endif */
299 } /* endfor */
300 if (j == n) {
301 return;
302 } /* endif */
303 sp = 0;
304 ls[sp] = v;
305 rs[sp] = v + (n - 1);
306 while (sp >= 0) {
307 if (rs[sp] - ls[sp] > minsize) {
308 l = ls[sp];
309 r = rs[sp];
310 m = l + (r - l) / 2;
311 if (*l > *m) {
312 t = *l;
313 *l = *m;
314 *m = t;
315 it = array2[l - v];
316 array2[l - v] = array2[m - v];
317 array2[m - v] = it;
318 }
319 if (*m > *r) {
320 t = *m;
321 *m = *r;
322 *r = t;
323 it = array2[m - v];
324 array2[m - v] = array2[r - v];
325 array2[r - v] = it;
326 if (*l > *m) {
327 t = *l;
328 *l = *m;
329 *m = t;
330 it = array2[l - v];
331 array2[l - v] = array2[m - v];
332 array2[m - v] = it;
333 }
334 }
335 c = *m;
336 while (r - l > 1) {
337 while (*(++l) < c)
338 ;
339 while (*(--r) > c)
340 ;
341 t = *l;
342 *l = *r;
343 *r = t;
344 it = array2[l - v];
345 array2[l - v] = array2[r - v];
346 array2[r - v] = it;
347 }
348 l = r - 1;
349 if (l < m) {
350 ls[sp + 1] = ls[sp];
351 rs[sp + 1] = l;
352 ls[sp] = r;
353 } else {
354 ls[sp + 1] = r;
355 rs[sp + 1] = rs[sp];
356 rs[sp] = l;
357 }
358 sp++;
359 } else
360 sp--;
361 }
362 for (l = v, m = v + (n - 1); l < m; l++) {
363 if (*l > *(l + 1)) {
364 c = *(l + 1);
365 it = array2[(l - v) + 1];
366 for (r = l; r >= v && *r > c; r--) {
367 *(r + 1) = *r;
368 array2[(r - v) + 1] = array2[(r - v)];
369 }
370 *(r + 1) = c;
371 array2[(r - v) + 1] = it;
372 }
373 }
374#if 0
375 if (number==boundary_sort3) {
376 printf("after sort %d entries\n",number);
377 for (int j=0;j<number;j++) {
378 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
379 }
380 std::cout<<std::endl;
381 CoinSort_2Many(key, lastKey, array2);
382 printf("after2 sort %d entries\n",number);
383 for (int j=0;j<number;j++) {
384 std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
385 }
386 std::cout<<std::endl;
387 }
388#endif
389}
390#endif
391#endif
393template < class S, class T >
394void CoinShortSort_2(S *key, S *lastKey, T *array2)
395{
396 const size_t number = coinDistance(key, lastKey);
397 if (number <= 2) {
398 if (number == 2 && key[0] > key[1]) {
399 S tempS = key[0];
400 T tempT = array2[0];
401 key[0] = key[1];
402 array2[0] = array2[1];
403 key[1] = tempS;
404 array2[1] = tempT;
405 }
406 return;
407 } else if (number > 10000) {
408 CoinSort_2Std(key, lastKey, array2);
409 return;
410 }
411 int minsize = 10;
412 size_t n = number;
413 int sp;
414 S *v = key;
415 S *m, t;
416 S *ls[32], *rs[32];
417 S *l, *r, c;
418 T it;
419 size_t j;
420 /*check already sorted */
421 S last = key[0];
422 for (j = 1; j < n; j++) {
423 if (key[j] >= last) {
424 last = key[j];
425 } else {
426 break;
427 } /* endif */
428 } /* endfor */
429 if (j == n) {
430 return;
431 } /* endif */
432 sp = 0;
433 ls[sp] = v;
434 rs[sp] = v + (n - 1);
435 while (sp >= 0) {
436 if (rs[sp] - ls[sp] > minsize) {
437 l = ls[sp];
438 r = rs[sp];
439 m = l + (r - l) / 2;
440 if (*l > *m) {
441 t = *l;
442 *l = *m;
443 *m = t;
444 it = array2[l - v];
445 array2[l - v] = array2[m - v];
446 array2[m - v] = it;
447 }
448 if (*m > *r) {
449 t = *m;
450 *m = *r;
451 *r = t;
452 it = array2[m - v];
453 array2[m - v] = array2[r - v];
454 array2[r - v] = it;
455 if (*l > *m) {
456 t = *l;
457 *l = *m;
458 *m = t;
459 it = array2[l - v];
460 array2[l - v] = array2[m - v];
461 array2[m - v] = it;
462 }
463 }
464 c = *m;
465 while (r - l > 1) {
466 while (*(++l) < c)
467 ;
468 while (*(--r) > c)
469 ;
470 t = *l;
471 *l = *r;
472 *r = t;
473 it = array2[l - v];
474 array2[l - v] = array2[r - v];
475 array2[r - v] = it;
476 }
477 l = r - 1;
478 if (l < m) {
479 ls[sp + 1] = ls[sp];
480 rs[sp + 1] = l;
481 ls[sp] = r;
482 } else {
483 ls[sp + 1] = r;
484 rs[sp + 1] = rs[sp];
485 rs[sp] = l;
486 }
487 sp++;
488 } else
489 sp--;
490 }
491 for (l = v, m = v + (n - 1); l < m; l++) {
492 if (*l > *(l + 1)) {
493 c = *(l + 1);
494 it = array2[(l - v) + 1];
495 for (r = l; r >= v && *r > c; r--) {
496 *(r + 1) = *r;
497 array2[(r - v) + 1] = array2[(r - v)];
498 }
499 *(r + 1) = c;
500 array2[(r - v) + 1] = it;
501 }
502 }
503}
504//#############################################################################
505//#############################################################################
506
508template < class S, class T, class U >
510public:
517
518public:
520 CoinTriple(const S &s, const T &t, const U &u)
521 : first(s)
522 , second(t)
523 , third(u)
524 {
525 }
526};
527
528//#############################################################################
533template < class S, class T, class U >
535public:
537 inline bool operator()(const CoinTriple< S, T, U > &t1,
538 const CoinTriple< S, T, U > &t2) const
539 {
540 return t1.first < t2.first;
541 }
542};
543//-----------------------------------------------------------------------------
546template < class S, class T, class U >
548public:
550 inline bool operator()(const CoinTriple< S, T, U > &t1,
551 const CoinTriple< S, T, U > &t2) const
552 {
553 return t1.first > t2.first;
554 }
555};
556//-----------------------------------------------------------------------------
559template < class S, class T, class U >
561public:
563 inline bool operator()(const CoinTriple< S, T, U > &t1,
564 const CoinTriple< S, T, U > &t2) const
565 {
566 const T t1Abs = t1.first < static_cast< T >(0) ? -t1.first : t1.first;
567 const T t2Abs = t2.first < static_cast< T >(0) ? -t2.first : t2.first;
568 return t1Abs < t2Abs;
569 }
570};
571//-----------------------------------------------------------------------------
574template < class S, class T, class U >
576public:
578 inline bool operator()(const CoinTriple< S, T, U > &t1,
579 const CoinTriple< S, T, U > &t2) const
580 {
581 const T t1Abs = t1.first < static_cast< T >(0) ? -t1.first : t1.first;
582 const T t2Abs = t2.first < static_cast< T >(0) ? -t2.first : t2.first;
583 return t1Abs > t2Abs;
584 }
585};
586//-----------------------------------------------------------------------------
592template < class S, class T, class U, class V >
594private:
596
597private:
598 const V *vec_;
599
600public:
601 inline bool operator()(const CoinTriple< S, T, U > &t1,
602 const CoinTriple< S, T, U > &t2) const
603 {
604 return vec_[t1.first] < vec_[t2.first];
605 }
607 : vec_(v)
608 {
609 }
610};
611//-----------------------------------------------------------------------------
617template < class S, class T, class U, class V >
619private:
621
622private:
623 const V *vec_;
624
625public:
626 inline bool operator()(const CoinTriple< S, T, U > &t1,
627 const CoinTriple< S, T, U > &t2) const
628 {
629 return vec_[t1.first] > vec_[t2.first];
630 }
632 : vec_(v)
633 {
634 }
635};
637
638//#############################################################################
639
650
651//#############################################################################
652
660#ifdef COIN_SORT_ARBITRARY_CONTAINERS
661template < class Iter_S, class Iter_T, class Iter_U, class CoinCompare3 >
662void CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
663 const CoinCompare3 &tc)
664{
665 typedef typename std::iterator_traits< Iter_S >::value_type S;
666 typedef typename std::iterator_traits< Iter_T >::value_type T;
667 typedef typename std::iterator_traits< Iter_U >::value_type U;
668 const size_t len = coinDistance(sfirst, slast);
669 if (len <= 1)
670 return;
671
672 typedef CoinTriple< S, T, U > STU_triple;
673 STU_triple *x = static_cast< STU_triple * >(::operator new(len * sizeof(STU_triple)));
674
675 int i = 0;
676 Iter_S scurrent = sfirst;
677 Iter_T tcurrent = tfirst;
678 Iter_U ucurrent = ufirst;
679 while (scurrent != slast) {
680 new (x + i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
681 }
682
683 std::sort(x, x + len, tc);
684
685 scurrent = sfirst;
686 tcurrent = tfirst;
687 ucurrent = ufirst;
688 for (i = 0; i < len; ++i) {
689 *scurrent++ = x[i].first;
690 *tcurrent++ = x[i].second;
691 *ucurrent++ = x[i].third;
692 }
693
694 ::operator delete(x);
695}
696//-----------------------------------------------------------------------------
697template < class Iter_S, class Iter_T, class Iter_U >
698void CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
699{
700 typedef typename std::iterator_traits< Iter_S >::value_type S;
701 typedef typename std::iterator_traits< Iter_T >::value_type T;
702 typedef typename std::iterator_traits< Iter_U >::value_type U;
703 CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3< S, T, U >());
704}
705
706#else //=======================================================================
707
708template < class S, class T, class U, class CoinCompare3 >
709void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
710{
711 const size_t len = coinDistance(sfirst, slast);
712 if (len <= 1)
713 return;
714
715 typedef CoinTriple< S, T, U > STU_triple;
716 STU_triple *x = static_cast< STU_triple * >(::operator new(len * sizeof(STU_triple)));
717
718 size_t i = 0;
719 S *scurrent = sfirst;
720 T *tcurrent = tfirst;
721 U *ucurrent = ufirst;
722 while (scurrent != slast) {
723 new (x + i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
724 }
725
726 std::sort(x, x + len, tc);
727
728 scurrent = sfirst;
729 tcurrent = tfirst;
730 ucurrent = ufirst;
731 for (i = 0; i < len; ++i) {
732 *scurrent++ = x[i].first;
733 *tcurrent++ = x[i].second;
734 *ucurrent++ = x[i].third;
735 }
736
737 ::operator delete(x);
738}
739//-----------------------------------------------------------------------------
740template < class S, class T, class U >
741void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst)
742{
743 CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3< S, T, U >());
744}
745
746#endif
747
748//#############################################################################
749
750#endif
751
752/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
753*/
void coinDistance(ForwardIterator first, ForwardIterator last, Distance &n)
CoinDistance.
void CoinShortSort_2(S *key, S *lastKey, T *array2)
Sort without new and delete.
Definition CoinSort.hpp:394
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
Definition CoinSort.hpp:648
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
Definition CoinSort.hpp:211
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
Definition CoinSort.hpp:246
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
Definition CoinSort.hpp:709
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
Definition CoinSort.hpp:645
CoinExternalVectorFirstGreater_2(const V *v)
Definition CoinSort.hpp:149
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition CoinSort.hpp:144
CoinExternalVectorFirstGreater_3(const V *v)
Definition CoinSort.hpp:631
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition CoinSort.hpp:626
CoinExternalVectorFirstLess_2(const V *v)
Definition CoinSort.hpp:124
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition CoinSort.hpp:119
CoinExternalVectorFirstLess_3(const V *v)
Definition CoinSort.hpp:606
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition CoinSort.hpp:601
Function operator.
Definition CoinSort.hpp:94
bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
Compare function.
Definition CoinSort.hpp:97
Function operator.
Definition CoinSort.hpp:575
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition CoinSort.hpp:578
Function operator.
Definition CoinSort.hpp:79
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition CoinSort.hpp:82
Function operator.
Definition CoinSort.hpp:560
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition CoinSort.hpp:563
Function operator.
Definition CoinSort.hpp:66
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition CoinSort.hpp:69
Function operator.
Definition CoinSort.hpp:547
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition CoinSort.hpp:550
Function operator.
Definition CoinSort.hpp:53
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition CoinSort.hpp:56
Function operator.
Definition CoinSort.hpp:534
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition CoinSort.hpp:537
T second
Second member of triple.
Definition CoinSort.hpp:514
S first
First member of triple.
Definition CoinSort.hpp:512
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
Definition CoinSort.hpp:520
U third
Third member of triple.
Definition CoinSort.hpp:516
An ordered pair.
Definition CoinSort.hpp:30
S first
First member of pair.
Definition CoinSort.hpp:33
CoinPair(const S &s, const T &t)
Construct from ordered pair.
Definition CoinSort.hpp:39
T second
Second member of pair.
Definition CoinSort.hpp:35