#include <iostream>
#include <string>
#include <iomanip>
#include <cstdlib>
#include <fstream>


bool checkPermissionForWriting(const std::string& PathToFile) {
    bool Flag;
    std::ofstream FileOut(PathToFile);
    if (FileOut.is_open()) {
        FileOut.close();
        Flag = true;
    }
    else {
        std::cout << "File isn't available for writing.\n";
        Flag = false;
    }
    return Flag;
}

bool checkPermissionForReading(const std::string& PathToFile) {
    bool Flag;
    std::ifstream FileIn(PathToFile);
    if (FileIn.is_open()) {
        FileIn.close();
        Flag = true;
    }
    else {
        std::cout << "File isn't available for reading.\n";
        Flag = false;
    }
    return Flag;
}

bool checkExtension(const std::string& PathToFile) {
    const std::string extension = "txt";
    bool Flag;
    if (PathToFile.length() > 4 && PathToFile.substr(PathToFile.length() - 3) == extension) {
        Flag = true;
    }
    else {
        std::cout << "Wrong extension.\n";
        Flag = false;
    }
    return Flag;
}

void printSourceArrayInConsole(int* SourceArray, int NumberOfElements) {
    std::cout << "Source array:\n";
    for (int i = 0; i < NumberOfElements; i++) {
        std::cout << std::setw(6) << SourceArray[i];
    }
    std::cout << "\n";
}

int inputIntegerNumber(const int MIN_NUMBER, const int MAX_NUMBER) {
    bool is_incorrect;
    int number;
    std::string input = "";
    do {
        getline(std::cin, input);
        is_incorrect = false;
        try {
            number = std::stoi(input);
        }
        catch (std::invalid_argument ex) {
            std::cout << "Enter a number:\n";
            is_incorrect = true;
        }
        catch (std::out_of_range ex) {
            std::cout << "Number mustn't be less than " << MIN_NUMBER << " and more than "
                << MAX_NUMBER << "\n";
            is_incorrect = true;
        }
        if (!is_incorrect && (number <  MIN_NUMBER || number > MAX_NUMBER)) {
            std::cout << "Number mustn't be less than " << MIN_NUMBER << " and more than "
                << MAX_NUMBER << "\n";
            is_incorrect = true;
        }
    } while (is_incorrect);
    return number;
}

int chooseWayOfInput() {
    const int CONSOLE_INPUT = 1;
    const int FILE_INPUT = 2;
    const int RANDOM_GENERATION_INPUT = 3;
    int UserWay;
    do {
        UserWay = inputIntegerNumber(1, 3);
    } while (UserWay != CONSOLE_INPUT && UserWay != FILE_INPUT && UserWay != RANDOM_GENERATION_INPUT);
    return UserWay;
}

int chooseWayOfOutput() {
    const int CONSOLE_OUTPUT = 1;
    const int FILE_OUTPUT = 2;
    int UserWay;
    do {
        UserWay = inputIntegerNumber(1, 2);
    } while (UserWay != CONSOLE_OUTPUT && UserWay != FILE_OUTPUT);
    return UserWay;
}

int inputNumberOfElements() {
    std::cout << "Input number of elements:\n";
    return inputIntegerNumber(2, 200);
}

int inputElement() {
    std::cout << "Input element: ";
    return inputIntegerNumber(-100, 100);
}

bool checkFile(const std::string PathToFile) {
    bool Flag = true;
    int IsNumber;
    std::string Text;
    std::ifstream InputFile(PathToFile);
    getline(InputFile, Text);
    int SizeOfText = Text.length();
    for (int i = 0; (i < SizeOfText && Flag); i++) {
        if (Text[i] != ' ' && Text[i] != '-') {
            try {
                IsNumber = std::stoi(Text.substr(i, 1));
            }
            catch (std::invalid_argument ex) {
                std::cout << "Received data includes non-integer chars.\n";
                Flag = false;
            }
        }
    }
    InputFile.close();
    if (Text[0] == NULL) {
        Flag = 0;
        std::cout << "File is empty\n";
    }
    return Flag;
}

