// Jan 17 2006 by Dustin McCormick < djmccormick@gmail.com >
// Tested with gcc version 3.3.4 on GNU/Linux 2.4.29 i686
//
// gcc: 	http://gcc.gnu.org/
// GNU: 	http://www.gnu.org/
// Linux: 	http://www.kernel.org/

#include <iostream> 
using namespace std;

void fillArray(int a[], unsigned int size, int quit);
// accepts an array, the size of the array, and the sentinel value to end input prematurely.
// modifies a[], filling it with user input until the value of quit is reached.
int smallestInArray(const int* a, unsigned int size, int quit, unsigned int offset=0);
// accepts an array, the size of the array, the sentinel value to end input prematurely, and 
//	the index of the offset to begin at.
// returns the index of the smallest value after offset.
void sortArray(int a[], unsigned int size, int quit, bool order = 0);
// accepts an array, the size of the array, the sentinel value to end input prematurely, and 
// 	the order (0 for ASC, 1 for DESC.
// modifies a[], ordering the elements by value in either ASC or DESC order.
void swapValues(int& x, int& y);
// accepts two variables, most often array elements.
// swaps the values x and y.
void showArray(int a[], unsigned int size, int quit, unsigned int offset = 0);
// accepts an array, the size of the array, the sentinel value to end input prematurely, and 
//	the index of the offset to begin at.
// displays a[] line by line
void reverseArray(int a[], unsigned int size, int quit);
// accepts an array, the size of the array, and the sentinel value to end input prematurely
// modifies a[], reversing the sort order.

int main(){
	int a[20], quit = -999, size = sizeof(a) / sizeof(a[0]), y = 1;

	// Produce an error if the size of the array is greater than 50 elements
	if(size > 50){
		cerr << "The array may not have more than 50 elements." << endl;
		exit(1);
	}

	// Fill and sort the array
	fillArray(a, size, quit);
	sortArray(a, size, quit, 1);

	// Print a heading
	cout << "\nN\t\tCount" << endl;

	// Display values along with the number of times they appear in the array
	for(unsigned int x = 0; x < size && a[x] != quit; x++){
		cout << a[x] << "\t\t";
		while(a[x] == a[x+1]){
			x++;
			y++;
		}
		cout << y << endl;
		y = 1;
	}

	// All done (wasn't that easy?)
	return 0;
}

void fillArray(int a[], unsigned int size, int quit){
	unsigned int x = 0;

	cout << "You can enter a maximum of " << size << " elements." << endl;

	do{
		cout << "Enter an integer, or " << quit << " to quit: ";
		cin >> a[x];

		x++;
	} while(x < size && a[x-1] != -999);
}

int smallestInArray(const int a[], unsigned int size, int quit, unsigned int offset){
	int indexOfSmallest = offset;

	for(unsigned int x = offset+1; x < size && a[x] != quit; x++){
		if(a[x] < a[indexOfSmallest]){
			indexOfSmallest = x;
		}
	}

	return indexOfSmallest;
}

void sortArray(int a[], unsigned int size, int quit, bool order){
	int y;

	// We have to make sure the first value isn't -999, otherwise we'll incorrectly 
	// 	begin swapping values
	if(a[1] != -999){
		for(unsigned int x = 0; x < size-1 && a[x] != quit; x++){
			y = smallestInArray(a, size, quit, x);
			swapValues(a[x], a[y]);
		}
	}

	// If they want a DESC array, we'll have to flip the order
	if(order == 1){
		reverseArray(a, size, quit);
	}
}

void swapValues(int& x, int& y){
	int tmp;

	tmp = x;
	x = y;
	y = tmp;
}

void showArray(int a[], unsigned int size, int quit, unsigned int offset){
	// This function is mainly for bugtesting and to assure that 
	// 	arrays have been sorted properly.
	for(unsigned int x = offset; x < size && a[x] != quit; x++){
		cout << x << ": " << a[x] << endl;
	}
}

void reverseArray(int a[], unsigned int size, int quit){
	unsigned int quitIndex = 51;

	// Did they quit prematurely when inputting?
	for(unsigned int x = 0; x < size && quitIndex == 51; x++){
		if(a[x] == quit){
			quitIndex = x;
		}
	}

	// If so, quitIndex should no longer be 51. Otherwise, we want size left alone.
	if(quitIndex != 51){
		size = quitIndex;
	}

	// Time to swap them around...
        for(unsigned int x = 0; x < (size/2); x++){
                swapValues(a[x], a[(size-1)-x]);
        }
}