//
//  main.cpp
//  Matrices
//
//  Created by Apple on 18.04.2018.
//  Copyright © 2018 Egor. All rights reserved.
//

#include <iostream>
#include <cmath>
#include <random>
#include <ctime>
#include <chrono>
#include <iomanip>
#include <vector>


using namespace std;
typedef std::vector<std::vector<int>> Matrix;




int log2(int x)
{
    int result = 1;
    while ((x >>= 1) != 0) result++;
    return 1 << result;
}


Matrix initMatrix(int size)
{
    Matrix matrix = vector<vector<int>>(size);
    for (auto &el:matrix)
        el=  vector<int>(size);
    return matrix;
}

void fillMatrix(Matrix &matrix,int size)
{

    for (int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            matrix[i][j] = rand()%100-50;
        }
    }
    cout << "\n";
}


void showMatrix(Matrix &matrix, int size)
{
    for (int i = 0 ; i < size;i++)
    {
        cout << "|";
        for (int j = 0; j < size; j++)
        {
            cout << setw(6) <<matrix[i][j];
        }
        cout << "|\n";
    }
}


Matrix multiplyMatrices(Matrix &leftMatrix,Matrix &rightMatrix, int size)
{
    Matrix resultMatrix = initMatrix(size);

    int buf;
    for (int i = 0 ; i < size; i++)
    {
        buf = 0;
        for(int j = 0; j < size; j++)
        {
            for (int l = 0; l < size; l++)
            {
                buf += leftMatrix[i][l] * rightMatrix[l][j];
            }
            resultMatrix[i][j] = buf;
        }

    }

    return resultMatrix;
}


Matrix sumMatrix(Matrix left, Matrix right)
{
    int size = left.size();
    Matrix c = initMatrix(size);

    for (int i = 0 ; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            c[i][j] = left[i][j] + right[i][j];
        }
    }
    return c;
}


Matrix subtractMatrix(Matrix left, Matrix right)
{
    int size = left.size();
    Matrix c = initMatrix(size);

    for (int i = 0 ; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            c[i][j] = left[i][j] - right[i][j];
        }
    }
    return c;
}

void splitMatrix(Matrix &A,Matrix &A11,Matrix &A12,Matrix &A21,Matrix &A22)
{
    int newSize = A.size()>>1;
    A11 = initMatrix(newSize);
    A12 = initMatrix(newSize);
    A21 = initMatrix(newSize);
    A22 = initMatrix(newSize);

    for (int i = 0 ; i < newSize; ++i)
    {
        for (int j = 0; j < newSize; ++j)
        {
            if (i >= newSize)
            {
                if (j>= newSize)
                {
                    A22[i-newSize][j-newSize] = A[i][j];
                }
                else
                {
                    A21[i-newSize][j] = A[i][j];

                }
            }
            else
            {
                if (j>= newSize)
                {
                    A12[i][j-newSize] = A[i][j];

                }
                else
                {
                    A11[i][j] = A[i][j];

                }
            }
        }
    }
}


Matrix collectMatrix(Matrix A11,Matrix A12,Matrix A21,Matrix A22)
{
    int newSize = A11.size();
    Matrix A = initMatrix( newSize << 1);

    for (int i = 0 ; i < newSize; ++i)
    {
        for (int j = 0; j < newSize; ++j)
        {
            if (i >= newSize)
            {
                if (j>= newSize)
                {
                    A[i][j] = A22[i-newSize][j-newSize];
                }
                else
                {
                    A[i][j] = A21[i-newSize][j];

                }
            }
            else
            {
                if (j>= newSize)
                {
                     A[i][j] = A12[i][j-newSize];

                }
                else
                {
                     A[i][j] = A11[i][j];
                }
            }
        }
    }
    return A;
}


Matrix multiStrassen(Matrix a, Matrix b, int size) {
    if (size <= 64) {
        return multiplyMatrices(a, b,size);
    }

    size = size >> 1;

    Matrix a11 = initMatrix(size);
    Matrix a12 = initMatrix(size);
    Matrix a21 = initMatrix(size);
    Matrix a22 = initMatrix(size);

    Matrix b11 = initMatrix(size);
    Matrix b12 = initMatrix(size);
    Matrix b21 = initMatrix(size);
    Matrix b22 = initMatrix(size);

    splitMatrix(a, a11, a12, a21, a22);
    splitMatrix(b, b11, b12, b21, b22);

    Matrix p1 = initMatrix(size);
    p1 = multiStrassen(sumMatrix(a11, a22), sumMatrix(b11, b22), size);
    Matrix p2 = initMatrix(size);
    p2 = multiStrassen(sumMatrix(a21, a22), b11, size);
    Matrix p3 = initMatrix(size);
    p3 = multiStrassen(a11, subtractMatrix(b12, b22), size);
    Matrix p4 = initMatrix(size);
    p4 = multiStrassen(a22, subtractMatrix(b21, b11), size);
    Matrix p5 = initMatrix(size);
    p5 = multiStrassen(sumMatrix(a11, a12), b22, size);
    Matrix p6 = initMatrix(size);
    p6 = multiStrassen(subtractMatrix(a21, a11), sumMatrix(b11, b12), size);
    Matrix p7 = initMatrix(size);
    p7 = multiStrassen(subtractMatrix(a12, a22), sumMatrix(b21, b22), size);

    Matrix c11 = initMatrix(size);
    c11 = sumMatrix(sumMatrix(p1, p4), subtractMatrix(p7, p5));
    Matrix c12 = initMatrix(size);
    c12 = sumMatrix(p3, p5);
    Matrix c21 = initMatrix(size);
    c21 = sumMatrix(p2, p4);
    Matrix c22 = initMatrix(size);
    c22 = sumMatrix(subtractMatrix(p1, p2), sumMatrix(p3, p6));
    return collectMatrix(c11, c12, c21, c22);
}

int main(int argc, const char * argv[])
{
    srand(time(nullptr));

    setlocale(LC_ALL, "russian");



    cout << "Введите размер матриц\n";
    Matrix matrixA;
    int size;
    cin >> size;
    matrixA = initMatrix(size);
    fillMatrix(matrixA, size);
//    showMatrix(matrixA, size);
    cout <<"\n";
    Matrix matrixB;
    matrixB = initMatrix(size);
    fillMatrix(matrixB, size);
//    showMatrix(matrixB, size);
    cout <<"\n";
     Matrix resMat1,resMat2;
    {

    auto start =  std::chrono::high_resolution_clock::now();

    resMat2 = multiStrassen(matrixA, matrixB, size);
    auto finish = std::chrono::high_resolution_clock::now();
    auto time = std::chrono::duration_cast<std::chrono::milliseconds>(finish-start);
    cout << static_cast<float>(time.count()/1000.0f) <<"s" << endl;
    }
//    showMatrix(resMat, size);

    {

        auto start =  std::chrono::high_resolution_clock::now();

        resMat1 = multiplyMatrices(matrixA, matrixB, size);
        auto finish = std::chrono::high_resolution_clock::now();
        auto time = std::chrono::duration_cast<std::chrono::milliseconds>(finish-start);
        cout << static_cast<float>(time.count()/1000.0f) <<"s" << endl;
    }


    return 0;
}