// File:         median.cc
// -------------------------------------------------------------------
// Author:       Russell Lowke, lowke@fas.harvard.edu
// TF:           Francis Crick
// Date:         7/29/2002
// Assignment:   Unit 7 Main programming exercises
// Version:      1	
//
// Description:
//
//     "Develop and implement an algorithm that finds the median of an array
//  of n elements by using the partitioning approach of quicksort.
//  Avoid sorting any partition that could not contain the median."
//
// 		findMedian first establishes if it is looking for one or two values
//	when searching for the median.  An n even array will need the two middle
//  values to be found (to be averaged), while an n odd array will need only
//  the middle value.
//		findMedian then calls the recursive fMedian() function passing to it the
//  index position it is looking for ( the middle(s) ).
//  	fMedian() is an adaptation of quicksort that sorts looking for only the value
//  at location index [indexAt].  This is done by sorting only the side of the partition
//  that covers the spot marked by said index [indexAt].
//			IMPORTANT: see "Note" inside function findMedian()  line 189
//
//     Methods:
//
//			getIntList() - reads a list of integers from the keyboard
//			swap()       - swap the values of two variables
//			printArray() - prints an array
//			fMedian()    - recursively quick sort array, looking only for value at [indexAt]
//			findMedian() - et the median value of an array
//
// Performance: When sorting an array of n UNSORTED elements, this program
//			    has approx moves*2 = comparisons.
//				Uneven sets of n elemets take about half the iterations, as only one value
//				need be searched for.
//
//		  Note: See "Note" inside function findMedian()  line 189
//

#include <iostream>
#include <iomanip>

const int MAXENTERIES = 100;  				// max number of enteries

// Note: I'm making the move and comparison counters global, as this is
// the cleanest implimentation, and such testing counters would be removed
// from final code when no longer needed for testing.
int mvs = 0;								// global count of moves
int cmp = 0;								// global count of comparisons


//
//  reads a list of integers from the keyboard,
//
int getIntList(char askStr[], int * intList, int endSig, int maxList)
{
	int  v = 0, n = 0;
	char c = '\0';
	
	// seed first value as 0
	*intList = 0;
	intList++;
	
	cout << askStr;
	
	do {
		cin >> v;
		c = cin.get();
		
		if ( cin.fail() ) {
			cout << "BAD input." << endl;
			cin.clear();					// clear error
			cin.ignore(80, '\n');			// empty buffer
			return -1;
		} else {
			*intList = v;
			intList++;
			n++;
		}
	} while ( c != '\n' && n < MAXENTERIES);
	
	return n;
}


//
// swap - swap the values of two variables.
// Used by several of the sorting algorithms below.
//
template <class elt>
void swap(elt& a, elt& b)
{
    elt temp;
    temp = a;
    mvs++;
    a = b;
    mvs++;
    b = temp;
    mvs++;
}


//
// prints the array
//
void printArray(int * array, int n)
{
	cout << "{ ";
	for (int i = 1; i <= n; i++) {
		cout << array[i] << " ";
	}
	cout << "}" << endl;
}


//
// fMedian - recursively perform quick sort on the subarray
// specifically looking for the value at index at position [indexAt]
//
template <class elt>
elt fMedian(elt arr[], int L, int R, int indexAt)
{
    int i = L;      // index moving from L to R
    int j = R;      // index moving from R to L

    // Select middle element as the pivot.
    arr[0] = arr[(L + R) / 2];
    mvs++;

    // Partition the array.
    do {
		// Find two elements to swap.
		while (arr[i] < arr[0]) {
			cmp++;
	    	i = i + 1;
		}
		while (arr[0] < arr[j]) {
			cmp++;
	    	j = j - 1;
		}

		if (i <= j) {
	    	swap(arr[i], arr[j]);
	    	i = i + 1;
	    	j = j - 1;
		}
    } while (i <= j);


	//
    // process only the partition half which holds [indexAt].
    //
    if ( indexAt >= L  && indexAt <= j) {
        
    	// process left side 
    	if (L < j) {
			fMedian(arr, L, j, indexAt);
		}
		
    } else if ( indexAt >= i  && indexAt <= R ) {
    	
    	// process right
    	if (j+1 < R) {
			fMedian(arr, i, R, indexAt);
		}
    } else {
    
    	// on partition
    }
    
    return arr[indexAt];	// return value at indexAt
}


//
// findMedian - get the median value of an array
//
template <class elt>
double findMedian(elt arr[], int num_objects)
{
	if (num_objects % 2 == 0) {
		
		// even length, 2 medians
		int left  = fMedian(arr, 1, num_objects, (num_objects / 2) );
		int right = fMedian(arr, 1, num_objects, (num_objects / 2) + 1 );
		
		// Note: Even though both median values are adjacent,
		//       frequently the second median falls outside the partition
		// 		 of the first, thus I seach for each separately, ensuring correct
		// 		 values.
		//
		// 		 fMedian could probably be improved to check for two locations
		// 		 and try to partition for both...
		
		return (left + right) / 2.0; // return average of the two
		
	} else {
	
		// odd length, 1 median
		return fMedian(arr, 1, num_objects, (num_objects / 2) + 1 );
	}
}

//
//  get a list of integers from user, and pass them to findMedian
//
int main()
{
	int array[MAXENTERIES];
	int n = -1;
	
	// get array of numbers
	while (n < 0) {
		n = getIntList("Type the numbers: ", array, -1, MAXENTERIES);
	}
	
	// output
	cout << "median is: " << findMedian(array, n) << endl;
	printArray(array, n);
	cout << "Number of comparisons = " << cmp << endl;	
	cout << "Number of moves       = " << mvs << endl;
	
    return 0;
}







