#include "triFusion.h"

void sousTriFusion(long* A, const size_t p, const size_t r) {

  if (p + 1 < r) {
    size_t q = (size_t)((p + r) / 2);
    sousTriFusion(A, p, q);
    sousTriFusion(A, q, r);
    fusion(A, p, q, r);
  }
}

void fusion(long* A, const size_t p, const size_t q, const size_t r) {

  size_t n1 = q - p;
  size_t n2 = r - q;
  long* Ag = (long*) malloc(n1 * sizeof(long));
  long* Ad = (long*) malloc(n2 * sizeof(long));

  size_t cursor = 0;
  for (size_t i = p; i < q; i++) {
    Ag[cursor++] = A[i];
  }
  cursor = 0;
  for (size_t i = q; i < r; i++) {
    Ad[cursor++] = A[i];
  }

  size_t ind_g = 0;
  size_t ind_d = 0;
  size_t i = p;
  while (i < r) {
    if (ind_g == n1) {
      A[i] = Ad[ind_d++];
    }
    else if (ind_d == n2) {
      A[i] = Ag[ind_g++];
    }
    else if (Ag[ind_g] < Ad[ind_d]) {
      A[i] = Ag[ind_g++];
    }
    else {
      A[i] = Ad[ind_d++];
    }
    i++;
  }

}

void triFusion(long * A, size_t n){
    sousTriFusion(A, 0, n);
}

// --------------------------------------------------------

void sousTriFusionVerbose(long * A, size_t p, size_t r, struct data* d){
    if(p<(r-1)){
        d->comparison++;
        size_t q = (size_t)((p+r)/2);
        d->write++;
        sousTriFusionVerbose(A, p, q,d);
        sousTriFusionVerbose(A, q, r, d);
        fusionVerbose(A, p, q, r, d);
    }
}

void fusionVerbose(long * A, size_t p, size_t q, size_t r, struct data* d){
    size_t n1 = q-p;
    d->write++;
    size_t n2 = r-q;
    d->write++;

    long Ad[n2];
    memset(Ad, 0, n2);
    d->write+=n2;
    int j = 0;
    for(size_t i = q; i<r; i++){
        Ad[j] = A[i];
        d->write++;
        j++;
        d->write++;
    }

    long Ag[n1];
    memset(Ag, 0, n1);
    d->write+=n1;
    j = 0;
    for(size_t i = p; i<q; i++){
        Ag[j] = A[i];
        d->write++;
        j++;
        d->write++;
    }

    size_t indg = 0;
    size_t indd = 0;
    size_t i = p;
    d->write++;
    while (i < r){
        d->comparison++;
        if(indg == n1){
            d->comparison++;
            A[i] = Ad[indd];
            d->write++;
            indd++;
            d->write++;
        }
        else if(indd == n2){
            d->comparison+=2;
            A[i] == Ag[indg];
            d->write++;
            indg++;
            d->write++;
        }
        else if(Ag[indg] < Ad[indd]){
            d->comparison+=3;
            A[i] = Ag[indg];
            d->write++;
            indg++;
            d->write++;
        }
        else{
            d->comparison+=4;
            A[i] = Ad[indd];
            d->write++;
            indd++;
            d->write++;
        }
        i++;
        d->write++;
    }
}

void triFusionVerbose(long * A, size_t n, struct data* d){
    sousTriFusionVerbose(A, 0, n, d);
}