/*
Authors:Travis Gadberry
	Patrick Hesser
	Chris Ladewig
Date:	9 Feb 05
Updated:16 Feb 05
File:	MergeSort.cpp
*/


#include "MergeSort.h"


MergeSort::
MergeSort() {
  n = 1;
  A = new int[n];
  B = new int[n];
  A[0] = 0;
  B[0] = 0;
  sorted = true;
  resetTime();
  resetIncrements();
}

MergeSort::
MergeSort(int * newArray, int N) {
  n = N;
  A = new int[n];
  B = new int[n];
  for(int i=0; i<n; i++)
    A[i] = newArray[i];
  sorted = false;
  resetTime();
  resetIncrements();
}

MergeSort::
~MergeSort() {
  delete(A);
}

int *
MergeSort::
getArray() {
  return A;
}

int
MergeSort::
getN() {
  return n;
}

bool
MergeSort::
getSorted() {
  return sorted;
}

double
MergeSort::
getTime() {
  return time;
}

int
MergeSort::
getIncrements() {
  return increments;
}

void
MergeSort::
setArray(int * newArray) {
  delete(A);
  n = sizeof(newArray);
  A = new int[n];
  B = new int[n];
  sorted = false;
}

void
MergeSort::
sort() {

  int i = n;
  int k;
  for(k=0; k<n; k++)
    B[k] = A[k];

  time_t t1, t2;
  t1 = clock();

  MSort(A, B, 0, n-1);

  t2 = clock();
  time = (t2 - t1)/CLOCKS_PER_SEC;

  for(k=0; k<i; k++)
    A[k] = B[k];
}

void
MergeSort::
MSort(int * source, int * destination, int lower, int upper) {
  int mid;
  if(increments++, lower < upper) {
    mid = (lower + upper) / 2;
    MSort(destination, source, lower, mid);
    MSort(destination, source, mid+1, upper);
    Merge(source, destination, lower, mid, upper);
  }
}

void
MergeSort::
Merge(int * source, int * destination, int lower, int mid, int upper) {
  int s1 = lower;
  int s2 = mid + 1;
  int d = lower;

  do {
    if(increments++, source[s1] < source[s2]) {
      destination[d] = source[s1];
      s1++;
    }
    else {
      destination[d] = source[s2];
      s2++;
    }
    d++;
  } while((increments++, s1 <= mid) && (increments++, s2 <= upper));

  if(increments++, s1 > mid)
    do {
      destination[d] = source[s2];
      s2++;
      d++;
    } while (increments++, s2 <= upper);
  else
    do {
      destination[d] = source[s1];
      s1++;
      d++;
    } while (increments++, s1 <= mid);
}

void
MergeSort::
setN(int newN) {
  n = newN;
}

void
MergeSort::
setSorted(bool newSorted) {
  sorted = newSorted;
}

void
MergeSort::
resetTime() {
  time = 0.0;
}

void
MergeSort::
resetIncrements() {
  increments = 0;
}