/* $Id$ */
// 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

/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
*/