/*
Authors:Travis Gadberry
	Patrick Hesser
	Chris Ladewig
Date:	18 Feb 05
Updated:18 Feb 05
File:	HeapSort.cpp
*/


#ifndef HEAPSORT_H
#define HEAPSORT_H
  #include "HeapSort.h"
#endif

HeapSort::
HeapSort() {
  n = 1;
  A = new int[n];
  A[0] = 0;
  sorted = true;
}

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

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

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

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

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

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

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

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

void
HeapSort::
sort() {
  clock_t t1, t2;
  t1 = clock();

  int i;
  int tmp;

  build_heap(A, n);
  for(i = n-1; i >= 1; i--) {
    tmp = A[0];
    A[0] = A[i];
    A[i] = tmp;
    heapify(A, i, 0);
  }

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

void
HeapSort::
build_heap(int * B, int n) {
  int i;
  for(i = n/2-1; i >= 0; i--)
    heapify(A, n, i);
}

void
HeapSort::
heapify(int * B, int n, int i) {
  int l, r, largest;
  int tmp;
  l = 2*i+1;
  r = 2*(i+1);
  if((increments++, l < n) && (increments++, A[l] > A[i]))
    largest = l;
  else
    largest = i;
  if((increments++, r < n) && (increments++, A[r] > A[largest]))
    largest = r;
  if(increments++, largest != i) {
    tmp = A[i];
	A[i]=A[largest];
    A[largest] = tmp;
    heapify(A, n, largest);
  }
}


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

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

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

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