//
// SORT.CC
// Sorting function for Points
//
#include "sort.h"

//
// local prototypes
//
static void merge_sort(XYPoint *[], XYPoint*[], int, int, Comparator);


//
// sort()
//
// Input: A:   array of refs to input points
//        nPoints: length of A
//        lessThan: comparison function on Point *'s
//
// Output: Upon completion, the points in A are sorted in nondecreasing
//         order according to the lessThan() operator.
//
void sort(XYPoint *A[], int nPoints, Comparator lessThan) {
  XYPoint **temp = new XYPoint* [nPoints]; // temp storage for merge sort
  merge_sort(A, temp, 0, nPoints - 1, lessThan);
  delete [] temp;
}


//
// merge_sort()
//
// Input: A:    array of refs to input points
//        temp: array of same size as A, used during merging
//        l and r:  left and right bounds of interval to sort in A
//        lessThan: comparison function on Point *'s
//
// Output: Upon completion, the points in the interval A[l..r] are sorted 
// in nondecreasing order according to the lessThan() operator.
//
static void merge_sort(XYPoint *A[], XYPoint *temp[],
		       int l,int r, Comparator lessThan) {
  int srcLeft;     // index of current location in left half of A
  int srcRight;    // index of current location in right half of A
  int dst;         // index of current location in temp array
  int mid;         // index of the last element of the left half of A
  
  if (l == r) return;
  
  mid = (l + r) / 2;                         // find the middle
  merge_sort(A, temp, l, mid, lessThan);     // recursively sort the left half
  merge_sort(A, temp, mid + 1, r,lessThan);  // recursively sort the right half
  
  //  Now merge the 2 halves of A, until reaching the end of one
  
  srcLeft  = dst = l;
  srcRight = mid + 1;
  
  while (srcLeft <= mid && srcRight <= r) {
    if (lessThan(A[srcLeft], A[srcRight])) {
	  temp[dst] = A[srcLeft]; 
	  srcLeft++;
    } else {
      temp[dst] = A[srcRight];
      srcRight++; 
    }
    dst++; 
  }
  
  //  If there are any elements from the left half, copy them to the temp array
  while (srcLeft <= mid) {
      temp[dst] = A[srcLeft]; 
      srcLeft++; dst++;
  }
  
  // Now copy temp back into A (except those that we know are already there)
  for (int j = l; j < srcRight; j++)
    A[j] = temp[j];
}