int receiveNumberOfElementsFromFile(const std::string PathToFile) {
    int NumberOfElements = 0;
    int Element;
    std::ifstream InputFile(PathToFile);
    while (!InputFile.eof()) {
        InputFile >> Element;
        NumberOfElements++;
    }
    InputFile.close();
    return NumberOfElements;
}

const std::string inputPathToFileForReading() {
    std::string PathToFile;
    do {
        std::cout << "Input path to file for reading:\n";
        getline(std::cin, PathToFile);
    } while (!checkExtension(PathToFile) || !checkPermissionForReading(PathToFile));
    return PathToFile;
}

void receiveSourceArrayFromFile(const std::string PathToFile, int* SourceArray) {
    int i = 0;
    std::string Text;
    std::ifstream InputFile(PathToFile);
    while (!InputFile.eof()) {
        InputFile >> SourceArray[i++];
    }
    InputFile.close();
}

int receiveNumberOfElements(int* UserWay, std::string& PathToFile) {
    std::cout << "Choose way of input: \nType '1' if you want to receive sequence from console;\nType '2' if you want to receieve sequence from file;\nType '3' if you want to fill sequence with random numbers:\n";
    int NumberOfElements;
    *UserWay = chooseWayOfInput();
    switch (*UserWay) {
    case 1:
    {
        NumberOfElements = inputNumberOfElements();
        break;
    }
    case 2:
    {
        do {
            PathToFile = inputPathToFileForReading();
        } while (!(checkPermissionForReading(PathToFile) && checkFile(PathToFile)));
        NumberOfElements = receiveNumberOfElementsFromFile(PathToFile);
        break;
    }
    case 3:
    {
        NumberOfElements = inputNumberOfElements();
        break;
    }
    }
    return NumberOfElements;
}

void fillingSourceArrayFromConsole(int* SourceArray, int NumberOfElements) {
    for (int i = 0; i < NumberOfElements; i++) {
        std::cout << "Input element: ";
        SourceArray[i] = inputIntegerNumber(-50, 50);
    }
}

int* fillingSourceArrayWithRandomNumbers(int* SourceArray, int NumberOfElements)
{
    srand(time(NULL));
    for (int i = 0; i < NumberOfElements; i++)
    {
        SourceArray[i] = rand() % 101 - 50;
    }
    return SourceArray;
}

void receiveSourceArray(int NumberOfElements, int* SourceArray, int* UserWay, const std::string& PathToFile) {
    switch (*UserWay) {
    case 1:
    {
        fillingSourceArrayFromConsole(SourceArray, NumberOfElements);
        break;
    }
    case 2:
    {
        receiveSourceArrayFromFile(PathToFile, SourceArray);
        break;
    }
    case 3:
    {
        fillingSourceArrayWithRandomNumbers(SourceArray, NumberOfElements);
        break;
    }
    }
    printSourceArrayInConsole(SourceArray, NumberOfElements);
}

void fillingArrayWithZeros(int* SizesOfIntermediateArray, int NumberOfElements) {
    int Counter = NumberOfElements / 2 + 1;
    for (int i = 0; i < Counter; i++) {
        SizesOfIntermediateArray[i] = 0;
    }
}

int findPositionToWriteSizesOfFirstSortingArray(int* SizesOfFirstSortingArray, int NumberOfElements) {
    for (int i = 0; i < NumberOfElements; i++) {
        if (SizesOfFirstSortingArray[i] == 0) {
            return i;
        }
    }
}

int findPositionToWriteSizesOfSecondSortingArray(int* SizesOfFSecondSortingArray, int NumberOfElements) {
    for (int i = 0; i < NumberOfElements; i++) {
        if (SizesOfFSecondSortingArray[i] == 0) {
            return i;
        }
    }
}

