#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#ifndef max
#define max(a,b)            (((a) > (b)) ? (a) : (b))
#endif


int merge(double *a, double *b, double *c, int na, int nb){
 int nc=na+nb;

 while(na || nb){
  if(!na){ *c++=*b++; nb--; }
  else if(!nb || *a<*b){ *c++=*a++; na--; }
  else { *c++=*b++; nb--; }
 }

 return nc;
}

void sort(double *a, int n){
 int i, j; double tmp;
 for(i = 1; i<n; i++){
  j = i;

  while(j>0 && a[j-1] > a[j]){
   tmp = a[j];
   a[j] = a[j - 1];
   a[j - 1] = tmp;
   j--;
  }  
 }
}

void polusum(double *a, int n){
 if(!n) return ;
 double c=a[0], r=a[1];

 for(int i=1; i<n-1; i++){
  r=a[i];
  a[i]=(c+a[i+1])/2;
  c=r;
 }

 return ;
}


#define TEST1_A 10
#define TEST1_B 10

#define TEST2_SZ 100

#define TEST3_SZ 100

int test(int t){

 srand (time(NULL));

 if(t==1){
  double a[TEST1_A], b[TEST1_B], c[TEST1_A+TEST1_B];
  for(int i=0; i<max(TEST1_A, TEST1_B); i++){
   if(i<TEST1_A) a[i]=rand() + (i ? a[i-1] : 0);
   if(i<TEST1_B) b[i]=rand() + (i ? b[i-1] : 0);
  }

  int cs=merge(a, b, c, 10, 10);
  if(cs!=TEST1_A+TEST1_B){ printf("TEST1 ERROR: cs\r\n"); return 0; }
  for(int i=0; i<cs-1; i++){
   if(c[i]>c[i+1]){ printf("TEST1 ERROR: array\r\n"); return 0; }
  }

  { printf("TEST1 DONE\r\n"); return 0; }

 }

 if(t==2){
  double a[TEST2_SZ];
  for(int i=0; i<TEST2_SZ; i++){
   a[i]=rand();
  }
  
  sort(a, TEST2_SZ);

  for(int i=0; i<TEST2_SZ-1; i++){
   if(a[i]>a[i+1]){ printf("TEST2 ERROR: array\r\n"); return 0; }
  }

  { printf("TEST2 DONE\r\n"); return 0; }
 }

 if(t==3){
  double a[TEST3_SZ], b[TEST3_SZ];
  for(int i=0; i<TEST3_SZ; i++){
   b[i]=a[i]=rand();
  }

  polusum(a, TEST3_SZ);

  for(int i=1; i<TEST3_SZ-1; i++){
   if(a[i]!=(b[i-1]+b[i+1])/2){
    printf("TEST3 ERROR: array\r\n");
    return 0;
   }
  }

  { printf("TEST3 DONE\r\n"); return 0; }
 }

 return 1;
}

int main(int args, char* arg[]){
 test(1);
 test(2);
 test(3);
 return 0;
}