1/* $Id: CoinSort.hpp 1448 2011-06-19 15:34:41Z stefan $ */
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
27/** An ordered pair. It's the same as std::pair, just this way it'll have the
28 same look as the triple sorting. */
29template <class S, class T>
30struct CoinPair {
31public:
32 /// First member of pair
33 S first;
34 /// Second member of pair
35 T second;
36public:
37 /// Construct from ordered pair
38 CoinPair(const S& s, const T& t) : first(s), second(t) {}
39};
40
41//#############################################################################
42
43/**@name Comparisons on first element of two ordered pairs */
44//@{
45/** Function operator.
46 Returns true if t1.first &lt; t2.first (i.e., increasing). */
47template < class S, class T>
48class CoinFirstLess_2 {
49public:
50 /// Compare function
51 inline bool operator()(const CoinPair<S,T>& t1,
52 const CoinPair<S,T>& t2) const
53 { return t1.first < t2.first; }
54};
55//-----------------------------------------------------------------------------
56/** Function operator.
57 Returns true if t1.first &gt; t2.first (i.e, decreasing). */
58template < class S, class T>
59class CoinFirstGreater_2 {
60public:
61 /// Compare function
62 inline bool operator()(const CoinPair<S,T>& t1,
63 const CoinPair<S,T>& t2) const
64 { return t1.first > t2.first; }
65};
66//-----------------------------------------------------------------------------
67/** Function operator.
68 Returns true if abs(t1.first) &lt; abs(t2.first) (i.e., increasing). */
69template < class S, class T>
70class CoinFirstAbsLess_2 {
71public:
72 /// Compare function
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//-----------------------------------------------------------------------------
82/** Function operator.
83 Returns true if abs(t1.first) &gt; abs(t2.first) (i.e., decreasing). */
84template < class S, class T>
85class CoinFirstAbsGreater_2 {
86public:
87 /// Compare function
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//-----------------------------------------------------------------------------
96/** Function operator.
97 Compare based on the entries of an external vector, i.e., returns true if
98 vec[t1.first &lt; vec[t2.first] (i.e., increasing wrt. vec). Note that to
99 use this comparison operator .first must be a data type automatically
100 convertible to int. */
101template < class S, class T, class V>
102class CoinExternalVectorFirstLess_2 {
103private:
104 CoinExternalVectorFirstLess_2();
105private:
106 const V* vec_;
107public:
108 inline bool operator()(const CoinPair<S,T>& t1,
109 const CoinPair<S,T>& t2) const
110 { return vec_[t1.first] < vec_[t2.first]; }
111 CoinExternalVectorFirstLess_2(const V* v) : vec_(v) {}
112};
113//-----------------------------------------------------------------------------
114/** Function operator.
115 Compare based on the entries of an external vector, i.e., returns true if
116 vec[t1.first &gt; vec[t2.first] (i.e., decreasing wrt. vec). Note that to
117 use this comparison operator .first must be a data type automatically
118 convertible to int. */
119template < class S, class T, class V>
120class CoinExternalVectorFirstGreater_2 {
121private:
122 CoinExternalVectorFirstGreater_2();
123private:
124 const V* vec_;
125public:
126 inline bool operator()(const CoinPair<S,T>& t1,
127 const CoinPair<S,T>& t2) const
128 { return vec_[t1.first] > vec_[t2.first]; }
129 CoinExternalVectorFirstGreater_2(const V* v) : vec_(v) {}
130};
131//@}
132
133//#############################################################################
134
135/** Sort a pair of containers.<br>
136
137 Iter_S - iterator for first container<br>
138 Iter_T - iterator for 2nd container<br>
139 CoinCompare2 - class comparing CoinPairs<br>
140*/
141
142#ifdef COIN_SORT_ARBITRARY_CONTAINERS
143template <class Iter_S, class Iter_T, class CoinCompare2> void
144CoinSort_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//-----------------------------------------------------------------------------
177template <class Iter_S, class Iter_T> void
178CoinSort_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
187template <class S, class T, class CoinCompare2> void
188CoinSort_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}
220template <class S, class T> void
221// This Always uses std::sort
222CoinSort_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//-----------------------------------------------------------------------------
228template <class S, class T> void
229CoinSort_2(S* sfirst, S* slast, T* tfirst)
230{
231 CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
232}
233#else
234//-----------------------------------------------------------------------------
235extern int boundary_sort;
236extern int boundary_sort2;
237extern int boundary_sort3;
238/// Sort without new and delete
239template <class S, class T> void
240CoinSort_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 = 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//#############################################################################
356//#############################################################################
357
358/**@name Ordered Triple Struct */
359template <class S, class T, class U>
360class CoinTriple {
361public:
362 /// First member of triple
363 S first;
364 /// Second member of triple
365 T second;
366 /// Third member of triple
367 U third;
368public:
369 /// Construct from ordered triple
370 CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
371};
372
373//#############################################################################
374/**@name Comparisons on first element of two ordered triples */
375//@{
376/** Function operator.
377 Returns true if t1.first &lt; t2.first (i.e., increasing). */
378template < class S, class T, class U >
379class CoinFirstLess_3 {
380public:
381 /// Compare function
382 inline bool operator()(const CoinTriple<S,T,U>& t1,
383 const CoinTriple<S,T,U>& t2) const
384 { return t1.first < t2.first; }
385};
386//-----------------------------------------------------------------------------
387/** Function operator.
388 Returns true if t1.first &gt; t2.first (i.e, decreasing). */
389template < class S, class T, class U >
390class CoinFirstGreater_3 {
391public:
392 /// Compare function
393 inline bool operator()(const CoinTriple<S,T,U>& t1,
394 const CoinTriple<S,T,U>& t2) const
395 { return t1.first>t2.first; }
396};
397//-----------------------------------------------------------------------------
398/** Function operator.
399 Returns true if abs(t1.first) &lt; abs(t2.first) (i.e., increasing). */
400template < class S, class T, class U >
401class CoinFirstAbsLess_3 {
402public:
403 /// Compare function
404 inline bool operator()(const CoinTriple<S,T,U>& t1,
405 const CoinTriple<S,T,U>& t2) const
406 {
407 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
408 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
409 return t1Abs < t2Abs;
410 }
411};
412//-----------------------------------------------------------------------------
413/** Function operator.
414 Returns true if abs(t1.first) &gt; abs(t2.first) (i.e., decreasing). */
415template < class S, class T, class U >
416class CoinFirstAbsGreater_3 {
417public:
418 /// Compare function
419 inline bool operator()(const CoinTriple<S,T,U>& t1,
420 const CoinTriple<S,T,U>& t2) const
421 {
422 const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
423 const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
424 return t1Abs > t2Abs;
425 }
426};
427//-----------------------------------------------------------------------------
428/** Function operator.
429 Compare based on the entries of an external vector, i.e., returns true if
430 vec[t1.first &lt; vec[t2.first] (i.e., increasing wrt. vec). Note that to
431 use this comparison operator .first must be a data type automatically
432 convertible to int. */
433template < class S, class T, class U, class V>
434class CoinExternalVectorFirstLess_3 {
435private:
436 CoinExternalVectorFirstLess_3();
437private:
438 const V* vec_;
439public:
440 inline bool operator()(const CoinTriple<S,T,U>& t1,
441 const CoinTriple<S,T,U>& t2) const
442 { return vec_[t1.first] < vec_[t2.first]; }
443 CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
444};
445//-----------------------------------------------------------------------------
446/** Function operator.
447 Compare based on the entries of an external vector, i.e., returns true if
448 vec[t1.first &gt; vec[t2.first] (i.e., decreasing wrt. vec). Note that to
449 use this comparison operator .first must be a data type automatically
450 convertible to int. */
451template < class S, class T, class U, class V>
452class CoinExternalVectorFirstGreater_3 {
453private:
454 CoinExternalVectorFirstGreater_3();
455private:
456 const V* vec_;
457public:
458 inline bool operator()(const CoinTriple<S,T,U>& t1,
459 const CoinTriple<S,T,U>& t2) const
460 { return vec_[t1.first] > vec_[t2.first]; }
461 CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
462};
463//@}
464
465//#############################################################################
466
467/**@name Typedefs for sorting the entries of a packed vector based on an
468 external vector. */
469//@{
470/// Sort packed vector in increasing order of the external vector
471typedef CoinExternalVectorFirstLess_3<int, int, double, double>
472CoinIncrSolutionOrdered;
473/// Sort packed vector in decreasing order of the external vector
474typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
475CoinDecrSolutionOrdered;
476//@}
477
478//#############################################################################
479
480/** Sort a triple of containers.<br>
481
482 Iter_S - iterator for first container<br>
483 Iter_T - iterator for 2nd container<br>
484 Iter_U - iterator for 3rd container<br>
485 CoinCompare3 - class comparing CoinTriples<br>
486*/
487#ifdef COIN_SORT_ARBITRARY_CONTAINERS
488template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
489CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
490 const CoinCompare3& tc)
491{
492 typedef typename std::iterator_traits<Iter_S>::value_type S;
493 typedef typename std::iterator_traits<Iter_T>::value_type T;
494 typedef typename std::iterator_traits<Iter_U>::value_type U;
495 const size_t len = coinDistance(sfirst, slast);
496 if (len <= 1)
497 return;
498
499 typedef CoinTriple<S,T,U> STU_triple;
500 STU_triple* x =
501 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
502
503 int i = 0;
504 Iter_S scurrent = sfirst;
505 Iter_T tcurrent = tfirst;
506 Iter_U ucurrent = ufirst;
507 while (scurrent != slast) {
508 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
509 }
510
511 std::sort(x, x+len, tc);
512
513 scurrent = sfirst;
514 tcurrent = tfirst;
515 ucurrent = ufirst;
516 for (i = 0; i < len; ++i) {
517 *scurrent++ = x[i].first;
518 *tcurrent++ = x[i].second;
519 *ucurrent++ = x[i].third;
520 }
521
522 ::operator delete(x);
523}
524//-----------------------------------------------------------------------------
525template <class Iter_S, class Iter_T, class Iter_U> void
526CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
527{
528 typedef typename std::iterator_traits<Iter_S>::value_type S;
529 typedef typename std::iterator_traits<Iter_T>::value_type T;
530 typedef typename std::iterator_traits<Iter_U>::value_type U;
531 CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
532}
533
534#else //=======================================================================
535
536template <class S, class T, class U, class CoinCompare3> void
537CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
538{
539 const size_t len = coinDistance(sfirst,slast);
540 if (len <= 1)
541 return;
542
543 typedef CoinTriple<S,T,U> STU_triple;
544 STU_triple* x =
545 static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
546
547 size_t i = 0;
548 S* scurrent = sfirst;
549 T* tcurrent = tfirst;
550 U* ucurrent = ufirst;
551 while (scurrent != slast) {
552 new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
553 }
554
555 std::sort(x, x+len, tc);
556
557 scurrent = sfirst;
558 tcurrent = tfirst;
559 ucurrent = ufirst;
560 for (i = 0; i < len; ++i) {
561 *scurrent++ = x[i].first;
562 *tcurrent++ = x[i].second;
563 *ucurrent++ = x[i].third;
564 }
565
566 ::operator delete(x);
567}
568//-----------------------------------------------------------------------------
569template <class S, class T, class U> void
570CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
571{
572 CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
573}
574
575#endif
576
577//#############################################################################
578
579#endif
580