bool findConditionOfSorted(int* IntermediateArray, int NumberOfElements) {
    int Counter = 0;
    for (int i = 1; i < NumberOfElements; i++) {
        if (IntermediateArray[i - 1] <= IntermediateArray[i]) {
            Counter++;
        }
    }
    return (Counter + 1 == NumberOfElements);
}

void creatingFirstF(int* IntermediateArray, int* SourceArray, int NumberOfElements) {
    for (int i = 0; i < NumberOfElements; i++) {
        IntermediateArray[i] = SourceArray[i];
    }
}

void creatingSortedArray(int* SortedArray, int* IntermediateArray, int NumberOfElements) {
    for (int i = 0; i < NumberOfElements; i++) {
        SortedArray[i] = IntermediateArray[i];
    }
}

int findNumberOfPairs(int* SizesOfFirstSortingArray, int NumberOfElements) {
    int Counter = NumberOfElements / 2 + 1;
    int NullPosition = Counter;
    for (int i = 0; i < Counter; i++) {
        if (SizesOfFirstSortingArray[i] == 0) {
            NullPosition = i;
            i = Counter;
        }
    }
    return NullPosition;
}

void findSortedPart(int* IntermediateArray, int* sort, int NumberOfElements, int* Index, int* Length) {
    int k = 0;
    for (int i = *Index; i < NumberOfElements; i++) {
        if (i + 1 < NumberOfElements) {
            if (IntermediateArray[i] <= IntermediateArray[i + 1]) {
                k++;
            }
            else {
                i = NumberOfElements;
            }
        }
    }
    if (k > 0) {
        int j = 0;
        for (int i = *Index; i < *Index + k + 1; i++) {
            sort[j] = IntermediateArray[i];
            j++;
        }
    }
    else {
        sort[0] = IntermediateArray[*Index];
    }
    *Length = k + 1;
    *Index += *Length;
}

void fillFirstSortingArray(int* FirstSortingArray, int* sort, int* SizesOfFirstSortingArray, int NumberOfElements, int Length, int* IndexOfIntermediateArray) {
    for (int i = *IndexOfIntermediateArray; i < *IndexOfIntermediateArray + Length; i++)
    {
        FirstSortingArray[i] = sort[i - *IndexOfIntermediateArray];
    }
    int NumberOfPosition = findPositionToWriteSizesOfFirstSortingArray(SizesOfFirstSortingArray, NumberOfElements);
    SizesOfFirstSortingArray[NumberOfPosition] = Length;
    *IndexOfIntermediateArray += Length;
}

void fillingSecondSortingArray(int* SecondSortingArray, int* sort, int* SizesOfFSecondSortingArray, int NumberOfElements, int Length, int* IndexOfIntermediateArray) {
    for (int i = *IndexOfIntermediateArray; i < *IndexOfIntermediateArray + Length; i++) {
        SecondSortingArray[i] = sort[i - *IndexOfIntermediateArray];
    }
    int NumberOfPosition = findPositionToWriteSizesOfSecondSortingArray(SizesOfFSecondSortingArray, NumberOfElements);
    SizesOfFSecondSortingArray[NumberOfPosition] = Length;
    *IndexOfIntermediateArray += Length;
}

void fillingSortingArrays(int* IntermediateArray, int* FirstSortingArray, int* SecondSortingArray, int* SizesOfFirstSortingArray, int* SizesOfFSecondSortingArray, int NumberOfElements) {
    int Index = 0;
    int IndexOfIntermediateArray = 0;
    int Length = 0;
    int condition = 0;
    int* sort = new int[NumberOfElements];
    fillingArrayWithZeros(SizesOfFirstSortingArray, NumberOfElements);
    fillingArrayWithZeros(SizesOfFSecondSortingArray, NumberOfElements);
    for (int i = 0; i < NumberOfElements; i += Length)
    {
        findSortedPart(IntermediateArray, sort, NumberOfElements, &Index, &Length);
        if (condition % 2 == 0)
        {
            fillFirstSortingArray(FirstSortingArray, sort, SizesOfFirstSortingArray, NumberOfElements, Length, &IndexOfIntermediateArray);
        }
        else
        {
            fillingSecondSortingArray(SecondSortingArray, sort, SizesOfFSecondSortingArray, NumberOfElements, Length, &IndexOfIntermediateArray);
        }
        condition++;
    }
    delete[] sort;
}

