// PROGRAM ID:  selection.cpp / The Selection Sort
// REMARKS:  This program illustrates the logic of the selection sort.
// This program reads a collection of words from a file and stores them
// in an array.  The name of the file is given on the UNIX command-line.
// No more than 50 words will ever be in the file.  After the words are
// read into an array, the array is sorted in ascending order using the
// "selection sort" algorithm and the sorted words are printed out.
                                                                        
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

// Global symbolic constants:
const int MAXWORDS   = 50;             // Maximum number of words to store.
const int NOT_FOUND  = -1;             // "Word not found" sentinel value.

// Function prototypes:
void LoadArray(string word[], int& numberOfWords, char wordsFileName[]);
void PrintArray(const string word[], int numberOfWords);
int  LocMin(const string word[], int first, int last);
void Sort(string word[], int numberOfWords);


int main( int argc, char * argv[] )
//        IN        IN
{
	string word[MAXWORDS];      // Word storage array.
	int numberOfWords;          // Number of words stored in "word" array.

	// Exit if wrong number of arguments supplied.
	if (argc != 2)
	{
		cout << "Error: wrong number of arguments.\n";
		return 1;
	}

	// Read words from word input file (argv[1]) into the "word" array.
	LoadArray(word, numberOfWords, argv[1]);

	// Sort the "word" array in ascending alphabetical order.
	Sort(word, numberOfWords);

	// Print the contents of the "word" array, one per line.
	PrintArray(word, numberOfWords);

	return 0;
} // end main


// Read entries from "wordsFileName" file and store in the "word" array.
void LoadArray(string word[], int& numberOfWords, char wordsFileName[])
//             OUT            OUT                 IN
{
	ifstream input;               // Input file containing words.
	string   wordEntry;           // Entry item from input file (a word)

	// Open specified input file.
	input.open( wordsFileName );

	// One by one, store each word in input file into "word" array.
	numberOfWords = 0;
	input >> wordEntry;
	while ( input && numberOfWords<MAXWORDS)
	{
		word[numberOfWords] = wordEntry;
		numberOfWords++;
		input >> wordEntry;
	}

	// Close the input file.
	input.close();
} // end LoadArray


// Print the contents of the "word" array, one per line.
void PrintArray(const string word[], int numberOfWords)
//              IN                   IN
{
	for (int i=0; i < numberOfWords; i++)
		cout << word[i] << endl;
} // end PrintArray


// Return the subscript of the "smallest/minimal" value in array slice
int  LocMin(const string word[], int first, int last)
//          IN                   IN         IN
{
	string best;     // smallest/minimal value (i.e., best) found so far
	int    bestPos;  // subscript where the value of "best" was drawn from

	best = word[first];
	bestPos   = first;
	for (int k=first+1; k<=last; k++)
	{
		if (word[k] < best)
		{
			best = word[k];
			bestPos =   k;
		}
	}
	return bestPos;
}


// Selection Sort the "word" array in nondescending alphabetical order.
void Sort(string word[], int numberOfWords)
//        INOUT          IN
{
	int minPos;  // subscript where the current smallest element was found
	int bottom;  // subscript of bottom element in the array

	bottom = numberOfWords - 1;
	for (int top=0; top < bottom; top++)
	{
		minPos = LocMin(word, top, bottom);
		swap( word[top], word[minPos] );
	}
} // end Sort