/******************************************************************************
 * This program demonstrates the Merge sort.
 * 
 * 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;

vector<int> merge(const vector<int> left, const vector<int> right) noexcept {
    vector<int> result = {};
    int left_ptr = 0;
    int right_ptr = 0;
    int const LEFT_SIZE = left.size();
    int const RIGHT_SIZE = right.size();

    while (left_ptr < LEFT_SIZE && right_ptr < RIGHT_SIZE) {
        if (left[left_ptr] <= right[right_ptr]) {
            Utils::push(result, left[left_ptr]);
            ++left_ptr;
        } else {
            Utils::push(result, right[right_ptr]);
            ++right_ptr;
        }
    }

// Either left or right may have elements left; consume them.
// (Only one of the following loops will actually be entered.)
    while (left_ptr < LEFT_SIZE) {
        Utils::push(result, left[left_ptr]);
        ++left_ptr;
    }
    while (right_ptr < RIGHT_SIZE) {
        Utils::push(result, right[right_ptr]);
        ++right_ptr;
    }
    return result;
}

vector<int> merge_sort(const vector<int> list) noexcept {
    int const LIST_SIZE = list.size();
// Base case. A list of zero or one elements is sorted, by definition.
    if (LIST_SIZE <= 1) {
        const vector<int> sorted_list = list;
        return sorted_list;
    }

//  Recursive case. First, divide the list into equal-sized sublists
//  consisting of the first half and second half of the list.
//  This assumes lists start at index 0.
    vector<int> left = {};
    vector<int> right = {};
    int const HALFWAY_POINT = LIST_SIZE / 2;
    for (int i = 0; i < LIST_SIZE; ++i) {
        if (i < HALFWAY_POINT) {
            Utils::push(left, list[i]);
        } else {
            Utils::push(right, list[i]);
        }
    }

// Recursively sort both sublists.
    left = merge_sort(left);
    right = merge_sort(right);

// Then merge the now-sorted sublists.
    const vector<int> result = merge(left, right);
    return result;
}

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;

    list_to_sort = merge_sort(list_to_sort);

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