void printArray(int* SourceArray, int NumberOfElements, int* UserWay, std::string& PathToFile) {
    switch (*UserWay) {
    case 1:
    {
        for (int i = 0; i < NumberOfElements; i++) {
            std::cout << std::setw(6) << SourceArray[i];
        }
        std::cout << '\n';
        break;
    }
    case 2:
    {
        std::ofstream FileOut(PathToFile, std::ios_base::app);
        for (int i = 0; i < NumberOfElements; i++) {
            FileOut << std::setw(6) << SourceArray[i];
        }
        FileOut << '\n';
        FileOut.close();
        break;
    }
    }
}

void receiveNewSourceArray(int* IntermediateArray, int* FirstSortingArray, int* SecondSortingArray, int* SizesOfFirstSortingArray,
    int* SizesOfFSecondSortingArray, int NumberOfElements, int* UserWay, std::string& PathToFile) {
    fillingSortingArrays(IntermediateArray, FirstSortingArray, SecondSortingArray, SizesOfFirstSortingArray, SizesOfFSecondSortingArray, NumberOfElements);
    int Counter = findNumberOfPairs(SizesOfFirstSortingArray, NumberOfElements);
    int Index = 0;
    for (int i = 0; i < Counter; i++) {
        int SizeOfFirstSortingArray = SizesOfFirstSortingArray[i];
        int SizeOfSecondSortingArray = SizesOfFSecondSortingArray[i];
        int j1 = Index;
        int j2 = Index + SizeOfFirstSortingArray;
        int z = Index;
        while (z < Index + SizeOfFirstSortingArray + SizeOfSecondSortingArray) {
            if ((j1 == Index + SizeOfFirstSortingArray) && (j2 != Index + SizeOfFirstSortingArray + SizeOfSecondSortingArray)) {
                for (j2; j2 < SizeOfFirstSortingArray + SizeOfSecondSortingArray + Index; j2++) {
                    IntermediateArray[z++] = SecondSortingArray[j2];
                }
            }
            if ((j2 == Index + SizeOfFirstSortingArray + SizeOfSecondSortingArray) && (j1 != Index + SizeOfFirstSortingArray)) {
                for (j1; j1 < SizeOfFirstSortingArray + Index; j1++) {
                    IntermediateArray[z++] = FirstSortingArray[j1];
                }
            }
            if ((FirstSortingArray[j1] < SecondSortingArray[j2]) && (j2 < NumberOfElements) && (j1 < NumberOfElements) && (z < Index + SizeOfFirstSortingArray + SizeOfSecondSortingArray)) {
                IntermediateArray[z++] = FirstSortingArray[j1++];
            }
            else {
                if ((SecondSortingArray[j2] < FirstSortingArray[j1]) && (j2 < NumberOfElements) && (j1 < NumberOfElements) && (z < Index + SizeOfFirstSortingArray + SizeOfSecondSortingArray)) {
                    IntermediateArray[z++] = SecondSortingArray[j2++];
                }
                else {
                    if ((SecondSortingArray[j2] == FirstSortingArray[j1]) && (j2 < NumberOfElements) && (j1 < NumberOfElements) && (z < Index + SizeOfFirstSortingArray + SizeOfSecondSortingArray)) {
                        IntermediateArray[z++] = FirstSortingArray[j1++];
                        IntermediateArray[z++] = SecondSortingArray[j2++];
                    }
                }
            }
        }
        Index += SizeOfFirstSortingArray + SizeOfSecondSortingArray;
    }
    printArray(IntermediateArray, NumberOfElements, UserWay, PathToFile);
}

