/*Matlab
figure; n=[100 1000 2000 3000 4000 5000 6000]; t=[0 0.04 0.15 0.32 0.56 0.87 1.26]; plot(n,t);

*/

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <assert.h>
#include <iomanip>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

// Aufgabe 2.1

vector <double> GenerateNumbers(string Selection, size_t n){
    vector<double> feld;

    for (size_t i = 0; i < n; i++){
        if (!string(Selection).compare("up")){ feld.push_back(i); }
        else if (!string(Selection).compare("down")){ feld.push_back(i*(-1)); }
        else if (!string(Selection).compare("constant")){ feld.push_back(17); }
        else if (!string(Selection).compare("random")){ feld.push_back((double)rand() / (RAND_MAX)); }
        else{ throw "Error: Das Programm braucht einen Modus! [random|up|down|constant]"; }
    }

    return feld;
}

//Aufgabe 2.2

template < class T > bool IsSortedAndNothingIsLost
(vector <T> &Before, vector <T> &After){
    bool SomethingIsLost = false;
    size_t n = Before.size();

    //überprüfung des sortierten vektors
    for (size_t i = 0; i<(n - 1); i++)
    {
        if (After[i]>After[i + 1])
        {
            return false;
        }
    }

    //Wir überprüfen jede einzelne Stelle und haken ab
    bool *hilfsarray = new bool[n];
    if (*hilfsarray == NULL){ throw "Das Hilfsarray hatte nicht genug speicher um erstellt zu werden."; }
    for (size_t i = 0; i<n; i++)
    {
        hilfsarray[i] = false;
    }

    // wir haken ab
    for (size_t i = 0; i<n; i++)
    {
        SomethingIsLost = true;
        for (size_t j = 0; j < n; j++){
            if (Before[i] == After[j] && false == hilfsarray[j]){
                hilfsarray[j] = true;
                SomethingIsLost = false;
                break;
            }
        }
        if (true == SomethingIsLost){
            delete[] hilfsarray;
            return false;
        }
    }
    delete[] hilfsarray;
    return true;

}

//Aufgabe 2.3

