# include <iostream>
# include <vector>
# include <string>
# include <cstdlib>
# include <ctime>
# include <fstream>

using namespace std;

void printVector(const vector< int > & a);
bool sorted(const vector< int > & a);
void bubbleSort1(vector< int > & );
void bubbleSort2(vector< int > & );

// A void function that takes three parameters:
// 1. a pointer to a function that takes a reference to a vector<int> object
// 2. a reference to a vector<int> object
// 3. a string - Name of sorting algorithm
// 3. a string - Name of input file
void runSort ( void( * )( vector<int> &) , const vector<int> & , string , string) ;

int main(){
    vector<string> fileNames;
    vector<int> original;
    int number;

    fileNames.push_back("listA1.txt");
    fileNames.push_back("listB1.txt");
    fileNames.push_back("listC1.txt");
    fileNames.push_back("listD1.txt");
    fileNames.push_back("listE1.txt");

    for(int i = 0; i < (int)fileNames.size(); i++){
        // Reset file stream and vector
        ifstream inFile;
        original.clear();

        // Open file
        inFile.open(fileNames[i].c_str());
        if(!inFile) {
            cerr << "Error! Cannot open " << fileNames[i] << endl;
            return EXIT_FAILURE;
        }

        // Read and close file
        inFile >> number; // First number
        while(inFile){ // Remaining numbers
            original.push_back(number);
            inFile >> number;
        }
        inFile.close();

        cout << "\n========== " << fileNames[i] << " (n = " << original.size() << ") ==========" << endl;

        // Sort the file using Bubble Sort
        runSort(bubbleSort1, original, "Bubble Sort Version 1" , fileNames[i]);
        runSort(bubbleSort2, original, "Bubble Sort Version 2" , fileNames[i]);


    } // End processing one file (end of for loop)


    return EXIT_SUCCESS;
}

// ================================================================
// Utility Functions
// ================================================================
void printVector(const vector< int > & a){
    cout << "[ ";

    if(!a.empty()){
        vector< int >::const_iterator itr = a.begin();
        cout << *itr++; // print first item

        while( itr != a.end() )
            cout << ", " << *itr++;
    }

    cout << " ]";
}

// ================================================================
// Returns true is sorted, returns false otherwise
bool sorted(const vector< int > & a){
    for(size_t i = 0; i < a.size()-1; i++){
        if(a[i] > a[i+1])
            return false;
    }
    return true;
}

// ================================================================
// Function to run the sorting routings
void runSort ( void( * sorter )( vector<int> &) , const vector<int> & original, string sorterName, string fileName){
    long start, elapsed;
    vector<int> a;

    cout << sorterName << ": ";
    a = original;
    start = clock();
    ( * sorter )(a);
    elapsed = clock() - start;

    if(!sorted(a))
        cout << "Error, result not sorted. ";
    cout << elapsed << " ticks ( "
        << elapsed / CLOCKS_PER_SEC << " seconds )." << endl;

}

// ================================================================
// Sorting Functions
// ================================================================

// ================================================================
// Bubble Sort that traverses entire list in each pass
void bubbleSort1(vector< int > & vect){
	size_t i, j;
	int temp;
    for (i = 0; i < vect.size(); i++){
        for (j = 0; j < vect.size()-1; j++){
            if(vect[j] > vect[j+1]){
    			temp = vect[j];
    			vect[j] = vect[j+1];
    			vect[j+1] = temp;
			}
        }
    }
}


// ================================================================
// Bubble Sort that traverses fewer items in each pass
void bubbleSort2(vector< int > & vect){
	size_t i, j;
	int temp;
    for (i = 0; i < vect.size(); i++){
        for (j = 0; j < vect.size()-1-i; j++){
            if(vect[j] > vect[j+1]){
    			temp = vect[j];
    			vect[j] = vect[j+1];
    			vect[j+1] = temp;
			}
        }
    }
}