#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>


//структура для матрицы
struct matrix {

    double** matr;
    int size;
};

//функция создания матрицы(выделение памяти и задание размера)
matrix* CreateMatrix(int size) {

    matrix* main_matrix = new matrix;
    main_matrix->size = size;
    main_matrix->matr = new double* [size];
    for (int i = 0; i < main_matrix->size; i++) {
        main_matrix->matr[i] = new double[main_matrix->size];
    }
    return main_matrix;
}

//функция удаления матрицы
void DeleteMatrix(matrix* mtrx) {

    // очистка памяти
    for (int j = 0; j < mtrx->size; j++) {
        delete[] mtrx->matr[j];
    }
    delete mtrx->matr;
    mtrx->size = 0;
}

//функция поиска строки с максимальным элементом в i-м столбце
int RowMax(matrix* mtrx, int StartCol) {

    double max = std::abs(mtrx->matr[StartCol][StartCol]);
    int maxPos = StartCol;
    for (int i = StartCol + 1; i < mtrx->size; i++) {
        double tmp = std::abs(mtrx->matr[i][StartCol]);
        if (tmp > max) {
            max = tmp;
            maxPos = i;
        }
    }
    return maxPos;
}

//функция приведения матрицы к треугольному виду путем элементарных преобразований
int Triangulation(matrix* mtrx) {

    int SwapCount = 0;
    double tmp;
    for (int i = 0; i < mtrx->size; i++) {
        int iMax = RowMax(mtrx, i);
        if (i != iMax) {
            std::swap(mtrx->matr[i], mtrx->matr[iMax]);
            SwapCount++; //считаем число перестановок строк
        }


        for (int j = i + 1; j < mtrx->size; j++) {
            double coeff = mtrx->matr[j][i] / mtrx->matr[i][i];
            for (int k = i; k < mtrx->size; k++) {
                tmp = mtrx->matr[j][k] - mtrx->matr[i][k] * coeff;
                if (std::abs(tmp) < 1e-12) mtrx->matr[j][k] = 0.0;
                else mtrx->matr[j][k] = tmp;
            }
        }
    }
    return SwapCount;

}

//функция создания матрицы заданнного размера со случайными значениями
matrix* RandomMatrix(int size) {

    std::srand(time(nullptr));
    matrix* mtrx = CreateMatrix(size);
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            //debug
            //mtrx->matr[i][j] = rand() % 10;

            //release
            mtrx->matr[i][j] = double(rand() % 100)/1000;
        }
    }
    return mtrx;
}

