// File:         heap.cc
// -------------------------------------------------------------------
// Author:       Russell Lowke, lowke@fas.harvard.edu
// TF:           Francis Crick
// Date:         7/31/2002
// Assignment:   Unit 7 Main programming exercises
// Version:      1	
//
// Description:
//
//     Modify heapsort so that it produced an ordered list of the 7 smallest
//  elements in an array.
//	
//	develop a formula for the average number of comparisons and the average
//  number of moves that your program requires for an array of n elements,
//  with n>>7.
//
//     Methods:
//				getIntList()  - reads a list of integers from the keyboard,
//				 printArray() - prints an array passed to it
//					   swap() - swap the values of two variables.
//					   sift() - sift the element in arr[start] down into position
//				   HeapSort() - heap sort an array.
//				   makeHeap() - Construct a heap from the unsorted array
//				  travArray() - array looking for smaller values
//
// Performance: 
//						data
//
//				20000 n = 20218 comparisons v 288 moves
//				15000 n = 15267 comparisons v 343 moves
//				10000 n = 10213 comparisons v 278 moves
//				 1600 n = 1766  comparisons v 219 moves
//				  800 n = 959   comparisons v 221 moves
//				  400 n = 517   comparisons v 169 moves
//				  200 n = 286   comparisons v 130 moves
//				  100 n = 172   comparisons v 116 moves
//
//
//		This shows that the number of comparisions for values of n = approx n,
//		while as n comparisons DOUBLES, numbers of moves increase at a rate of around 30 moves. 
//



#include <iostream>
#include <iomanip>
#include <cmath>
#include <values.h>

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


// 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;
}


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


//
// 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++;
}



//
// sift - move the element in arr[start] down into its correct
// position in a max-at-top heap
//
template <class elt>
void sift(elt arr[], int start, int end)
{
    int parent = start;
    int child = 2 * start;

    // Store the element being sifted in arr[0].
    arr[0] = arr[start];
	mvs++;
	
	
    // Find where the sifted element belongs.
    while (child <= end) {
		
		// Compare with the right child if it's bigger.
		// cmp++; ???
		if (child < end) {
			cmp++;
	    	if (arr[child] < arr[child + 1]) {
				child = child + 1;
			}
		}

		// Check if we're done.
		cmp++;
		if (arr[0] >= arr[child]) {
		    break;
		}

		//
		// If not, move child up and move down
		// one level in the tree.
		//
		arr[parent] = arr[child];
		mvs++;
		parent = child;
		child = 2 * child;
    }
    
    arr[parent] = arr[0];
    mvs++;
}



//
// HeapSort - perform heap sort on the specified array.
//
template <class elt>
void HeapSort(elt arr[], int num_objects)
{
    // Construct a heap from the unsorted array.
	makeHeap(arr, num_objects);

    // Repeatedly put elements in their correct positions.
    for (int right = num_objects; right >= 2; right--) {
		//
		// Put the top element (the largest element in
		// the unsorted portion of the array) in its
		// correct position, swapping it with the element
		// currently at that spot.
		//
		swap(arr[1], arr[right]);

		//
		// Rebuild a heap out of the unsorted portion
		// of the array.
		//
		sift(arr, 1, right - 1);
    }

}


//
// makeHeap - Construct a heap from the unsorted array.
//
template <class elt>
void makeHeap(elt arr[], int num_objects)
{
    // Construct a heap from the unsorted array.
    for (int left = num_objects/2; left >= 1; left--) {
		sift(arr, left, num_objects);
	}
}


//
// traverse large array looking for
// values smaller that that at top of heap
void travArray(int * array, int * small, int& sortPos, int n)
{
	for (; sortPos <= n; sortPos++) {
		
		// looking for smaller value
		cmp++;
		if (array[sortPos] < small[1]) {
			
			small[1] = array[sortPos];	// place small num on heap top
			mvs++;
			sift(small, 1, SMALLHEAP);	// sift
		}
	}
}


//
//  Asks for large array from user, copies first seven elements into small array,
//  then makes a heap of the small array.  Calls travArray to 
//
int main()
{
	int array[MAXENTERIES];
	int small[SMALLHEAP + 1];
	int n = -1;
	
	// get large array of numbers
	while (n < 7) {
		n = getIntList("Type the numbers: ", array, -1, MAXENTERIES);
		
		if (n < 7) {
			cout << "need at least 7 numbers" << endl;
		}
	}
	
	// copy the first seven items from array into small
	small[0] = 0;
	int sortPos = 1;
	for (; sortPos <= SMALLHEAP; sortPos++) {
		small[sortPos] = array[sortPos];
	}
	
	// sort
	makeHeap(small, SMALLHEAP);			 // make "largest at top" heap
	travArray(array, small, sortPos, n); // traverse array for small ints
	HeapSort(small, SMALLHEAP);			 // sort the small heap
	
	// output
	printArray(small, SMALLHEAP);
	cout << "Number of comparisons = " << cmp << endl;
	cout << "Number of moves       = " << mvs << endl;
	
	exit (0);
}