//
//  main.cpp
//  Order Statistics & Min Heap Comparison
//
//  Created by Himanshu on 21/11/23.
//

#include <iostream>
#include <algorithm>
#include <ctime>
#include <random>
#include <vector>
#include <chrono>
#include <queue>
#include <unordered_set>
using namespace std;

random_device rd;  // Obtain a random seed from the hardware
mt19937 gen(rd()); // Standard mersenne_twister_engine seeded with rd()

// Random number generator
int choosePivot(int low, int high) {
    uniform_int_distribution<int> distrib(low, high); // Define the range
    return distrib(gen); // Generate a random number
}

// Order Statistic Algorithm
int partition(int arr[], int low, int high) {
    int pivotIndex = choosePivot(low, high);
    int pivot = arr[pivotIndex];
    
    swap(arr[pivotIndex], arr[high]);
    
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

int kthSmallest(int arr[], int low, int high, int k) {
    
    if (k > 0 && k <= high - low + 1) {
        int pivot = partition(arr, low, high);

        if (pivot - low == k - 1) {
            return arr[pivot];
        } else if (pivot - low > k - 1) {
            return kthSmallest(arr, low, pivot - 1, k);
        } else {
            return kthSmallest(arr, pivot + 1, high, k - pivot + low - 1);
        }
    }
    
    return -1; // Return -1 for invalid input
}

// Min Heap Approach
int kthSmallestUsingHeap(int arr[], int n, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap(arr, arr + n);

    for (int i = 0; i < k - 1; i++) {
        minHeap.pop();
    }

    return minHeap.top();
}
    

int main() {
    const int listSize = 100000; // Adjust the list size as needed
    int arr[listSize];
    
    unordered_set<int> uniqueNumbers;

    // Generate a random list of sequential numbers
    srand((unsigned int) time(NULL));
    for (int i = 0; i < listSize; i++) {
        int randomNumber;
        do {
            randomNumber = rand() % 100000; // Generate a random number between 0 and 99999
        } while (!uniqueNumbers.insert(randomNumber).second); // Insert and check uniqueness

        arr[i] = randomNumber;
    }

    int kValues[] = {100, 500, 1000, 5000, 10000, 50000}; // Different values of k to test
    
    for (int k : kValues) {
        
        // Measure execution time for Order Statistic algorithm
        auto start = chrono::high_resolution_clock::now();
        int result1 = kthSmallest(arr, 0, listSize - 1, k);
        auto end = chrono::high_resolution_clock::now();
        chrono::duration<double> duration1 = end - start;

        // Measure execution time for Min Heap approach
        start = chrono::high_resolution_clock::now();
        int result2 = kthSmallestUsingHeap(arr, listSize, k);
        end = chrono::high_resolution_clock::now();
        chrono::duration<double> duration2 = end - start;
        
        // Output result
        cout<< k <<"th smallest " << "using Order Statistic algorithm: "<<result1 << endl;
        cout<< k <<"th smallest " << "using Min Heap approach: "<<result2 << endl;

        // Output execution times
        cout << "Time taken for k = " << k << " using Order Statistic algorithm: " << duration1.count() << " seconds\n";
        cout << "Time taken for k = " << k << " using Min Heap approach: " << duration2.count() << " seconds\n\n";
    }

    return 0;
}