/*
 * Function:    External Sort Demo
 * Environment: LinuxMint/g++5.4.0
 * Date:        2017-3-20
 * Author:      zhaoyu/DUT
 */
#include <bits/stdc++.h>
using namespace std;
typedef double ElemType;

#define HEAP_SIZE 10000000
#define K_WAYS 10
#define IN_FORMAT "%lf"
#define OUT_FORMAT "%.2lf\n"

struct MinHeapNode {
    ElemType element;
    int index;
};

void swap(MinHeapNode *x, MinHeapNode *y);

class MinHeap {
    MinHeapNode* harr;  // pointer to array of elements in heap
    int heap_size;      // size of min heap

public:
    MinHeap(MinHeapNode a[], int size);
    void MinHeapify(int);
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }
    MinHeapNode getMin() { return harr[0]; }
    void replaceMin(MinHeapNode x) {
        harr[0] = x;
        MinHeapify(0);
    }
};

MinHeap::MinHeap(MinHeapNode a[], int size) {
    heap_size = size;
    harr = a;
    for (int i = (heap_size-1)/2; i >= 0; i--) {
        MinHeapify(i);
    }
}

void MinHeap::MinHeapify(int i) {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l].element < harr[i].element) {
        smallest = l;
    }
    if (r < heap_size && harr[r].element < harr[smallest].element) {
        smallest = r;
    }
    if (smallest != i) {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}

FILE *openFile(const char *fileName, const char *mode);
void closeFile(FILE *fp);
void sliceFile(const char *in_file);
void mergeFiles(const char *out_file);
void externalSort(const char *in_file, const char *out_file);
ElemType randNumber(void);

int main(int argc, char const* argv[]) {
    const char *in_file = "in.txt";
    const char *out_file = "out.txt";
    FILE *fin = openFile(in_file, "w");
    clock_t begin, end_rand, end_sort;
    begin = clock();
    srand((unsigned)time(NULL));
    for (int i = 0; i < K_WAYS*HEAP_SIZE; i++) {
        fprintf(fin, "%.2f\n", randNumber());
    }
    closeFile(fin);
    end_rand = clock();
    externalSort(in_file, out_file);
    end_sort = clock();
    printf("Generate Time:%.5lf\n", (end_rand - begin)*1.0/CLOCKS_PER_SEC);
    printf("Sort Time:%.5lf\n", (end_sort - end_rand)*1.0/CLOCKS_PER_SEC);
    return 0;
}

void swap(MinHeapNode *x, MinHeapNode *y) {
    MinHeapNode temp = *x;
    *x = *y;
    *y = temp;
}

FILE *openFile(const char *fileName, const char *mode) {
    FILE *fp = fopen(fileName, mode);
    if (fp == NULL) {
        fprintf(stderr, "Error while opening %s\n", fileName);
        exit(EXIT_FAILURE);
    }
    return fp;
}

void closeFile(FILE *fp) {
    if (fclose(fp) != 0) {
        fprintf(stderr, "CLOSE ERROR\n");
        exit(EXIT_FAILURE);
    }
}

ElemType randNumber(void) {
    return (ElemType) (rand()/10.0*9.0);
}

int comp(const void *p1, const void *p2) {
    return *((ElemType *)p1) - *((ElemType *)p2);
}

void sliceFile(const char *in_file) {
    FILE *fin = openFile(in_file, "r");
    FILE *fout[K_WAYS];
    char fileName[2];

    for (int i = 0; i < K_WAYS; i++) {
        // convert i to string
        snprintf(fileName, sizeof(fileName), "%d", i);
        fout[i] = openFile(fileName, "w");
    }

    ElemType *arr = (ElemType*) malloc(HEAP_SIZE * sizeof(ElemType));
    bool moreInput = true;
    int nextOutputFile = 0;

    while (moreInput) {
        int i;
        for (i = 0; i < HEAP_SIZE; i++) {
            if (fscanf(fin, "%lf", (arr+i)) != 1) {
                moreInput = false;  // end of input file.
                break;
            }
        }
        // Attention: last i may less than HEAP_SIZE.
        qsort(arr, i, sizeof(ElemType), comp);
        for (int j = 0; j < i; j++) {
            fprintf(fout[nextOutputFile], OUT_FORMAT, arr[j]);
        }
        nextOutputFile++;
    }

    free(arr);
    for (int i = 0; i < K_WAYS; i++) {
        closeFile(fout[i]);
    }
    closeFile(fin);
}

void mergeFiles(const char *out_file) {
    FILE *fin[K_WAYS];
    for (int i = 0; i < K_WAYS; i++) {
        char fileName[2];
        snprintf(fileName, sizeof(fileName), "%d", i);
        fin[i] = openFile(fileName, "r");
    }
    FILE *fout = openFile(out_file, "w");

    // Use MinHeap to Sort K files.
    MinHeapNode *harr = new MinHeapNode[K_WAYS];
    int i;
    for (i = 0; i < K_WAYS; i++) {
        if (fscanf(fin[i], IN_FORMAT, &harr[i].element) != 1) {
            break;
        }
        harr[i].index = i;
    }

    MinHeap hp(harr, i);
    int count = 0; // sorted files.
    while (count != i) {
        MinHeapNode root = hp.getMin();
        fprintf(fout, OUT_FORMAT, root.element);
        if (fscanf(fin[root.index], IN_FORMAT, &root.element) != 1) {
            root.element = INT_MAX*1.0;
            count++;
        }
        hp.replaceMin(root);
    }
    delete []harr;
    for (int i = 0; i < K_WAYS; i++) {
        closeFile(fin[i]);
    }
    closeFile(fout);
}

void externalSort(const char *in_file, const char *out_file) {
    sliceFile(in_file);

    mergeFiles(out_file);
}