/******************************************************************************
 * This program demonstrates the Quicksort.
 * 
 * Copyright © 2021 Richard Lesh.  All rights reserved.
 *****************************************************************************/

#include "Utils.hpp"
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int partition(vector<int> &list, int low, int high) noexcept {
    int const pivot = list[(high + low) / 2];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            ++i;
        } while (list[i] < pivot);
        do {
            --j;
        } while (list[j] > pivot);
        if (i >= j) {
            return j;
        }
        int const temp = list[j];
        list[j] = list[i];
        list[i] = temp;
    }
}

void quicksort0(vector<int> &list, int low, int high) noexcept {
    if (low < high) {
        int const p = partition(list, low, high);
        quicksort0(list, low, p);
        quicksort0(list, p + 1, high);
    }
}

void quicksort(vector<int> &list) noexcept {
    quicksort0(list, 0, list.size() - 1);
}

int main(int argc, char **argv) {
    if (argc != 3) {
        cout << "Syntax: " << argv[0] << " list_size max_int" << endl;
        exit(1);
    }
    int const listSize = Utils::stoiWithDefault(string(argv[1]), 10);
    int const maxInt = Utils::stoiWithDefault(string(argv[2]), 100);

    vector<int> listToSort = {};
    srand(time(0));
    cout << "Random List" << endl;
    for (int i = 0; i < listSize; ++i) {
        Utils::push(listToSort, int(maxInt * (rand()/(RAND_MAX + 1.0))));
    }
    cout << Utils::to_string(listToSort) << endl;

    quicksort(listToSort);

    cout << "Sorted List" << endl;
    cout << Utils::to_string(listToSort) << endl;
    return 0;
}