template <class T> void InsertionSort(vector<T> &a){
    const int len = (int)a.size();
    int i, j;
    T temp;
    for (i = 1; i < len; i++){
        temp = a[i];
        for (j = i - 1; j >= 0 && a[j] > temp; j--){
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

//template <class T> void MergeSort(vector<T> &a){
    /*int curr_size;  // For current size of subarrays to be merged
    // curr_size varies from 1 to n/2
    int left_start; // For picking starting index of left subarray
    // to be merged
    int n = a.size();

    // Merge subarrays in bottom up manner.  First merge subarrays of
    // size 1 to create sorted subarrays of size 2, then merge subarrays
    // of size 2 to create sorted subarrays of size 4, and so on.
    for (curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size)
    {
        // Pick starting point of different subarrays of current size
        for (left_start = 0; left_start<n - 1; left_start += 2 * curr_size)
        {
            // Find ending point of left subarray. mid+1 is starting
            // point of right
            int mid = left_start + curr_size - 1;

            int right_end = min(left_start + 2 * curr_size - 1, n - 1);

            // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
            merge(a, left_start, mid, right_end);
        }
    }
}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
//template <class T> void merge(vector<T> &a, int l, int m, int r)
/*{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // create temp vectors
    vector<T> L (n1), R(n2);

    // Copy data to temp vectors L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = a[l + i];
    for (j = 0; j < n2; j++)
        R[j] = a[m + 1 + j];

    // Merge the temp arrays back into arr[l..r]
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            a[k] = L[i];
            i++;
        }
        else
        {
            a[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1)
    {
        a[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2)
    {
        a[k] = R[j];
        j++;
        k++;
    }
}
/*
//Aufgabe 2.4
/*

template <class T> void MergeSort(vector<T> &a){
const int len = (int)a.size();
T* x = a;
T* y = new T[len];
for (int seg = 1; seg < len; seg += seg){
for (int start = 0; start < len; start += seg + seg){
int low = start;
int mid = (start + seg) < len ? (start + seg) : len;
int high = (start + seg + seg) < len ? (start + seg + seg) : len;
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2){
y[k++] = x[start1] < x[start2] ? a[start1++] : a[start2++];
}
while(start1 < end1){
y[k++] = x[start1++];
}
while (start2 < end2){
y[k++] = x[start2++];
}
}
T* temp = x;
x = y;
y = temp;
}
if (x != a){
for (int i = 0; i < len; i++){
y[i] = x[i];
}
y = x;
}
delete y[];
}
*/
//template <class T> void MergeSort(vector<T> &a){}



template <class T> void merge_sort(vector<T> &V, int size){
    vector<T> temp[size];
    int mid, i;
    if (size < 2) {
        return;
    }
    else {
        mid = size / 2;
        merge_sort(V, mid);
        merge_sort(V + mid, size - mid);
        merge(V, mid, V + mid, size - mid, temp);
        for (i = 0; i < size; i++) {
            V[i] = temp[i];
        }
    }
}

template <class T> int  merge(vector<T> &List1, int size1, vector<T> &List2, int size2, vector<T> &List3)
{
    int i1, i2, i3;
    if (size1 + size2 > size) {
        return false;
    }
    i1 = 0; i2 = 0; i3 = 0;
    /* while both lists are non-empty */
    while (i1 < size1 && i2 < size2) {
        if (list1[i1] < list2[i2]) {
            list3[i3++] = list1[i1++];
        }
        else {
            list3[i3++] = list2[i2++];
        }
    }
    while (i1 < size1) {
        /* copy remainder of list1 */
        list3[i3++] = list1[i1++];
    }
    while (i2 < size2) {
        /* copy remainder of list2 */
        list3[i3++] = list2[i2++];
    }
    return true;
}


int main(int argc, char *argv[]) {

    char *Selection = NULL;

    // Flags
    bool Vergleich = false;
    bool CheckResult = false;
    bool Zeitmessung = false;
    bool UseMergeSort = false;

    int SizeOfArray = 0;
    vector<double> Original;
    double MeasuredTime;

    // Zuerst fragen wir die Paramter ab:
    try{
        if (argv[1] == NULL){
            throw "mysort n Direction [ -o ] [ -c ] [ -t ] [ -m | -i ]";
        }

        if (!(istringstream(argv[1]) >> dec >> SizeOfArray)){
            throw "Der erste Wert muss ein Integer sein!";
        }

        if (SizeOfArray < 1){
            throw "keine negativen Zahlen erlaubt!";
        }


        // Selection
        if (!string(argv[2]).compare("up") ||
            !string(argv[2]).compare("down") ||
            !string(argv[2]).compare("constant") ||
            !string(argv[2]).compare("random")) {
            Selection = argv[2];
        }

        // checken für flags
        for (int i = 3; i < argc; i++){
            if (!string(argv[i]).compare("-c")) {
                CheckResult = true;
                continue;
            }
            if (!string(argv[i]).compare("-o")) {
                Vergleich = true;
                continue;
            }
            if (!string(argv[i]).compare("-t")) {
                Zeitmessung = true;
                continue;
            }
            if (!string(argv[i]).compare("-m") && !string(argv[i]).compare("-i")){
                throw "-m und -i darf nur einmal benutzt werden!";
            }
            if (!string(argv[i]).compare("-m")) {
                UseMergeSort = true;
                continue;
            }
            if (!string(argv[i]).compare("-i")) {
                UseMergeSort = false;
                continue;
            }
            else{
                throw "Wrong Switch, use only one of - o | -c | -t | -m | -i ";
            }

        }

        if (Selection == NULL){
            throw "Error: Das Programm braucht einen Modus! [random|up|down|constant]";
        }

        //Aufgabe 2.5

        Original.reserve(SizeOfArray);

        Original = GenerateNumbers(Selection, SizeOfArray);
        vector<double>Sorted(Original);

        MeasuredTime = double(clock());

        // Welchen Algorithmus ?
        if (UseMergeSort == true){
            merge_sort(Sorted, SizeOfArray);
        }
        else{
            InsertionSort(Sorted);
        }


        if (Zeitmessung == true){ MeasuredTime = (double(clock()) - MeasuredTime) / CLOCKS_PER_SEC; }

        // Erfolgsüberprüfung
        if (CheckResult == true){
            if (true == IsSortedAndNothingIsLost(Original, Sorted)){
                cout << "Success" << endl;
            }
            else{
                throw "Check failed";
            }
        }

        /*
        if (Vergleich == true){
            cout << "Ergebnisse:" << endl << " Original : Sorted" << endl;
            for (int i = 0; i < SizeOfArray; i++){
                cout << setprecision(5) << setw(9) << Original[i] << " : " << setprecision(5) << Sorted[i] << endl;
            }
        }
        */
        if (Zeitmessung == true){
            cout << "--- It took " << setprecision(32) << MeasuredTime << " seconds to compute---" << endl;
        }


    }
    catch (const char *Error){
        cerr << Error;
        exit(1);
    }

    return 0;
}