summaryrefslogtreecommitdiff
path: root/newstructure/thirdparty/linux/include/coin/CoinSort.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'newstructure/thirdparty/linux/include/coin/CoinSort.hpp')
-rw-r--r--newstructure/thirdparty/linux/include/coin/CoinSort.hpp678
1 files changed, 0 insertions, 678 deletions
diff --git a/newstructure/thirdparty/linux/include/coin/CoinSort.hpp b/newstructure/thirdparty/linux/include/coin/CoinSort.hpp
deleted file mode 100644
index 259fb35..0000000
--- a/newstructure/thirdparty/linux/include/coin/CoinSort.hpp
+++ /dev/null
@@ -1,678 +0,0 @@
-/* $Id: CoinSort.hpp 1594 2013-04-19 14:33:00Z forrest $ */
-// Copyright (C) 2000, International Business Machines
-// Corporation and others. All Rights Reserved.
-// This code is licensed under the terms of the Eclipse Public License (EPL).
-
-#ifndef CoinSort_H
-#define CoinSort_H
-
-#include <functional>
-#include <new>
-#include <algorithm>
-#include "CoinDistance.hpp"
-
-// Uncomment the next three lines to get thorough initialisation of memory.
-// #ifndef ZEROFAULT
-// #define ZEROFAULT
-// #endif
-
-#ifdef COIN_FAST_CODE
-#ifndef COIN_USE_EKK_SORT
-#define COIN_USE_EKK_SORT
-#endif
-#endif
-
-//#############################################################################
-
-/** An ordered pair. It's the same as std::pair, just this way it'll have the
- same look as the triple sorting. */
-template <class S, class T>
-struct CoinPair {
-public:
- /// First member of pair
- S first;
- /// Second member of pair
- T second;
-public:
- /// Construct from ordered pair
- CoinPair(const S& s, const T& t) : first(s), second(t) {}
-};
-
-//#############################################################################
-
-/**@name Comparisons on first element of two ordered pairs */
-//@{
-/** Function operator.
- Returns true if t1.first &lt; t2.first (i.e., increasing). */
-template < class S, class T>
-class CoinFirstLess_2 {
-public:
- /// Compare function
- inline bool operator()(const CoinPair<S,T>& t1,
- const CoinPair<S,T>& t2) const
- { return t1.first < t2.first; }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Returns true if t1.first &gt; t2.first (i.e, decreasing). */
-template < class S, class T>
-class CoinFirstGreater_2 {
-public:
- /// Compare function
- inline bool operator()(const CoinPair<S,T>& t1,
- const CoinPair<S,T>& t2) const
- { return t1.first > t2.first; }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Returns true if abs(t1.first) &lt; abs(t2.first) (i.e., increasing). */
-template < class S, class T>
-class CoinFirstAbsLess_2 {
-public:
- /// Compare function
- inline bool operator()(const CoinPair<S,T>& t1,
- const CoinPair<S,T>& t2) const
- {
- const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
- const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
- return t1Abs < t2Abs;
- }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Returns true if abs(t1.first) &gt; abs(t2.first) (i.e., decreasing). */
-template < class S, class T>
-class CoinFirstAbsGreater_2 {
-public:
- /// Compare function
- inline bool operator()(CoinPair<S,T> t1, CoinPair<S,T> t2) const
- {
- const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
- const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
- return t1Abs > t2Abs;
- }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Compare based on the entries of an external vector, i.e., returns true if
- vec[t1.first &lt; vec[t2.first] (i.e., increasing wrt. vec). Note that to
- use this comparison operator .first must be a data type automatically
- convertible to int. */
-template < class S, class T, class V>
-class CoinExternalVectorFirstLess_2 {
-private:
- CoinExternalVectorFirstLess_2();
-private:
- const V* vec_;
-public:
- inline bool operator()(const CoinPair<S,T>& t1,
- const CoinPair<S,T>& t2) const
- { return vec_[t1.first] < vec_[t2.first]; }
- CoinExternalVectorFirstLess_2(const V* v) : vec_(v) {}
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Compare based on the entries of an external vector, i.e., returns true if
- vec[t1.first &gt; vec[t2.first] (i.e., decreasing wrt. vec). Note that to
- use this comparison operator .first must be a data type automatically
- convertible to int. */
-template < class S, class T, class V>
-class CoinExternalVectorFirstGreater_2 {
-private:
- CoinExternalVectorFirstGreater_2();
-private:
- const V* vec_;
-public:
- inline bool operator()(const CoinPair<S,T>& t1,
- const CoinPair<S,T>& t2) const
- { return vec_[t1.first] > vec_[t2.first]; }
- CoinExternalVectorFirstGreater_2(const V* v) : vec_(v) {}
-};
-//@}
-
-//#############################################################################
-
-/** Sort a pair of containers.<br>
-
- Iter_S - iterator for first container<br>
- Iter_T - iterator for 2nd container<br>
- CoinCompare2 - class comparing CoinPairs<br>
-*/
-
-#ifdef COIN_SORT_ARBITRARY_CONTAINERS
-template <class Iter_S, class Iter_T, class CoinCompare2> void
-CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst, const CoinCompare2& pc)
-{
- typedef typename std::iterator_traits<Iter_S>::value_type S;
- typedef typename std::iterator_traits<Iter_T>::value_type T;
- const size_t len = coinDistance(sfirst, slast);
- if (len <= 1)
- return;
-
- typedef CoinPair<S,T> ST_pair;
- ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
-# ifdef ZEROFAULT
- memset(x,0,(len*sizeof(ST_pair))) ;
-# endif
-
- int i = 0;
- Iter_S scurrent = sfirst;
- Iter_T tcurrent = tfirst;
- while (scurrent != slast) {
- new (x+i++) ST_pair(*scurrent++, *tcurrent++);
- }
-
- std::sort(x.begin(), x.end(), pc);
-
- scurrent = sfirst;
- tcurrent = tfirst;
- for (i = 0; i < len; ++i) {
- *scurrent++ = x[i].first;
- *tcurrent++ = x[i].second;
- }
-
- ::operator delete(x);
-}
-//-----------------------------------------------------------------------------
-template <class Iter_S, class Iter_T> void
-CoinSort_2(Iter_S sfirst, Iter_S slast, Iter_T tfirst)
-{
- typedef typename std::iterator_traits<Iter_S>::value_type S;
- typedef typename std::iterator_traits<Iter_T>::value_type T;
- CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
-}
-
-#else //=======================================================================
-
-template <class S, class T, class CoinCompare2> void
-CoinSort_2(S* sfirst, S* slast, T* tfirst, const CoinCompare2& pc)
-{
- const size_t len = coinDistance(sfirst, slast);
- if (len <= 1)
- return;
-
- typedef CoinPair<S,T> ST_pair;
- ST_pair* x = static_cast<ST_pair*>(::operator new(len * sizeof(ST_pair)));
-# ifdef ZEROFAULT
- // Can show RUI errors on some systems due to copy of ST_pair with gaps.
- // E.g., <int, double> has 4 byte alignment gap on Solaris/SUNWspro.
- memset(x,0,(len*sizeof(ST_pair))) ;
-# endif
-
- size_t i = 0;
- S* scurrent = sfirst;
- T* tcurrent = tfirst;
- while (scurrent != slast) {
- new (x+i++) ST_pair(*scurrent++, *tcurrent++);
- }
-
- std::sort(x, x + len, pc);
-
- scurrent = sfirst;
- tcurrent = tfirst;
- for (i = 0; i < len; ++i) {
- *scurrent++ = x[i].first;
- *tcurrent++ = x[i].second;
- }
-
- ::operator delete(x);
-}
-template <class S, class T> void
-// This Always uses std::sort
-CoinSort_2Std(S* sfirst, S* slast, T* tfirst)
-{
- CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
-}
-#ifndef COIN_USE_EKK_SORT
-//-----------------------------------------------------------------------------
-template <class S, class T> void
-CoinSort_2(S* sfirst, S* slast, T* tfirst)
-{
- CoinSort_2(sfirst, slast, tfirst, CoinFirstLess_2<S,T>());
-}
-#else
-//-----------------------------------------------------------------------------
-extern int boundary_sort;
-extern int boundary_sort2;
-extern int boundary_sort3;
-/// Sort without new and delete
-template <class S, class T> void
-CoinSort_2(S* key, S* lastKey, T* array2)
-{
- const size_t number = coinDistance(key, lastKey);
- if (number <= 1) {
- return;
- } else if (number>10000) {
- CoinSort_2Std(key, lastKey, array2);
- return;
- }
-#if 0
- if (number==boundary_sort3) {
- printf("before sort %d entries\n",number);
- for (int j=0;j<number;j++) {
- std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
- }
- std::cout<<std::endl;
- }
-#endif
- int minsize=10;
- int n = static_cast<int>(number);
- int sp;
- S *v = key;
- S *m, t;
- S * ls[32] , * rs[32];
- S *l , *r , c;
- T it;
- int j;
- /*check already sorted */
- S last=key[0];
- for (j=1;j<n;j++) {
- if (key[j]>=last) {
- last=key[j];
- } else {
- break;
- } /* endif */
- } /* endfor */
- if (j==n) {
- return;
- } /* endif */
- sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
- while( sp >= 0 )
- {
- if ( rs[sp] - ls[sp] > minsize )
- {
- l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
- if ( *l > *m )
- {
- t = *l ; *l = *m ; *m = t ;
- it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
- }
- if ( *m > *r )
- {
- t = *m ; *m = *r ; *r = t ;
- it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
- if ( *l > *m )
- {
- t = *l ; *l = *m ; *m = t ;
- it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
- }
- }
- c = *m ;
- while ( r - l > 1 )
- {
- while ( *(++l) < c ) ;
- while ( *(--r) > c ) ;
- t = *l ; *l = *r ; *r = t ;
- it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
- }
- l = r - 1 ;
- if ( l < m )
- { ls[sp+1] = ls[sp] ;
- rs[sp+1] = l ;
- ls[sp ] = r ;
- }
- else
- { ls[sp+1] = r ;
- rs[sp+1] = rs[sp] ;
- rs[sp ] = l ;
- }
- sp++ ;
- }
- else sp-- ;
- }
- for ( l = v , m = v + (n-1) ; l < m ; l++ )
- { if ( *l > *(l+1) )
- {
- c = *(l+1) ;
- it = array2[(l-v)+1] ;
- for ( r = l ; r >= v && *r > c ; r-- )
- {
- *(r+1) = *r ;
- array2[(r-v)+1] = array2[(r-v)] ;
- }
- *(r+1) = c ;
- array2[(r-v)+1] = it ;
- }
- }
-#if 0
- if (number==boundary_sort3) {
- printf("after sort %d entries\n",number);
- for (int j=0;j<number;j++) {
- std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
- }
- std::cout<<std::endl;
- CoinSort_2Many(key, lastKey, array2);
- printf("after2 sort %d entries\n",number);
- for (int j=0;j<number;j++) {
- std::cout<<" ( "<<key[j]<<","<<array2[j]<<")";
- }
- std::cout<<std::endl;
- }
-#endif
-}
-#endif
-#endif
-/// Sort without new and delete
-template <class S, class T> void
-CoinShortSort_2(S* key, S* lastKey, T* array2)
-{
- const size_t number = coinDistance(key, lastKey);
- if (number <= 2) {
- if (number == 2 && key[0] > key[1]) {
- S tempS = key[0];
- T tempT = array2[0];
- key[0] = key[1];
- array2[0] = array2[1];
- key[1] = tempS;
- array2[1] = tempT;
- }
- return;
- } else if (number>10000) {
- CoinSort_2Std(key, lastKey, array2);
- return;
- }
- int minsize=10;
- size_t n = number;
- int sp;
- S *v = key;
- S *m, t;
- S * ls[32] , * rs[32];
- S *l , *r , c;
- T it;
- size_t j;
- /*check already sorted */
- S last=key[0];
- for (j=1;j<n;j++) {
- if (key[j]>=last) {
- last=key[j];
- } else {
- break;
- } /* endif */
- } /* endfor */
- if (j==n) {
- return;
- } /* endif */
- sp = 0 ; ls[sp] = v ; rs[sp] = v + (n-1) ;
- while( sp >= 0 )
- {
- if ( rs[sp] - ls[sp] > minsize )
- {
- l = ls[sp] ; r = rs[sp] ; m = l + (r-l)/2 ;
- if ( *l > *m )
- {
- t = *l ; *l = *m ; *m = t ;
- it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
- }
- if ( *m > *r )
- {
- t = *m ; *m = *r ; *r = t ;
- it = array2[m-v] ; array2[m-v] = array2[r-v] ; array2[r-v] = it ;
- if ( *l > *m )
- {
- t = *l ; *l = *m ; *m = t ;
- it = array2[l-v] ; array2[l-v] = array2[m-v] ; array2[m-v] = it ;
- }
- }
- c = *m ;
- while ( r - l > 1 )
- {
- while ( *(++l) < c ) ;
- while ( *(--r) > c ) ;
- t = *l ; *l = *r ; *r = t ;
- it = array2[l-v] ; array2[l-v] = array2[r-v] ; array2[r-v] = it ;
- }
- l = r - 1 ;
- if ( l < m )
- { ls[sp+1] = ls[sp] ;
- rs[sp+1] = l ;
- ls[sp ] = r ;
- }
- else
- { ls[sp+1] = r ;
- rs[sp+1] = rs[sp] ;
- rs[sp ] = l ;
- }
- sp++ ;
- }
- else sp-- ;
- }
- for ( l = v , m = v + (n-1) ; l < m ; l++ )
- { if ( *l > *(l+1) )
- {
- c = *(l+1) ;
- it = array2[(l-v)+1] ;
- for ( r = l ; r >= v && *r > c ; r-- )
- {
- *(r+1) = *r ;
- array2[(r-v)+1] = array2[(r-v)] ;
- }
- *(r+1) = c ;
- array2[(r-v)+1] = it ;
- }
- }
-}
-//#############################################################################
-//#############################################################################
-
-/**@name Ordered Triple Struct */
-template <class S, class T, class U>
-class CoinTriple {
-public:
- /// First member of triple
- S first;
- /// Second member of triple
- T second;
- /// Third member of triple
- U third;
-public:
- /// Construct from ordered triple
- CoinTriple(const S& s, const T& t, const U& u):first(s),second(t),third(u) {}
-};
-
-//#############################################################################
-/**@name Comparisons on first element of two ordered triples */
-//@{
-/** Function operator.
- Returns true if t1.first &lt; t2.first (i.e., increasing). */
-template < class S, class T, class U >
-class CoinFirstLess_3 {
-public:
- /// Compare function
- inline bool operator()(const CoinTriple<S,T,U>& t1,
- const CoinTriple<S,T,U>& t2) const
- { return t1.first < t2.first; }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Returns true if t1.first &gt; t2.first (i.e, decreasing). */
-template < class S, class T, class U >
-class CoinFirstGreater_3 {
-public:
- /// Compare function
- inline bool operator()(const CoinTriple<S,T,U>& t1,
- const CoinTriple<S,T,U>& t2) const
- { return t1.first>t2.first; }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Returns true if abs(t1.first) &lt; abs(t2.first) (i.e., increasing). */
-template < class S, class T, class U >
-class CoinFirstAbsLess_3 {
-public:
- /// Compare function
- inline bool operator()(const CoinTriple<S,T,U>& t1,
- const CoinTriple<S,T,U>& t2) const
- {
- const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
- const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
- return t1Abs < t2Abs;
- }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Returns true if abs(t1.first) &gt; abs(t2.first) (i.e., decreasing). */
-template < class S, class T, class U >
-class CoinFirstAbsGreater_3 {
-public:
- /// Compare function
- inline bool operator()(const CoinTriple<S,T,U>& t1,
- const CoinTriple<S,T,U>& t2) const
- {
- const T t1Abs = t1.first < static_cast<T>(0) ? -t1.first : t1.first;
- const T t2Abs = t2.first < static_cast<T>(0) ? -t2.first : t2.first;
- return t1Abs > t2Abs;
- }
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Compare based on the entries of an external vector, i.e., returns true if
- vec[t1.first &lt; vec[t2.first] (i.e., increasing wrt. vec). Note that to
- use this comparison operator .first must be a data type automatically
- convertible to int. */
-template < class S, class T, class U, class V>
-class CoinExternalVectorFirstLess_3 {
-private:
- CoinExternalVectorFirstLess_3();
-private:
- const V* vec_;
-public:
- inline bool operator()(const CoinTriple<S,T,U>& t1,
- const CoinTriple<S,T,U>& t2) const
- { return vec_[t1.first] < vec_[t2.first]; }
- CoinExternalVectorFirstLess_3(const V* v) : vec_(v) {}
-};
-//-----------------------------------------------------------------------------
-/** Function operator.
- Compare based on the entries of an external vector, i.e., returns true if
- vec[t1.first &gt; vec[t2.first] (i.e., decreasing wrt. vec). Note that to
- use this comparison operator .first must be a data type automatically
- convertible to int. */
-template < class S, class T, class U, class V>
-class CoinExternalVectorFirstGreater_3 {
-private:
- CoinExternalVectorFirstGreater_3();
-private:
- const V* vec_;
-public:
- inline bool operator()(const CoinTriple<S,T,U>& t1,
- const CoinTriple<S,T,U>& t2) const
- { return vec_[t1.first] > vec_[t2.first]; }
- CoinExternalVectorFirstGreater_3(const V* v) : vec_(v) {}
-};
-//@}
-
-//#############################################################################
-
-/**@name Typedefs for sorting the entries of a packed vector based on an
- external vector. */
-//@{
-/// Sort packed vector in increasing order of the external vector
-typedef CoinExternalVectorFirstLess_3<int, int, double, double>
-CoinIncrSolutionOrdered;
-/// Sort packed vector in decreasing order of the external vector
-typedef CoinExternalVectorFirstGreater_3<int, int, double, double>
-CoinDecrSolutionOrdered;
-//@}
-
-//#############################################################################
-
-/** Sort a triple of containers.<br>
-
- Iter_S - iterator for first container<br>
- Iter_T - iterator for 2nd container<br>
- Iter_U - iterator for 3rd container<br>
- CoinCompare3 - class comparing CoinTriples<br>
-*/
-#ifdef COIN_SORT_ARBITRARY_CONTAINERS
-template <class Iter_S, class Iter_T, class Iter_U, class CoinCompare3> void
-CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst,
- const CoinCompare3& tc)
-{
- typedef typename std::iterator_traits<Iter_S>::value_type S;
- typedef typename std::iterator_traits<Iter_T>::value_type T;
- typedef typename std::iterator_traits<Iter_U>::value_type U;
- const size_t len = coinDistance(sfirst, slast);
- if (len <= 1)
- return;
-
- typedef CoinTriple<S,T,U> STU_triple;
- STU_triple* x =
- static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
-
- int i = 0;
- Iter_S scurrent = sfirst;
- Iter_T tcurrent = tfirst;
- Iter_U ucurrent = ufirst;
- while (scurrent != slast) {
- new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
- }
-
- std::sort(x, x+len, tc);
-
- scurrent = sfirst;
- tcurrent = tfirst;
- ucurrent = ufirst;
- for (i = 0; i < len; ++i) {
- *scurrent++ = x[i].first;
- *tcurrent++ = x[i].second;
- *ucurrent++ = x[i].third;
- }
-
- ::operator delete(x);
-}
-//-----------------------------------------------------------------------------
-template <class Iter_S, class Iter_T, class Iter_U> void
-CoinSort_3(Iter_S sfirst, Iter_S slast, Iter_T tfirst, Iter_U, ufirst)
-{
- typedef typename std::iterator_traits<Iter_S>::value_type S;
- typedef typename std::iterator_traits<Iter_T>::value_type T;
- typedef typename std::iterator_traits<Iter_U>::value_type U;
- CoinSort_3(sfirts, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
-}
-
-#else //=======================================================================
-
-template <class S, class T, class U, class CoinCompare3> void
-CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst, const CoinCompare3& tc)
-{
- const size_t len = coinDistance(sfirst,slast);
- if (len <= 1)
- return;
-
- typedef CoinTriple<S,T,U> STU_triple;
- STU_triple* x =
- static_cast<STU_triple*>(::operator new(len * sizeof(STU_triple)));
-
- size_t i = 0;
- S* scurrent = sfirst;
- T* tcurrent = tfirst;
- U* ucurrent = ufirst;
- while (scurrent != slast) {
- new (x+i++) STU_triple(*scurrent++, *tcurrent++, *ucurrent++);
- }
-
- std::sort(x, x+len, tc);
-
- scurrent = sfirst;
- tcurrent = tfirst;
- ucurrent = ufirst;
- for (i = 0; i < len; ++i) {
- *scurrent++ = x[i].first;
- *tcurrent++ = x[i].second;
- *ucurrent++ = x[i].third;
- }
-
- ::operator delete(x);
-}
-//-----------------------------------------------------------------------------
-template <class S, class T, class U> void
-CoinSort_3(S* sfirst, S* slast, T* tfirst, U* ufirst)
-{
- CoinSort_3(sfirst, slast, tfirst, ufirst, CoinFirstLess_3<S,T,U>());
-}
-
-#endif
-
-//#############################################################################
-
-#endif
generated by cgit (git 2.34.1) at 2024-12-19 15:07:29 +0000