#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <string>
#include <algorithm>
#include <chrono>
#include <windows.h>
#include <random>

std::wstring generateRandomText(int length) {
    std::wstring result;
    int newLength = length + rand() % 50;
    result.reserve(newLength);

    for (int i = 0; i < newLength; ++i) {
        int unicode_code = 33 + rand() % 94;
        wchar_t symbol = static_cast<wchar_t>(unicode_code);
        result.push_back(symbol);
    }

    return result;
}

void quickSortRange(std::vector<std::wstring>& arr, int low, int high, bool ascending) {
    if (low < high) {
        int pivotIndex = low + (high - low) / 2;
        std::wstring pivot = arr[pivotIndex];
        int i = low;
        int j = high;

        while (i <= j) {
            if (ascending == 1) {
                while (arr[i] < pivot) {
                    i++;
                }
                while (arr[j] > pivot) {
                    j--;
                }
            }
            else {
                while (arr[i] > pivot) {
                    i++;
                }
                while (arr[j] < pivot) {
                    j--;
                }
            }

            if (i <= j) {
                std::swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }

        if (low < j) {
            quickSortRange(arr, low, j, ascending);
        }
        if (i < high) {
            quickSortRange(arr, i, high, ascending);
        }
    }
}

struct ThreadData {
    std::vector<std::wstring>& arr;
    int low;
    int high;
    bool ascending;
};

DWORD WINAPI QuickSortThread(LPVOID lpParam) {
    ThreadData* data = static_cast<ThreadData*>(lpParam);
    quickSortRange(data->arr, data->low, data->high, data->ascending);

    delete data;
    return 0;
}

void quickSortMultithread(std::vector<std::wstring>& arr, int numThreads, bool ascending) {
    if (numThreads <= 1 || arr.size() <= 1) {
        quickSortRange(arr, 0, arr.size() - 1, ascending);
        return;
    }

    std::vector<HANDLE> threadHandles;
    for (int i = 0; i < numThreads; i++) {
        ThreadData* data = new ThreadData{ arr, 0, (int)arr.size() - 1, ascending };
        HANDLE hThread = CreateThread(NULL, 0, QuickSortThread, data, 0, NULL);
        threadHandles.push_back(hThread);
    }

    WaitForMultipleObjects(numThreads, threadHandles.data(), TRUE, INFINITE);

    for (HANDLE hThread : threadHandles) {
        CloseHandle(hThread);
    }
}

int main() {
    setlocale(LC_CTYPE, "");
    srand(static_cast<unsigned int>(time(nullptr)));

    const int LENGTH_OF_STRINGS = 10;
    const int AMOUNT_OF_OUTPUT_STRINGS_PER_PART = 20;

    int amountOfStrings;
    int amountOfThreads;
    bool ascending;

    std::wcout << "Enter the number of threads: ";
    std::wcin >> amountOfThreads;
    std::wcout << "Enter the number of strings: ";
    std::wcin >> amountOfStrings;
    std::wcout << "Sort in ascending (1) or descending (0) order: ";
    std::wcin >> ascending;

    std::locale::global(std::locale("en_US.UTF-8"));
    std::vector<std::wstring> strings;
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < amountOfStrings; i++) {
        strings.push_back(generateRandomText(LENGTH_OF_STRINGS));
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    std::wcout << amountOfStrings << " strings has been successfully generated in " << duration.count() / 1000.0 << " seconds" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    quickSortMultithread(strings, amountOfThreads, ascending);
    end = std::chrono::high_resolution_clock::now();
    duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    std::wcout << "--------------------------------------------------------------\n";
    std::wcout << "First " << AMOUNT_OF_OUTPUT_STRINGS_PER_PART << " sorted strings : \n";
    std::wcout << "--------------------------------------------------------------\n";
    for (int i = 0; i < AMOUNT_OF_OUTPUT_STRINGS_PER_PART; i++) {
        std::wcout << strings[i] << std::endl;
    }

    int upperPart = std::ceil(static_cast<double>(AMOUNT_OF_OUTPUT_STRINGS_PER_PART) / 2);
    int lowerPart = std::floor(static_cast<double>(AMOUNT_OF_OUTPUT_STRINGS_PER_PART) / 2);

    std::wcout << "--------------------------------------------------------------\n";
    std::wcout << "Middle " << AMOUNT_OF_OUTPUT_STRINGS_PER_PART << " sorted strings:\n";
    std::wcout << "--------------------------------------------------------------\n";
    for (int i = amountOfStrings / 2 - lowerPart; i < amountOfStrings / 2 + upperPart; i++) {
        std::wcout << strings[i] << std::endl;
    }

    std::wcout << "--------------------------------------------------------------\n";
    std::wcout << "Last " << AMOUNT_OF_OUTPUT_STRINGS_PER_PART << " sorted strings:\n";
    std::wcout << "--------------------------------------------------------------\n";
    for (int i = amountOfStrings - AMOUNT_OF_OUTPUT_STRINGS_PER_PART; i < amountOfStrings; i++) {
        std::wcout << strings[i] << std::endl;
    }

    std::wcout << "Time taken for sorting: " << duration.count() / 1000.0 << " seconds" << std::endl;

    exit(0);
}