Back to index

texmacs  1.0.7.15
merge_sort.hpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : merge_sort
00004 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00005 *******************************************************************************
00006 * This software falls under the GNU general public license version 3 or later.
00007 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00008 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00009 ******************************************************************************/
00010 
00011 #ifndef MERGE_SORT_H
00012 #define MERGE_SORT_H
00013 #include "array.hpp"
00014 #include "hashmap.hpp"
00015 
00016 template<class T> struct less_eq_operator {
00017   static inline bool leq(T& a, T& b) { return a<=b; }
00018 };
00019 
00020 template<class T, class LEQ> static void
00021 merge_sort_sub (array<T>& a, int start, int end, array<T> &merge_buf) {
00022   if (end-start<=1) return;
00023   if (end-start==2) {
00024     if (!LEQ::leq(a[start], a[start+1])) {
00025       merge_buf[start]=a[start];
00026       a[start]=a[start+1];
00027       a[start+1]=merge_buf[start];
00028     }
00029     return;
00030   }
00031   int middle=(start+end)>>1; 
00032   merge_sort_sub<T, LEQ> (a,start,middle,merge_buf);
00033   merge_sort_sub<T, LEQ> (a,middle,end,merge_buf);
00034   int i,j,k;
00035   for (i=start, j=middle, k=start; (i<middle) && (j<end); )
00036     if (LEQ::leq(a[i], a[j])) merge_buf[k++]=a[i++];
00037     else                      merge_buf[k++]=a[j++];
00038   j=k;
00039   while (i!=middle) a[k++]=a[i++];
00040   for (i=start; i<j; i++) a[i]=merge_buf[i];
00041 }
00042 
00043 template<class T, class LEQ> void
00044 merge_sort_leq (array<T>& a) {
00045   array<T> merge_buf(N(a)); 
00046   merge_sort_sub<T, LEQ> (a, 0, N(a), merge_buf); }
00047 
00048 template<class T> inline void
00049 merge_sort (array<T>& a) {
00050   merge_sort_leq <T, less_eq_operator<T> > (a); }
00051 
00052 struct less_eq_associate {
00053   static inline bool leq (tree& a, tree& b) {
00054     return as_string(a[0]) <= as_string(b[0]); }
00055 };
00056 
00057 template <class T, class U> static tree
00058 make_collection (hashmap<T,U> h) {
00059   tree t(h);
00060   array<tree> a=A(h);
00061   merge_sort_leq <tree, less_eq_associate> (a);
00062   int i, n=N(a);
00063   for (i=0; i<n; i++) t[i] = a[i];
00064   return t;
00065 }
00066 
00067 #endif // MERGE_SORT_H