#include <iostream>
using namespace std;
class Matrix {
private:
    int** v;
    int size;
    Matrix merge(const Matrix& c11, const Matrix& c12, const Matrix& c21, const Matrix& c22) const {
        Matrix m(size);
        int cursize = size / 2;
        for (int i = 0; i < cursize; i++) {
            for (int j = 0; j < cursize; j++) {
                m(i, j) = c11(i, j);
                m(i + cursize, j) = c21(i, j);
                m(i, j + cursize) = c12(i, j);
                m(i + cursize, j + cursize) = c22(i, j);
            }
        }
        return m;
    }
public:
    static bool added;
    Matrix() : size(0), v(nullptr) {}
    Matrix(int s) : size(s) {
        v = new int* [size];
        for (int i = 0; i < size; i++) {
            v[i] = new int[size];
        }
    }

    Matrix(const Matrix& m, const int index1, const int index2) {
        size = m.size / 2;
        v = new int* [size];
        for (int i = 0; i < size; i++) {
            v[i] = new int[size];
        }
        for (int i = index1; i - index1 < size; i++) {
            for (int j = index2; j - index2 < size; j++) {
                int item = m(i, j);
                v[i - index1][j - index2] = item;
            }
        }
    }
    void getMatrix(int size) {
        int n = size;
        if (n % 2 != 0) {
            size++;
            added = true;
        }
        this->size = size;
        v = new int* [size];
        for (int i = 0; i < size; i++) {
            v[i] = new int[size];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                v[i][j] = rand() % 100;
            }
        }
    }
    void display() const {
        int n = added ? size - 1 : size;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << v[i][j] << " ";
            }
            cout << endl;
        }
    }
    int& operator() (const int index1, const int index2) const {
        return v[index1][index2];
    }

    Matrix(const Matrix& m) {
        if (m.v == nullptr) return;
        this->v = new int*[m.size];
        for (int i = 0; i < m.size; ++i)
            v[i] = new int[m.size];
        this->size = m.size;
    }

    Matrix(Matrix&& m) {
        this->v = m.v;
        this->size = m.size;
        m.v = nullptr;
        m.size = 0;
    }

    ~Matrix() {
        if(v != nullptr)
            for (int i = 0; i < size; ++i)
                delete[] v[i];
        delete[] v;
        v = nullptr;
        size = 0;
    }

    const Matrix operator+(const Matrix& m) const {
        Matrix r(size);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                r(i, j) = v[i][j] + m(i, j);
            }
        }
        return r;
    }
    const Matrix operator-(const Matrix& m) const {
        Matrix r(size);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                r(i, j) = v[i][j] - m(i, j);
            }
        }
        return r;
    }

    Matrix& operator =(const Matrix& other) {
        if (this == &other || other.v == nullptr)
            return *this;
        this->~Matrix();
        v = new int* [other.size];
        for (int i = 0; i < other.size; ++i) {
            v[i] = new int[other.size];
            for (int j = 0; j < other.size; ++j)
                v[i][j] = other.v[i][j];
        }
        size = other.size;
        return *this;
    }

    Matrix simpleMultiplication(const Matrix& m) const {
        Matrix res(size);
        int prom = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                for (int k = 0; k < size; k++) {
                    prom += v[i][k] * m(k, j);
                }
                res(i, j) = prom;
            }
        }
        return res;
    }
    const Matrix operator* (const Matrix& B) const {
        if (size == 1) {
            Matrix m(size);
            m(0, 0) = v[0][0] * B(0, 0);
            return m;
        }
        // init of base matrixes
        Matrix A11(*this, 0, 0);
        Matrix A12(*this, 0, size / 2);
        Matrix A21(*this, size / 2, 0);
        Matrix A22(*this, size / 2, size / 2);
        Matrix B11(B, 0, 0);
        Matrix B12(B, 0, size / 2);
        Matrix B21(B, size / 2, 0);
        Matrix B22(B, size / 2, size / 2);
        // end of init
        //prom matrixes S
        Matrix s1 = A21 + A22;
        Matrix s2 = s1 - A11;
        Matrix s3 = A11 - A21;
        Matrix s4 = A12 - s2;
        Matrix s5 = B12 - B11;
        Matrix s6 = B22 - s5;
        Matrix s7 = B22 - B12;
        Matrix s8 = s6 - B21;
        // end of prom matrixes
        Matrix p1 = s2 * s6;
        Matrix p2 = A11 * B11;
        Matrix p3 = A12 * B21;
        Matrix p4 = s3 * s7;
        Matrix p5 = s1 * s5;
        Matrix p6 = s4 * B22;
        Matrix p7 = A22 * s8;

        Matrix t1 = p1 + p2;
        Matrix t2 = t1 + p4;

        Matrix c11 = p2 + p3;
        Matrix c12 = t1 + p5 + p6;
        Matrix c21 = t2 - p7;
        Matrix c22 = t2 + p5;

        return merge(c11, c12, c21, c22);
    }
};

class Test {
private:
    int matrixSizes[6] = { 4, 16, 32, 64,128,256 };

public:
    void getTests() {
        for (int size : matrixSizes) {
            clock_t average1 = 0;
            clock_t average2 = 0;
            for (int i = 0; i < 1; i++) {
                Matrix m1;
                m1.getMatrix(size);
                Matrix m2;
                m2.getMatrix(size);
                clock_t start1 = clock();
                Matrix m = m1 * m2;
                clock_t finish1 = clock() - start1;
                clock_t start2 = clock();
                m = m1.simpleMultiplication(m2);
                clock_t finish2 = clock() - start2;
                average1 += finish1;
                average2 += finish2;
            }
            cout << "For size of matrix: " << size << endl;
            cout << "Time in seconds for shtrassen alghoritm: " << average1 * 1.0 / CLOCKS_PER_SEC << endl;
            cout << "Time in seconds for simple alghoritm: " << average2 * 1.0 / CLOCKS_PER_SEC << endl;
        }
    }
};
bool Matrix::added = false;
int main() {
    Test t;
    t.getTests();
    return 0;
}