00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #ifndef __MMX__VECTOR_SORT__HPP
00013 #define __MMX__VECTOR_SORT__HPP
00014 #include <basix/pair.hpp>
00015 #include <basix/vector.hpp>
00016 #include <basix/operators.hpp>
00017 namespace mmx {
00018
00019 template<typename Op, typename T> static void
00020 sort_sub (vector<T>& a, int start, int end, vector<T>& merge_buf) {
00021 if (end-start <= 1) return;
00022 if (end-start == 2) {
00023 if (!Op::op (a[start], a[start+1])) {
00024 merge_buf[start]= a[start];
00025 a[start]= a[start+1];
00026 a[start+1]= merge_buf[start];
00027 }
00028 return;
00029 }
00030 int middle= (start+end)>>1;
00031 sort_sub<Op> (a, start, middle, merge_buf);
00032 sort_sub<Op> (a, middle, end, merge_buf);
00033 int i,j,k;
00034 for (i=start, j=middle, k=start; (i<middle) && (j<end); )
00035 if (Op::op (a[i], a[j])) merge_buf[k++]= a[i++];
00036 else merge_buf[k++]= a[j++];
00037 j=k;
00038 while (i!=middle) a[k++]= a[i++];
00039 for (i=start; i<j; i++) a[i]= merge_buf[i];
00040 }
00041
00042 template<typename Op, typename T> void
00043 sort_leq (vector<T>& v) {
00044 vector<T> merge_buf= fill<T> (N(v), CF(v));
00045 sort_sub<Op> (v, 0, N(v), merge_buf);
00046 }
00047
00048 template<typename T> inline void
00049 sort (vector<T>& v) {
00050 sort_leq<less_op> (v);
00051 }
00052
00053
00054
00055 template<typename Op>
00056 struct sort_op_pair_wrapper {
00057 #define Pair pair<T,X>
00058 template<typename T, typename X> static inline bool
00059 op (const Pair& x, const Pair& y) {
00060 return Op::op (car (x), car (y)); }
00061 template<typename T, typename X> static inline bool
00062 not_op (const Pair& x, const Pair& y) {
00063 return Op::not_op (car (x), car (y)); }
00064 #undef Pair
00065 };
00066
00067 template<typename Op, typename T> void
00068 sort_leq (vector<T>& v, vector<nat>& sigma) {
00069 typedef pair<T,nat> Pair;
00070 vector<Pair> tmp_v (Pair(T(),0), N(v)), merge_buf (Pair(T(),0), N(v));
00071 for (nat i= 0; i < N(v); i++) tmp_v[i]= Pair (v[i], i);
00072 sort_sub<sort_op_pair_wrapper<Op> > (tmp_v, 0, N(v), merge_buf);
00073 sigma= fill<nat> (N(v), CF(v));
00074 for (nat i= 0; i < N(v); i++) sigma[i]= cdr (tmp_v[i]);
00075 for (nat i= 0; i < N(v); i++) v[i] = car (tmp_v[i]);
00076 }
00077
00078 template<typename T> inline void
00079 sort (vector<T>& v, vector<nat>& sigma) {
00080 sort_leq<less_op> (v, sigma);
00081 }
00082
00083 }
00084 #endif // __MMX__VECTOR_SORT__HPP