include/basix/vector_sort.hpp

Go to the documentation of this file.

/******************************************************************************
* MODULE     : vector_sort.hpp
* COPYRIGHT  : (C) 1999  Joris van der Hoeven
*******************************************************************************
* This software falls under the GNU general public license and comes WITHOUT
* ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
* If you don't have this file, write to the Free Software Foundation, Inc.,
* 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
******************************************************************************/

#ifndef __MMX__VECTOR_SORT__HPP
#define __MMX__VECTOR_SORT__HPP
#include <basix/pair.hpp>
#include <basix/vector.hpp>
#include <basix/operators.hpp>
namespace mmx {

template<typename Op, typename T> static void
sort_sub (vector<T>& a, int start, int end, vector<T>& merge_buf) {
  if (end-start <= 1) return;
  if (end-start == 2) {
    if (!Op::op (a[start], a[start+1])) {
      merge_buf[start]= a[start];
      a[start]= a[start+1];
      a[start+1]= merge_buf[start];
    }
    return;
  }
  int middle= (start+end)>>1; 
  sort_sub<Op> (a, start, middle, merge_buf);
  sort_sub<Op> (a, middle, end, merge_buf);
  int i,j,k;
  for (i=start, j=middle, k=start; (i<middle) && (j<end); )
    if (Op::op (a[i], a[j])) merge_buf[k++]= a[i++];
    else                     merge_buf[k++]= a[j++];
  j=k;
  while (i!=middle) a[k++]= a[i++];
  for (i=start; i<j; i++) a[i]= merge_buf[i];
}

template<typename Op, typename T> void
sort_leq (vector<T>& v) {
  vector<T> merge_buf= fill<T> (N(v), CF(v)); 
  sort_sub<Op> (v, 0, N(v), merge_buf);
}

template<typename T> inline void
sort (vector<T>& v) {
  sort_leq<less_op> (v);
}

// Same functions but with the permutation sigma returned

template<typename Op>
struct sort_op_pair_wrapper {
#define Pair pair<T,X>
  template<typename T, typename X> static inline bool
  op (const Pair& x, const Pair& y) {
    return Op::op (car (x), car (y)); }
  template<typename T, typename X> static inline bool
  not_op (const Pair& x, const Pair& y) {
    return Op::not_op (car (x), car (y)); }
#undef Pair
};
  
template<typename Op, typename T> void
sort_leq (vector<T>& v, vector<nat>& sigma) {
  typedef pair<T,nat> Pair;
  vector<Pair> tmp_v (Pair(T(),0), N(v)), merge_buf (Pair(T(),0), N(v));
  for (nat i= 0; i < N(v); i++) tmp_v[i]= Pair (v[i], i);  
  sort_sub<sort_op_pair_wrapper<Op> > (tmp_v, 0, N(v), merge_buf);
  sigma= fill<nat> (N(v), CF(v));
  for (nat i= 0; i < N(v); i++) sigma[i]= cdr (tmp_v[i]);
  for (nat i= 0; i < N(v); i++) v[i]    = car (tmp_v[i]);
}

template<typename T> inline void
sort (vector<T>& v, vector<nat>& sigma) {
  sort_leq<less_op> (v, sigma);
}

} // namespace mmx
#endif // __MMX__VECTOR_SORT__HPP

---