#include <stdio.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <time.h>
#include <stack>
using namespace std;

//Liste von Zufallszahlen erzeugen
vector<double> generate_func()
{
    cout << "Wie viele zufällige Zahlen möchtest du erzeugen?" << endl;
    int anzahl_rand_numbers=10;
    //cin >> anzahl_rand_numbers;
    cout << endl << "Zufallszahlen:" << endl;

    double random_number=0;
    vector<double> unsort_feld(anzahl_rand_numbers);

    for (int i=0; i<anzahl_rand_numbers; i++)
    {
        random_number = rand()%100;
        unsort_feld[i] = random_number;
        cout << random_number << ", ";
    }
    cout << endl;

    return unsort_feld;
}

//Liste von Zahlen einlesen
vector<double> input_func()
{
    ifstream list ("list.txt");
    // Prüfe ob die Datei offen ist
    if (!list.is_open())
    {
        throw 404;
    }

    //Ausgabe des inputs
    cout << "Input:" << endl;
    string line;
    int anzahl=0;
    while (list.good())
    {
        getline (list,line);
        cout << line << ", ";
        anzahl++;
    }
    cout << endl;

    //Einlesen in Feld
    vector<double> unsort_feld(anzahl);
    int i=0;
    //An Anfang der Liste gehen
    list.seekg( ios_base::beg );
    //Fehlerstatus der Liste leeren
    list.clear();
    while (list.good())
    {
        list >> unsort_feld[i];
        ++i;
    }
    list.close();

    return unsort_feld;
}

//Quick Sort Algorithmus
void quick_sort(vector<double> unsort_feld)
{
    int left=0, right;
    double pivot;
    int i, j;
    double swap;
    right = unsort_feld.size()-1;
    stack<int> mem;

    //äußere Schleife
    while (true)
    {
        if (left < right)
        {
            //Auswahl eines zufälligen Elements
            pivot = unsort_feld[left + rand() % (right - left)];
            i = left; //unsort_feld[(left+right)/2];
            j = right;
            //innere Schleife, teile Feld
            while (true)
            {
                while (unsort_feld[i] < pivot) i++;
                while (unsort_feld[j] > pivot) j--;
                if(i>=j) break;
                swap = unsort_feld[i];
                unsort_feld[i] = unsort_feld[j];
                unsort_feld[j] = swap;
            }
            mem.push(right);
            right = max(left,i-1);
        }
        else
        {
            if (mem.empty() == true) break;
            left = right + 1;
            right = mem.top();
            mem.pop();

        }
    }

    //Ausgabe der sortierten Liste
    for (unsigned int m=0; m<unsort_feld.size(); ++m)
    {
        cout << unsort_feld[m] << endl;
    }

}

int main()
{
    cout << "Möchtest du eine Liste von Zufallszahlen erzeugen (1) oder einlesen (2)?" << endl;
    int generate_or_read=1;
    //cin >> generate_or_read;

    //initialisiere random seed
    srand (time(NULL) );

    vector<double> unsort_feld;
    try
    {
        if (generate_or_read == 1) unsort_feld = generate_func();
        else if (generate_or_read == 2) unsort_feld = input_func();
        else throw 1;
    }
    catch(int e)
    {
        if (e==404) cout << "Konnte Datei list.txt nicht öffnen!" << endl;
        else if (e==1) cout << "Falsche Eingabe! Programm wird beendet." << endl;
        return 1;
    }
    cout << "Beginne Quicksort"<<endl;
    quick_sort(unsort_feld);

    return 0;
}