//функция вывода матрицы на экран
void OutputMatrix(matrix* mtrx) {

    for (int i = 0; i < mtrx->size; i++) {
        for (int j = 0; j < mtrx->size; j++) {
            std::cout << std::setw(13) << mtrx->matr[i][j] << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
    return;
}

//функция копирования матрицы
matrix* CopyMatrix(matrix* matrix_SRC) {

    matrix* matrix_DST = CreateMatrix(matrix_SRC->size);
    if (matrix_SRC->size != matrix_DST->size) {
        std::cout << "Copy error!" << std::endl;
        return NULL;
    }
    for (int i = 0; i < matrix_SRC->size; i++) {
        for (int j = 0; j < matrix_SRC->size; j++) {
            matrix_DST->matr[i][j] = matrix_SRC->matr[i][j];
        }

    }
    return matrix_DST;
}

//функция вычисления оперделителя матрицы методом Гаусса
double GaussDet(matrix* mtrx) {

    double det;
    switch (mtrx->size) {
    case 0:
        det = 0;
        break;
    case 1:
        det = mtrx->matr[0][0];
        break;
    case 2:
        det = mtrx->matr[0][0] * mtrx->matr[1][1] - mtrx->matr[0][1] * mtrx->matr[1][0];
        break;
    default:
        //создание копии исходной матрицы для приведения к треугольному виду
        //и вычисления определителя
        matrix* tr_matrix = CopyMatrix(mtrx);

        int SwapCount = Triangulation(tr_matrix);
        det = 1;
        if (SwapCount % 2 == 1)
        {
            det = -1;
        }
        for (int i = 0; i < tr_matrix->size; i++) {
            det *= tr_matrix->matr[i][i];
        }

        //debug
        //std::cout << "Triangle matrix:" << std::endl;
        //OutputMatrix(tr_matrix);

        DeleteMatrix(tr_matrix);
    }
    return det;
}

//функция транспонирования матрицы
matrix* TransposeMatrix(matrix* mtrx) {

    matrix* tr_matrix = CreateMatrix(mtrx->size);
    for (int i = 0; i < tr_matrix->size; i++) {
        for (int j = 0; j < tr_matrix->size; j++) {

            //std::swap(tr_matrix->matr[i][j], tr_matrix->matr[j][i]);
            tr_matrix->matr[i][j] = mtrx->matr[j][i];

        }
    }
    //debug
    //OutputMatrix(tr_matrix);
    return tr_matrix;
}

//функция вычисления алгебраического дополнения для элемента матрицы
double Cofactor(matrix* mtrx, matrix* minor, int row, int col) {

    int minor_row, minor_col;
    //int minor_size = min->size - 1;
    int cofactor;
    int sign = ((row + col) % 2) ? -1 : 1;

    for (int i = 0; i < mtrx->size; i++) {

        minor_row = i;
        if (i > row) minor_row--;

        for (int j = 0; j < mtrx->size; j++) {
            minor_col = j;
            if (j > col) minor_col--;
            if (i != row && j != col) {
                minor->matr[minor_row][minor_col] = mtrx->matr[i][j];
            }
            //OutputMatrix(matrix, size);
        }
    }
    cofactor = sign * GaussDet(minor);

    // debug
    /*std::cout << "\nsome minor" << std::endl;
    OutputMatrix(minor);
    std::cout << "det of minor = " << GaussDet(minor) << std::endl;*/

    return cofactor;
}

//функция вычисления обратной матрицы
matrix* InverseMatrix(matrix* mtrx, double det) {

    //временная матрица для миноров матрицы
    matrix* tmp_minor = CreateMatrix(mtrx->size - 1);

    //результирующая матрица
    matrix* res_matrix = CreateMatrix(mtrx->size);

    //транспонированная матрица
    matrix* tr_matrix = TransposeMatrix(mtrx);

    //debug
    /*std::cout << "Transposed matrix " << std::endl;
    OutputMatrix(tr_matrix);*/

    double cofactor;

    //алгебраические дополнения для элементов матрицы
    for (int i = 0; i < res_matrix->size; i++) {
        for (int j = 0; j < res_matrix->size; j++) {

            cofactor = Cofactor(tr_matrix, tmp_minor, i, j);

            if (std::abs(cofactor) < 1e-12) res_matrix->matr[i][j] = 0.0;
            else res_matrix->matr[i][j] = cofactor / det;
        }
    }

    //очистка памяти под миноры
    DeleteMatrix(tmp_minor);
    delete tmp_minor;

    //очистка памяти под транспонированную матрицу
    DeleteMatrix(tr_matrix);
    delete tr_matrix;

    return res_matrix;
}



int main(int argc, char* argv[]) {

    /*if (argc < 1) {
        std::cout << "Wrong size!" << std::endl;
        return -1;
    }

    int size = std::stoi(argv[1]);*/

    int size = 10;

    //исходная матрица
    matrix* main_matrix = RandomMatrix(size);

    /*std::cout << "Main matrix " << std::endl;
    OutputMatrix(main_matrix);*/
    std::cout << "OnePointerMatrix with size " << size << std::endl;

    auto start = std::chrono::steady_clock::now();
    double det = GaussDet(main_matrix);
    //std::cout << "Determinant of main matrix: " << det << std::endl;
    if (det == 0) {
        std::cout << "Inverse matrix doesn't exist!";
        return -1;
    }

    //обратная матрица
    matrix* inverse_matrix = InverseMatrix(main_matrix, det);

    auto end = std::chrono::steady_clock::now();

    std::chrono::duration<double> elapsed = end - start;
    std::cout << "Executions time: " << elapsed.count() << " seconds" << std::endl;

    /*std::cout << "\nInversed matrix " << std::endl;
    OutputMatrix(inverse_matrix);*/

    //очистка памяти под обратную матрицу
    DeleteMatrix(inverse_matrix);
    delete inverse_matrix;

    //очистка памяти под исходную матрицу
    DeleteMatrix(main_matrix);
    delete main_matrix;

    return 0;
}