#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/time.h>

#define TIME 1000000ll

long long GetUSecTime(){
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (long long)tv.tv_sec*TIME+tv.tv_usec;
}

void lRead(FILE* in,int* array){
    int current;
    int i=0;
    while(fscanf(in,"%d",&current) != EOF){
        array[i] = (int)current;
        i++;
    }
}

void q_sort(int*,int,int);
int q_part(int*,int,int);
int* i_sort(int*, int);
int* b_sort(int*,int);
int *m_sort(int *, int, int);
void quicksort(int*, int);
int *heapsort(int* ,int);
void heapify(int* ,int);
void bubbleDown(int* ,int, int);
void bubbleUp(int* , int);

int main(int argc, char* argv[]){
    if(argc < 2){
        printf("-q Quicksort\n");
        printf("-b Bubblesort\n");
        printf("-i Insertsort\n");
        printf("-h Heapsort\n");
        printf("-F File length\n");
        exit(EXIT_FAILURE);
    }
    if(argv[1] = '-F'){
        FILE* in = fopen(argv[2],"r");
        int size = atoi(argv[3]);
        int* unsorted = malloc(sizeof(int) * size);
        lRead(in,unsorted); //Datei in Txt einlesen
        long long time1, time2;
        if(argv[4] = '-i'){ //Insertsort
            printf("Insertsort: \n");
            time1 = GetUSecTime();
            unsorted = i_sort(unsorted,size); // funktioniert vollstaendig
            time2 = GetUSecTime();
            printf("Elapsed time: %lld usec \n", time2-time1);
        }else if(argv[4] = '-b'){ //Bubblesort
            printf("Bubblesort: \n");
            time1 = GetUSecTime();
            unsorted = b_sort(unsorted,size);
            time2 = GetUSecTime();
            printf("Elapsed time: %lld usec \n", time2-time1);
        }else if(argv[4] = '-q'){//Quicksort
            printf("Quicksort: \n");
            time1 = GetUSecTime();
            q_sort(unsorted,0,size); // funktioniert vollstaendig
            time2 = GetUSecTime();
            printf("Elapsed time: %lld usec \n", time2-time1);
        }else if(argv[4] = '-h'){//Heapsort
            printf("Heapsort: \n");
            time1 = GetUSecTime();
            unsorted = heapsort(unsorted,size);
            time2 = GetUSecTime();
            printf("Elapsed time: %lld usec \n", time2-time1);
        }
        fclose(in);
        //for(int i = 0; i < size; i++){
		//    printf("%d \n",unsorted[i]);
        //}
    }else{
        printf("./a.out -F _filename_ _numberofelements_ _sortingmethod_");
        exit(EXIT_FAILURE);
    }
}

void heapify(int *array,int end){
    int last;
    if((end-1)%2 != 0){
        last = (end - 1)/2+1;
    }
    else {
        last = (end - 1) / 2;
    }
    printf("last: %d\n",last);
    for(int i = last; i > -1; i--){
        bubbleDown(array,i,end);
    }
}

int *heapsort(int *array,int length){
    int last = length-1;
    heapify(array,length);
    for(int i = last; i > 0; i--){
        int tmp = array[0];
        array[0] = array[i];
        array[i] = tmp;
        bubbleDown(array,0,i);
    }
    return array;
}

void bubbleDown(int *array,int node, int end){
    int lci = 2*node+1; 
    if(lci < end){
        int gci = lci;
        int rci = lci + 1;
        if(rci < end){
            if(array[rci] > array[lci]){
                gci = rci;
            }
        }
        if(array[gci] > array[node]){
            int tmp = array[node];
            array[node] = array[gci];
            array[gci] = tmp;
            bubbleDown(array,gci,end);
        }
    }
}

void bubbleUp(int *array, int current){
    if(current == 0){
        return;
    }
    int parent = (current-1)/2;
    if(array[current] > array[parent]){
        int tmp = array[current];
        array[current] = array[parent];
        array[parent] = tmp;
        bubbleUp(array,parent);
    }

}

