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

std::string generateRandomText(int length) {
    const char characters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    std::string randomText;

    for (int i = 0; i < length; i++) {
        int index = rand() % (sizeof(characters) - 1);
        randomText += characters[index];
    }

    return randomText;
}

// Quick sort function for a given range [low, high]
void quickSortRange(std::vector<std::string>& arr, int low, int high, bool ascending) {
    if (low < high) {
        int pivotIndex = low + (high - low) / 2;
        std::string pivot = arr[pivotIndex];
        int i = low;
        int j = high;

        while (i <= j) {
            if (ascending) {
                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::string>& arr;
    int low;
    int high;
    bool ascending;
};

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

    delete data;
    return 0;
}

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

    int numElements = arr.size();
    int elementsPerThread = numElements / numThreads;

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

    WaitForMultipleObjects(numThreads, &threadHandles[0], TRUE, INFINITE);

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

int main() {
    srand(static_cast<unsigned int>(time(nullptr)));

    const int LENGTH_OF_STRINGS = 10;

    int amountOfStrings = 1000;
    int amountOfThreads = 4;
    bool ascending = true;
    bool isAgain = false;

    do {
        std::cout << "Enter the number of threads: ";
        std::cin >> amountOfThreads;
        std::cout << "Enter the number of strings: ";
        std::cin >> amountOfStrings;

        std::cout << "Sort in ascending (1) or descending (0) order: ";
        std::cin >> ascending;

        std::vector<std::string> strings;
        for (int i = 0; i < amountOfStrings; i++) {
            strings.push_back(generateRandomText(LENGTH_OF_STRINGS));
        }

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

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

        std::cout << "Middle 5 sorted strings:\n";
        for (int i = amountOfStrings / 2 - 2; i < amountOfStrings / 2 + 3; i++) {
            std::cout << strings[i] << std::endl;
        }

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

        std::cout << "Total time taken for quickSortMultithread: " << duration.count() / 1000.0 << " seconds" << std::endl;

        std::cout << "Do you want to use it again? (yes - 1, no - 0)" << std::endl;
        std::cin >> isAgain;

    } while (isAgain);

    return 0;
}