CoinSort.hpp
Go to the documentation of this file.
1 /* $Id: CoinSort.hpp 1239 2009-12-10 16:16:11Z ladanyi $ */
2 // Copyright (C) 2000, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 #ifndef CoinSort_H
5 #define CoinSort_H
6 
7 #include <functional>
8 #include <new>
9 #include "CoinDistance.hpp"
10 #include "CoinFinite.hpp"
11 
12 // Uncomment the next three lines to get thorough initialisation of memory.
13 // #ifndef ZEROFAULT
14 // #define ZEROFAULT
15 // #endif
16 
17 //#############################################################################
18 
21 template <class S, class T>
22 struct CoinPair {
23 public:
25  S first;
27  T second;
28 public:
30  CoinPair(const S& s, const T& t) : first(s), second(t) {}
31 };
32 
33 //#############################################################################
34 
39 template < class S, class T>
41 public:
43  inline bool operator()(const CoinPair<S,T>& t1,
44  const CoinPair<S,T>& t2) const
45  { return t1.first < t2.first; }
46 };
47 //-----------------------------------------------------------------------------
50 template < class S, class T>
52 public:
54  inline bool operator()(const CoinPair<S,T>& t1,
55  const CoinPair<S,T>& t2) const
56  { return t1.first > t2.first; }
57 };
58 //-----------------------------------------------------------------------------
61 template < class S, class T>
63 public:
65  inline bool operator()(const CoinPair<S,T>& t1,
66  const CoinPair<S,T>& t2) const
67  {
68  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
69  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
70  return t1Abs < t2Abs;
71  }
72 };
73 //-----------------------------------------------------------------------------
76 template < class S, class T>
78 public:
80  inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
81  {
82  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
83  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
84  return t1Abs > t2Abs;
85  }
86 };
87 //-----------------------------------------------------------------------------
93 template < class S, class T, class V>
95 private:
97 private:
98  const V* vec_;
99 public:
100  inline bool operator()(const CoinPair<S,T>& t1,
101  const CoinPair<S,T>& t2) const
102  { return vec_[t1.first] < vec_[t2.first]; }
104 };
105 //-----------------------------------------------------------------------------
111 template < class S, class T, class V>
113 private:
115 private:
116  const V* vec_;
117 public:
118  inline bool operator()(const CoinPair<S,T>& t1,
119  const CoinPair<S,T>& t2) const
120  { return vec_[t1.first] > vec_[t2.first]; }
122 };
124 
125 //#############################################################################
126 
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)
137 {
138  typedef typename std::iterator_traits<Iter_S>::value_type S;
139  typedef typename std::iterator_traits<Iter_T>::value_type T;
140  const size_t len = coinDistance(sfirst, slast);
141  if (len <= 1)
142  return;
143 
144  typedef CoinPair<S,T> ST_pair;
145  ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
146 # ifdef ZEROFAULT
147  memset(x,0,(len*sizeof(ST_pair))) ;
148 # endif
149 
150  int i = 0;
151  Iter_S scurrent = sfirst;
152  Iter_T tcurrent = tfirst;
153  while (scurrent != slast) {
154  new (x+i++) ST_pair(*scurrent++, *tcurrent++);
155  }
156 
157  std::sort(x.begin(), x.end(), pc);
158 
159  scurrent = sfirst;
160  tcurrent = tfirst;
161  for (i = 0; i < len; ++i) {
162  *scurrent++ = x[i].first;
163  *tcurrent++ = x[i].second;
164  }
165 
166  ::operator delete(x);
167 }
168 //-----------------------------------------------------------------------------
169 template <class Iter_S, class Iter_T> void
170 CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
171 {
172  typedef typename std::iterator_traits<Iter_S>::value_type S;
173  typedef typename std::iterator_traits<Iter_T>::value_type T;
174  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
175 }
176 
177 #else //=======================================================================
178 
179 template <class S, class T, class CoinCompare2> void
180 CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
181 {
182  const size_t len = coinDistance(sfirst, slast);
183  if (len <= 1)
184  return;
185 
186  typedef CoinPair<S,T> ST_pair;
187  ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
188 # ifdef ZEROFAULT
189  // Can show RUI errors on some systems due to copy of ST_pair with gaps.
190  // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro.
191  memset(x,0,(len*sizeof(ST_pair))) ;
192 # endif
193 
194  size_t i = 0;
195  S* scurrent = sfirst;
196  T* tcurrent = tfirst;
197  while (scurrent != slast) {
198  new (x+i++) ST_pair(*scurrent++, *tcurrent++);
199  }
200 
201  std::sort(x, x + len, pc);
202 
203  scurrent = sfirst;
204  tcurrent = tfirst;
205  for (i = 0; i < len; ++i) {
206  *scurrent++ = x[i].first;
207  *tcurrent++ = x[i].second;
208  }
209 
210  ::operator delete(x);
211 }
212 template <class S, class T> void
213 // This Always uses std::sort
214 CoinSort_2Std(S* sfirst, S* slast, T* tfirst)
215 {
216  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
217 }
218 #ifndef COIN_USE_EKK_SORT
219 //-----------------------------------------------------------------------------
220 template <class S, class T> void
221 CoinSort_2(S* sfirst, S* slast, T* tfirst)
222 {
223  CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
224 }
225 #else
226 //-----------------------------------------------------------------------------
227 extern int boundary_sort;
228 extern int boundary_sort2;
229 extern int boundary_sort3;
231 template <class S, class T> void
232 CoinSort_2(S* key, S* lastKey, T* array2)
233 {
234  const size_t number = coinDistance(key, lastKey);
235  if (number <= 1) {
236  return;
237  } else if (number>10000) {
238  CoinSort_2Std(key, lastKey, array2);
239  return;
240  }
241 #if 0
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]<<")";
246  }
247  std::cout<<std::endl;
248  }
249 #endif
250  int minsize=10;
251  int n = number;
252  int sp;
253  S *v = key;
254  S *m, t;
255  S * ls[32] , * rs[32];
256  S *l , *r , c;
257  T it;
258  int j;
259  /*check already sorted */
260  S last=key[0];
261  for (j=1;j<n;j++) {
262  if (key[j]>=last) {
263  last=key[j];
264  } else {
265  break;
266  } /* endif */
267  } /* endfor */
268  if (j==n) {
269  return;
270  } /* endif */
271  sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
272  while( sp >= 0 )
273  {
274  if ( rs[sp] - ls[sp] > minsize )
275  {
276  l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
277  if ( *l > *m )
278  {
279  t = *l ; *l = *m ; *m = t ;
280  it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
281  }
282  if ( *m > *r )
283  {
284  t = *m ; *m = *r ; *r = t ;
285  it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
286  if ( *l > *m )
287  {
288  t = *l ; *l = *m ; *m = t ;
289  it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
290  }
291  }
292  c = *m ;
293  while ( r - l > 1 )
294  {
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 ;
299  }
300  l = r - 1 ;
301  if ( l < m )
302  { ls[sp+1] = ls[sp] ;
303  rs[sp+1] = l ;
304  ls[sp ] = r ;
305  }
306  else
307  { ls[sp+1] = r ;
308  rs[sp+1] = rs[sp] ;
309  rs[sp ] = l ;
310  }
311  sp++ ;
312  }
313  else sp-- ;
314  }
315  for ( l = v , m = v + (n-1) ; l < m ; l++ )
316  { if ( *l > *(l+1) )
317  {
318  c = *(l+1) ;
319  it = array2[(l-v)+1] ;
320  for ( r = l ; r >= v && *r > c ; r-- )
321  {
322  *(r+1) = *r ;
323  array2[(r-v)+1] = array2[(r-v)] ;
324  }
325  *(r+1) = c ;
326  array2[(r-v)+1] = it ;
327  }
328  }
329 #if 0
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]<<")";
334  }
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]<<")";
340  }
341  std::cout<<std::endl;
342  }
343 #endif
344 }
345 #endif
346 #endif
347 //#############################################################################
348 //#############################################################################
349 
351 template <class S, class T, class U>
352 class CoinTriple {
353 public:
355  S first;
359  U third;
360 public:
362  CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
363 };
364 
365 //#############################################################################
370 template < class S, class T, class U >
372 public:
374  inline bool operator()(const CoinTriple<S,T,U>& t1,
375  const CoinTriple<S,T,U>& t2) const
376  { return t1.first < t2.first; }
377 };
378 //-----------------------------------------------------------------------------
381 template < class S, class T, class U >
383 public:
385  inline bool operator()(const CoinTriple<S,T,U>& t1,
386  const CoinTriple<S,T,U>& t2) const
387  { return t1.first>t2.first; }
388 };
389 //-----------------------------------------------------------------------------
392 template < class S, class T, class U >
394 public:
396  inline bool operator()(const CoinTriple<S,T,U>& t1,
397  const CoinTriple<S,T,U>& t2) const
398  {
399  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
400  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
401  return t1Abs < t2Abs;
402  }
403 };
404 //-----------------------------------------------------------------------------
407 template < class S, class T, class U >
409 public:
411  inline bool operator()(const CoinTriple<S,T,U>& t1,
412  const CoinTriple<S,T,U>& t2) const
413  {
414  const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
415  const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
416  return t1Abs > t2Abs;
417  }
418 };
419 //-----------------------------------------------------------------------------
425 template < class S, class T, class U, class V>
427 private:
429 private:
430  const V* vec_;
431 public:
432  inline bool operator()(const CoinTriple<S,T,U>& t1,
433  const CoinTriple<S,T,U>& t2) const
434  { return vec_[t1.first] < vec_[t2.first]; }
436 };
437 //-----------------------------------------------------------------------------
443 template < class S, class T, class U, class V>
445 private:
447 private:
448  const V* vec_;
449 public:
450  inline bool operator()(const CoinTriple<S,T,U>& t1,
451  const CoinTriple<S,T,U>& t2) const
452  { return vec_[t1.first] > vec_[t2.first]; }
454 };
456 
457 //#############################################################################
458 
469 
470 //#############################################################################
471 
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)
483 {
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;
487  const size_t len = coinDistance(sfirst, slast);
488  if (len <= 1)
489  return;
490 
491  typedef CoinTriple<S,T,U> STU_triple;
492  STU_triple* x =
493  static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
494 
495  int i = 0;
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++);
501  }
502 
503  std::sort(x, x+len, tc);
504 
505  scurrent = sfirst;
506  tcurrent = tfirst;
507  ucurrent = ufirst;
508  for (i = 0; i < len; ++i) {
509  *scurrent++ = x[i].first;
510  *tcurrent++ = x[i].second;
511  *ucurrent++ = x[i].third;
512  }
513 
514  ::operator delete(x);
515 }
516 //-----------------------------------------------------------------------------
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)
519 {
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;
523  CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
524 }
525 
526 #else //=======================================================================
527 
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)
530 {
531  const size_t len = coinDistance(sfirst,slast);
532  if (len <= 1)
533  return;
534 
535  typedef CoinTriple<S,T,U> STU_triple;
536  STU_triple* x =
537  static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
538 
539  size_t i = 0;
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++);
545  }
546 
547  std::sort(x, x+len, tc);
548 
549  scurrent = sfirst;
550  tcurrent = tfirst;
551  ucurrent = ufirst;
552  for (i = 0; i < len; ++i) {
553  *scurrent++ = x[i].first;
554  *tcurrent++ = x[i].second;
555  *ucurrent++ = x[i].third;
556  }
557 
558  ::operator delete(x);
559 }
560 //-----------------------------------------------------------------------------
561 template <class S, class T, class U> void
562 CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
563 {
564  CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
565 }
566 
567 #endif
568 
569 //#############################################################################
570 
571 #endif
Function operator.
Definition: CoinSort.hpp:94
CoinExternalVectorFirstGreater_2(const V *v)
Definition: CoinSort.hpp:121
CoinExternalVectorFirstLess_3(const V *v)
Definition: CoinSort.hpp:435
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition: CoinSort.hpp:118
Function operator.
Definition: CoinSort.hpp:77
void CoinSort_2Std(S *sfirst, S *slast, T *tfirst)
Definition: CoinSort.hpp:214
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:385
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Definition: CoinSort.hpp:100
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:43
U third
Third member of triple.
Definition: CoinSort.hpp:359
Function operator.
Definition: CoinSort.hpp:371
S first
First member of pair.
Definition: CoinSort.hpp:25
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:411
T second
Second member of triple.
Definition: CoinSort.hpp:357
T second
Second member of pair.
Definition: CoinSort.hpp:27
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition: CoinSort.hpp:432
Function operator.
Definition: CoinSort.hpp:51
void CoinSort_3(S *sfirst, S *slast, T *tfirst, U *ufirst, const CoinCompare3 &tc)
Sort a triple of containers.
Definition: CoinSort.hpp:529
Function operator.
Definition: CoinSort.hpp:40
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:396
void coinDistance(ForwardIterator first, ForwardIterator last, Distance &n)
CoinDistance.
CoinTriple(const S &s, const T &t, const U &u)
Construct from ordered triple.
Definition: CoinSort.hpp:362
CoinExternalVectorFirstLess_3< int, int, double, double > CoinIncrSolutionOrdered
Sort packed vector in increasing order of the external vector.
Definition: CoinSort.hpp:464
S first
First member of triple.
Definition: CoinSort.hpp:355
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Definition: CoinSort.hpp:450
CoinExternalVectorFirstLess_2(const V *v)
Definition: CoinSort.hpp:103
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:54
CoinPair(const S &s, const T &t)
Construct from ordered pair.
Definition: CoinSort.hpp:30
void CoinSort_2(S *sfirst, S *slast, T *tfirst, const CoinCompare2 &pc)
Sort a pair of containers.
Definition: CoinSort.hpp:180
bool operator()(CoinPair< S, T > t1, CoinPair< S, T > t2) const
Compare function.
Definition: CoinSort.hpp:80
An ordered pair.
Definition: CoinSort.hpp:22
Function operator.
Definition: CoinSort.hpp:62
Function operator.
Definition: CoinSort.hpp:426
Function operator.
Definition: CoinSort.hpp:382
CoinExternalVectorFirstGreater_3(const V *v)
Definition: CoinSort.hpp:453
Function operator.
Definition: CoinSort.hpp:408
CoinExternalVectorFirstGreater_3< int, int, double, double > CoinDecrSolutionOrdered
Sort packed vector in decreasing order of the external vector.
Definition: CoinSort.hpp:467
Function operator.
Definition: CoinSort.hpp:393
bool operator()(const CoinTriple< S, T, U > &t1, const CoinTriple< S, T, U > &t2) const
Compare function.
Definition: CoinSort.hpp:374
bool operator()(const CoinPair< S, T > &t1, const CoinPair< S, T > &t2) const
Compare function.
Definition: CoinSort.hpp:65