#include "Strassen.h"

int leafsize=1;

void ikjalgorithm(Matrice  A,
                                   Matrice  B,
                                   Matrice  &C, int n) {
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {


            }
        }
    }
}

void strassenR(Matrice &A,
              Matrice &B,
              Matrice &C, int tam) {
    if (tam <= leafsize) {

        ikjalgorithm(A, B, C, tam);
        return;
    }

    // other cases are treated here:
    else {

        int newTam = tam/2;

        Matrice
            a11(newTam), a12(newTam), a21(newTam), a22(newTam),
            b11(newTam), b12(newTam), b21(newTam), b22(newTam),
              c11(newTam), c12(newTam), c21(newTam), c22(newTam),
            p1(newTam), p2(newTam), p3(newTam), p4(newTam),
            p5(newTam), p6(newTam), p7(newTam),
            aResult(newTam), bResult(newTam);



        //dividing the matrices in 4 sub-matrices:
        for (int i = 0; i < newTam; i++) {
            for (int j = 0; j < newTam; j++) {
                a11.ajouterElement(i,j,A.Element(i,j));
                a12.ajouterElement(i,j,A.Element(i,j+newTam));
                a21.ajouterElement(i,j,A.Element(i+newTam,j));
                a22.ajouterElement(i,j,A.Element(i+newTam,j+newTam));

                b11.ajouterElement(i,j,B.Element(i,j));
                b12.ajouterElement(i,j,B.Element(i,j+newTam));
                b21.ajouterElement(i,j,B.Element(i+newTam,j));
                b22.ajouterElement(i,j,B.Element(i+newTam,j+newTam));

            }
        }

        // Calculating p1 to p7:

        sum(a11, a22, aResult, newTam); // a11 + a22
        sum(b11, b22, bResult, newTam); // b11 + b22
        strassenR(aResult, bResult, p1, newTam); //p1 = (a11+a22) * (b11+b22)

        sum(a21, a22, aResult, newTam); // a21 + a22
        strassenR(aResult, b11, p2, newTam); // p2 = (a21+a22) * (b11)

        subtract(b12, b22, bResult, newTam); // b12 - b22
        strassenR(a11, bResult, p3, newTam); // p3 = (a11) * (b12 - b22)

        subtract(b21, b11, bResult, newTam); // b21 - b11
        strassenR(a22, bResult, p4, newTam); // p4 = (a22) * (b21 - b11)

        sum(a11, a12, aResult, newTam); // a11 + a12
        strassenR(aResult, b22, p5, newTam); // p5 = (a11+a12) * (b22)

        subtract(a21, a11, aResult, newTam); // a21 - a11
        sum(b11, b12, bResult, newTam); // b11 + b12
        strassenR(aResult, bResult, p6, newTam); // p6 = (a21-a11) * (b11+b12)

        subtract(a12, a22, aResult, newTam); // a12 - a22
        sum(b21, b22, bResult, newTam); // b21 + b22
        strassenR(aResult, bResult, p7, newTam); // p7 = (a12-a22) * (b21+b22)

        // calculating c21, c21, c11 e c22:

        sum(p3, p5, c12, newTam); // c12 = p3 + p5
        sum(p2, p4, c21, newTam); // c21 = p2 + p4

        sum(p1, p4, aResult, newTam); // p1 + p4
        sum(aResult, p7, bResult, newTam); // p1 + p4 + p7
        subtract(bResult, p5, c11, newTam); // c11 = p1 + p4 - p5 + p7

        sum(p1, p3, aResult, newTam); // p1 + p3
        sum(aResult, p6, bResult, newTam); // p1 + p3 + p6
        subtract(bResult, p2, c22, newTam); // c22 = p1 + p3 - p2 + p6

        // Grouping the results obtained in a single matrix:
        for (int i = 0; i < newTam ; i++) {
            for (int j = 0 ; j < newTam ; j++) {
                C.ajouterElement(i,j,c11.Element(i,j));
                C.ajouterElement(i,j+newTam,c12.Element(i,j));
                C.ajouterElement(i+newTam,j,c21.Element(i,j));
                 C.ajouterElement(i+newTam,j+newTam,c22.Element(i,j));
            }
        }
    }
}

unsigned int nextPowerOfTwo(int n) {
    return pow(2, int(ceil(log2(n))));
}

void strassen(Matrice &A,
              Matrice &B,
              Matrice &C, unsigned int n) {
    //unsigned int n = tam;
    unsigned int m = nextPowerOfTwo(n);

    Matrice APrep(m), BPrep(m), CPrep(m);
    CPrep.initialiser();

    for(unsigned int i=0; i<n; i++) {
        for (unsigned int j=0; j<n; j++) {
            APrep.ajouterElement(i,j,A.Element(i,j));

            BPrep.ajouterElement(i,j,B.Element(i,j));
        }
    }

    strassenR(APrep, BPrep, CPrep, m);
    for(unsigned int i=0; i<n; i++) {
        for (unsigned int j=0; j<n; j++) {
            C.ajouterElement(i,j,CPrep.Element(i,j));
        }
    }
}

void sum(Matrice &A,
         Matrice &B,
         Matrice &C, int tam) {
    int i, j;

    for (i = 0; i < tam; i++) {
        for (j = 0; j < tam; j++) {
            C.ajouterElement(i,j,A.Element(i,j)+B.Element(i,j));
        }
    }
}

void subtract(Matrice &A,
              Matrice &B,
              Matrice &C, int tam) {
    int i, j;

    for (i = 0; i < tam; i++) {
        for (j = 0; j < tam; j++) {
            C.ajouterElement(i,j,A.Element(i,j)-B.Element(i,j));
        }
    }
}