void sorting(int* SourceArray, int* SortedArray, int NumberOfElements, int* UserWay, std::string& PathToFile) {
    int* IntermediateArray = new int[NumberOfElements];
    int* FirstSortingArray = new int[NumberOfElements];
    int* SecondSortingArray = new int[NumberOfElements];
    int* SizesOfFirstSortingArray = new int[NumberOfElements / 2 + 1];
    int* SizesOfFSecondSortingArray = new int[NumberOfElements / 2 + 1];
    creatingFirstF(IntermediateArray, SourceArray, NumberOfElements);
    while (!findConditionOfSorted(IntermediateArray, NumberOfElements)) {
        receiveNewSourceArray(IntermediateArray, FirstSortingArray, SecondSortingArray, SizesOfFirstSortingArray,
            SizesOfFSecondSortingArray, NumberOfElements, UserWay, PathToFile);
    }
    creatingSortedArray(SortedArray, IntermediateArray, NumberOfElements);
    delete[] IntermediateArray;
    delete[] FirstSortingArray;
    delete[] SecondSortingArray;
    delete[] SizesOfFirstSortingArray;
    delete[] SizesOfFSecondSortingArray;
}

void printSortedArrayInConsole(int* SortedArray, int NumberOfElements)
{
    std::cout << "Sorted array:\n";
    for (int i = 0; i < NumberOfElements; i++)
    {
        std::cout << std::setw(6) << SortedArray[i];
    }
    std::cout << "\n";
}

void printSortedArrayInFile(int* SortedArray, int NumberOfElements, const std::string PathToFile)
{
    std::ofstream FileOut(PathToFile, std::ios_base::app);
    FileOut << "Sorted array:\n";
    for (int i = 0; i < NumberOfElements; i++)
    {
        FileOut << std::setw(6) << SortedArray[i];
    }
    FileOut.close();
    std::cout << "Result is written in file.\n";
}

const std::string inputPathToFileForWriting() {
    std::string PathToFile;
    do {
        std::cout << "Input path to file for writing:  \n";
        getline(std::cin, PathToFile);
    } while (!checkExtension(PathToFile) || !checkPermissionForWriting(PathToFile));
    return PathToFile;
}

void receiveWayOfOutput(int* UserWay, std::string& PathToFile) {
    std::cout << "Choose way of output:\nType '1' if you want to print sorting and result in console.\nType '2' if you want to print sorting and result in file.\n";
    *UserWay = chooseWayOfOutput();
    switch (*UserWay) {
    case 1:
        std::cout << "Sorting:\n";
        break;
    case 2:
    {
        do {
            PathToFile = inputPathToFileForWriting();
        } while (!checkExtension(PathToFile) && !checkPermissionForWriting(PathToFile));
        std::ofstream FileOut(PathToFile, std::ios::trunc);
        FileOut << "Sorting:\n";
        FileOut.close();
        break;
    }
    }
}

void printResult(int* SortedArray, int NumberOfElements, int* UserWay, std::string& PathToFile) {
    switch (*UserWay) {
    case 1:
    {
        printSortedArrayInConsole(SortedArray, NumberOfElements);
        break;
    }
    case 2:
    {
        printSortedArrayInFile(SortedArray, NumberOfElements, PathToFile);
        break;
    }
    }
    std::cout << "Program is completed.";
}

int main() {
    std::string PathToFile = "";
    int UserWay;
    std::cout << "This program implements natural merge sorting.\n";
    int NumberOfElements = receiveNumberOfElements(&UserWay, PathToFile);
    int* SourceArray = new int[NumberOfElements];
    receiveSourceArray(NumberOfElements, SourceArray, &UserWay, PathToFile);
    int* SortedArray = new int[NumberOfElements];
    receiveWayOfOutput(&UserWay, PathToFile);
    sorting(SourceArray, SortedArray, NumberOfElements, &UserWay, PathToFile);
    printResult(SortedArray, NumberOfElements, &UserWay, PathToFile);
    delete[] SourceArray;
    delete[] SortedArray;
}