void quicksort(int *A, int len) {
    if (len < 2) return;

    int pivot = A[len / 2];

    int i, j;
    for (i = 0, j = len - 1; ; i++, j--) {
        while (A[i] < pivot) i++;
        while (A[j] > pivot) j--;

        if (i >= j) break;

        int temp = A[i];
        A[i]     = A[j];
        A[j]     = temp;
    }

    quicksort(A, i);
    quicksort(A + i, len - i);
}


int q_part(int *array, int low, int high){
    int pivotindex = (low + high)/2;
    int pivotvalue = array[pivotindex];
    int tmp = array[high];
    array[high] = array[pivotindex];
    array[pivotindex] = tmp;
    int sp = low;
    for(int su = low; su < high; su++){
        if(array[su] < pivotvalue){
            tmp = array[sp];
            array[sp] = array[su];
            array[sp] = tmp;
            sp++;

        }
    }
    int tmp2 = array[sp];
    array[sp] = array[high];
    array[high] = tmp2;
    return sp;
}

void q_sort(int *array, int low, int high){
    if(low < high){
        int pivotindex = q_part(array,low,high);
        q_sort(array, low, pivotindex-1);
        q_sort(array, pivotindex+1, high);
    }
}

// Bubblesort
int* b_sort(int *array,int size){
    int end = 1;
    while(end != 0){
        end = 0;
        for(int i = 0; i < size; i++){
            if(array[i] > array[i+1]){
                int tmp = array[i];
                array[i] = array[i+1];
                array[i+1] = tmp;
                end = 1;
            }
        }
        size--;
    }
    return array;
}

// Insert sort
int* i_sort(int *array, int n) {
    for(int i = 1; i < n; ++i) {
        int tmp = array[i];
        int j = i;
        while(j > 0 && tmp < array[j - 1]) {
            array[j] = array[j - 1];
            --j;
        }
        array[j] = tmp;
    }
    return array;
}

// Merge sort
//bei ungerader anzahl bekommt arr2 das zusaetyliche element zugewiesen
// um das zu aendern, (size/2)+1 bei arr1 kopier schleife
// ar1size = size von 1. uebergeben array
// ar2size= size von 2. uebergeben array
int* m_sort(int *array, int l, int r){
    //if(size == 1){
    if(l < r){

        //printf("arraysize=1");
        //return array;


        int mid = (l + r)/2;
        // teile array in zwei haelften auf, arr1 1. haelfte arr2 2. haelfte
        //int newarr1s = size/2;
        int *arr1 = malloc(sizeof(int) * 5); //erste haelfte
        //printf("erster");
        //printf("newarr1s %d \n",newarr1s);
        //for(int i = 0; i < l; i++){ // kopiere erste haelfte von array
        //arr1[i] = array[i];
        //	printf("%d\n",array[i]);
        //}
        printf("zweiter teil: \n");
        //int newarr2s = size - (size/2);
        //printf("newarr2s %d \n",newarr2s);
        int *arr2 = malloc(sizeof(int) * 5); // zweite healfte

        for(int i = l; i < r; i++){
            //arr2[i] = array[i];
            printf("%d\n",array[i]);
        }

        arr1 = m_sort(array,l,mid);


        arr2 = m_sort(array,mid+1,r);
        //printf("\n\n");
        //for(int i = newarr1s; i < size; i++){
//		printf("%d\n",arr2[i]);
//	}

        int e1,e2;
        for(int i = l; i < r; i++){
            if(e1 >= r){
                array[i] = arr2[e2];
                e2++;
            }
            else if(e2 >= r){
                array[i] = arr1[e1];
                e1++;
            }
            else if(arr1[e1] <= arr2[e2]){
                array[i] = arr1[e1];
                e1++;
            }
            else{
                array[i] = arr2[e2];
                e2++;
            }


        }

        //return array;


    }

}