Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CoinSort.hpp
Go to the documentation of this file.
1 /* $Id: CoinSort.hpp 1594 2013-04-19 14:33:00Z forrest $ */
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 
29 template <class S, class T>
30 struct CoinPair {
31 public:
33  S first;
35  T second;
36 public:
38  CoinPair(const S& s, const T& t) : first(s), second(t) {}
39 };
40 
41 //#############################################################################
42 
47 template < class S, class T>
49 public:
51  inline bool operator()(const CoinPair<S,T>& t1,
52  const CoinPair<S,T>& t2) const
53  { return t1.first < t2.first; }
54 };
55 //-----------------------------------------------------------------------------
58 template < class S, class T>
60 public:
62  inline bool operator()(const CoinPair<S,T>& t1,
63  const CoinPair<S,T>& t2) const
64  { return t1.first > t2.first; }
65 };
66 //-----------------------------------------------------------------------------
69 template < class S, class T>
71 public:
73  inline bool operator()(const CoinPair<S,T>& t1,
74  const CoinPair<S,T>& t2) const
75  {
76  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
77  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
78  return t1Abs < t2Abs;
79  }
80 };
81 //-----------------------------------------------------------------------------
84 template < class S, class T>
86 public:
88  inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
89  {
90  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
91  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
92  return t1Abs > t2Abs;
93  }
94 };
95 //-----------------------------------------------------------------------------
101 template < class S, class T, class V>
103 private:
105 private:
106  const V* vec_;
107 public:
108  inline bool operator()(const CoinPair<S,T>& t1,
109  const CoinPair<S,T>& t2) const
110  { return vec_[t1.first] < vec_[t2.first]; }
112 };
113 //-----------------------------------------------------------------------------
119 template < class S, class T, class V>
121 private:
123 private:
124  const V* vec_;
125 public:
126  inline bool operator()(const CoinPair<S,T>& t1,
127  const CoinPair<S,T>& t2) const
128  { return vec_[t1.first] > vec_[t2.first]; }
130 };
132 
133 //#############################################################################
134 
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)
145 {
146  typedef typename std::iterator_traits<Iter_S>::value_type S;
147  typedef typename std::iterator_traits<Iter_T>::value_type T;
148  const size_t len = coinDistance(sfirst, slast);
149  if (len <= 1)
150  return;
151 
152  typedef CoinPair<S,T> ST_pair;
153  ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
154 # ifdef ZEROFAULT
155  memset(x,0,(len*sizeof(ST_pair))) ;
156 # endif
157 
158  int i = 0;
159  Iter_S scurrent = sfirst;
160  Iter_T tcurrent = tfirst;
161  while (scurrent != slast) {
162  new (x+i++) ST_pair(*scurrent++, *tcurrent++);
163  }
164 
165  std::sort(x.begin(), x.end(), pc);
166 
167  scurrent = sfirst;
168  tcurrent = tfirst;
169  for (i = 0; i < len; ++i) {
170  *scurrent++ = x[i].first;
171  *tcurrent++ = x[i].second;
172  }
173 
174  ::operator delete(x);
175 }
176 //-----------------------------------------------------------------------------
177 template <class Iter_S, class Iter_T> void
178 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
179 {
180  typedef typename std::iterator_traits<Iter_S>::value_type S;
181  typedef typename std::iterator_traits<Iter_T>::value_type T;
182  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
183 }
184 
185 #else //=======================================================================
186 
187 template <class S, class T, class CoinCompare2> void
188 CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
189 {
190  const size_t len = coinDistance(sfirst, slast);
191  if (len <= 1)
192  return;
193 
194  typedef CoinPair<S,T> ST_pair;
195  ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
196 # ifdef ZEROFAULT
197  // Can show RUI errors on some systems due to copy of ST_pair with gaps.
198  // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro.
199  memset(x,0,(len*sizeof(ST_pair))) ;
200 # endif
201 
202  size_t i = 0;
203  S* scurrent = sfirst;
204  T* tcurrent = tfirst;
205  while (scurrent != slast) {
206  new (x+i++) ST_pair(*scurrent++, *tcurrent++);
207  }
208 
209  std::sort(x, x + len, pc);
210 
211  scurrent = sfirst;
212  tcurrent = tfirst;
213  for (i = 0; i < len; ++i) {
214  *scurrent++ = x[i].first;
215  *tcurrent++ = x[i].second;
216  }
217 
218  ::operator delete(x);
219 }
220 template <class S, class T> void
221 // This Always uses std::sort
222 CoinSort_2Std(S* sfirst, S* slast, T* tfirst)
223 {
224  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
225 }
226 #ifndef COIN_USE_EKK_SORT
227 //-----------------------------------------------------------------------------
228 template <class S, class T> void
229 CoinSort_2(S* sfirst, S* slast, T* tfirst)
230 {
231  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
232 }
233 #else
234 //-----------------------------------------------------------------------------
235 extern int boundary_sort;
236 extern int boundary_sort2;
237 extern int boundary_sort3;
239 template <class S, class T> void
240 CoinSort_2(S* key, S* lastKey, T* array2)
241 {
242  const size_t number = coinDistance(key, lastKey);
243  if (number <= 1) {
244  return;
245  } else if (number>10000) {
246  CoinSort_2Std(key, lastKey, array2);
247  return;
248  }
249 #if 0
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]<<")";
254  }
255  std::cout<<std::endl;
256  }
257 #endif
258  int minsize=10;
259  int n = static_cast<int>(number);
260  int sp;
261  S *v = key;
262  S *m, t;
263  S * ls[32] , * rs[32];
264  S *l , *r , c;
265  T it;
266  int j;
267  /*check already sorted */
268  S last=key[0];
269  for (j=1;j<n;j++) {
270  if (key[j]>=last) {
271  last=key[j];
272  } else {
273  break;
274  } /* endif */
275  } /* endfor */
276  if (j==n) {
277  return;
278  } /* endif */
279  sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
280  while( sp >= 0 )
281  {
282  if ( rs[sp] - ls[sp] > minsize )
283  {
284  l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
285  if ( *l > *m )
286  {
287  t = *l ; *l = *m ; *m = t ;
288  it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
289  }
290  if ( *m > *r )
291  {
292  t = *m ; *m = *r ; *r = t ;
293  it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
294  if ( *l > *m )
295  {
296  t = *l ; *l = *m ; *m = t ;
297  it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
298  }
299  }
300  c = *m ;
301  while ( r - l > 1 )
302  {
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 ;
307  }
308  l = r - 1 ;
309  if ( l < m )
310  { ls[sp+1] = ls[sp] ;
311  rs[sp+1] = l ;
312  ls[sp ] = r ;
313  }
314  else
315  { ls[sp+1] = r ;
316  rs[sp+1] = rs[sp] ;
317  rs[sp ] = l ;
318  }
319  sp++ ;
320  }
321  else sp-- ;
322  }
323  for ( l = v , m = v + (n-1) ; l < m ; l++ )
324  { if ( *l > *(l+1) )
325  {
326  c = *(l+1) ;
327  it = array2[(l-v)+1] ;
328  for ( r = l ; r >= v && *r > c ; r-- )
329  {
330  *(r+1) = *r ;
331  array2[(r-v)+1] = array2[(r-v)] ;
332  }
333  *(r+1) = c ;
334  array2[(r-v)+1] = it ;
335  }
336  }
337 #if 0
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]<<")";
342  }
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]<<")";
348  }
349  std::cout<<std::endl;
350  }
351 #endif
352 }
353 #endif
354 #endif
355 template <class S, class T> void
357 CoinShortSort_2(S* key, S* lastKey, T* array2)
358 {
359  const size_t number = coinDistance(key, lastKey);
360  if (number <= 2) {
361  if (number == 2 && key[0] > key[1]) {
362  S tempS = key[0];
363  T tempT = array2[0];
364  key[0] = key[1];
365  array2[0] = array2[1];
366  key[1] = tempS;
367  array2[1] = tempT;
368  }
369  return;
370  } else if (number>10000) {
371  CoinSort_2Std(key, lastKey, array2);
372  return;
373  }
374  int minsize=10;
375  size_t n = number;
376  int sp;
377  S *v = key;
378  S *m, t;
379  S * ls[32] , * rs[32];
380  S *l , *r , c;
381  T it;
382  size_t j;
383  /*check already sorted */
384  S last=key[0];
385  for (j=1;j<n;j++) {
386  if (key[j]>=last) {
387  last=key[j];
388  } else {
389  break;
390  } /* endif */
391  } /* endfor */
392  if (j==n) {
393  return;
394  } /* endif */
395  sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
396  while( sp >= 0 )
397  {
398  if ( rs[sp] - ls[sp] > minsize )
399  {
400  l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
401  if ( *l > *m )
402  {
403  t = *l ; *l = *m ; *m = t ;
404  it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
405  }
406  if ( *m > *r )
407  {
408  t = *m ; *m = *r ; *r = t ;
409  it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
410  if ( *l > *m )
411  {
412  t = *l ; *l = *m ; *m = t ;
413  it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
414  }
415  }
416  c = *m ;
417  while ( r - l > 1 )
418  {
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 ;
423  }
424  l = r - 1 ;
425  if ( l < m )
426  { ls[sp+1] = ls[sp] ;
427  rs[sp+1] = l ;
428  ls[sp ] = r ;
429  }
430  else
431  { ls[sp+1] = r ;
432  rs[sp+1] = rs[sp] ;
433  rs[sp ] = l ;
434  }
435  sp++ ;
436  }
437  else sp-- ;
438  }
439  for ( l = v , m = v + (n-1) ; l < m ; l++ )
440  { if ( *l > *(l+1) )
441  {
442  c = *(l+1) ;
443  it = array2[(l-v)+1] ;
444  for ( r = l ; r >= v && *r > c ; r-- )
445  {
446  *(r+1) = *r ;
447  array2[(r-v)+1] = array2[(r-v)] ;
448  }
449  *(r+1) = c ;
450  array2[(r-v)+1] = it ;
451  }
452  }
453 }
454 //#############################################################################
455 //#############################################################################
456 
458 template <class S, class T, class U>
459 class CoinTriple {
460 public:
462  S first;
466  U third;
467 public:
469  CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
470 };
471 
472 //#############################################################################
477 template < class S, class T, class U >
479 public:
481  inline bool operator()(const CoinTriple<S,T,U>& t1,
482  const CoinTriple<S,T,U>& t2) const
483  { return t1.first < t2.first; }
484 };
485 //-----------------------------------------------------------------------------
488 template < class S, class T, class U >
490 public:
492  inline bool operator()(const CoinTriple<S,T,U>& t1,
493  const CoinTriple<S,T,U>& t2) const
494  { return t1.first>t2.first; }
495 };
496 //-----------------------------------------------------------------------------
499 template < class S, class T, class U >
501 public:
503  inline bool operator()(const CoinTriple<S,T,U>& t1,
504  const CoinTriple<S,T,U>& t2) const
505  {
506  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
507  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
508  return t1Abs < t2Abs;
509  }
510 };
511 //-----------------------------------------------------------------------------
514 template < class S, class T, class U >
516 public:
518  inline bool operator()(const CoinTriple<S,T,U>& t1,
519  const CoinTriple<S,T,U>& t2) const
520  {
521  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
522  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
523  return t1Abs > t2Abs;
524  }
525 };
526 //-----------------------------------------------------------------------------
532 template < class S, class T, class U, class V>
534 private:
536 private:
537  const V* vec_;
538 public:
539  inline bool operator()(const CoinTriple<S,T,U>& t1,
540  const CoinTriple<S,T,U>& t2) const
541  { return vec_[t1.first] < vec_[t2.first]; }
543 };
544 //-----------------------------------------------------------------------------
550 template < class S, class T, class U, class V>
552 private:
554 private:
555  const V* vec_;
556 public:
557  inline bool operator()(const CoinTriple<S,T,U>& t1,
558  const CoinTriple<S,T,U>& t2) const
559  { return vec_[t1.first] > vec_[t2.first]; }
561 };
563 
564 //#############################################################################
565 
576 
577 //#############################################################################
578 
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)
590 {
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;
594  const size_t len = coinDistance(sfirst, slast);
595  if (len <= 1)
596  return;
597 
598  typedef CoinTriple<S,T,U> STU_triple;
599  STU_triple* x =
600  static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
601 
602  int i = 0;
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++);
608  }
609 
610  std::sort(x, x+len, tc);
611 
612  scurrent = sfirst;
613  tcurrent = tfirst;
614  ucurrent = ufirst;
615  for (i = 0; i < len; ++i) {
616  *scurrent++ = x[i].first;
617  *tcurrent++ = x[i].second;
618  *ucurrent++ = x[i].third;
619  }
620 
621  ::operator delete(x);
622 }
623 //-----------------------------------------------------------------------------
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)
626 {
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;
630  CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
631 }
632 
633 #else //=======================================================================
634 
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)
637 {
638  const size_t len = coinDistance(sfirst,slast);
639  if (len <= 1)
640  return;
641 
642  typedef CoinTriple<S,T,U> STU_triple;
643  STU_triple* x =
644  static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
645 
646  size_t i = 0;
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++);
652  }
653 
654  std::sort(x, x+len, tc);
655 
656  scurrent = sfirst;
657  tcurrent = tfirst;
658  ucurrent = ufirst;
659  for (i = 0; i < len; ++i) {
660  *scurrent++ = x[i].first;
661  *tcurrent++ = x[i].second;
662  *ucurrent++ = x[i].third;
663  }
664 
665  ::operator delete(x);
666 }
667 //-----------------------------------------------------------------------------
668 template <class S, class T, class U> void
669 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
670 {
671  CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
672 }
673 
674 #endif
675 
676 //#############################################################################
677 
678 #endif
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:51
CoinPair(const S &s, const T &t)
Construct from ordered pair.
Definition: CoinSort.hpp:38
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
Definition: CoinSort.hpp:574
CoinExternalVectorFirstGreater_3(const V *v)
Definition: CoinSort.hpp:560
CoinExternalVectorFirstLess_2(const V *v)
Definition: CoinSort.hpp:111
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:557
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
Definition: CoinSort.hpp:469
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:518
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
Definition: CoinSort.hpp:188
void CoinShortSort_2(S *key, S *lastKey, T *array2)
Sort without new and delete.
Definition: CoinSort.hpp:357
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition: CoinSort.hpp:539
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:542
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
Definition: CoinSort.hpp:222
Function operator.
Definition: CoinSort.hpp:489
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:503
Function operator.
Definition: CoinSort.hpp:85
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:62
Function operator.
Definition: CoinSort.hpp:500
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:492
Function operator.
Definition: CoinSort.hpp:70
Function operator.
Definition: CoinSort.hpp:533
U third
Third member of triple.
Definition: CoinSort.hpp:466
Function operator.
Definition: CoinSort.hpp:48
Function operator.
Definition: CoinSort.hpp:102
S first
First member of triple.
Definition: CoinSort.hpp:462
bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
Compare function.
Definition: CoinSort.hpp:88
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:481
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition: CoinSort.hpp:126
T second
Second member of triple.
Definition: CoinSort.hpp:464
Function operator.
Definition: CoinSort.hpp:478
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:73
CoinExternalVectorFirstGreater_2(const V *v)
Definition: CoinSort.hpp:129
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
Definition: CoinSort.hpp:636
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition: CoinSort.hpp:108
Function operator.
Definition: CoinSort.hpp:515
Function operator.
Definition: CoinSort.hpp:59
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
Definition: CoinSort.hpp:571