html/doxygen/vector__sort_8hpp_source.html

00001
00002 /******************************************************************************
00003 * MODULE     : vector_sort.hpp
00004 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00005 *******************************************************************************
00006 * This software falls under the GNU general public license and comes WITHOUT
00007 * ANY WARRANTY WHATSOEVER. See the file $TEXMACS_PATH/LICENSE for more details.
00008 * If you don't have this file, write to the Free Software Foundation, Inc.,
00009 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
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 // Same functions but with the permutation sigma returned
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 (first (x), first (y)); }
00061   template<typename T, typename X> static inline bool
00062   not_op (const Pair& x, const Pair& y) {
00063     return Op::not_op (first (x), first (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]= second (tmp_v[i]);
00075   for (nat i= 0; i < N(v); i++) v[i]    = first  (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 } // namespace mmx
00084 #endif // __MMX__VECTOR_SORT__HPP