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

#undef NDEBUG

#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 LIST_SIZE = Utils::stoiWithDefault(string(argv[1]), 10);
    int const MAX_INT = Utils::stoiWithDefault(string(argv[2]), 100);

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

    quicksort(list_to_sort);

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