Cgl  0.60.3
CoinSort.hpp
Go to the documentation of this file.
1 /* \$Id: CoinSort.hpp 2083 2019-01-06 19:38:09Z unxusr \$ */
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
29 template < class S, class T >
30 struct CoinPair {
31 public:
33  S first;
35  T second;
36
37 public:
39  CoinPair(const S &s, const T &t)
40  : first(s)
41  , second(t)
42  {
43  }
44 };
45
46 //#############################################################################
47
52 template < class S, class T >
54 public:
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 //-----------------------------------------------------------------------------
65 template < class S, class T >
67 public:
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 //-----------------------------------------------------------------------------
78 template < class S, class T >
80 public:
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 //-----------------------------------------------------------------------------
93 template < class S, class T >
95 public:
97  inline bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
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 //-----------------------------------------------------------------------------
110 template < class S, class T, class V >
112 private:
114
115 private:
116  const V *vec_;
117
118 public:
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 //-----------------------------------------------------------------------------
135 template < class S, class T, class V >
137 private:
139
140 private:
141  const V *vec_;
142
143 public:
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
166 template < class Iter_S, class Iter_T, class CoinCompare2 >
167 void 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 //-----------------------------------------------------------------------------
200 template < class Iter_S, class Iter_T >
201 void 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
210 template < class S, class T, class CoinCompare2 >
211 void 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 }
243 template < class S, class T >
244 void
245 // This Always uses std::sort
246 CoinSort_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 //-----------------------------------------------------------------------------
252 template < class S, class T >
253 void CoinSort_2(S *sfirst, S *slast, T *tfirst)
254 {
255  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2< S, T >());
256 }
257 #else
258 //-----------------------------------------------------------------------------
259 extern int boundary_sort;
260 extern int boundary_sort2;
261 extern int boundary_sort3;
263 template < class S, class T >
264 void 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;
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
392 template < class S, class T >
394 void 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;
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
508 template < class S, class T, class U >
509 class CoinTriple {
510 public:
512  S first;
516  U third;
517
518 public:
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 //#############################################################################
533 template < class S, class T, class U >
535 public:
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 //-----------------------------------------------------------------------------
546 template < class S, class T, class U >
548 public:
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 //-----------------------------------------------------------------------------
559 template < class S, class T, class U >
561 public:
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 //-----------------------------------------------------------------------------
574 template < class S, class T, class U >
576 public:
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 //-----------------------------------------------------------------------------
592 template < class S, class T, class U, class V >
594 private:
596
597 private:
598  const V *vec_;
599
600 public:
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 //-----------------------------------------------------------------------------
617 template < class S, class T, class U, class V >
619 private:
621
622 private:
623  const V *vec_;
624
625 public:
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
661 template < class Iter_S, class Iter_T, class Iter_U, class CoinCompare3 >
662 void 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 //-----------------------------------------------------------------------------
697 template < class Iter_S, class Iter_T, class Iter_U >
698 void 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
708 template < class S, class T, class U, class CoinCompare3 >
709 void 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 //-----------------------------------------------------------------------------
740 template < class S, class T, class U >
741 void 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 */
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
Definition: CoinSort.hpp:648
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:56
CoinPair(const S &s, const T &t)
Construct from ordered pair.
Definition: CoinSort.hpp:39
CoinExternalVectorFirstGreater_3(const V *v)
Definition: CoinSort.hpp:631
CoinExternalVectorFirstLess_2(const V *v)
Definition: CoinSort.hpp:124
S first
First member of pair.
Definition: CoinSort.hpp:33
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition: CoinSort.hpp:626
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
Definition: CoinSort.hpp:520
An ordered pair.
Definition: CoinSort.hpp:30
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:578
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
Definition: CoinSort.hpp:211
void CoinShortSort_2(S *key, S *lastKey, T *array2)
Sort without new and delete.
Definition: CoinSort.hpp:394
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition: CoinSort.hpp:601
void coinDistance(ForwardIterator first, ForwardIterator last, Distance &n)
CoinDistance.
T second
Second member of pair.
Definition: CoinSort.hpp:35
CoinExternalVectorFirstLess_3(const V *v)
Definition: CoinSort.hpp:606
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
Definition: CoinSort.hpp:246
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:563
Function operator.
Definition: CoinSort.hpp:94
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:69
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:550
Function operator.
Definition: CoinSort.hpp:79
Function operator.
Definition: CoinSort.hpp:593
U third
Third member of triple.
Definition: CoinSort.hpp:516
Function operator.
Definition: CoinSort.hpp:53
Function operator.
Definition: CoinSort.hpp:111
S first
First member of triple.
Definition: CoinSort.hpp:512
bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
Compare function.
Definition: CoinSort.hpp:97
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:537
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition: CoinSort.hpp:144
T second
Second member of triple.
Definition: CoinSort.hpp:514
Function operator.
Definition: CoinSort.hpp:534
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:82
CoinExternalVectorFirstGreater_2(const V *v)
Definition: CoinSort.hpp:149
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
Definition: CoinSort.hpp:709
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition: CoinSort.hpp:119
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
Definition: CoinSort.hpp:645
Function operator.
Definition: CoinSort.hpp:575
Function operator.
Definition: CoinSort.hpp:66