#include <iostream>
#include <time.h>
#include <limits.h>
#include <stdlib.h>
#include <chrono>
#include <fcntl.h>
#include <vector>
#include <unistd.h>
#include <cstring>

/**
 * @fn void BubbleSort(int* arr, unsigned n)
 * @briefTrie le tableau passé en argument selon méthode du tri à bulles
 * @param arr Le tableau a trier
 * @param n La taille du tableau
 * @pre Le tableau doit être de taille strictement positive soit <em> n > 0</em>
 */
void BubleSort(int* arr, unsigned n){
    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if(arr[i] > arr[j+1]){
                int tmp = arr[i];
                arr[i] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

void insertSort(int* arr, unsigned n){
    for (int i = 1; i < n ; ++i) {
        int ainserer = arr[i];
        int j = i;
        while ( (j > 0) && (arr[j-1] > ainserer)){
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = ainserer;
    }
}

int main(int argc, char* argv[]) {
    char buff[254];
    time_t t;
    std::vector<std::pair<int,int>> containerBubble;
    std::vector<std::pair<int,int>> containerInsert;

    srand((unsigned) time(&t));
    //fill array with random number

    int fdBubble;
    int fdInsert;
    fdBubble = open("bubble.time",O_WRONLY | O_CREAT | O_TRUNC,0666);
    fdInsert = open("insert.time",O_WRONLY | O_CREAT | O_TRUNC,0666);
    if(fdBubble == -1){
        perror("Error on open");
        exit(EXIT_FAILURE);
    }
    if(fdInsert == -1){
        perror("Error on open");
        exit(EXIT_FAILURE);
    }

    //bubble sort
    int nb = 10;
    while(nb <= 81920){
        int arr[nb];
        for (unsigned i = 0; i < nb; ++i) {
            arr[i] = rand() % INT_MAX;
        }
        auto start = std::chrono::high_resolution_clock::now();
        BubleSort(arr,nb);
        auto end = std::chrono::high_resolution_clock::now();
        auto durationSec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        containerBubble.emplace_back(nb,durationSec.count());
        nb *=2;
    }
    std::cout << "Bubble\n";
    std::cout << "N\t\t"<<"Duration"<<"\n";

    for (auto itt  = containerBubble.begin(); itt < containerBubble.end() ; itt++) {
        sprintf(buff,"%5d\t\t%5d\n",itt->first,itt->second);
        printf("%s",buff);
        if(write(fdBubble,buff,strlen(buff)) == -1){
            perror("Error: write");
        }
    }

    //insert
    nb = 10;
    while(nb <= 81920){
        int arr[nb];
        for (unsigned i = 0; i < nb; ++i) {
            arr[i] = rand() % INT_MAX;
        }
        auto start = std::chrono::high_resolution_clock::now();
        insertSort(arr,nb);
        auto end = std::chrono::high_resolution_clock::now();
        auto durationSec = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        containerInsert.emplace_back(nb,durationSec.count());
        nb *=2;
    }
    std::cout << "Insert\n";
    std::cout << "N\t\t"<<"Duration"<<"\n";

    for (auto itt  = containerInsert.begin(); itt < containerInsert.end() ; itt++) {
        sprintf(buff,"%5d\t\t%5d\n",itt->first,itt->second);
        printf("%s",buff);
        if(write(fdInsert,buff,strlen(buff)) == -1){
            perror("Error: write");
        }
    }


    return 0;
}