Back to index

texmacs  1.0.7.15
Classes | Functions
merge_sort.hpp File Reference
#include "array.hpp"
#include "hashmap.hpp"
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  less_eq_operator< T >
struct  less_eq_associate

Functions

template<class T , class LEQ >
static void merge_sort_sub (array< T > &a, int start, int end, array< T > &merge_buf)
template<class T , class LEQ >
void merge_sort_leq (array< T > &a)
template<class T >
void merge_sort (array< T > &a)
template<class T , class U >
static tree make_collection (hashmap< T, U > h)

Function Documentation

template<class T , class U >
static tree make_collection ( hashmap< T, U >  h) [static]

Definition at line 58 of file merge_sort.hpp.

                                 {
  tree t(h);
  array<tree> a=A(h);
  merge_sort_leq <tree, less_eq_associate> (a);
  int i, n=N(a);
  for (i=0; i<n; i++) t[i] = a[i];
  return t;
}

Here is the call graph for this function:

Here is the caller graph for this function:

template<class T >
void merge_sort ( array< T > &  a) [inline]

Definition at line 49 of file merge_sort.hpp.

                         {
  merge_sort_leq <T, less_eq_operator<T> > (a); }

Here is the caller graph for this function:

template<class T , class LEQ >
void merge_sort_leq ( array< T > &  a)

Definition at line 44 of file merge_sort.hpp.

                             {
  array<T> merge_buf(N(a)); 
  merge_sort_sub<T, LEQ> (a, 0, N(a), merge_buf); }

Here is the call graph for this function:

template<class T , class LEQ >
static void merge_sort_sub ( array< T > &  a,
int  start,
int  end,
array< T > &  merge_buf 
) [static]

Definition at line 21 of file merge_sort.hpp.

                                                                      {
  if (end-start<=1) return;
  if (end-start==2) {
    if (!LEQ::leq(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; 
  merge_sort_sub<T, LEQ> (a,start,middle,merge_buf);
  merge_sort_sub<T, LEQ> (a,middle,end,merge_buf);
  int i,j,k;
  for (i=start, j=middle, k=start; (i<middle) && (j<end); )
    if (LEQ::leq(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];
}

Here is the call graph for this function: